بهینه‌سازی پرسش - ویکی‌پدیا، دانشنامهٔ آزاد

این نوشتار نیازمند پیوند میان‌زبانی است. در صورت وجود، با توجه به خودآموز ترجمه، میان‌ویکی مناسب را به نوشتار بیفزایید.

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

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

نحوه اجرای پرسش[ویرایش]

ابتد مروری می‌کنیم بر نحوه اجرای پرسش در پایگاه داده. ترتیب اجرای عمومی پرسش به شکل زیر است.

1. ورودی: ابتدا سیستم یک فایل ورودی را که شامل دستورهای اس‌کیوال است را دریافت می‌کند.
2. سیستم مدیریت پایگاه داده پرسش را کامپایل کرده و نقشه اجرای پرسش را به دست می‌آورد، خروجی این مرحله (نقشه اجرای پرسش) به عنوان ورودی مرحله بعد در نظر گرفته می‌شود.
3. سیستم مدیریت پایگاه داده نقشه اجرای پرسش را اجرا می‌کند.
4. خروجی: نتیجه پرسش به محل مربوطه فرستاده می‌شود.

لزوم بهینه‌سازی پرسش[ویرایش]

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

پرسش زیر را در نظر بگیرید:

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 = ۲۰ را ارضا می‌کنند و تعداد ۲۰۰ سطر هر دو شرط را ارضا می‌کنند.

با روش‌های مختلفی می‌توان پرسش ذکر شده را اجرا کرد که در اینجا به دو روش اشاره می‌کنیم:

1. می‌توان ابتدا دو جدول student و esrouc را در یکدیگر ادغام کرد (بدون در نظر گرفتن شرایط مطرح شده در erehw) در این صورت به اندازه ۰۰۰٬۰۰۱ (۰۰۱* ۰۰۰۱) سطر تولید می‌شود، سپس بین سطرهای تولید شده آنهایی که شرایط ذکر شده در عبارت erehw را ارضا می‌کنند انتخاب کرد.
2. می‌توان ابتدا با اعمال شرایط مربوط به جدول course تعداد سطرهای را به ۲۰۰ سطر کاهش داد (سطرهایی که هر دو شرط را ارضا می‌کنند) سپس دو جدول student , course را با هم ادغام کرد در این صورت ۲۰۰۰۰(۲۰۰*۱۰۰) سطر تولید می‌شود سپس آنهایی را که شرط student.stuID=course.stuID را ارضا می‌کنند انتخاب کرد.

روشن است که خروجی هر دو روش یکسان است اما روش اول به مراتب منابع بیشتری برای اجرا نیاز دارد (نگهداری ۱۰۰٬۰۰۰ سطر حافظه بیشتری نسبت به ۲۰٬۰۰۰ سطر نیاز دارد) و زمان پردازش آن نیز بیشتر خواهد بود. این مثال لزوم انتخاب روش درست برای اجرای پرسش را تأیید می‌کند.

به‌طور کلی، کاربران نمی‌توانند به شکل مستقیم به بهینه‌ساز پرسش دسترسی داشته باشند. البته بعضی از سیستم‌های مدیریت پایگاه داده اجازه راهنمایی بهینه‌ساز را توسط راهنماها می‌دهند. راهنما یک دستورالعمل اضافه نسبت به زبان SQL استاندارد است که به بهینه‌ساز در جهت بدست آوردن بهترین روش اجرای پرسش کمک می‌کند.

