بهینهسازی پرسوجو مبتنی بر هزینه
بهینهسازی پرسوجو مبتنی بر هزینه، فضای طرحهای اجرایی معادل برای یک پرسوجو را جستجو میکند و با استفاده از آمار مربوط به دادهها و یک مدل هزینه اجرا، طرحی را با کمترین هزینه تخمینی انتخاب میکند.
Definition
بهینهسازی پرسوجو مبتنی بر هزینه، فرآیند تخمین هزینه اجرای طرحهای معادل جایگزین برای یک پرسوجو، از طریق آمار دادهها و یک مدل هزینه، و انتخاب طرحی با کمترین هزینه تخمینی است که معمولاً با ترتیب اتصال انتخاب شده توسط برنامهنویسی پویا انجام میشود.
Scope
این موضوع به چگونگی انتخاب یک طرح توسط بهینهساز میپردازد: فضای جستجوی طرح که توسط همارزیهای جبر رابطهای و عملگرهای فیزیکی جایگزین تولید میشود، مدل هزینهای که به طرحها امتیاز میدهد (عمدتاً در ورودی/خروجی و CPU)، تخمین کاردینالیتی و انتخابپذیری از آمار و هیستوگرامها، و رویکرد برنامهنویسی پویا برای شمارش ترتیب اتصال که توسط سیستم R معرفی شد. این موضوع شامل پیادهسازی خود عملگرها و بازنویسی منطقی مبتنی بر قاعده فراتر از آنچه که به تولید طرح کمک میکند، نمیشود.
Core questions
- فضای طرحهای اجرایی معادل چگونه تولید و هرس میشود؟
- بهینهساز چگونه کاردینالیتی و انتخابپذیری عملیات را تخمین میزند؟
- برنامهنویسی پویا چگونه ترتیب اتصال را به طور کارآمد شمارش میکند؟
- مدل هزینه چه مواردی را در نظر میگیرد و چگونه هزینههای ورودی/خروجی و CPU ترکیب میشوند؟
- چرا خطاهای تخمین کاردینالیتی باعث انتخاب طرحهای ضعیف میشوند؟
Key concepts
- فضای جستجوی طرح
- مدل هزینه (ورودی/خروجی و CPU)
- تخمین انتخابپذیری و کاردینالیتی
- هیستوگرامها و آمار
- شمارش ترتیب اتصال
- برنامهنویسی پویا
- ترتیبهای جالب
- بهینهسازی مبتنی بر تبدیل
Key theories
- بهینهسازی برنامهنویسی پویا سیستم R
- بهینهساز سلینگر ترتیب اتصال را به صورت پایین به بالا با برنامهنویسی پویا شمارش میکند و ارزانترین طرح را برای هر زیرمجموعه از روابط (و هر ترتیب مرتبسازی جالب) نگه میدارد، که جستجوی فضای بزرگ ترتیب اتصال را قابل مدیریت میکند.
- تخمین کاردینالیتی و انتخابپذیری
- بهینهساز تعداد تاپلهایی را که هر عملیات تولید میکند با استفاده از آمار جدول، هیستوگرامها و فرمولهای انتخابپذیری تخمین میزند؛ این تخمینها مدل هزینه را هدایت میکنند و منبع اصلی خطای بهینهسازی هستند.
- مدلهای هزینه و استراتژیهای جستجو
- طرحها توسط یک مدل هزینه که اثرات ورودی/خروجی، CPU و حافظه را ترکیب میکند، امتیازدهی میشوند؛ فراتر از برنامهنویسی پویای سیستم R، بهینهسازهای مبتنی بر تبدیل، طرحها را از طریق قوانین بازنویسی برای گسترش بهینهسازی به عملگرهای غنیتر و تنظیمات توزیعشده بررسی میکنند.
Clinical relevance
بهینهساز (optimizer) مؤلفهای است که به کاربران امکان میدهد SQL اعلامی را بدون تعیین نحوه اجرای آن بنویسند؛ کیفیت تخمینهای هزینه و جستجوی آن مستقیماً تعیین میکند که آیا پرسوجوها در پایگاههای داده بزرگ سریع هستند یا خیر، بنابراین بهینهسازی مبتنی بر هزینه از جمله مورد مطالعهترین و از نظر تجاری مهمترین بخشهای سیستمهای پایگاه داده است.
History
بهینهساز سیستم R در سال 1979 توسط سلینگر و همکارانش، بهینهسازی مبتنی بر هزینه را با ترتیب اتصال برنامهنویسی پویا و تخمین هزینه مبتنی بر انتخابپذیری معرفی کرد و این حوزه را تعریف نمود. بهینهسازهای مبتنی بر تبدیل بعدی مانند Volcano و Cascades جستجو را تعمیم دادند و کارهای جاری بر روی تخمین کاردینالیتی، از جمله مدلهای یادگیری ماشین، به ضعف اصلی این چارچوب میپردازند.
Debates
- تخمین کاردینالیتی در مقابل اجرای تطبیقی
- از آنجا که بهینهسازی مبتنی بر هزینه تنها به اندازه تخمینهای اندازه آن خوب است، که اغلب برای دادههای همبسته اشتباه هستند، محققان بحث میکنند که آیا باید در آمار بهتر و تخمینگرهای یادگیری ماشین سرمایهگذاری کرد یا بیشتر به بهینهسازی مجدد تطبیقی و زمان اجرا که طرحهای بد را در طول اجرا اصلاح میکند، تکیه کرد.
Key figures
- Patricia Selinger
- Goetz Graefe
- Surajit Chaudhuri
Related topics
Seminal works
- selinger1979
- graefe1993
Frequently asked questions
- چرا یک بهینهساز گاهی اوقات یک طرح بد را انتخاب میکند؟
- بهینهسازهای مبتنی بر هزینه به تخمینهایی از تعداد ردیفهایی که هر عملیات تولید میکند، متکی هستند. هنگامی که دادهها کج یا ستونها همبسته هستند، این تخمینها میتوانند بسیار دور از واقعیت باشند و خطا در اتصالات (joins) تشدید میشود. یک تخمین اشتباه میتواند بهینهساز را به انتخاب یک ترتیب اتصال یا مسیر دسترسی ضعیف سوق دهد، حتی اگر طرح روی کاغذ ارزان به نظر میرسید.
- چرا از برنامهنویسی پویا برای ترتیب اتصال استفاده میشود؟
- تعداد ترتیبهای اتصال ممکن با تعداد جداول به صورت ترکیبی رشد میکند، بنابراین جستجوی جامع غیرممکن است. برنامهنویسی پویا طرحهای بهینه را برای مجموعههای بزرگتر از روابط از طرحهای بهینه برای زیرمجموعههای کوچکتر میسازد، که به طور چشمگیری کار را کاهش میدهد در حالی که همچنان یک ترتیب اتصال خوب (اغلب بهینه) را برای اندازههای پرسوجوی معمولی پیدا میکند.