ما از query optimizing برای حل مسائل زیادی استفاده می کنیم.
زمانی که یک query مطرح می شود، سیستم مدیریت بانک اطلاعاتی (DBMS ) می تواند از روش های مختلفی برای پردازش آن query و رسیدن به جواب استفاده کند.
همه آن روش ها در نهایت یک نتیجه را تولید می کنند ولی از نظر هزینه های انجام شده مانند کل زمان مورد نیاز برای اجرا متفاوت اند.
چه روشی حداقل زمان را برای اجرا نیاز دارد؟
در یک DBMS ، بهینه سازی query بسیار ضروری می باشد.
هزینه انجام دو selection مختلف می تواند بسیار متفاوت باشد.
برای مثال به شمای بانک اطلاعاتی زیر که ممکن است در طی این بخش از آن استفاده شود توجه نمایید :
emp (name,age,sal,dno)
dept (dno,dname,floor,budget,mgr,ano )
acnt ( ano,type,balance,bno )
bank ( bno,bname,address )
به Query ساده زیر توجه کنید :
Select name, floor
From emp, dept
Where emp.dno=dept.dno and sal>100k
ویژگیهای زیر را برای محتوا، ساختار و محیط هنگام اجرا در نظر بگیرید :
ویژگیهای زیر را برای محتوا، ساختار و محیط هنگام اجرا در نظر بگیرید : به سه روش متفاوت زیر توجه کنید : P1 : از طریق B + - tree تمام tuple های emp را که شرط emp.sal را ارضا می کنند پیدا می کنیم.
برای هر کدام، از hashing index برای یافتن tuple های مناسب dept استفاده می کنیم.
( حلقه های تو در تو، استفاده از index روی هر دو رابطه) P2 : برای هر صفحه از dept، کل رابطه emp اسکن می شود.
اگر مقدار dno یک tuple از emp با مقدار tuple روی یک صفحه dept برابر باشد و شرط انتخاب روی emp.sal را ارضا نماید، زوج tuple emp – dept در نتیجه ظاهر می شود.
( حلقه های تودرتو در سطح صفحه، بدون استفاده از index ) P3 : به ازای هر dept tuple ، کل رابطه emp اسکن شده و تمام زوج های emp – dept tuple ذخیره می شوند.
سپس، این مجموعه از زوج ها اسکن می شوند و ، به ازای هر کدام، بررسی می شود آیا هر دو dno یک مقدار دارند و آیا شرط روی emp.sal را ارضا می کنند یا خیر.
(ساخت عرضی tuple ها، با اسکن ثانویه برای تست پیوند و اتصال) محاسبه هزینه مورد انتظار I/O این سه طرح نشان می دهد که چه تفاوت بزرگی از نظر کارایی میان این سه روش وجود دارد در صورتی که هر سه یک نتیجه را تولید می کنند.
P1 32/0 ثانبه، p2 کمی بیشتر از یک ساعت و p3 بیشتر از یک روز کامل نیاز دارد.
Query optimizer تمام انتخاب های ممکن را بررسی می کند، به همین دلیل انتخاب p1 برای پردازش query نباید خیلی سخت باشد.
مسیری که یک query از DBMS تا رسیدن به جواب طی می کند در شکل 1 نشان داده شده است.
ماژولهای سیستمی که از طریق آن حرکت می کند عملکردهای زیر را دارد : Query parser اعتبار query را بررسی می کند و سپس آن را به یک شکل داخلی ترجمه می کند، معمولاً به صورت یک عبارت calculus یا چیزی معادل آن.
Query optimizer همه عبارات جبری را که معادل query داده شده است تست کرده و یکی را که به نظر می رسد ارزانتر باشد انتخاب می کند.
Code generator یا مفسر، طرح تولید شده به وسیله optimizer را به فراخوانی پردازشگر query تبدیل می کند.
پردازشگر query به صورت واقعی query را اجرا می کند.
پرس و جو ها از طریق کاربران فعال و یا برنامه هایی که به زبان های همه منظوره ای که پرس و جوها را به صورت مخفی درون خود دارند ( مانند c یا c++ ، فرترن یا PL-1 ) ، نوشته شده اند و برای DBMS ارسال می شوند.
یک پرس و جوی فعال در مسیری که در شکل 1 نشان داده شده است حرکت می کند.
به عبارت دیگر، یک پرس و جوی مخفی در زمانیکه برنامه ای که در آن مخفی است کامپایل می شود ( زمان کامپایل ) بین سه مرحله اول تنها یکبار عبور می کند.
بنابراین، مستقل از تعداد دفعاتی که یک query مخفی نیاز دارد که اجرا شود، بهینه سازی تکرار نمی شود مگر اینکه بهنگام سازی بانک اطلاعاتی طرح دسترسی را غیر معتبر کند ( مانند حذف ایندکس )، یا بهینه سازی فرعی به صورت بهینه سازی بالا ( تغییرات گسترده در محتوای بانک اطلاعاتی ).
هیچ تفاوت واقعی بین بیهنه سازی فعال یا پرس و جوهای مخفی نیست، بنابراین در این فصل تمایزی بین آنها قائل نمی شویم.
در زمینه بانک اطلاعاتی، محدوده بهینه سازی پرس و جوها بسیار وسیع است.
این مورد از زوایای مختلفی می تواند مطالعه و بررسی شود، که در هر مورد به بخش های متعددی تقسیم می شود.
هدف این فصل این است که مشکل اصلی در بهینه سازی پرس و جوها و راه حل های آنها است.
به صورت خاص، ما روی یک پرس و جوی SQL ساده با تنها یک اتصال بولی and ( همچنین به عنوان پرس و جوی ربط دهنده، پرس و جوی select-project-join و یا عبارات غیر بازگشتی horn شناخته می شوند) در یک DBMS رابطه ای تمرکز می کنیم، فرض کنید که در زمان کامپایل دانش کاملی از محیط زمان اجرا وجود دارد.
همچنین، ما سعی نخواهیم کرد از ادبیات کاملی استفاده کنیم، در بیشتر مواقع تنها به تعدادی مثال ارجاع می دهیم.
باقیمانده این فصل به صورت زیر خواهد بود.
بخش 2 یک معماری پیمانه ای برای یک query optimizer ارائه می دهد و نقش هر ماژول را توضیح می دهد.
بخش 3 انتخاب هایی را که در شکل های طرح های دسترسی پرس و جوهای رابطه ای وجود دارد تحلیل می کند و محدودیت ها غالباً بوسیله optimizer فعلی تحمیل می شوند تا قابلیت نگهداری کل فرایند را افزایش دهند.
بخش 4 روی برنامه نویسی داینامیک استراتژی جستجو که به وسیله query optimizer تجاری استفاده شده است و به صورت واضح استراتژی های قابل انتخاب ارائه شده را تشریح می کند، متمرکز شده است.
بخش 5 مشکل تخمین اندازه نتایج پرس و جو و یا توزیع فراوانی مقادیر در آنها را تعریف می کند، و در هستوگرام های جزئی تشریح می شود که اطلاعات آماریی که به صورت نمونه برای چنین تخمینهایی به کار می رود استفاده شده است.
بخش 6 بهینه سازی پرس و جو ها را در محیط های غیر متمرکز مانند DBMS های موازی و توزیع شده، مورد بحث قرار می دهد.
در نهایت، بخش 7 خلاصه ای از مطالب فصل و سؤالاتی را که در رابطه با بهینه سازی پرس و جوها بدون جواب هستند مطرح می کند.
2.
معماری Query optimizer 2.1.
معماری کلی در این بخش، ما به صورت تجریدی در مورد فرایند بهینه سازی پرس و جوها در DBMS صحبت خواهیم کرد.
یک بانک اطلاعاتی و پرس و جویی روی آن داده شده است، طرح های اجرایی متعددی وجود دارد که می توان برای یافتن جواب پرس و جو به کار برد.
در ابتدا، همه گزینه ها را باید در نظر گرفت، در نهایت یکی که بهترین کارایی را دارد انتخاب خواهد شد.
به صورت تجریدی فرایند تولید و تست این گزینه ها در شکل 2 نشان داده شده است، که در اصل معماری پیمانه ای یک query optimizer است.
هرچند یک نفر می تواند یک optimizer را بر اساس این معماری بسازد ولی در سیستم های واقعی، پیمانه های نشان داده شده، همین حدود مشخص شده در شکل 2 را ندارند.
بر اساس شکل 2، کل فرایند بهینه سازی پرس و جو شامل دو مرحله است : بازنویسی و طرح ریزی.
در مرحله اول تنها یک ماژول وجود دارد، Rewrite ، و بقیه ماژول ها در مرحله دوم قرار دارند.
عملکرد هر یک از ماژول های شکل 2 به صورت زیر تحلیل می شود.
2.2.
عملکرد ماژول ها Rewiter : این ماژول روی یک پرس و جوی داده شده به کار می رود و پرس و جوهای معادلی را که مؤثرتر هستند تولید می کنند، مانند جایگزینی view ها با تعاریفشان، باز کردن یک پرس و جوی فشرده و غیره.
انتقالی که به وسیله Rewiter انجام می شود تنها به نحوه تعاریف مانند استاتیک و ویژگیهای پرس و جوها وابسته است.
اگر بازنویسی به عنوان کاری که همیشه سودمند است شناخته و یا فرض شود، پرس و جوی اصلی شکسته می شود؛ از طرف دیگر، برای ادامه به مرحله بعدی فرستاده می شود.
بوسیله طبیعت انتقالات بازنویسی، این مرحله به عنوان یک سطح تعریفی شناخته می شود.
ماژول طرح ریزی : این ماژول، ماژول اصلی مرحله سفارش است.
این ماژول همه طرح های قابل اجرا برای هر یک از پرس و جوهای تولید شده در مرحله قبل را آزمایش می کند و در نهایت طرحی که برای تولید جواب پرس و جوی اصلی از همه ارزان تر است انتخاب می شود.
این ماژول از یک استراتژی جستجو استفاده می کند، که فضای طرح های قابل اجرا را در یک شکل جزئی آزمایش می کند.
این فضا به وسیله دو ماژول دیگر optimizer تعیین شده است، فضای جبری و فضای متد – ساختار.
برای بیشتر بخش ها، این دو ماژول و استراتژی جستجو، هزینه را تعیین می کند مانند زمان اجرای خود optimizer ، که باید تا حد امکان پایین باشد.
اجرای طرح ها که به وسیله planner آزمایش شده اند بر مبنای تخمین هزینه های آنها تا اینکه ارزان ترین انتخاب شود.
این هزینه ها به وسیله دو ماژول آخر optimizer ، یعنی ماژول هزینه و تخمین گر اندازه توزیع شده انجام می شود.
ماژول فضای جبری : این ماژول عمل سفارشات اجرا شده ای را که به ازای هر پرس و جوی ارسال شده مورد توجه طراح ( برنامه ریز) هستند مشخص می کند.
این مجموعه عمل ها، جواب یکسانی برای پرس و جوها تولید می کنند، اما معمولاً در میزان کارایی متفاوت اند.
آنها معمولاً در جبر رابطه ای به شکل فرمول و یا درخت ارائه می شوند.
به خاطر اینکه ماهیت اشیایی که به وسیله این ماژول تولید و به برنامه ریز ارسال می شوند الگوریتمی است، مرحله طرح ریزی کلی به عنوان عملی در سطح روال شناخه می شود.
فضای متد – ساختار : این ماژول انتخاب های پیاده سازی که برای اجرای هر یک مجموعه سفارشات عمل های مشخص شده به وسیله فضای جبری موجود است را مشخص می کند.
این انتخاب وابسته به تعداد متدهای پیوند (join) است که به ازای هر پیوند وجود دارد (مانند حلقه ای ، تودرتو، merge scan و پیوند (hash، اگر ساختمان داده ها را که بر مبنای جهش، اگر زمانیکه کپی ها حذف می شوند و یا سایر ویژگیهای پیاده سازی از این دسته که از قبل به وسیله DMBS تعیین شده اند .
این انتخاب وابسته به شاخص های موجود برای دسترسی به هر یک از رابطه های موجود است که به وسیله شمای فیزیکی بانک اطلاعاتی که در کاتالوگ آن ذخیره شده است تعیین می شود.
با دادن یک فرمول جبری یا ساختار درختی فضای جبری، این ماژول همه طرح های اجرایی کامل مشابه را تولید می کند که پیاده سازی هر یک از عملگرهای جبری و هر یک از شاخص را مشخص می کند.
ماژول هزینه : این ماژول فرمول های ریاضی را که برای تخمین هزینه اجرای طرح ها به کار می رود مشخص می کند.
برای هر متد پیوند متفاوت، به ازای هر نوع دسترسی متفاوت و به صورت کلی برای هر یک از مراحل که در اجرای یک برنامه وجود دارد، فرمولی وجود دارد که هزینه را تعیین می کند.
میزان پیچیدگی خیلی از این مراحل، بسیاری از فرمول ها وابسته به مفروضاتی مانند مدیریت بافرها، تداخل دیسک و CPU و ورودی/خروجی متوالی هستند.
یکی از پارامترهای مهم ورودی اندازه بافری است که استفاده می شود، اندازه ارتباطات یا شاخص دسترسی ها و امکان توزیع داده ها در این روابط.
به ازای هر پرس و جو، مورد اول به وسیله DBMS محاسبه می شود دو مورد بعدی به وسیله تخمین گر میزان توزیع تخمین زده می شود.
تخمین گر اندازه توزیع : این ماژول مشخص می کند که چطور اندازه های ( و امکان توزیع مقادیر خصوصیات ) ارتباطات و شاخص های پایگاه داده تخمین زده می شود.
همانطور که در بالا یادآوری شد، این تخمین مورد نیاز ماژول هزینه است.
همچنین روش تخمینی خاصی که در این ماژول به کار می رود شکل آماری را که برای نگهداری در کاتالوگ هر پایگاه داده مورد نیاز است تعیین می کند.
2.3.
تمرکز روی توضیحات از شش ماژولی که در شکل 2 وجود داشت سه ماژول به صورت جزئی در این بخش به صورت تفصیلی و جزئی مورد بحث قرار نمی گیرند؛ Rewiter ، فضای ساختار – متد و مدل هزینه.
Rewiter ماژولی است که در برخی از DBMS های تجاری استفاده می شود ( DB2 client/server و Illustra )، اگر چه در همه آنها به کار نمی رود.
بیشتر انتقالاتی که به صورت نرمال به وسیله این ماژول انجام می شود به عنوان شکل پیشرفته بهینه سازی پرس و جوها مورد توجه است و بخشی از فرایند مرکزی محسوب نمی شود.
فضای متد – ساختار متدهای پیوند جایگزینی را مشخص می کند که مبتنی بر تصمیم گیری خارج از پیاده سازی بهینه سازی پرس و جو است و باقیمانده آن را تحت تأثیر قرار نمی دهد.
برای مدل هزینه، به ازای هر متد پیوند جایگزین، دسترسی شاخص ها که توسط فضای متد – ساختار پیشنهاد شده است فرمول استاندارد مشابهی وجود دارد که مردم به وسیله محاسبه تعداد عمل های مشابه به کار می برند، همچنین تعداد زیادی فرمول وجود دارد که مردم ارائه کرده اند که برای تقریب این عمل ها به کار می رود.
در سایر موارد، اشتقاق این فرمول ها یک بخش درونی بهینه سازی اشتقاق مورد توجه نیست.
بنا به همین دلایل، ما تا بخش 7 این سه ماژول را بیشتر مورد بحث قرار نمی دهیم، زمانیکه تعدادی از انتقالات Rewiter مورد بررسی قرار می گیرد.
سه بخش بعدی توضیحات بیشتری به ترتیب در مورد فضای جبری، برنامه ریز و ماژول تخمین گر میزان توزیع ارائه می شود.
3.
فضای جبری همانطور که در بالا یادآوری شد یک پرس و جوی SQL به یک پرس و جوی select – project – join در جبر رابطه ای پاسخ می دهد.
به صورت کلی چنین پرس و جوی جبری به وسیله یک درخت پرس و جو که برگ های آن روابط پایگاه داده و نودهای دیگر به جز برگ ها، عملگرهایی مانند select ( که با نشان داده می شود ) ، تصویر ( ) و الحاق ( ∞) هستند نشان داده می شود.
نود میانی کاربرد عملگر نظیر با روابط ایجاد شده به وسیله فرزندانش را تعیین می کند، سپس نتیجه تولیده شده به سمت بالا فرستاده می شود.
بنابراین یال های یک درخت جریان داده را از پایین به سمت بالا یعنی از برگ ها که معادل داده در پایگاه داده می باشد به سمت ریشه که آخرین عملگری است که جواب پرس و جو را تولید می کند، نشان می دهد.
شکل 3، سه مثال از درخت پرس و جو برای پرس و جوی زیر ارائه می کند : select name,floor from emp,dept where emp.dno=dept.dno and sal>100k.
شکل 3 : مثال هایی از درخت های عمومی پرس و جو برای یک پرس و جوی پیچیده تعداد کل درخت های پرس و جو می تواند زیاد باشد.
برای کاهش اندازه فضایی که استراتژی جستجو باید بررسی کند، DBMS ها معمولاً فضا را به روشهای مختلفی کاهش می دهند.
اولین محدودیت عمومی در رابطه با انتخاب و تصویر است : محدودیت اول (R1) : انتخاب و تصویر هیچگاه روابط میانی تولید نمی کنند.
انتخاب به عنوان رابطه ای که در بار اول در دسترس هستند پردازش می شوند.
تصاویر روی نتایجی که سایر عملگرها تولید کرده اند پردازش می شوند.
برای مثال طرح p1 بخش اول محدودیت R1 را ارضا می کند : شاخص اسکن emp همه رکوردهایemp هایی را که شرط انتخاب روی emp.sal را ارضا می کند و تلاش می کند تنها آنها را به هم الحاق کند؛ به علاوه، عملگر تصویر روی نتیجه، رکورد های مورد نظر را تولید می کند.
R1 برای پرس و جوهایی که الحاق ندارند، مطرح است.
هر چند که برای پرس و جوهایی نیز که الحاق دارند، این محدودیت تصریح می کند که همه عملگرها به عنوان بخشی از اجرای پیوند هستند.
محدودیت R1 تنها درخت های پرس و جوی بهینه فرعی را حذف می کند، زیرا فرایندهای جداگانه انتخاب و تصویر هزینه های اضافی تحمیل می کند.
بنابراین ماژول فضای جبری درخت های پرس و جوی جایگزین را تنها با عملگرهای الحاق مشخص می کند، انتخاب ها و تصاویر ضمنی هستند.
مجموعه ای از روابط در پرس و جوها به کار می رود ، مجموعه همه درخت های پیوند جایگزین به وسیله دو خاصیت جبری پیوند مشخص می شود : جابجایی پذیری (R1 ∞ R2) و خاصیت شرکت پذیری ((R1∞R2) ∞R3 = R1 ∞(R2∞R3)) .
خاصیت اول نشان می دهد که چه روابطی می توانند در اجرای عملگر پیوند داخل و چه روابطی می تواند خارج باشد.
خاصیت دوم ترتیب اجرای عملگرهای پیوند را نشان می دهد.
حتی با توجه به محدودیت R1 ، تعداد درخت های جایگزینی که طبق خصوصیت های جابجا پذیری و اشتراک پذیری تولید می شود خیلی زیاد خواهد بود، به ازای N رابطه، (N!) خواهد بود.
بنابراین DBMS ها معمولاً محدودیت های بیشتری را اعمال می کند.
به صورت خاص، محدودیت دوم با محصولات cross برخورد می کند.
محدودیت دوم (R2) : محصولات cross هیچ گاه تشکیل نمی شوند مگر اینکه پرس و جو خودش آن را درخواست کرده باشد.
در پرس و جو، روابط همیشه با استفاده از پیوند با یکدیگر ترکیب می شوند.
برای مثال به پرس و جوی زیر توجه کنید : Select ame,floor,balance From emp,dept,acnt Where emp.dno=dept.dno and dept.ano=acnt.ano شکل 4 سه درخت پیوندی را که می توان تولید کرد نشان می دهد از بین این درخت ها، درخت T3 محصول cross دارد، چون پایین ترین پیوندش شامل پیوند emp و acnt است ، که در پرس و جو صراحتاً با یکدیگر ترکیب نشده اند.
محدودیت R2 همیشه درخت های پیوند را که به صورت فرعی بهینه شده اند حذف می کند، و علت آن اندازه بزرگ نتایجی است که به وسیله محصولات cross تولید می شوند.
استثنائات خیلی کم هستند و در مواردی هستند که روابطی که محصولات cross تولید می کنند بی نهایت کوچک هستند.
بنابراین، ماژول فضای جبری درخت های پیوندی را جایگزین می کند که محصولات cross ندارند.
حذف محصولات cross اندازه فضایی را که پوشش داده شود را کاهش می دهد، اما این فضا همچنان خیلی بزرگ است.
اگر چه خیلی از سیستم ها این فضا را محدود تر نمی کنند ( برای مثال Ingres و DB2 Client/Server ) ، برخی دیگر به فضای خیلی کوچکتری نیاز دارند ( برای مثال DB2/MVS ).
به صورت خاص، محدودیت نوع سوم با شکل درخت های پیوند برخورد می کند.
محدودیت سوم (R3) : عملوندهای میانی هر پیوندی یک رابطه در data base هستند، هیچ گاه نتایج میانی نیستند.
برای مثال به پرس و جوی زیر دقت کنید : select name,floor,balance,address from emp,dept,acnt,bank where emp.dno=dept.dno and dept.ano=acnt.ano and acnt.bno=bank.bno شکل 5 سه درخت محصول cross را که می توان برای پیوند emp ، dept ، acnt و bank به منظور یافتن نتیجه پرس و جو به کار برد نشان می دهد.
درخت T1 محدودیت R3 را ارضا می کند، در حالی که درخت T2 و T3 چنین نیستند، چون آنها حداقل یک پیوند با یک نتیجه واسط به عنوان یک رابطه میانی دارند.
به خاطر شکل درخت پیوند T1 که محدودیت R3 را ارضا می کند به درخت T1 ، left-deep گفته می شود.
درخت هایی که روابط خارجی دارند همیشه یک رابطه data base هستند برای مثال مانند T2 که به آن right – deep گفته می شود.
درخت هایی با حداقل با یک پیوند بین دو نتیجه میانی مانند درخت T3 درخت انبوه نامیده می شود.
محدودیت R3 ذاتاً اکتشافی تر از R1 و R2 است و در موارد متعددی می تواند طرح های بهینه فرعی را حذف نماید.
ممکن است ادعا شود که اغلب درخت های بهینه left – deep هزینه بر تر از درخت های بهینه کلی نیستند.
آرگومانهای عمومی که استفاده می شوند دو نوع هستند : داشتن ارتباطات اصلی data base ها به عنوان روابط داخلی استفاده از هر شاخص دیگری را افزایش می دهد.
داشتن روابط میانی اجازه می دهد حلقه های پیوند تودرتو به روش های pipeline اجرا شوند.
استفاده از شاخص ها و pipelining هزینه درخت های پیوند را کاهش می دهد.
به علاوه ، محدودیت R3 به صورت خاص تعداد درخت های پیوند جایگزین را به O(2N) برای پرس و جوهایی با N رابطه کاهش می دهد.
بنابراین، ماژول فضای جبری بهینه ساز پرس و جوی عمومی فقط درخت های پیوندی را نگه می دارد که left-deep هستند.
به صورت خلاصه، بهینه سازهای معمولی از محدودیت های R1,R2,R3 برای کاهش فضایی که باید جستجو شود استفاده می کنند.
4.
planner ( برنامه ریز ) وظیفه planner این است که طرح های قابل اجرا را که به وسیله فضای جبری و فضای ساختار متد مشخص شده اند بررسی کند و طرحی را که به وسیله مدل قیمت و تخمین گر اندازه توزیع تعیین شده و ارزانتر است پیدا کند.
سه بخش زیر در مورد انواع مختلف استراتژیهای بررسی که planner می تواند برای جستجویش مورد استفاده قرار دهد بحث می کند.
در بخش اول روی استراتژی های مهم، برنامه نویسی داینامیک، که معمولاً برای سیستم های تجاری مورد استفاده قرار می گیرد صحبت می شود.
در بخش دوم در مورد روشی که مبتنی بر الگوریتم تصادفی است بحث می شود و در بخش سوم سایر استراتژی ها مورد بحث قرار خواهند گرفت.
4.1.
الگوریتم های برنامه نویسی داینامیک اولین بار برنامه نویسی داینامیک به عنوان استراتژی جستجوی پرس و جوی بهینه در سیستم به وسیله Selinger استفاده شد.
سپس سیستم های تجاری آن را در اشکال مختلفی به کار بردند.
ما این الگوریتم را به صورت اصلی خود ارائه می کنیم، تنها از جزئیاتی که در پرس و جوهای SQL به کار نمی رود صرفنظر می کنیم.
این الگوریتم شامل تمامی درخت های پیوند جایگزین (که محدودیت های R1-R3 را ارضا می کند) می باشد که با تکرار روی تعداد روابط پیوند، درخت را حرص می کند تا درخت بهینه را به دست آورد.
قبل از اینکه جزئیات الگوریتم را ارائه کنیم، لازم است در مورد راه های جالب بحث کنیم.
یکی از روش های پیوند که اغلب با ماژول فضای ساختار-متد شناخته می شود merge scan است.
merge scan ابتدا دو رابطه ورودی پیوند را مرتب می کند و سپس آنها را با یک اسکن همزمان merge می کند.
اگر یکی از ورودی ها ، قبلاً ویژگی های پیوند آن ذخیره شده است، در مرحله مرتب کردن از آن رابطه می گذرد.
بنابراین، دو برنامه مختلف برای بهینه سازی پرس و جو ارائه شده است، یکی نمی تواند آنها را بر اساس قیمت مقایسه کند و آن طرحی را که قیمت بیشتری دارد حذف کند؛ یکی مجبور است که ورودی های خود را به ترتیب دریافت کند و خروجی بر اساس همن ترتیب به دست می آید.
یکی از طرح ها ممکن است خیلی پر هزینه باشد ولی ممکن است نتایجش را به ترتیبی که در اجرای merge scan ذخیره کرده است تولید کند.
برای اینکه این امکان را به وجود آوریم، در یک پرس و جویی که داده شده است، ترتیب مورد نظر تعریف می شود تا طبق آن نتایج میانی روی هر ویژگی رابطه که در پیوند شریک است انجام شود.
( برای بیشتر پرس و جوهای SQL ، ویژگی on order by و group by باعث می شود نتایج به شکل بهتری به دست آید.
) برای مثال، در پرس و جوی بخش 3، ترتیب روی ویژگی های emp.dno ، dept.dno ، dept.ano، acnt.ano ، acnt.bno و bank.bno مورد نظر هستند.
در طی بهینه سازی این پرس و جو، اگر هر نتیجه میانی از این ترتیب روی هر یک از این ویژگی ها خارج شود، طرح جزئی که این نتیجه را می دهد باید به صورت خاص کار کند.
با استفاده از روش بالا، ما جزئیات الگوریتم بهینه سازی پرس و جوی N رابطه را با استفاده از برنامه نویسی داینامیک ارائه می دهیم : مرحله 1 : برای هر رابطه روی پرس و جو، همه راه های ممکن برای دسترسی به آن، از طریق شاخص است و شامل اسکن متوالی ساده، به دست می آید.
( دسترسی یک شاخص روی تعداد هر انتخاب پرس و جو روی شاخص ویژگی کلید اتفاق می افتد.) این روابط ( روابط ساده ) جزئی به کلاس های مساوی مبتنی بر هر ترتیب دلخواهی که طبق آن نتایج را تولید می کنند تقسیم می شوند.
یک کلاس مساوی اضافه، به وسیله طرح های جزئی که نتایج آن هیچ ترتیبی ندارند، شکل گرفته است.
تخمین هزینه همه طرح ها از ماژول مدل قیمت به دست می آید، و ارزانترین طرح در هر کلاس هم ارزی ، برای بررسی بیشتر نگهداشته شده است.
به هر حال، ارزانترین طرح بدون ترتیب کلاس هم ارز نگهداشته نمی شود مگر اینکه از همه طرح های دیگر ارزانتر باشد.
مرحله 2 : برای هر زوج رابطه پیوند در پرس و جو، همه راه های ممکن برای ارزیابی پیوندشان با استفاده از همه روابط طرح های دسترسی نگهداشته شده مرحله 1 بدست می آیند.
تقسیم بندی و حذف این طرح های ( دو رابطه ) جزئی همانند بالا.
.............
مرحله i : برای هر مرحله i-1 روابط در پرس و جو پیوند داده می شوند، ارزانترین طرح ها برای پیوند آنها برای هر ترتیب دلخواهی از مرحله قبل شناخته می شود.
در این مرحله، برای هر مجموعه، تمام راه های ممکن برای پیوند بیشتر از یک رابطه با آن بدون تولید محصول cross بررسی می شود.
برای هر مجموعه از روابط i ، همه طرح های ( جزئی ) تولید شده مانند قبل تقسیم بندی و حذف می شوند.
.....
مرحله N : همه طرح های ممکن برای پاسخگویی به پرس و جو ( مجموعه یکتا از N رابطه پیوند زده شده در پرس و جو ) از طرح هایی که در مرحله قبل نگهداری شده اند تولید می شوند.
ارزانترین طرح خروجی نهایی بهینه ساز ، برای استفاده در پردازش پرس و جو است.
برای یک پرس و جوی داده شده، الگوریتم بالا تضمین می کند طرح بهینه را در میان محدودیت های R1-R3 پیدا کنید.
این الگوریتم از طریق حذف بعضی از بخش ها ، فضای طرح ها را کاهش می دهد.
در حقیقت، هر چند در حالت کلی پیچیدگی این الگوریتم همچنان نمایی است، ولی پرس و جوهایی وجود دارد که برای آنها تنها O(N3) طرح تولید می شود.
مثالی که برنامه نویسی داینامیک را با همه جزئیاتش نشان دهد نیاز به فضای زیادی دارد.
ما مکانیزم این نوع برنامه نویسی را با بررسی یک پرس و جوی ساده و نحوه پردازش آن بررسی می کنیم.
select name,mgr from emp,dept where emp.dno=dept.dno and sal>30k and floor = 2 فرض کنید که یک شاخص B+-tree روی emp.sal ، یک شاخص B+-tree روی emp.dno و یک شاخص hashing روی dept.floor وجود داشته باشد.
همچنین فرض کنید که DBMS از دو متد پیوند پشتیبانی کند، حلقه های تودرتو و merge scan .( هر دو نوع اطلاعات باید در ماژول فضای ساختار- متد مشخص شوند .) به یاد داشته باشید که بر اساس این تعریف، ترتیبی که مد نظر است emp.dno و dept.dno است، زیرا اینها تنها خصوصیات پیوند در پرس و جو هستند.
الگوریتم به شکل زیر پردازش می شود : مرحله 1 : همه راه های ممکن برای دسترسی به emp و dept پیدا می شود.
تنها ترتیب مورد نظر از دسترسی به emp از طریق B+-tree روی emp.dno به دست می آید که رکوردهای مرتب شده emp را تولید می کند و برای پیوند با dept آماده است.
همه مجموعه جایگزین، که به صورت مناسبی تقسیم بندی شده است در جدول زیر نشان داده شده است.
هر طرح جزئی، با قیمت های فرضی جمع زده شده است؛ در حقیقت این قیمت ها با استفاده از ماژول مدل قیمت به دست می آیند.
در هر کلاس هم ارزی، تنها ارزانترین طرح برای مرحله بعدی به دست می آید، که به وسیله یک مستطیل قیمت آن مشخص شده است.
مرحله 2 : از آنجایی که پرس و جو دو رابطه دارد، این مرحله آخرین مرحله الگوریتم است.
همه راههای ممکن برای پیوند emp و dept پیدا شدند، از هر دو متدهای پیوند پشتیبانی شده و همه طرح های جزئی برای دسترسی به همه روابط اختصاصی پیدا شده در مرحله 1 استفاده می شود.
برای متد حلقه های تودرتو، کدام روابط داخلی هستند و کدام روابط خارجی.
از آنجایی که این مرحله آخرین مرحله الگوریتم است، هیچ مطلبی از ترتیب دلخواه وجود ندارد.
تمام مجموعه های جایگزین به روشی مشابه روش مرحله 1 در جدول زیر نشان داده شده است.
بر مبنای قیمت های فرضی هر طرح، بهینه ساز طرح خروجی را با یک مستطیل متناظر با قیمت در جدول مشخص کرده است.
همانگونه که در مثال بالا بیان شد، انتخابی که به وسیله فضای متد- ساختار در مجموع با نتایج فضای جبری در تعداد بسیار زیاد جایگزین هایی است که با اندازه پرس و جو نسبت نمایی دارد ( تعداد پیوندها) در بدترین حالت از آنجایی که طرح های جزئی ماندنی تولید شده اند در هر مرحله باید ذخیره شوند تا در مرحله بعدی استفاده شوند.
در حقیقت، خیلی از سیستم های مدرن محدودیتی را روی اندازه پرس و جوهایی که می تواند ارسال شود قرار می دهند ( معمولاً حدود پانزده پیوند )، زیرا برای پرس و جوهای بزرگتر بهینه ساز در حین انجام کارش به خاطر نیاز به حافظه زیاد crash می کند.
با این وجود، بیشتر پرس و جو ها به نظر می رسد با کمتر از 10 پیوند مواجه باشند، و ثابت شده است که الگوریتم در چنین مواردی بسیار کاربردی است.
در استراتژی های پرس و جوی بهینه سازی استانداردها مورد توجه هستند.
4.2.
الگوریتم های تصادفی برای پوشاندن عدم توانایی برنامه نویسی پویا در رابطه با پرس و جوهایی که واقعاً بزرگ هستند، و زمینه کاربردهای جدید مختلفی مطرح اند، اخیراً الگوریتم های متعدد زیادی ارائه شده است.
از جمله این الگوریتم ها، الگوریتم های تصادفی است، برای مثال الگوریتم هایی که در مورد پرتاب سکه تصمیم گیری می کنند، به نظر امید بخش می آید.
مهمترین دسته از الگوریتم های بهینه سازی مبتنی بر انتقال طرح ها به جای ساخت طرح با زبان برنامه نویسی است، و شامل الگوریتم هایی مانند simulated annealing ، تکرار شونده در حال رشد و بهینه سازی دو مرحله ای است .
الگوریتم های عمده ای وجود دارد که می تواند برای بسیاری از مسائل بهینه سازی به کار رود و به صورت واضح در زیر برای تطبیق با بهینه سازی پرس و جو توضیح داده شده است.
آنها از طریق جستجوی یک گراف که نودهای آن طرح اجرایی ممکن است می توانند به نتیجه برسند.
هر نود قیمتی دارد که به آن نسبت داده شده است، و هدف الگوریتم یافتن نودی با کمترین هزینه است.
الگوریتم های تصادفی از طریق مسیرهای تصادفی که طی می کنند، این کار را انجام می دهند.
نودهایی که از نود S قابل دسترسی هستند، همسایه های S نامیده می شوند.
یک حرکت را سربالا می گویند اگر هزینه نود مبدأ کمتر از نود مقصد باشد.
یک نود مینیمم عمومی است اگر در بین همه نودها کمترین هزینه را داشته باشد.
یک نود مینیمم محلی است اگر در بین تمام مسیرهایی که با آن نود شروع می شود کمترین هزینه را داشته باشد.