از آنجایی که ساختار پایگاه‌های داده پیچیده‌است، به جز در پرسش‌های ساده نیاز است تا اطلاعات مورد نیاز برای پرسش از راه‌های مختلفی تأمین گردد، به عنوان نمونه از جداول مختلف، از داده ساختارهای مختلف، از داده‌ها با ترتیب‌های مختلف؛ و هر راه هم‌زمان اجرای خاص خود را دارد. همان گونه که در مثال بالا نشان داده شد برای یک پرسش واحد زمان پردازش می‌تواند از کسری از ثانیه تا چندین ساعت متغیر باشد و این زمان بستگی به روش اجرای پرسش دارد. هدف بهینه‌سازی پرسش به عنوان یک فرایند خودکار پیدا کردن راهی است که بتوان پرسش را در حداقل زمان ممکن اجرا کرد. همان‌طور که ذکر شد بازه زمانی اجرای پرسش می‌تواند خیلی متغیر باشد و این موضوع لزوم بهینه‌سازی پرسش را برای رسیدن به بهینه‌ترین راه اجرا تأیید می‌کند. از آنجایی که پیدا کردن راه بهینه از میان تمام راه‌های ممکن خیلی پیچیده‌است و زمان صرف شده برای این موضوع خیلی مهم است و همین زمان باعث می‌شود از لحاظ عملی بررسی تمام راه‌ها برای اجرای پرسش غیرممکن باشد؛ بنابراین در بهینه‌سازی پرسش تلاش می‌کنیم تا به شکل تقریبی نقشه‌های اجرایی را برای پرسش بدست آوریم که از لحاظ زمانی قابل قبول بوده و تفاوت زیادی با زمان بهینه نداشته باشد.

تبدیل پرسش به جبر رابطه ای^[۲][ویرایش]

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

در این مقاله از نمادهای زیر استفاده می‌کنیم:

برای بیان شرط‌ها از نمادهای ${\displaystyle \theta {_{1}},\theta {_{2}},\theta {_{3}}}$استفاده می‌کنیم. برای بیان صفات رابطه از نمادهای ${\displaystyle L{_{1}},L{_{2}},L{_{3}}}$استفاده می‌کنیم و برای بیان عبارت‌های جبر رابطه ای از نمادهای ${\displaystyle E{_{1}},E{_{2}},E{_{3}}}$استفاده می‌کنیم. 

قوانین برابری جبر رابطه ای[ویرایش]

قوانین برابری جبر رابطه ای بیان می‌کنند چگونه دو عبارت با هم برابر هستند و می‌توان آنها را به جای یکدیگر استفاده کرد.

• عملیات‌های انتخاب عطفی می‌تواند به شکل دنباله ای از انتخاب‌های یکتا بیان شود. به این تبدیل، تبدیل آبشاری ${\displaystyle \sigma }$ نیز گویند.

${\displaystyle \sigma {_{\theta {_{1}}\land \theta {_{2}}}}(E)=\sigma {_{\theta }{_{1}}}(\sigma {_{\theta }{_{2}}})(E)}$ 

• عملیات‌های انتخاب قابل جابجایی هستند.

${\displaystyle \sigma {_{\theta {_{1}}}}(\sigma {_{\theta {_{2}}}}(E))=\sigma {_{\theta {_{2}}}}(\sigma {_{\theta {_{1}}}}(E))}$ 

• در یک عملیات افکنش فقط آخرین عملیات مهم است و از بقیه عملیات‌ها می‌توان صرف نظر کرد. به این تبدل، تبدیل آبشاری ${\displaystyle \Pi }$ گویند.

${\displaystyle \Pi {_{L}{_{1}}}(\Pi {_{L}{_{2}}}(\Pi {_{L}{_{3}}}...(\Pi {_{L}{_{n}}}(E))))=\Pi {_{L}{_{1}}}(E)}$ 

• عملیات‌های انتخاب می‌توانند با ضرب کارتزین و ادغام شرطی، ترکیب شود.

این عبارت  ${\displaystyle \sigma {_{\theta {_{1}}}}(E{_{1}}\times E{_{2}})=E{_{1}}\bowtie {_{\theta }}E{_{2}}}$را می‌توان به شکل ${\displaystyle \sigma {_{\theta {_{1}}}}(E{_{1}}\times E{_{2}})=E{_{1}}\bowtie {_{\theta {_{1}}\wedge \theta {_{2}}}}E{_{2}}}$نوشت. 

• عملیات‌های ادغام شرطی قابل جابجایی هستند.

