بهینه‌سازی و پردازش پرس و جو

 

در این تحقیق ما به تكنیك‌های بكار رفته توسط DMBS برای پردازش، بهینه‌سازی و اجرای پرس و جوهای سطح بالا می‌پردازیم.   پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه . معتبر شود. پویشگر (اسكنر) علامت هر زبان، مثل لغات كلیدی SQL، اساس ویژگی، و اساس رابطه، را در متن پرس و جو شناسایی می‌كند،‌ در عوض تجربه كننده، ساختار دستوری پرس و جو را برای تعیین اینكه آیا بر طبق قوانین دستوری زبان پرس و جو تدوین می‌شود یا خیر، چك می‌كند. پرس و جو باید همچنین معتبر شود، با چك كردن اینكه تمام اسامی رابطه و ویژگی معتبر هستند و اسامی معنی‌دار در طرح پایگاه اطلاعاتی ویژها‌ی پرس و جو می‌شوند. نمونه داخلی پرس و جو ایجاد می‌شود،‌‌ كه تحت عنوان ساختار داده‌های درختی بنام درخت پرس و جو می‌باشد. ارائه پرس و جو با استفاده از ساختار داده‌های گراف بنام گراف پرس و جو نیز امكان پذیر است. DOMS باید استراتژی اجرایی برای بازیابی نتیجه پرس و جو از فایل‌های پایگاه اطلاعاتی را هدایت كند. پرس و جو استراتژیهای اجرایی بسیاری دارد. و مرحلة انتخاب،‌ مورد مناسبی برای پردازش پرس وجو تحت عنوان بهینه‌سازی پرس و جو شناخته شده است.    تصویر 1، مراحل مختلف پردازش پرس و جوی سطح بالا را نشان می‌دهد. قطعه بر نامه بهینه‌ساز پرس وجو، وظیفه ایجاد طرح اجرایی را بعهده دارد و ژنراتور (تولید كننده) كه ، كد را برای اجرای آن طرح ایجاد می‌كند. پردازنده پایگاه اطلاعاتی زمان اجرا وظیفه اجرای كه پرس و جو را بعهده دارد،‌ خواه در وضعیت كامپایل شده یا تفسیر شده جهت ایجاد نتیجه پرس و جو. اگر خطای زمان اجرا نتیجه شود،‌ پیام خطا توسط پایگاه اطلاعاتی زمان اجرا ایجاد می‌شود.  اصطلاح بهینه‌سازی نام بی مسمایی است چون در بعضی موارد،‌ طرح اجرایی انتخاب شده، استراتژی بهینه نمی‌باشد، آن فقط استراتژی كارآمد معقول برای اجرای پرس و جو است. یافتن استراتژی بهینه، ضامن صرف زمان زیادی است، بجز برای ساده‌ترین پرس و جوها،‌ ممكن است به اطلاعاتی روی چگونگی اجرای فایل‌ها در فهرست‌های فایل‌ها، اطلاعاتی كه ممكن است كاملاً در كاتالوگ DBMS در دسترس نباشد، نیاز باشد. از اینرو،‌ برنامه‌ریزی استراتژی اجرا ممكن است توصیف درست‌تری نسبت به بهینه‌سازی پرس و جو باشد.  برای زبانهای پایگاه اطلاعاتی (دریایی) جهت‌یابی در سطح پایینتر در سیستم‌های قانونی، مثل شبكه DML شبكه‌ای یا MOML سلسله مراتبی،‌ برنامه نویس باید، استراتی اجرای پذیرش و جو را انتخاب كند ضمن اینكه برنامه پایگاه اطلاعاتی را می‌نویسد. اگر DBMS فقط زیان جهت‌یابی را ارائه دهد. فرصت و نیاز محدودی برای بهینه‌سازی پرس وجوی وسیع توسط DBMS وجود دارد، در عوض به برنامه نویس قابلیت انتخاب استراتژی اجرایی بهینه ارائه می‌شود. بعبارت دیگر، زبان پرس و جو در سطح بالا، مثل SQL  برای DBMSهای رابطه‌ای یا OQL برای DBMS‌های مقصد،‌ در ماهیت تفریطی‌تر است. چون آنچه نتایج مورد نظر پرس و جو است بغیر از شناسایی جزئیات چگونگی بدست آمدن نتیجه،‌ را تعیین می‌كند. بهینه‌سازی پرس و جو برای پرس و جوهایی ضروی است كه در زبان پرس و جوی سطح بالا تعیین می شوند. ما روی توصیف بهینه‌سازی پرس و جو در زمینه ROBMS تمركز می‌كنیم چون بسیاری از تكنیك‌هایی كه توصیف می‌ كنیم برای، برای ODBMSها تطبیق یافته‌اند. DBMS رابطه‌ای باید استراتژیهای اجرای پرس و جوی دیگری را ارزیابی كند و استراتژی بهینه یا كارآمد معقولی را انتخاب كند. هر DBMS ،‌ تعدادی الگاریتم دسترسی به پایگاه اطلاعاتی كلی دارد كه علامتهای رابطه‌ای مثل SELECT یا JOIN یا تركیبی از این عملیات ‌ها را اجرا می‌كند. تنها استراتژیهای اجرایی كه می‌توانند توسط الگاریتم‌های دسترسی DBMS اجرا شوند و برای طراحی پایگاه اطلاعاتی فیزیكی ویژه و پرس و جوی خاص بكار روند،‌ می‌توانند توسط قطعه برنامه بهینه‌سازی پرس و جو در نظر گرفته شوند.  ما با بحث كلی چگونگی ترجمه پرس و جوهای SQL به پرس و جوهای جبری رابطه‌ای و در بهینه‌شدن آنها كار را شروع می‌كنیم. بعد ما روی الگاریتم‌ها برای اجرای عملیات‌های رابطه‌ای در بخش 1802 بحث می‌كنیم. بدنبال این مطلب، بررسی از استراتژیهای بهینه‌سازی پرس و جو را ارائه می‌دهیم. دو تكنیك اصلی برای اجرای بهینه‌‌سازی پرس و جو وجود دارد. اولین تكنیك بر اساس قوانین ذهنی جهت ترتیب دادن عملیات‌ها در استراتژی اجرای پرس و جو می‌باشد. ذهن قانونی است كه بخوبی در اكثر موارد عمل می‌كند ولی برای كار مناسب در هر مورد كنش تضمین نمی‌شود. قوانین عملیات‌ها را در درخت پرس وجو مجدداً ترتیب می‌دهند. دومین تكنیك شامل برآورد هزینه استراتژیهای اجرای متفاوت و انتخاب طرح اجرایی با پایین‌ترین هزینه برآورد است. دو تكنیك معمولاً در بهینه ساز پرس و جو (باهم تركیب می‌شوند) بهم ملحق می‌گردند. بررسی مختصری از عوامل در نظر گرفته شده در طول بهینه‌سازی پرس و جو در RDBMS بازرگانی ORACLL= را ارائه می‌دهیم. در بخش بعدی نوعی بهینه‌سازی پرس و جوی معنایی را ارائه می‌دهد كه در آن محدودیت‌های شناخته شده برای پرداختن به استراتژیهای اجرایی پرس و جوی كارآمد استفاده می‌شوند.  2 – ترجمه پرس و جوهای SQL به پرس و جوهای رابطه‌ای:  در عمل، SQL زبان پرس وجویی است كه در اكثر RDBMS ‌های بازرگانی استفاده می‌شود. پرس وجوی SQL ، ابتدا به عبارت جبری رابطه‌ای توسعه یافته معادل،‌ نمایانگر ساختار داروهای درخت پرس و جو، ترجمه می‌شود و بعد بهینه‌سازی می‌شود. پرس و جوهای SQL به بلوكهای پرس و جو تجزیه می‌شوند،‌ كه واحدهای اساسی را تشكیل می‌دهند كه می‌توانند به عملكردهای جبری ترجمه شوند و بهینه‌سازی شوند. بلوك پرس و جو شامل عبارت SELECT- FROM-WHERE تكی و بندهای Groop By و HAVING است چنانچه این‌ها بخشی از بلوك باشند. از اینرو،‌ پرس و جوهای تو در تو در پرس و جو بعنوان بلوكهای پرس و جوی مجزا شناسایی می‌شوند. چون SQL شامل عملكردهای گروهی، مثل MAX ،‌ COUNT,SUM می‌باشد، این عملگرها باید در پرس و جوی جبری توسعه یافته‌ای شامل شوند، همانطوریكه در بخش 705 توصیف شد. پرس و جوی SQL در رابطه EMPLOEE در تصویر 705 را در نظر بگیرید:  این پرس و جو شامل، پرس و جوی فرعی تو در تو است و از اینرو به دو بلوك تجزیه می‌شود. بلوك درونی بدین صورت است:  و بلوك بیرونی بدین صورت می باشد:  كه C نمایانگر نتیجه حاصله از بلوك درونی است. بلوك درونی به عبارت جبری رابطه‌ای توسعه یافته زیر ترجمه شده است:  و بلوك بیرونی به عبارت زیر  ترجمه شده است:  بهینه‌ساز پرس و جو، طرح اجرایی را برای هر بلوك انتخاب می‌كند. ما باید اشاره كنیم به در مثال فوق، بلوك درونی نیاز به ارزیابی شدن دارد تنها زمانی كه، حداكثرحقوقی كه بعكار می‌رود كه بعنوان ثابت C، توسط بلوك بیرونی استفاده می‌شود. ما اینرو پرس و جوی تودرتوی غیرمرتبط نامیدیم (در فصل 8). آن برای بهینه‌سازی پرس و جوهای تو در توی مرتبط پیچیده‌تر، خیلی سخت‌تر است، جایی كه متغیر Tuple از بلوك بیرونی در بند WHERE در بلوك درونی ظاهر می‌شود.  1802- الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو:  RDBMS شامل الگاریتم‌هایی برای اجرای انواع مختلف عملیاتهای رابطه‌‌ای است كه می‌توانند در استراتژی اجرای پرس و جو نمایان شوند، این عملیات‌ها شامل عملیاتهای جبری بیسیك (اصلی) و توسعه یافته مورد بحث در فصل 7 ، و در بسیاری موارد، الحاقاتی از این عملیات‌ها می‌باشد. برای هر یك از این عملیات ها یا الحاقی از عملیات‌ها، یك یا چند الگاریتم برای اجرای عملیات‌ها در دسترس قرار دارند. الگاریتم ممكن است فقط برای ساختارهای ذخیره خاص مسیرهای دستیابی بكار روند، در اینصورت ،‌ تنها در صورتی استفاده می‌شود كه فایل های موجود در عملیات شامل این مسیرهای دستیابی هستند. در این بخش، ما به الگاریتم‌های نمونه بكار رفته برای اجرای SEKECT ، JOIN و دیگر عملیاتهای رابطه‌ای می‌پردازیم. ما بحث مرتب كردن خارجی را در بخش 180201 آغاز می‌كنیم كه در قلب عملیاتهای رابطه‌ای قرار دارد كه از استراتژیهای ادغام كردن به مرتب كردن استفاده می‌كند. بعد ما به الگاریتم‌هایی برای اجرای عملیات SELECT در بخش 180202 می‌پردازیم،‌ به عملیات ‌JOIN در بخش 180203 و عملیات PRIJECT و عملیاتهای مجموعه در بخش IE 1802 و عملیات‌های گروهی و جمعی در بخش 2 .2 . 18 می‌پردازیم.  1. 2. 18- مرتب كردن خارجی:  مرتب كردن، یكی از الگاریتم‌های اولیه بكار رفته در پردازش پرس و جو است. برای مثال، ‌به هر وقت پرس و جوی SQL ، بعد ORDER BY را تعیین می‌كند، نتیجه پرس و جو باید مرتب گردد. مرتب كردن، مؤلفه كلیدی در الگاریتم‌های مرتب كردن- ادغام كردن (مرتب-ادغام) بكار رفته برای Join و عملیاتهای دیگر، دور الگاریتم‌های حذف كپی برای عملیات PROYECT است. ما روی بعضی از این الگاریتم‌ها در بخش‌ 3. 2. 18 و 4. 02 18 بحث خواهیم كرد. توجه كنید كه مرتب كردن در صورتی كه اجتناب می‌شود كه شاخص مناسب برای امكان دسترسی مرتب شده به ثبت‌ها وجود دارد.  مرتب كردن خارجی به الگاریتم‌های مرتب كردن اشاره می‌كند كه برای فایل های بزرگ ثبت ‌های ذخیره شده روی دیسك مناسب هستند كه در حافظه اصلی، مثل اكثر فایل های پایگاه اطلاعاتی تناسب نمی‌‌یابد. الگاریتم‌ مرتب كردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌كند، كه با مرتب كردن- فایل‌های فرعی كوچك بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام می‌شوند،‌‍ فایل‌های فرعی مرتب شده بزرگتری ایجاد می‌شوند كه بترتیب ادغام می‌شوند. الگاریتم ادغام –مرتب،‌ مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد،‌ جایی كه مرتب كردن واقعی و ادغام اجراها انجام می‌ شود. الگاریتم اصلی (سیبك) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب كردن و (2) مرحله ادغام. در مرحله مرتب كردن، اجراهای فایلی كه می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده می‌شوند و با استفاده از الگاریتم مرتب كردن داخلی مرتب می‌شود عقب دیسك بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود. اندازه اجرا و تعداد اجراهای آغازین   توسط تعداد بلوكهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود. برای مثال اگر   بلوكو اندازه قایل 1024=b  بلوك باشد،‌ بعد   یا 205 اجرای آغازین در هر اندازه 5 بلوك  است. از اینرو، بعد از مرحله مرتب كردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسك ذخیره می‌شوند. اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسك ذخیره می‌شوند.  در مرحله ادغام شدن، اجراهای مرتب شده،‌ در طول یك یا چند گذر ادغام می‌‌شوند. درجه ادغام شدن   تعداد اجراهایی است كه می‌توانند با همدیگر در هر گذر ادغام شوند. در هر گذر، یك بلوك بافر، برای حفظ یك بلوك از هر اجرای ادغام شده نیاز می‌باشد، و یك بلوك برای تشكیل یك بلوك نتیجه ادغام لازم است . از اینرو،‌  كوچكتر از   و   است و تعداد گذرها،   است. در مثالها،   است. لذا،‌ 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: كه بعد به 12، بعد 4 بعد یك اجرا ادغام می‌شوند، كه بدین معنی است كه چهارگذر لازم می‌باشد. حداقل   از 2،‌ عملكرد بدترین مورد الگاریتم را ارائه می‌دهد كه بدین قرار است:    اولین جمله، تعداد دسترسی‌های بلوك برای مرحله مرتب سازی را نشان می‌دهد، چون هر بلوك فایل دو برابر دسترسی می‌شود، یكبار برای خواندن در حافظه،‌ یكبار برای نوشتن ثبت‌ها دیسك بعد از مرتب كردن. دومین جمله، تعداد دسترسی‌های بلوك برای مرحله ادغام كردن را نشان می‌دهد، با فرض اینكه بدترین مورد   از 2 وجود دارد. بطور كلی، ثبت وقایع در مبنای   و عبارت برای تعداد دسترسی‌های بلوك نوین قرار می‌شود:    تصویر 1802- شرح الگاریتم ادغام – مرتب كردن برای مرتب كردن خارجی:  2. 2. 18- اجرا و پیاده‌سازی عملیات SELECT :  تعداد Option‌هایی ( انتخاب‌ها) برای اجرای عملیات SELECT وجود دارد، كه بعضی به فایل دارای مسیرهای دستیابی خاص بستگی دارند و تنها برای انواع معین شرایط انتخاب بكار می‌رود. ما به الگاریتم‌هایی جهت اجرای SELECT در این بخش می‌پردازیم. ما از عملیاتهای زیر استفاده می‌كنیم كه روی پایگاه اطلاعاتی رابطه‌ای در تصویر 507 مشخص شده و بحث ما را روشن می‌سازد:     متدهای جستجو برای انتخاب ساده:  تعدادی الگاریتم های جستجو برای انتخاب ثبت‌ها از فایل امكان‌پذیر می‌باشند،‌ چون ثبت‌‌های فایل نامیده می شوند، چون ثبت‌‌های فایل را برای جستجو و بازیابی ثبت‌هایی كه شرایط انتخاب را برآورده می‌سازند، پویش می‌كنند. اگر الگاریتم جستجو شامل كاربرد شاخص باشد،‌ جستحوی شاخص پویش شاخص نامیده می‌شد. متدهای جستجوی زیر ( 1S تا s6 ) مثالهایی از الگاریتم‌های جستجو هستند كه می‌توانند برای اجرای عملیات انتخاب بكار روند:  - s1 : جستجوی خطی (روش برنامه‌سازی پر قدرت): بازیابی هر ثبت در فایل، و تست اینكه آیا مقادیر ویژگی آن،‌ شرط انتخاب را براورده می‌سازد یا خیر.  - S2: جستجوی بنیادی (دودویی):‌ اگر شرط انخاب شامل قیاس تساوی روی ویژگی كلیدی باشد كه روی آن فایل مرتب می‌شود، جستجوی بنیادی، كه نسبت به جستجوی خطی كارآمدتر است، می‌تواند بكار رود. مثال OP1 است چنانچه ssn ، ‌ویژگی كلیدی با شاخص اولیه‌( یا كلید hash) باشد،‌ برای مثال، SNN-‘123456789’ در opt، شاخص اولیه یا كلید hosh) برای بازیابی ثبت استفاده می‌شود، توجه كنید كه این شرط، ثبت تكی را بازیابی می‌كند.  - S4: كاربرد شاخص اولیه برای بازیابی ثبت‌های متعدد: اگر شرط انتخاب شدن قیاس تساوی روی ویژگی غیر كلیدی با شاخص خدشه‌سازی باشد،‌ برای مثال    در  ، شاخص را برای بازیابی كل ثبت‌ها در برآورده ساختن شرط،‌ استفاده كنید.  - S6: بكارگیری  شاخص ثانویه (درخت   ) روی قیاس تساوی: این متد جستجو می‌تواند برای بازیابی ثبت تكی بكار رود چنانچه فیلد نمایه‌سازی (شاخص‌سازی) كلید باشد یا برای بازیابی ثبت‌های متعدد بكار می‌رود چنانچه فیلد شاخص‌سازی كلید نباشد،‌ این می‌تواند برای مقایساتی شامل  یا   بكار رود. در بخش 3. 4. 18، ما به چگونگی توسعه فرمول‌هایی می‌پردازیم كه هزینه‌دستیابی این متدهای جستجو را در اصطلاحات تعداد دستیابی‌های بلوك و زمان دستیابی برآورد می‌كند. Method S!برای هر فایلی استفاده می‌شود ولی تمام متدهای دیگر به داشتن مسیر دستیابی مناسب روی ویژگی‌بكار رفته در شرط انتخاب بستگی دارند. متدهای S4  و 6،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بكار روند برای مثال    پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند. متدهای جستجو برای  انتخاب پیچیده:  اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشكیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده كند:  S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متكی در شرط تقارنی، مسیر دستیابی داشته باشد كه به كاربرد یكی از متدهای S2 تا S6 امكان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده كنید و بعد كنترل كنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌كند یا خیر.  S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مركب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مركب در فیلدهای مركب وجود داشته باشد، برای مثال اگر شاخص روی كلید مركب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره كرد.

