موضوع مقاله: بهینه‌سازی پرسش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بهینه‌سازی پرسش | مقدمه: بهینه‌سازی پرسش پرسش یک درخواست اطلاعات از پایگاه داده‌است.مفاهیم بنیادی پایگاه داده‌ها - محمد تقی روحانی رانکوهی- ویرایش چهارم - نشر جلوه پرسش می‌تواند به سادگی یک عبارت مثل" پیدا کن آدرس فردی را با شماره ملی ۱۲۳۴۵۶۷۸۹" یا یک عبارت پیچیده مثل " پیدا کن نام دانشجویانی از دانشکده کامپیوتر دانشگاه شریف که درس پایگاه داده را اخذ کرده‌اند ولی درس ساختمان داده را اخذ نکرده‌اند و درس طراحی الگوریتم را با نمره بیشتر از ۱۷ گذرانده‌اند سپس آنها را بر حسب شماره دانشجویی مرتب کن" یکی از وظایف سیستم‌های مدیریت پایگاه‌های داده رابطه ای بهینه‌سازی پرسش است. | ## بخش 1: بهینه‌سازی پرسش | بهینه‌ساز پرسش به معنی انتخاب پربازده‌ترین راه اجرای پرسش در میان تمام راه‌های ممکن برای اجرای آن پرسش است. ورودی: ابتدا سیستم یک فایل ورودی را که شامل دستورهای اس‌کیوال است را دریافت می‌کند. سیستم مدیریت پایگاه داده پرسش را کامپایل کرده و نقشه اجرای پرسش را به دست می‌آورد، خروجی این مرحله (نقشه اجرای پرسش) به عنوان ورودی مرحله بعد در نظر گرفته می‌شود. لزوم بهینه‌سازی پرسش ابتدا با یک مثال تشریح می‌کنیم برای اجرای یک پرسش راه‌های مختلفی وجود دارد، سپس در ادامه اهمیت بهینه‌سازی پرسش را نشان خواهیم داد. با روش‌های مختلفی می‌توان پرسش ذکر شده را اجرا کرد که در اینجا به دو روش اشاره می‌کنیم: می‌توان ابتدا دو جدول student و esrouc را در یکدیگر ادغام کرد (بدون در نظر گرفتن شرایط مطرح شده در erehw) در این صورت به اندازه ۰۰۰٬۰۰۱ (۰۰۱* ۰۰۰۱) سطر تولید می‌شود، سپس بین سطرهای تولید شده آنهایی که شرایط ذکر شده در عبارت erehw را ارضا می‌کنند انتخاب کرد. به‌طور کلی، کاربران نمی‌توانند به شکل مستقیم به بهینه‌ساز پرسش دسترسی داشته باشند. البته بعضی از سیستم‌های مدیریت پایگاه داده اجازه راهنمایی بهینه‌ساز را توسط راهنماها می‌دهند. راهنما یک دستورالعمل اضافه نسبت به زبان SQL استاندارد است که به بهینه‌ساز در جهت بدست آوردن بهترین روش اجرای پرسش کمک می‌کند. از آنجایی که ساختار پایگاه‌های داده پیچیده‌است، به جز در پرسش‌های ساده نیاز است تا اطلاعات مورد نیاز برای پرسش از راه‌های مختلفی تأمین گردد، به عنوان نمونه از جداول مختلف، از داده ساختارهای مختلف، از داده‌ها با ترتیب‌های مختلف؛ و هر راه هم‌زمان اجرای خاص خود را دارد. همان گونه که در مثال بالا نشان داده شد برای یک پرسش واحد زمان پردازش می‌تواند از کسری از ثانیه تا چندین ساعت متغیر باشد و این زمان بستگی به روش اجرای پرسش دارد. هدف بهینه‌سازی پرسش به عنوان یک فرایند خودکار پیدا کردن راهی است که بتوان پرسش را در حداقل زمان ممکن اجرا کرد. همان‌طور که ذکر شد بازه زمانی اجرای پرسش می‌تواند خیلی متغیر باشد و این موضوع لزوم بهینه‌سازی پرسش را برای رسیدن به بهینه‌ترین راه اجرا تأیید می‌کند. از آنجایی که پیدا کردن راه بهینه از میان تمام راه‌های ممکن خیلی پیچیده‌است و زمان صرف شده برای این موضوع خیلی مهم است و همین زمان باعث می‌شود از لحاظ عملی بررسی تمام راه‌ها برای اجرای پرسش غیرممکن باشد؛ بنابراین در بهینه‌سازی پرسش تلاش می‌کنیم تا به شکل تقریبی نقشه‌های اجرایی را برای پرسش بدست آوریم که از لحاظ زمانی قابل قبول بوده و تفاوت زیادی با زمان بهینه نداشته باشد. تبدیل پرسش به جبر رابطه ای همان‌طور که قبلاً گفته شد هر پرسش می‌تواند از راه‌های متفاوتی با هزینه‌های متفاوت اجرا شود. دو عبارت جبر رابطه ای را یکسان گوییم هرگاه خروجی‌های آن دو عبارت با یکدیگر برابر باشد. در این مقاله از نمادهای زیر استفاده می‌کنیم: برای بیان شرط‌ها از نمادهای استفاده می‌کنیم. برای بیان صفات رابطه از نمادهای استفاده می‌کنیم و برای بیان عبارت‌های جبر رابطه ای از نمادهای استفاده می‌کنیم. | ## بخش 2: بهینه‌سازی پرسش | قوانین برابری جبر رابطه ای قوانین برابری جبر رابطه ای بیان می‌کنند چگونه دو عبارت با هم برابر هستند و می‌توان آنها را به جای یکدیگر استفاده کرد. در یک عملیات افکنش فقط آخرین عملیات مهم است و از بقیه عملیات‌ها می‌توان صرف نظر کرد. از این قوانین می‌توان برای بدست آوردن درخت پرسش استفاده کرد و نقشه‌های اجرا را بدست آورد. اجزای بهینه‌ساز در سیستم‌های مدیریت پایگاه‌های داده ممکن است اجزای متفاوتی وجود داشته باشد، اما می‌توان به‌طور کلی گفت همه آن‌ها دارای اجزا زیر هستند (این اجزا به ترتیب مرحله اجرا ذکر شده‌اند). تخمین زننده: برای هر نقشه پرسش زمان مورد نیاز را برا اساس فرهنگ داده تخمین می‌زند. تولیدکننده نقشه پرسش: هزینه تمام نقشه‌های اجرای مختلف را با یکدیگر مقایسه کرده و کم هزینه‌ترین را انتخاب می‌کند، سپس نقشه انتخاب شده را برای اجرا به بخش بعدی ارسال می‌کند. تبدیل کننده پرسش در این مرحله تشخیص داده می‌شود آیا بازنویسی پرسش به شکلی که خروجی با پرسش اولیه یکسان باشد مفید است یا خیر. انتخاب شوندگی برابر صفر است اگر هیچ سطری انتخاب نشود و برابر ۱ است اگر همه سطرها انتخاب شوند. اندازه: تعداد سطرهایی که توسط هر عملیات در نقشه‌های مختلف اجرا برگردانده می‌شود. تولیدکننده نقشه پرسش کم هزینه‌ترین نقشه اجرا برای یک بلاک از پرسش را انتخاب می‌کند. ملاحظات عمومی همیشه یک معامله بین زمان صرف شده برای بدست آوردن بهترین نقشه اجرای پرسش و کیفیت نقشه انتخاب شده وجود دارد. سیستم‌های مدیریت پایگاه داده متفاوت راه‌های متفاوتی برای ایجاد تعادل بین دو فاکتور ذکر شده دارند. این مدل از بهینه‌سازها به هر نقشه ممکن برای اجرای پرسش یک هزینه تخمین می‌زنند و سپس کمترین آنها را انتخاب می‌کنند. هزینه‌هایی که برای تخمین زدن زمان اجرای یک پرسش در نظر گرفته می‌شوند عبارتند از تعداد عملیات‌های I/O مورد نیاز، میزان دستور مورد نیاز به زبان ماشین برای اجرای پرسش، میزان حافظه بافر مورد نیاز از دیسک، زمان مورد نیاز دیسک و عامل‌های دیگر که توسط فرهنگ داده مشخصی می‌شود. بهینه‌ساز منطقی -که زنجیره ای از جبر رابطه ای برای اجرای پرسش تولید می‌کند-و بهینه‌سازی فیزیکی برای مشخص کردن مجری هر عملیات استفاده می‌شود. پیاده‌سازی تعداد زیادی از بهینه‌سازهای پرسش، نقشه‌های پرسش را به شکل درختی نشان می‌دهند که از تعدادی گره تشکیل شده‌است. این گره‌ها به شکل یک درخت مرتب شده‌اند که برای به دست آوردن نتیجه نهایی باید گره‌های درخت را به ترتیب از پایین به بالا اجرا کنیم و نتیجه هر گره را به عنوان ورودی گره پدر در نظر بگیریم. | ## بخش 3: بهینه‌سازی پرسش | تعداد بچه‌های هر گره می‌تواند صفر یا بیشتر باشد به عنوان مثال یک گره که حاوی دستور join است دو بچه دارد که شامل عملوندهای ورودی آن است ولی یک دستور sort صرفاً یک ورودی (ورودی که می‌خواهیم مرتب شود) دارد. تخمین هزینه یکی از دشوارترین مسائل در بهینه‌سازی پرسش، تخمین دقیق هزینه برای نقشه‌های پرسش است. بهینه‌سازها هزینه نقشه‌های پرسش را با استفاده از مدل‌های ریاضی که شدیداً به اندازه یا تعداد زوج‌ها (سطرها) که در یال‌های درخت اجرای پرسش قرار دارد وابسته است تخمین می‌زنند. تخمین اندازه بستگی به تخمین عامل انتخاب (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(join) می‌شود) در گزاره‌های پرسش دارد. سیستم‌های پایگاه‌های داده قدیمی تعداد منتخب‌ها را از طریق آمارهای جزئی توزیع مقادیر در هر ستون مثل نمودارهای histogram تخمین می‌زنند. برای اینکه این دیدگاه بتواند درست کار کند باید بتوان تخمین دقیقی از هزینه اجرای پرسش بدست آورد تا در نهایت رویکردهای مختلف اجرای پرسش عادلانه و واقع گرایانه مقایسه شوند. همچین باید این نکته را در نظر گرفت بهینه‌ساز باید تعداد محدودی رویکرد اجرای پرسش را بررسی کند در واقع اگر قرار باشد تمام حالت‌های اجرا را در نظر بگیرد زمان زیادی از دست می‌رود. فرایند کلی بهینه‌سازی هزینه محور را می‌توان به شکل زیر خلاصه کرد: برای یک زیر عبارت در پرسش، تعدادی راه‌های معادل وجود دارد واجب است که تعدادی معیار برای ارزیابی راه‌های مختلف اجرای پرسش داشته باشیم. می‌توانیم دو معیار زمان و حافظه مورد نیاز را در نظر گرفته و از هر دو آنها تحت عنوان هزینه یاد کنیم. با طراحی رویکرد جستجوی مناسب می‌توان کم هزینه‌ترین راه‌ها را انتخاب کرد و راه‌های پر هزینه را کنار گذاشت. اجزای هزینه در بهینه‌سازی پرسش هزینه دسترسی به حافظه ثانویه هزینه انتقال (خواندن یا نوشتن) بلاک‌های اطلاعات بین دیسک حافظه ثانویه و بافرهای حافظه اصلی. هزینه جستجوی یک فایل در دیسک به نوع دسترسی به آن فایل بستگی دارد به‌طور مثال آیا فایل مرتب شده‌است؟ هزینه ذخیره‌سازی دیسک هزینه ذخیره‌سازی هر فایل میانی که با اجرای پرسش تولید شده‌است برروی دیسک را گویند. هزینه محاسبه این هزینه شامل هزینه انجام عملیات روی رکوردهای حافظه اصلی در طول اجرای پرسش است. این هزینه شامل عملیاتی است که در داخل حافظه انجام می‌شود مثل:جستجو، مرتب‌سازی، ادغام چند رکورد برای یک عملیات join. هزینه استفاده از حافظه اصلی این هزینه مربوط به تعداد بافر مورد نیاز از حافظه در طول اجرای پرسش می‌باشد. هزینه ارتباط هزینه انتقال پرسش و نتایج آن از محل پایگاه داده به محل یا ترمینالی که پرسش از آنجا فرستاد شده‌است. | ## جمع‌بندی | در :پایگاه داده توزیع‌شده، این هزینه شامل هزینه انتقال جدول‌ها و نتایج آن بین کامپیوترهای مختلف در طول ارزیابی پرسش است.