بهینه‌سازی پرسش
بهینه‌سازی پرسش پرسش یک درخواست اطلاعات از پایگاه داده‌است. پرسش می‌تواند به سادگی یک عبارت مثل" پیدا کن آدرس فردی را با شماره ملی ۱۲۳۴۵۶۷۸۹" یا یک عبارت پیچیده مثل " پیدا کن نام دانشجویانی از دانشکده کامپیوتر دانشگاه شریف که درس پایگاه داده را اخذ کرده‌اند ولی درس ساختمان داده را اخذ نکرده‌اند و درس طراحی الگوریتم را با نمره بیشتر از ۱۷ گذرانده‌اند سپس آنها را بر حسب شماره دانشجویی مرتب کن"
یکی از وظایف سیستم‌های مدیریت پایگاه‌های داده رابطه ای بهینه‌سازی پرسش است. بهینه‌ساز پرسش به معنی انتخاب پربازده‌ترین راه اجرای پرسش در میان تمام راه‌های ممکن برای اجرای آن پرسش است. این موضوع وقتی که پرسش شامل عبارت‌های پیچیده‌است بسیار مهم است.
ابتد مروری می‌کنیم بر نحوه اجرای پرسش در پایگاه داده. ترتیب اجرای عمومی پرسش به شکل زیر است.
ابتدا با یک مثال تشریح می‌کنیم برای اجرای یک پرسش راه‌های مختلفی وجود دارد، سپس در ادامه اهمیت بهینه‌سازی پرسش را نشان خواهیم داد.
پرسش زیر را در نظر بگیرید: select student.stuID,course.course_name,course.grade from student , course where student.stuID=course.stuID and course_name="database" and course.grade = 20 فرض می‌کنیم در جدول student تعداد ۱۰۰ سطر و در جدول course، تعداد ۱۰۰۰ سطر را داریم. در بین ۱۰۰۰ سطر جدول course، تعداد ۳۰۰ سطر فقط شرط "course_name="database و تعداد ۲۵۰ سطر فقط شرط
course.grade = ۲۰ را ارضا می‌کنند و تعداد ۲۰۰ سطر هر دو شرط را ارضا می‌کنند.
با روش‌های مختلفی می‌توان پرسش ذکر شده را اجرا کرد که در اینجا به دو روش اشاره می‌کنیم:
روشن است که خروجی هر دو روش یکسان است اما روش اول به مراتب منابع بیشتری برای اجرا نیاز دارد (نگهداری ۱۰۰٬۰۰۰ سطر حافظه بیشتری نسبت به ۲۰٬۰۰۰ سطر نیاز دارد) و زمان پردازش آن نیز بیشتر خواهد بود. این مثال لزوم انتخاب روش درست برای اجرای پرسش را تأیید می‌کند.
به‌طور کلی، کاربران نمی‌توانند به شکل مستقیم به بهینه‌ساز پرسش دسترسی داشته باشند. البته بعضی از سیستم‌های مدیریت پایگاه داده اجازه راهنمایی بهینه‌ساز را توسط راهنماها می‌دهند. راهنما یک دستورالعمل اضافه نسبت به زبان SQL استاندارد است که به بهینه‌ساز در جهت بدست آوردن بهترین روش اجرای پرسش کمک می‌کند.
از آنجایی که ساختار پایگاه‌های داده پیچیده‌است، به جز در پرسش‌های ساده نیاز است تا اطلاعات مورد نیاز برای پرسش از راه‌های مختلفی تأمین گردد، به عنوان نمونه از جداول مختلف، از داده ساختارهای مختلف، از داده‌ها با ترتیب‌های مختلف؛ و هر راه هم‌زمان اجرای خاص خود را دارد. همان گونه که در مثال بالا نشان داده شد برای یک پرسش واحد زمان پردازش می‌تواند از کسری از ثانیه تا چندین ساعت متغیر باشد و این زمان بستگی به روش اجرای پرسش دارد. هدف بهینه‌سازی پرسش به عنوان یک فرایند خودکار پیدا کردن راهی است که بتوان پرسش را در حداقل زمان ممکن اجرا کرد. همان‌طور که ذکر شد بازه زمانی اجرای پرسش می‌تواند خیلی متغیر باشد و این موضوع لزوم بهینه‌سازی پرسش را برای رسیدن به بهینه‌ترین راه اجرا تأیید می‌کند. از آنجایی که پیدا کردن راه بهینه از میان تمام راه‌های ممکن خیلی پیچیده‌است و زمان صرف شده برای این موضوع خیلی مهم است و همین زمان باعث می‌شود از لحاظ عملی بررسی تمام راه‌ها برای اجرای پرسش غیرممکن باشد؛ بنابراین در بهینه‌سازی پرسش تلاش می‌کنیم تا به شکل تقریبی نقشه‌های اجرایی را برای پرسش بدست آوریم که از لحاظ زمانی قابل قبول بوده و تفاوت زیادی با زمان بهینه نداشته باشد.
همان‌طور که قبلاً گفته شد هر پرسش می‌تواند از راه‌های متفاوتی با هزینه‌های متفاوت اجرا شود. دو عبارت جبر رابطه ای را یکسان گوییم هرگاه خروجی‌های آن دو عبارت با یکدیگر برابر باشد. در نظر داشته باشید در این تعریف ترتیب سطرهای خروجی مهم نیست.
در این مقاله از نمادهای زیر استفاده می‌کنیم:
قوانین برابری جبر رابطه ای بیان می‌کنند چگونه دو عبارت با هم برابر هستند و می‌توان آنها را به جای یکدیگر استفاده کرد.از این قوانین می‌توان برای بدست آوردن درخت پرسش استفاده کرد و نقشه‌های اجرا را بدست آورد.
در سیستم‌های مدیریت پایگاه‌های داده ممکن است اجزای متفاوتی وجود داشته باشد، اما می‌توان به‌طور کلی گفت همه آن‌ها دارای اجزا زیر هستند (این اجزا به ترتیب مرحله اجرا ذکر شده‌اند).
در این مرحله تشخیص داده می‌شود آیا بازنویسی پرسش به شکلی که خروجی با پرسش اولیه یکسان باشد مفید است یا خیر. مثال زیر می‌تواند این موضوع را روشن کند.
پرسش اولیه به شکل زیر به پایگاه داده فرستاده می‌شود. هدف از این پرسش بدست آوردن اسم درس و نمرات دو دانشجو با شماره دانشجویی‌های ۱۲۳ یا ۲۳۴ است. select course.name , course.grade from course where course.stuID = '123' or course.stuID='234' این پرسش پس از گذر از تبدیل کننده پرسش به شکل زیر در خواهد آمد. select course.name , course.grade from course where course.stuID = '123' union select course.name , course.grade from course where course.stuID='234' با استفاده از دستور UNION، پرسش به شکل معادل خود تبدیل شده‌است.
تخمین زننده از سه معیار برای انجام کار خود استفاده می‌کند.
کم هزینه‌ترین نقشه اجرا برای یک بلاک از پرسش را انتخاب می‌کند. برای درک بهتر این موضوع در نظر بگیرید برای یک عملیات join می‌توان از سه روش متفاوتnested loop joint,sort merge یا hash join استفاده کرد. برای هر کدام از این روش‌ها زمان‌های زیر تخمین زده شده‌است. Best Nested Loop join cost: 13.17 Sort Merge cost: 6.08 Hash join cost: 4.57 Best:: JoinMethod: Hash مشاهده می‌شود که کمترین زمان اجرا متعلق به روش hash join است، پس از این روش برای اجرای نقشه پرسش استفاده می‌شود.
همیشه یک معامله بین زمان صرف شده برای بدست آوردن بهترین نقشه اجرای پرسش و کیفیت نقشه انتخاب شده وجود دارد. بهینه‌ساز مستقلاً نمی‌تواند بهترین انتخاب را داشته باشد. سیستم‌های مدیریت پایگاه داده متفاوت راه‌های متفاوتی برای ایجاد تعادل بین دو فاکتور ذکر شده دارند. بهینه‌سازهای هزینه محور میزان استفاده پرسش را از منابع سیستم ارزیابی می‌کنند و آن را به عنوان مبنایی برای انتخاب یک نقشه اجرا در نظر می‌گیرند. این مدل از بهینه‌سازها به هر نقشه ممکن برای اجرای پرسش یک هزینه تخمین می‌زنند و سپس کمترین آنها را انتخاب می‌کنند. هزینه‌هایی که برای تخمین زدن زمان اجرای یک پرسش در نظر گرفته می‌شوند عبارتند از تعداد عملیات‌های I/O مورد نیاز، میزان دستور مورد نیاز به زبان ماشین برای اجرای پرسش، میزان حافظه بافر مورد نیاز از دیسک، زمان مورد نیاز دیسک و عامل‌های دیگر که توسط فرهنگ داده مشخصی می‌شود.
دو نوع بهینه‌سازی وجود دارد. بهینه‌ساز منطقی -که زنجیره ای از جبر رابطه ای برای اجرای پرسش تولید می‌کند-و بهینه‌سازی فیزیکی برای مشخص کردن مجری هر عملیات استفاده می‌شود.
تعداد زیادی از بهینه‌سازهای پرسش، نقشه‌های پرسش را به شکل درختی نشان می‌دهند که از تعدادی گره تشکیل شده‌است. هر گره این درخت یک عملیات مورد نیاز برای اجرای نقشه پرسش را نشان می‌دهد. این گره‌ها به شکل یک درخت مرتب شده‌اند که برای به دست آوردن نتیجه نهایی باید گره‌های درخت را به ترتیب از پایین به بالا اجرا کنیم و نتیجه هر گره را به عنوان ورودی گره پدر در نظر بگیریم. تعداد بچه‌های هر گره می‌تواند صفر یا بیشتر باشد به عنوان مثال یک گره که حاوی دستور join است دو بچه دارد که شامل عملوندهای ورودی آن است ولی یک دستور sort صرفاً یک ورودی (ورودی که می‌خواهیم مرتب شود) دارد. برگ‌های درخت گره‌هایی هستند که نتایج را با پویش دیسک انجام می‌دهند. برای مثال این گره‌ها می‌توانند اینکار را با index scan یا sequential scan انجام دهند.
یک نمونه :جبر رابطه‌ای عبارت formula_12 است.
یکی از دشوارترین مسائل در بهینه‌سازی پرسش، تخمین دقیق هزینه برای نقشه‌های پرسش است. بهینه‌سازها هزینه نقشه‌های پرسش را با استفاده از مدل‌های ریاضی که شدیداً به اندازه یا تعداد زوج‌ها (سطرها) که در یال‌های درخت اجرای پرسش قرار دارد وابسته است تخمین می‌زنند. تخمین اندازه بستگی به تخمین (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(join) می‌شود) در گزاره‌های پرسش دارد.
سیستم‌های پایگاه‌های داده قدیمی تعداد منتخب‌ها را از طریق آمارهای جزئی توزیع مقادیر در هر ستون مثل نمودارهای histogram تخمین می‌زنند. این روش برای تخمین منتخب‌های یک گزاره خوب کار می‌کند. اگرچه تعداد زیادی از پرسش‌ها چندین شرط را تواماً با هم دارند به‌طور مثال:  select student.ID ,student.name ,student.last_name from student where student.name= 'ali' and student.major = "cs" یک بهینه‌ساز پرسش تنها به درخت پرسش وابسته نیست، بهینه‌ساز پرسش هزینه اجرای یک پرسش را با رویکردها و الگوریتم‌های مختلف تخمین زده و مقایسه می‌کند و در نهایت رویکردی را انتخاب می‌کند که کمترین هزینه را داشته باشد. برای اینکه این دیدگاه بتواند درست کار کند باید بتوان تخمین دقیقی از هزینه اجرای پرسش بدست آورد تا در نهایت رویکردهای مختلف اجرای پرسش عادلانه و واقع گرایانه مقایسه شوند. همچین باید این نکته را در نظر گرفت بهینه‌ساز باید تعداد محدودی رویکرد اجرای پرسش را بررسی کند در واقع اگر قرار باشد تمام حالت‌های اجرا را در نظر بگیرد زمان زیادی از دست می‌رود. بنابر این دیدگاه بهینه‌سازی هزینه محور مناسب پرسش‌های کامپایل شده‌است.
تصمیم‌گیری در فرایند بهینه‌سازی پرسش ساده و چالش‌های زیاده دارد. فرایند کلی بهینه‌سازی هزینه محور را می‌توان به شکل زیر خلاصه کرد:هزینه انتقال (خواندن یا نوشتن) بلاک‌های اطلاعات بین دیسک حافظه ثانویه و بافرهای حافظه اصلی. این هزینه به اسم هزینه ورودی و خروجی دیسک ((disk I/O (input/output) هم شناخته می‌شود. هزینه جستجوی یک فایل در دیسک به نوع دسترسی به آن فایل بستگی دارد به‌طور مثال آیا فایل مرتب شده‌است؟ در هم سازی صورت گرفته‌است؟ اندیس گذاری انجام شده‌است؟ و… عوامل مختلف دیگر.
هزینه ذخیره‌سازی هر فایل میانی که با اجرای پرسش تولید شده‌است برروی دیسک را گویند.
این هزینه شامل هزینه انجام عملیات روی رکوردهای حافظه اصلی در طول اجرای پرسش است. این هزینه شامل عملیاتی است که در داخل حافظه انجام می‌شود مثل:جستجو، مرتب‌سازی، ادغام چند رکورد برای یک عملیات join. این هزینه به اسم CPU cost(واحد پردازش مرکزی) هم شناخته می‌شود.
این هزینه مربوط به تعداد بافر مورد نیاز از حافظه در طول اجرای پرسش می‌باشد.
هزینه انتقال پرسش و نتایج آن از محل پایگاه داده به محل یا ترمینالی که پرسش از آنجا فرستاد شده‌است. در :پایگاه داده توزیع‌شده، این هزینه شامل هزینه انتقال جدول‌ها و نتایج آن بین کامپیوترهای مختلف در طول ارزیابی پرسش است.