در این تحقیق ما به تكنیك‌های بكار رفته توسط DMBS برای پردازش، بهینه‌سازی و اجرای پرس و جوهای سطح بالا می‌پردازیم.  پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه . معتبر شود. پویشگر (اسكنر) علامت هر زبان، مثل لغات كلیدی SQL، اساس ویژگی، و اساس رابطه، را در متن پرس و جو شناسایی می‌كند،‌ در عوض تجربه كننده، ساختار دستوری پرس و جو را برای تعیین اینكه آیا بر طبق قوانین دستوری زبان پرس و جو تدوین می‌شود یا خیر، چك می‌كند. پرس و جو باید همچنین معتبر شود، با چك كردن اینكه تمام اسامی رابطه و ویژگی معتبر هستند و اسامی معنی‌دار در طرح پایگاه اطلاعاتی ویژها‌ی پرس و جو می‌شوند. نمونه داخلی پرس و جو ایجاد می‌شود،‌‌ كه تحت عنوان ساختار داده‌های درختی بنام درخت پرس و جو می‌باشد. ارائه پرس و جو با استفاده از ساختار داده‌های گراف بنام گراف پرس و جو نیز امكان پذیر است. DOMS باید استراتژی اجرایی برای بازیابی نتیجه پرس و جو از فایل‌های پایگاه اطلاعاتی را هدایت كند. پرس و جو استراتژیهای اجرایی بسیاری دارد. و مرحلة انتخاب،‌ مورد مناسبی برای پردازش پرس وجو تحت عنوان بهینه‌سازی پرس و جو شناخته شده است.  تصویر 1، مراحل مختلف پردازش پرس و جوی سطح بالا را نشان می‌دهد. قطعه بر نامه بهینه‌ساز پرس وجو، وظیفه ایجاد طرح اجرایی را بعهده دارد و ژنراتور (تولید كننده) كه ، كد را برای اجرای آن طرح ایجاد می‌كند. پردازنده پایگاه اطلاعاتی زمان اجرا وظیفه اجرای كه پرس و جو را بعهده دارد،‌ خواه در وضعیت كامپایل شده یا تفسیر شده جهت ایجاد نتیجه پرس و جو. اگر خطای زمان اجرا نتیجه شود،‌ پیام خطا توسط پایگاه اطلاعاتی زمان اجرا ایجاد می‌شود. 
اصطلاح بهینه‌سازی نام بی مسمایی است چون در بعضی موارد،‌ طرح اجرایی انتخاب شده، استراتژی بهینه نمی‌باشد، آن فقط استراتژی كارآمد معقول برای اجرای پرس و جو است. یافتن استراتژی بهینه، ضامن صرف زمان زیادی است، بجز برای ساده‌ترین پرس و جوها،‌ ممكن است به اطلاعاتی روی چگونگی اجرای فایل‌ها در فهرست‌های فایل‌ها، اطلاعاتی كه ممكن است كاملاً در كاتالوگ DBMS در دسترس نباشد، نیاز باشد. از اینرو،‌ برنامه‌ریزی استراتژی اجرا ممكن است توصیف درست‌تری نسبت به بهینه‌سازی پرس و جو باشد. برای زبانهای پایگاه اطلاعاتی (دریایی) جهت‌یابی در سطح پایینتر در سیستم‌های قانونی، مثل شبكه DML شبكه‌ای یا MOML سلسله مراتبی،‌ برنامه نویس باید، استراتی اجرای پذیرش و جو را انتخاب كند ضمن اینكه برنامه پایگاه اطلاعاتی را می‌نویسد. اگر DBMS فقط زیان جهت‌یابی را ارائه دهد. فرصت و نیاز محدودی برای بهینه‌سازی پرس وجوی وسیع توسط DBMS وجود دارد، در عوض به برنامه نویس قابلیت انتخاب استراتژی اجرایی بهینه ارائه می‌شود. بعبارت دیگر، زبان پرس و جو در سطح بالا، مثل SQL  برای DBMSهای رابطه‌ای یا OQL برای DBMS‌های مقصد،‌ در ماهیت تفریطی‌تر است. چون آنچه نتایج مورد نظر پرس و جو است بغیر از شناسایی جزئیات چگونگی بدست آمدن نتیجه،‌ را تعیین می‌كند. بهینه‌سازی پرس و جو برای پرس و جوهایی ضروی است كه در زبان پرس و جوی سطح بالا تعیین می شوند. ما روی توصیف بهینه‌سازی پرس و جو در زمینه ROBMS تمركز می‌كنیم چون بسیاری از تكنیك‌هایی كه توصیف می‌ كنیم برای، برای ODBMSها تطبیق یافته‌اند. DBMS رابطه‌ای باید استراتژیهای اجرای پرس و جوی دیگری را ارزیابی كند و استراتژی بهینه یا كارآمد معقولی را انتخاب كند. هر DBMS ،‌ تعدادی الگاریتم دسترسی به پایگاه اطلاعاتی كلی دارد كه علامتهای رابطه‌ای مثل SELECT یا JOIN یا تركیبی از این عملیات ‌ها را اجرا می‌كند. تنها استراتژیهای اجرایی كه می‌توانند توسط الگاریتم‌های دسترسی DBMS اجرا شوند و برای طراحی پایگاه اطلاعاتی فیزیكی ویژه و پرس و جوی خاص بكار روند،‌ می‌توانند توسط قطعه برنامه بهینه‌سازی پرس و جو در نظر گرفته شوند. ما با بحث كلی چگونگی ترجمه پرس و جوهای SQL به پرس و جوهای جبری رابطه‌ای و در بهینه‌شدن آنها كار را شروع می‌كنیم. بعد ما روی الگاریتم‌ها برای اجرای عملیات‌های رابطه‌ای در بخش 1802 بحث می‌كنیم. بدنبال این مطلب، بررسی از استراتژیهای بهینه‌سازی پرس و جو را ارائه می‌دهیم. دو تكنیك اصلی برای اجرای بهینه‌‌سازی پرس و جو وجود دارد. اولین تكنیك بر اساس قوانین ذهنی جهت ترتیب دادن عملیات‌ها در استراتژی اجرای پرس و جو می‌باشد. ذهن قانونی است كه بخوبی در اكثر موارد عمل می‌كند ولی برای كار مناسب در هر مورد كنش تضمین نمی‌شود. قوانین عملیات‌ها را در درخت پرس وجو مجدداً ترتیب می‌دهند. دومین تكنیك شامل برآورد هزینه استراتژیهای اجرای متفاوت و انتخاب طرح اجرایی با پایین‌ترین هزینه برآورد است. دو تكنیك معمولاً در بهینه ساز پرس و جو (باهم تركیب می‌شوند) بهم ملحق می‌گردند. بررسی مختصری از عوامل در نظر گرفته شده در طول بهینه‌سازی پرس و جو در RDBMS بازرگانی ORACLL= را ارائه می‌دهیم. در بخش بعدی نوعی بهینه‌سازی پرس و جوی معنایی را ارائه می‌دهد كه در آن محدودیت‌های شناخته شده برای پرداختن به استراتژیهای اجرایی پرس و جوی كارآمد استفاده می‌شوند. 2 – ترجمه پرس و جوهای SQL به پرس و جوهای رابطه‌ای: در عمل، SQL زبان پرس وجویی است كه در اكثر RDBMS ‌های بازرگانی استفاده می‌شود. پرس وجوی SQL ، ابتدا به عبارت جبری رابطه‌ای توسعه یافته معادل،‌ نمایانگر ساختار داروهای درخت پرس و جو، ترجمه می‌شود و بعد بهینه‌سازی می‌شود. پرس و جوهای SQL به بلوكهای پرس و جو تجزیه می‌شوند،‌ كه واحدهای اساسی را تشكیل می‌دهند كه می‌توانند به عملكردهای جبری ترجمه شوند و بهینه‌سازی شوند. بلوك پرس و جو شامل عبارت SELECT- FROM-WHERE تكی و بندهای Groop By و HAVING است چنانچه این‌ها بخشی از بلوك باشند. از اینرو،‌ پرس و جوهای تو در تو در پرس و جو بعنوان بلوكهای پرس و جوی مجزا شناسایی می‌شوند. چون SQL شامل عملكردهای گروهی، مثل MAX ،‌ COUNT,SUM می‌باشد، این عملگرها باید در پرس و جوی جبری توسعه یافته‌ای شامل شوند، همانطوریكه در بخش 705 توصیف شد. پرس و جوی SQL در رابطه EMPLOEE در تصویر 705 را در نظر بگیرید: این پرس و جو شامل، پرس و جوی فرعی تو در تو است و از اینرو به دو بلوك تجزیه می‌شود. بلوك درونی بدین صورت است: و بلوك بیرونی بدین صورت می باشد: كه C نمایانگر نتیجه حاصله از بلوك درونی است. بلوك درونی به عبارت جبری رابطه‌ای توسعه یافته زیر ترجمه شده است: و بلوك بیرونی به عبارت زیر  ترجمه شده است: بهینه‌ساز پرس و جو، طرح اجرایی را برای هر بلوك انتخاب می‌كند. ما باید اشاره كنیم به در مثال فوق، بلوك درونی نیاز به ارزیابی شدن دارد تنها زمانی كه، حداكثرحقوقی كه بعكار می‌رود كه بعنوان ثابت C، توسط بلوك بیرونی استفاده می‌شود. ما اینرو پرس و جوی تودرتوی غیرمرتبط نامیدیم (در فصل 8). آن برای بهینه‌سازی پرس و جوهای تو در توی مرتبط پیچیده‌تر، خیلی سخت‌تر است، جایی كه متغیر Tuple از بلوك بیرونی در بند WHERE در بلوك درونی ظاهر می‌شود. 1802- الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو: RDBMS شامل الگاریتم‌هایی برای اجرای انواع مختلف عملیاتهای رابطه‌‌ای است كه می‌توانند در استراتژی اجرای پرس و جو نمایان شوند، این عملیات‌ها شامل عملیاتهای جبری بیسیك (اصلی) و توسعه یافته مورد بحث در فصل 7 ، و در بسیاری موارد، الحاقاتی از این عملیات‌ها می‌باشد. برای هر یك از این عملیات ها یا الحاقی از عملیات‌ها، یك یا چند الگاریتم برای اجرای عملیات‌ها در دسترس قرار دارند. الگاریتم ممكن است فقط برای ساختارهای ذخیره خاص مسیرهای دستیابی بكار روند، در اینصورت ،‌ تنها در صورتی استفاده می‌شود كه فایل های موجود در عملیات شامل این مسیرهای دستیابی هستند. در این بخش، ما به الگاریتم‌های نمونه بكار رفته برای اجرای SEKECT ، JOIN و دیگر عملیاتهای رابطه‌ای می‌پردازیم. ما بحث مرتب كردن خارجی را در بخش 180201 آغاز می‌كنیم كه در قلب عملیاتهای رابطه‌ای قرار دارد كه از استراتژیهای ادغام كردن به مرتب كردن استفاده می‌كند. بعد ما به الگاریتم‌هایی برای اجرای عملیات SELECT در بخش 180202 می‌پردازیم،‌ به عملیات ‌JOIN در بخش 180203 و عملیات PRIJECT و عملیاتهای مجموعه در بخش IE 1802 و عملیات‌های گروهی و جمعی در بخش 2 .2 . 18 می‌پردازیم. 1. 2. 18- مرتب كردن خارجی: مرتب كردن، یكی از الگاریتم‌های اولیه بكار رفته در پردازش پرس و جو است. برای مثال، ‌به هر وقت پرس و جوی SQL ، بعد ORDER BY را تعیین می‌كند، نتیجه پرس و جو باید مرتب گردد. مرتب كردن، مؤلفه كلیدی در الگاریتم‌های مرتب كردن- ادغام كردن (مرتب-ادغام) بكار رفته برای Join و عملیاتهای دیگر، دور الگاریتم‌های حذف كپی برای عملیات PROYECT است. ما روی بعضی از این الگاریتم‌ها در بخش‌ 3. 2. 18 و 4. 02 18 بحث خواهیم كرد. توجه كنید كه مرتب كردن در صورتی كه اجتناب می‌شود كه شاخص مناسب برای امكان دسترسی مرتب شده به ثبت‌ها وجود دارد. مرتب كردن خارجی به الگاریتم‌های مرتب كردن اشاره می‌كند كه برای فایل های بزرگ ثبت ‌های ذخیره شده روی دیسك مناسب هستند كه در حافظه اصلی، مثل اكثر فایل های پایگاه اطلاعاتی تناسب نمی‌‌یابد. الگاریتم‌ مرتب كردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌كند، كه با مرتب كردن- فایل‌های فرعی كوچك بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام می‌شوند،‌‍ فایل‌های فرعی مرتب شده بزرگتری ایجاد می‌شوند كه بترتیب ادغام می‌شوند. الگاریتم ادغام –مرتب،‌ مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد،‌ جایی كه مرتب كردن واقعی و ادغام اجراها انجام می‌ شود. الگاریتم اصلی (سیبك) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب كردن و (2) مرحله ادغام.در مرحله مرتب كردن، اجراهای فایلی كه می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده می‌شوند و با استفاده از الگاریتم مرتب كردن داخلی مرتب می‌شود عقب دیسك بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود. اندازه اجرا و تعداد اجراهای آغازین   توسط تعداد بلوكهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود. برای مثال اگر   بلوكو اندازه قایل 1024=b  بلوك باشد،‌ بعد   یا 205 اجرای آغازین در هر اندازه 5 بلوك  است. از اینرو، بعد از مرحله مرتب كردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسك ذخیره می‌شوند. اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسك ذخیره می‌شوند. در مرحله ادغام شدن، اجراهای مرتب شده،‌ در طول یك یا چند گذر ادغام می‌‌شوند. درجه ادغام شدن   تعداد اجراهایی است كه می‌توانند با همدیگر در هر گذر ادغام شوند. در هر گذر، یك بلوك بافر، برای حفظ یك بلوك از هر اجرای ادغام شده نیاز می‌باشد، و یك بلوك برای تشكیل یك بلوك نتیجه ادغام لازم است . از اینرو،‌  كوچكتر از   و   است و تعداد گذرها،   است. در مثالها،   است. لذا،‌ 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: كه بعد به 12، بعد 4 بعد یك اجرا ادغام می‌شوند، كه بدین معنی است كه چهارگذر لازم می‌باشد. حداقل   از 2،‌ عملكرد بدترین مورد الگاریتم را ارائه می‌دهد كه بدین قرار است:  اولین جمله، تعداد دسترسی‌های بلوك برای مرحله مرتب سازی را نشان می‌دهد، چون هر بلوك فایل دو برابر دسترسی می‌شود، یكبار برای خواندن در حافظه،‌ یكبار برای نوشتن ثبت‌ها دیسك بعد از مرتب كردن. دومین جمله، تعداد دسترسی‌های بلوك برای مرحله ادغام كردن را نشان می‌دهد، با فرض اینكه بدترین مورد   از 2 وجود دارد. بطور كلی، ثبت وقایع در مبنای   و عبارت برای تعداد دسترسی‌های بلوك نوین قرار می‌شود:  تصویر 1802- شرح الگاریتم ادغام – مرتب كردن برای مرتب كردن خارجی: 2. 2. 18- اجرا و پیاده‌سازی عملیات SELECT : تعداد Option‌هایی ( انتخاب‌ها) برای اجرای عملیات SELECT وجود دارد، كه بعضی به فایل دارای مسیرهای دستیابی خاص بستگی دارند و تنها برای انواع معین شرایط انتخاب بكار می‌رود. ما به الگاریتم‌هایی جهت اجرای SELECT در این بخش می‌پردازیم. ما از عملیاتهای زیر استفاده می‌كنیم كه روی پایگاه اطلاعاتی رابطه‌ای در تصویر 507 مشخص شده و بحث ما را روشن می‌سازد:   متدهای جستجو برای انتخاب ساده: تعدادی الگاریتم های جستجو برای انتخاب ثبت‌ها از فایل امكان‌پذیر می‌باشند،‌ چون ثبت‌‌های فایل نامیده می شوند، چون ثبت‌‌های فایل را برای جستجو و بازیابی ثبت‌هایی كه شرایط انتخاب را برآورده می‌سازند، پویش می‌كنند. اگر الگاریتم جستجو شامل كاربرد شاخص باشد،‌ جستحوی شاخص پویش شاخص نامیده می‌شد. متدهای جستجوی زیر ( 1S تا s6 ) مثالهایی از الگاریتم‌های جستجو هستند كه می‌توانند برای اجرای عملیات انتخاب بكار روند: - s1 : جستجوی خطی (روش برنامه‌سازی پر قدرت): بازیابی هر ثبت در فایل، و تست اینكه آیا مقادیر ویژگی آن،‌ شرط انتخاب را براورده می‌سازد یا خیر. - S2: جستجوی بنیادی (دودویی):‌ اگر شرط انخاب شامل قیاس تساوی روی ویژگی كلیدی باشد كه روی آن فایل مرتب می‌شود، جستجوی بنیادی، كه نسبت به جستجوی خطی كارآمدتر است، می‌تواند بكار رود. مثال OP1 است چنانچه ssn ، ‌ویژگی كلیدی با شاخص اولیه‌( یا كلید hash) باشد،‌ برای مثال، SNN-‘123456789’ در opt، شاخص اولیه یا كلید hosh) برای بازیابی ثبت استفاده می‌شود، توجه كنید كه این شرط، ثبت تكی را بازیابی می‌كند. - S4: كاربرد شاخص اولیه برای بازیابی ثبت‌های متعدد: اگر شرط انتخاب شدن قیاس تساوی روی ویژگی غیر كلیدی با شاخص خدشه‌سازی باشد،‌ برای مثال    در  ، شاخص را برای بازیابی كل ثبت‌ها در برآورده ساختن شرط،‌ استفاده كنید. - S6: بكارگیری  شاخص ثانویه (درخت   ) روی قیاس تساوی: این متد جستجو می‌تواند برای بازیابی ثبت تكی بكار رود چنانچه فیلد نمایه‌سازی (شاخص‌سازی) كلید باشد یا برای بازیابی ثبت‌های متعدد بكار می‌رود چنانچه فیلد شاخص‌سازی كلید نباشد،‌ این می‌تواند برای مقایساتی شامل  یا   بكار رود. در بخش 3. 4. 18، ما به چگونگی توسعه فرمول‌هایی می‌پردازیم كه هزینه‌دستیابی این متدهای جستجو را در اصطلاحات تعداد دستیابی‌های بلوك و زمان دستیابی برآورد می‌كند. Method S!برای هر فایلی استفاده می‌شود ولی تمام متدهای دیگر به داشتن مسیر دستیابی مناسب روی ویژگی‌بكار رفته در شرط انتخاب بستگی دارند. متدهای S4  و 6،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بكار روند برای مثال    پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند.متدهای جستجو برای  انتخاب پیچیده: اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشكیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده كند: S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متكی در شرط تقارنی، مسیر دستیابی داشته باشد كه به كاربرد یكی از متدهای S2 تا S6 امكان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده كنید و بعد كنترل كنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌كند یا خیر. S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مركب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مركب در فیلدهای مركب وجود داشته باشد، برای مثال اگر شاخص روی كلید مركب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره كرد.

 

کامپیوتر