ما از 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 )، اگر چه در همه آنها به کار نمی رود.
بیشتر