بهینه‌سازی پرسش

بهینه‌سازی پرسش

پرسش یک درخواست اطلاعات از پایگاه داده‌است. پرسش می‌تواند به سادگی یک عبارت مثل" پیدا کن آدرس فردی را با شماره ملی ۱۲۳۴۵۶۷۸۹" یا یک عبارت پیچیده مثل " پیدا کن نام دانشجویانی از دانشکده کامپیوتر دانشگاه شریف که درس پایگاه داده را اخذ کرده‌اند ولی درس ساختمان داده را اخذ نکرده‌اند و درس طراحی الگوریتم را با نمره بیشتر از ۱۷گذرانده‌اند سپس آنها را بر حسب شماره دانشجویی مرتب کن"
یکی از وظایف سیستم‌های مدیریت پایگاه‌های داده رابطه ای بهینه‌سازی پرسش است. بهینه‌ساز پرسش به معنی انتخاب پربازده‌ترین راه اجرای پرسش در میان تمام راه‌های ممکن برای اجرای آن پرسش است. این موضوع وقتی که پرسش شامل عبارت‌های پیچیده‌است بسیار مهم است.

تبدیل پرسش به جبر رابطه ای

همان‌طور که قبلاً گفته شد هر پرسش می‌تواند از راه‌های متفاتی با هزینه‌های متفاوت اجرا شود. دو عبارت جبر رابطه ای را یکسان گوییم هرگاه خروجی‌های آن دو عبارت با یکدیگر برابر باشد. در نظر داشته باشید در این تعریف ترتیب سطرهای خروجی مهم نیست.
در این مقاله از نمادهای زیر استفاده می‌کنیم:
برای بیان شرط‌ها از نمادهای استفاده می‌کنیم. برای بیان صفات رابطه از نمادهای استفاده می‌کنیم و برای بیان عبارت‌های جبر رابطه ای از نمادهای استفاده می‌کنیم.

تبدیل کننده پرسش

در این مرحله تشخیص داده می‌شود آیا بازنویسی پرسش به شکلی که خروجی با پرسش اولیه یکسان باشد مفید است یا خیر. مثال زیر می‌تواند این موضوع را روشن کند.

پرسش اولیه به شکل زیر به پایگاه داده فرستاده می‌شود. هدف از این پرسش بدست آوردن اسم درس و نمرات دو دانشجو با شماره دانشجویی‌های ۱۲۳ یا ۲۳۴ است.
1 select course.name , course.grade2 from course3 where course.stuID = '123' or course.stuID='234'
این پرسش پس از گذر از تبدیل کننده پرسش به شکل زیر در خواهد آمد.
1 select course.name , course.grade2 from course3 where course.stuID =  '123'4 union5 select course.name , course.grade6 from course7 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 انجام دهند.
یک نمونه جبر رابطه ای عبارت   است.

تخمین هزینه

یکی از دشوارترین مسائل در بهینه‌سازی پرسش، تخمین دقیق هزینه برای نقشه‌های پرسش است. بهینه‌سازها هزینه نقشه‌های پرسش را با استفاده از مدل‌های ریاضی که شدیداً به اندازه یا تعداد زوج‌ها (سطرها) که در یال‌های درخت اجرای پرسش قرار دارد وابسته است تخمین می‌زنند. تخمین اندازه بستگی به تخمین عامل انتخاب (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(join) می‌شود) در گزاره‌های پرسش دارد.

سیستم‌های پایگاه‌های داده قدیمی تعداد منتخب‌ها را از طریق آمارهای جزئی توزیع مقادیر در هر ستون مثل نمودارهای histogram تخمین می‌زنند. این روش برای تخمین منتخب‌های یک گزاره خوب کار می‌کند. اگرچه تعداد زیادی از پرسش‌ها چندین شرط را تواماً با هم دارند به‌طور مثال: 
1 select student.ID ,student.name ,student.last_name2 from student3 where student.name= 'ali' and student.major = "cs"