ترتیب پیوندها

[Hamid.Kad]

سلام. وقتی که میخوایم توی کوئری چند تا join داشته باشیم بهتره که ترتیب اونا جوری باشه که یک ترتیب کوچیک به بزرگ رو مرتب کنیم و اگه خود DBMS بخواد اینکارو انجام بده نیاز به دونستن بعضی اطلاعات مثل تخمینی از درصد بازیابی در پیوندها و ... دارد و اگه اینها رو بدونه میشه با یک الگوریتم Sort ساده (یا حداقل با دوتا حلقه تودرتو) این کارو انجام بده. درصورتیکه در مقالات عنوان میشه که این مساله NP-Complete هست و حداقل زمانی که براش پیدا شده با استفاده از الگوریتم پویا از مرتبه 2^N هستش. من فکر میکنم یا صورت مساله رو اشتباه متوجه شدم!!! یا راه حلی که ارائه میدم اشتباهه. دوستان لطفاً کمک کنید که بدجور گیر استاد افتادم

[AminSobati]

دوست عزیزم،
در Inner Join برای SQL Server تفاوتی نمیکنه که شما چه ترتیبی رعایت کنید چون خودش بهترین روش رو انتخاب میکنه. در Outer Join باز هم از نظر Performance مهم نیست که چه ترتیبی رعایت کنید، اما از نظر درست بودن خود Query که به جواب برسید طبیعتا رعایت ترتیب منطقی مهمه.

[Hamid.Kad]

با تشکر از جناب ثباتی
راستش هدف من حل کردن این مساله به کمک روشهای اکتشافی مثل کلونی مورچه هاست که برای اینجور مسائل (NP-Complete) بسیار مناسبند. یعنی میخوام بدونم پایگاه داده چجوری همچین کاری انجام میده و چرا زمانی بهتر از مرتبه نمایی براش بدست نیومده. (در حقیقت چرا راه حل من اشتباهه؟) شاید طرح این مساله توی این فروم چندان مناسب نبود. ولی امیدوارم توی فهم صورت مساله کمکم کنید

[AminSobati]

هدف اصلی سوال شما برای من کمی مبهمه اما به هر حال این توضیح رو میدم شاید به هدف بخوره!
بخشی از نرم افزار مدیریت بانک اطلاعاتی که تحلیل Query رو بعهده داره Query Processor (یا QP) نامیده میشه. QPها معمولا از دو خط مشی استفاده میکنند تا اجرای Query بهینه بشه. یکی اصطلاحا Cost-Based و دیگری Rule-Based. پس از گذشت سالها عملا در دنیای واقعی کار و خارج از لابراتوارهای تست، این نتیجه حاصل شد که Cost-Based Optimizer از کارآیی بهتری برخورداره. SQL Server روش Cost-Based استفاده میکنه. Oracle از هر دو پشتیبانی میکرد اما تا جایی که اطلاع دارم روی Rule-Based دیگه سرمایه گذاری نکرد و به خاطر کارآیی، روش Cost-Based رو جلو برد.
SQL Server در عملکرد خودش، از what if scenario استفاده میکنه و با توجه به چیزهایی که بهش آموختن، Planهای مختلفی رو از نظر Cost تخمین میزنه. در حین بررسی یک Query، از مراحل مختلفی عبور میکنه. اولیش Trivial Plan هست. اگر در این مرحله بدست بیاره که با ساده ترین Plan میتونه Query رو در کمتر از سه دهم ثانیه انجام بده (مثلا به کمک Table Scan)، دیگه وقتش رو برای تحلیل بیشتر تلف نمیکنه و میره سراغ اجرا. در غیر این صورت وارد اولین مرحله Optimization میشه. اگر Planهای بدست اومده کارآیی داشته باشه، بهترینش رو انتخاب میکنه و اجرا شروع میشه اگر نه، مرحله جدیدی از Optimization شروع میشه که در اون پارالل کردن Query بین Processorها رو دربر میگیره. اساسا به خاطر هزینه داشتن این تحلیل ها هستش که Plan بدست اومده Cache میشه و در دفعات بعدی اجرا، Compile و همچنین Optimization انجام نمیشه.

[Hamid.Kad]

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