${\displaystyle E{_{1}}\bowtie {_{\theta }}E{_{2}}=E{_{2}}\bowtie {_{\theta }}E{_{1}}}$ 

از این قوانین می‌توان برای بدست آوردن درخت پرسش استفاده کرد و نقشه‌های اجرا را بدست آورد.

اجزای بهینه‌ساز^[۳][ویرایش]

در سیستم‌های مدیریت پایگاه‌های داده ممکن است اجزای متفاوتی وجود داشته باشد، اما می‌توان به‌طور کلی گفت همه آن‌ها دارای اجزا زیر هستند (این اجزا به ترتیب مرحله اجرا ذکر شده‌اند).

1. تبدیل کننده پرسش: تشخیص می‌دهد آیا تغییر پرسش به شکل دیگری مفید هست یا نه.
2. تخمین زننده: برای هر نقشه پرسش زمان مورد نیاز را برا اساس فرهنگ داده تخمین می‌زند.
3. تولیدکننده نقشه پرسش: هزینه تمام نقشه‌های اجرای مختلف را با یکدیگر مقایسه کرده و کم هزینه‌ترین را انتخاب می‌کند، سپس نقشه انتخاب شده را برای اجرا به بخش بعدی ارسال می‌کند.

تبدیل کننده پرسش[ویرایش]

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

پرسش اولیه به شکل زیر به پایگاه داده فرستاده می‌شود. هدف از این پرسش بدست آوردن اسم درس و نمرات دو دانشجو با شماره دانشجویی‌های ۱۲۳ یا ۲۳۴ است.

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، پرسش به شکل معادل خود تبدیل شده‌است.

تخمین زننده[ویرایش]

تخمین زننده از سه معیار برای انجام کار خود استفاده می‌کند.

1. انتخاب شوندگی: کسر سطرهای انتخاب شده به کل سطرها را گویند. انتخاب شوندگی برابر صفر است اگر هیچ سطری انتخاب نشود و برابر ۱ است اگر همه سطرها انتخاب شوند. این عدد بستگی به شرط‌های پرسش دارد. معیار انتخاب شوندگی در نقشه پرسش قابل دستیابی و تعیین نیست.
2. اندازه: تعداد سطرهایی که توسط هر عملیات در نقشه‌های مختلف اجرا برگردانده می‌شود.
3. هزینه: معیاری برای اندازه‌گیری مقدار منابع یا کاری که برای اجرای نقشه پرسش باید در نظر گرفته شود، مثل ورودی -خروجی دیسک، استفاده از پردازنده، استفاده از حافظه و….

تولیدکننده نقشه پرسش[ویرایش]

کم هزینه‌ترین نقشه اجرا برای یک بلاک از پرسش را انتخاب می‌کند. برای درک بهتر این موضوع در نظر بگیرید برای یک عملیات 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 انجام دهند.

یک نمونه جبر رابطه‌ای عبارت ${\displaystyle \textstyle \prod _{B}^{\displaystyle }(R(A,B)\times S(B,C))}$ است.

تخمین هزینه[ویرایش]

یکی از دشوارترین مسائل در بهینه‌سازی پرسش، تخمین دقیق هزینه برای نقشه‌های پرسش است. بهینه‌سازها هزینه نقشه‌های پرسش را با استفاده از مدل‌های ریاضی که شدیداً به اندازه یا تعداد زوج‌ها (سطرها) که در یال‌های درخت اجرای پرسش قرار دارد وابسته است تخمین می‌زنند. تخمین اندازه بستگی به تخمین عامل انتخاب (درصد یا کسری از رکوردها در یک فایل که با رکوردهای یک فایل دیگر پیوند(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(واحد پردازش مرکزی) هم شناخته می‌شود.

• هزینه استفاده از حافظه اصلی

این هزینه مربوط به تعداد بافر مورد نیاز از حافظه در طول اجرای پرسش می‌باشد.

• هزینه ارتباط

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

فهرست منابع[ویرایش]