دانلود با لینک مستقیم و پر سرعت .
مقدمه
در اواسط دهه 1980، با نزول قیمت DRAM، این ایده مطرح شد که کامپیوترهای آتی با داشتن حافظه اصلی با ظرفیت بالا، می توانند بسیاری از پایگاه داده ها را درحافظه اصلی داشته باشند. در این شرایط می توان همه I/O ها (که بسیار هزینه بر می باشند) را از پردازش DBMS حذف نمود. بنابراین معماری DBMS دستخوش تغییرات جدی می شود و در یک MAIN MEMORY DBMS(MMDBMS)، مدیریت I/O دیگر نقشی نخواهد داشت.
نکته مهم در یک MMDB، چگونگی انجام تراکنشها و recovery بصورت کارا است. برخی از الگوریتمهای پیشنهادی براساس این فرض عمل می کنند که قسمت کوچکی از حافظه اصلی بصورت ماندگار وجود دارد که اطلاعاتش توسط باطری در صورت قطع برق از بین نخواهد رفت. این قسمت از حافظه اصلی برای نگهداری redo log ها استفاده می شود.
تعداد دیگری از الگوریتمهای پیشنهادی پیش فرض حافظه ماندگار را ندارند و همچنان از عملیات I/O برای نوشتن اطلاعات تراکنش در حافظه ماندگار استفاده می کنند. بنابراین در این الگوریتمها عملیات I/O بطور کامل حذف نمی شود، بلکه تعدادشان بسیار کمتر می شود زیرا I/Oمربوط به نوشتن اطلاعات صفحات buffer ها، حذف خواهد شد.
در یک MMDBMS، ساختارداده های ساده مانند T-Tree و همچنین bucket-chained hash جایگزین ساختارداده هایی چون B-Tree و linear hash در DBMS های مبتنی بر دیسک می شوند. بنابراین سرعت اجرای پرس و جو(پرس و جو) و بهنگام سازی بسیار افزایش می یابد و هزینه index lookup و نگهداری ،فقط مربوط به پردازنده و دسترسی به حافظه اصلی خواهد شد.
یکی از مشکلات اصلی در MMDBMS ها بهینه کردن درخواستهاست. عدم وجود I/O به عنوان فاکتور اصلی در هزینه ها به معنای پیچیدگی بیشتر مدل کردن هزینه در یک MMDBMS است زیرا در اینجا یکسری فاکتورهای فازی از قبیل هزینه اجرای پردازنده ، باید در نظر گرفته شوند. در این حالت باید با استفاده از تعامل روش coding، عوامل سخت افزاری مانند پردازنده و معماری حافظه و پارامترهای پرس و جو، به یک مدل قابل اطمینان از هزینه اجرا در حافظه اصلی رسید.
در دهه 1990، MMDBMS ها با افزایش سایز دیسکها و سایز مسائل همراه با افزایش ظرفیت DRAM ها، به اوج محبوبیت خود رسیدند. MMDBMS ها اغلب برای برنامه هایی که به پایگاه داده Real Time نیاز دارند (مانند سیستمهای embedded سوئیجهای تلفن) ، استفاده می شود. از آنجایط که سایز حافظه اصلی در کامپیوترها روز به روز در حال افزایش است، این امید وجود دارد که برای بسیاری از پایگاه داده هایی که امروزه امکان قرارگفتن آنها بصورت کامل در حافظه اصلی وجود ندارد، این شرایط مهیا شود.
مدلهای هزینه حافظه اصلی
متاسفانه تا کنون تلاشهای اندکی جهت مدل کردن هزینه کارایی MMDBMSها صورت گرفته است. تحقیقات اولیه روی طراحی ماشینهای پایگاه داده ها، بیشتر در زمینه وابستگیهای میان الگوریتمها و دسترسی حافظه صورت می گرفت.در صورتیکه امروزه به دلیل محدود شدن استفاده از MMDBMS ها به کاربرد در پایگاه داده های Real Time(به صورت پرس وجوهای ساده، مانند یک hash lookup در یک جدول)، اینگونه تحقیقات از اهمیت کمتری برخوردارند.
در تحقیقات اخیر در زمینه MMDBMS ها دو نمونه تحقیقاتی Office-By-Example (OBE) مربوط به شرکت IBM و Smallbase مربوط به شرکت HP مسائل ارزشمندی را درمورد بهینه سازی پرس وجو ها و مدلسازی هزینه حافظه اصلی مطرح کرده اند که در ادامه به بررسی این دو نمونه می پردازیم.
Office-By-Example (OBE)
OBE یک پایگاه داده در حافظه اصلی است که بسیاری از مفاهیمQuery-by-example(QBE)، را گسترش می دهد. برای بهینه سازی پرس و جو، مبتنی بر هزینه، OBE یک مدل کامل از هزینه را ارائه می دهد. باتوجه به این پیش فرض که داده هایی که پردازش می شوند در حافظه اصلی قرار گرفته اند، عامل اصلی هزینه در پایگاه داده های متداول که همان دسترسی I/O است حذف خواهد شد.
در این صورت هزینه محاسبات پردازنده از اهمیت بالایی برخوردار خواهد شد. این در حالیست که مدلسازی هزینه پردازنده بسیاردشوار است و پارامترهای زیادی از قبیل طراحی نرم افزار، معماری سخت افزار و حتی روش برنامه نویسی، در مدلسازی هزینه پردازنده دخیل هستند. بعلاوه تحلیل دقیق سیستمهای بزرگ به منظور شمارش تعداد سیکلهای پردازنده غیر ممکن می باشد.
راه حل پیشنهادی، استفاده از روشهای تجربی و روشهای تحلیلی در کنار یکدیگر است.
در ابتدا، bottleneck های سیستم با استفاده از یک تحلیلگرِ اجرا شناسایی می شوند. در این روش تنها bottleneck ها، برای مدلسازی هزینه پردازنده بکار می روند.
البته در این مرحله، بسیار مهم است که bottleneck ها تا حد ممکن توسط تلاشهای معقول اصلاح شوند.
مرحله بعد پیدا کردن وزن نسبی هریک از bottleneck ها و مشخص سازی واحد هزینه آنها توسط روشهای تجربی است.
برای OBE، bottleneck ها و واحدهای هزینه بصورت زیر مشخص می شوند :
• ارزیابی expression هایی که در predicate ها آمده اند. (واحد هزینه = C1)
• عملیات قیاسی که برای مشخص کردن خروجی نهایی predicate ها لازم است. (واحد هزینه = C2)
• بازیابی یک tuple از یک رابطه موجود در حافظه اصلی. (واحد هزینه = C3)
• واحد عملیاتِ ساختن شاخص (index) ( ساختن شاخص روی رابطه ای که n تا tuple دارد، nLog2n برابر واحد هزینه دارد. واحد هزینه = C4)
• واحد عملیات در مرتب سازی ،که در شرایط شاخصهای چند ستونی(multi-column index) مورد نیاز است. (واحد هزینه = C5)
جالبترین نتیجه بدست آمده از آزمایشات این است که، هزینه ارزیابی expression های سیستم، بیشترین هزینه از میان هزینه های مطرح شده در OBE می باشد.در حالیکه C2 تا C5 تقریبا یکسان می باشند، C1 به میزان قابل توجهی بیشتر از آنهامی باشد.
در ادامه به بررسی نمونه Smallbase می پردازیم.
Smallbase
در smallbase، مدل هزینه حافظه اصلی به سه گروه تقسیم می شود:
1. Hardware-based
این مدل بسیار شبیه مدل هزینه مبتنی بر I/O در پایگاه داده های متداول است. به جای شمارش عملیات I/O، تعداد سیکلهای پردازنده شمارش می شود. علیرغم اینکه این روش بسیار ساده به نظر می رسد، از جهت پیاده سازی مشکلات عمده ای وجود دارد.بعلاوه، portability بسیار محدود خواهد شد زیرا این سیاستها میان معماریهای سخت افزار، متفاوت است. در هر حال این مدل بسیار دقیق و قابل لطمینان می باشد.
2. Application-based
در این روش هزینه ها بر اساس هزینه bottleneck های سیستم بیان می شود.علیرغم اینکه این روش از جهت پیاده سازی بسیار ساده تر از روش hardware-based است، این نوع مدل از عمومیت کمتری برخوردار است.
Bottleneck ها بسیار وابسته به workload ِمورد استفاده برای شناسایی آنها، دارد و بنابراین نمی توان از این روش برای نمایش هزینه های همه انواع پرس و جو استفاده کرد.
در اصل،این مدل نسبت به مدل hardware-based از portability بالاتری (توسط تولید دوباره پروفیل) برخوردار است. به هر حال، این روش نه تنها باعث تفاوت در واحدهای هزینه می شود بلکه مجموعه bottleneck ها هم متفاوت خواهد شد.در این حالت اگر مدل، دستخوش تغییرات شود، هزینه توابعِ هزینه مربوط به عملیات پایگاه داده، باید دوباره بر اساس bottleneck های جدید فرمولسازی شود.
3. Engine-based
این مدل هزینه، مابین مدل hardware-based - که دقیق و پیچیده است- و مدل application-based -که علیرغم سادگی از عمومیت کمتری برخوردار است-، قرار دارد. این مدل بر اساس هزینه عملیات ابتدایی که موتور اجرایی MMDBMS تامین می کند، عمل می کند.
در یک پروسه دو مرحله ای این مدل توضیح داده می شود:
در این مدل عمومی ابتدا عوامل اصلی هزینه شناخته می شوند و هزینه پردازش پرس و جو بر اساس عوامل شناخته شده بیان می گردد. سپس مدل با مشخص کردن مقادیر مربوط به این عوامل، مقداردهی اولیه شده و سپس ارزیابی می شود.
مرحله اول نیاز به اطلاعات کامل در مورد اجزای داخلی موتور اجرایی دارد و عموماً توسط دست انجام می شود. در مورد اینکه مدل تا چه حد باید جزئی و دقیق باشد، این پاسخ مطرح می شود که مدل باید تا آنجایی که به feasibility سیستم خدشه ای وارد نشود، بصورت جزئی مدل شود. یکسری ساده سازیها و بهبود و دوباره نگری در طی مرحله ارزیابی قابل انجام است.
برای سیستم smallbase ، هزینه های ابتدایی زیرشناسایی شده اند :
• Fetch کردن یک ستون ویا مقدار یک پارامتر
• انجام عملیات ریاضی و منطقی
• اجرای یک عمل مقایسه
• اجرای expression ایی که like داشته باشد
• scan کردن جدول، T-tree index، hash index، جدول موقت
• ساخت و از بین بردن T-tree index، hash index، جدول موقت
• مرتب سازی tuple ها
• انتخاب tuple های مشخص
• انجام عمل join (nested loop join، merge join)
به وابستگیهای هزینه به فاکتورهایی از قبیل سایز جداول، نوع داده ها و ... در مرحله دوم پرداخته می شود.
در مرحله دوم یک برنامه تست ،وظیفه مقداردهی اولیه و ارزیابی مدل را بصورت اتوماتیک برعهده دارد. برای هر واحد هزینه دو پرس و جو که هزینه اجرایشان، فقط در آن مقدار متفاوت باشد، در نظر گرفته می شود. بعلاوه فرمولهایی که وابستگی هر واحد هزینه را به سایز جدولها نشان می دهند، باید مشخص شوند.
برنامه تست هزینه سپس پارامترهای مربوطه و ارزیابی مدل را با اجرای هر زوج پرس و جو به تعداد مکرر با سایزهای متفاوت جداول انجام می دهد.
ساختارهای شاخص در حافظه اصلی
ساختارهای شاخصِ طراحی شده برای حافظه اصلی، متفاوت از طراحی های رایج برای سیتم های مبتنی بر دیسک می باشند.اهداف اصلی در طراحی یک شاخص مبتنی بردیسک عبارتند از : به حداقل رساندن تعداد دستیابی ها به دیسک و به حداقل رساندن فضای دیسک.در حالی که یک شاخص مبتنی بر حافظه اصلی ،در حافظه اصلی قرار گرفته واصلا دستیابی به دیسک وجود ندارد که حداقل شود از این رو، هدف اصلی از طراحی یک ساختار شاخص مبتنی بر حافظه اصلی ،کاهش زمان کلی محاسبات و در عین حال ، به کار گیری حداقل حافظه ممکن می باشد.
در یک پایگاه داده مبتنی بر حافظه اصلی، رابطه ها در حافظه قرار می گیرند،بنابراین،نیازی نخواهد بود که شاخص، مقادیر واقی صفات را ذخیره کند، در عوض می توان از اشاره گر هایی به tupleها استقاده نمود و با استفاده از این اشاره گرها ، مقادیر واقعی صفات را در هنگام لازم ، بازیابی نمود.
چنین روشی جندین مزیت دارد:
با استقاده از اشاره گرِ tuple،شاخص، هم به مقادیر صفات آن tuple دسترسی دارد و هم به خود tuple ،بنابراین اندازه شاخص کاهش می یابد.
این روش ، سبب کاهش پیچیدگی در سازماندهیِ رکوردهایی با اندازه های زیاد و متغیر،و روشهای فشرده سازی در شاخص ها می شود.
با انجام عملیات بهنگام سازی،شاخص ها نیز باید بهنگام شوند، در این حالت، جابجایی اشاره گرها بسیار ارزان تر از جابحایی مقادیر صقاتِ (معمولاً) طولانی تر می باشد.
یک اشاره گر شاخص، امکان دستیابی به کلیه فیلدهای یک tuple را فراهم می سازد،بنابراین در حالتهای خاص نیز، نیاز کمتری به شاخص های چندصفتی، وجود خواهد داشت.
ساختار T-Tree ، یک ساختار درختی با حفظ ترتیب می باشد که اساساً به منظور استفاده در حافظه اصلی طراحی شده است و در ادامه به شرح آن می پردازیم.
ساختار T-Tree
این ساختار جدید، از ترکیب ساختارهای AVL و B-Tree بدست آمده است: T-Tree یک درخت باینری است با چندین عنصر در هر گره.در شکل زیر، ساختار یک T-Tree و یک گره از آن را – به نام T-Node- مشاهده می کنید. T-Treeیک درخت باینری است بنابراین خصوصیت Binary Search را از درختان AVL، به طور ذاتی به همراه دارد.همچنین، هر T-Node شامل چندین عنصر می باشد بنابراین T-Tree ، خصوصیات مثبتِ بهنگام سازی و ذخیره سازی B-Tree را به همراه دارد.جابجایی داده ها که عموماً پس از حذف و درج لازم می شود نیز، معمولا تنها در یک گره باید صورت بگیرد.Rebalancing نیز با استفاده از چرخشهایی مشابه با درختهای AVL ، انجام می شود با این تفاوت که با توجه به امکان جابحایی داده در داخل یک گره، تناوب انجام آن خیلی کمتر خواهد بود.
سه گونه متفاوت از T-Node ها وجود دارند:
Internal Node: (گره داخلی):T-Node ایی که دو زیر درخت دارد.
Half-leaf node : T-Node ایی که یک اشاره گرِ فرزند تهی و یک اشاره گرِ فرزند غیر تهی دارد.
Leaf Node :T-Node ایی که هر دو اشاره گرِ فرزند آن، تهی می باشند.
به ازای هر گره داخلیA، یک leaf (و یا half-leaf ) متناظر با آن وجود دارد که شامل مفدار داده ایی است که ،"جد "(predecessor) ِ کمترین مقدار داده در A ، محسوب می شود.همچنین، یک leaf (ویا half-leaf) ،شامل مفدار داده ایی که ،successor ِ بیشترین مقدار داده در A ، محسوب می شود،نیز وجودخواهد داشت.به predecessor، بزرگترین حد پائین A و به successor کوچکترین حد بالای A ، گفته می شود،مطابق با شکل زیر:
به ازای هر گره N و هر مفدار X ، اگر مقدار X مابین مقادیرکمترین عنصر و بیشترین عنصردرA ، قرار بگیرد، می گوئیم که A ، X را "می پوشاند". توجه کنید که داده ها در یک T-Node به صورت مرتب شده قرار می گیرند، بنابراین،سمت چپ ترین عنصر دارای کوچکترین مقدار و سمت راست ترین عنصر ، دارای بزرگترین مقدار خواهند بود.
هر T-Tree دارای یک حدِ حداقل و یک حدِ حداکثر می باشد که معمولا به میزان اندکی با هم تفاوت دارند، گره های داخلی ظرفیتشان - یعنی : تعداد مقادیرداده در هر گره - را در داخل بازه این حدود،نگه می دارند، بدین ترتیب در تلفیقی از عملیات حدف و درج،مقدار داده ایی که باید به علت سربارحاصل از درج به leafها منتقل شده و یا به علت پاریز (underflow) حاصل ازحذف ،از leafها قرض گرفته شود،کاهش یافته و نتیجتاً از چرخشهای اضافی در درخت، جلوگیری خواهد شد. داشتن چنین انعطافی در ظرفیت گره های داخلی، تا حدودی سبب حفظ تعادل میان بهبود ِ ذخیره سازی و زمانِ حذف/درج خواهد شد. گره های leaf و half-leaf نیز،ظرفیتی متغیر میان صفرو حد ِحداکثر خواهند داشت.
1. الگوریتم جستجو
جستجو در T-Tree مانند جستجو در Binary Tree صورت می گیرد با این تفاوت که به جای مقایسه با یک مقدار،مانند B-Tree، مقایسه با مقادیر حداقل وحداکثرِ آن گره صورت می گیرد.مراحل این الگوریتم عبارتند از:
1. جستجو همیشه از ریشه درخت آغاز می شود.
2. اگر مقدار مورد جستجو کمتر از کمترین مقدار در آن گره باشد،جستجو در زیر درختی ادامه خواهد یافت که اشاره گرِ فرزند چپ، به آن اشاره می کند.
3. در غیر این صورت، اگر مقدار مورد جستجو، بیشتر ازبزرگترین مقدار در آن گره باشد،جستجو در زیر درختی ادامه خواهد یافت که اشاره گرِ فرزند راست،به آن اشاره می کند.
4. در غیر این صورت، گره فعلی جستجو خواهد شد.
5. جستجو هنگامی نا موفق خواهد بود که گره ایی جستجو شود ولی داده مورد نظر در آن یافت نشود و یا هنگامی که گره ایی که مقدار ِمورد جستجو را بپوشاند، پیدا نشود.
2 . الگوریتم درج
عملیات درج با جستجو برای گره پوشاننده ،آغاز می شود، مفدار جدید در این گره درج شده و سپس درخت به منظور Rebalancing بررسی می شود.اگر توازن درخت در اثر درج (و یا حذف)، به هم خورده باشد، پروسه Rebalancing ِ مناسب، گرههایی که در مسیر ریشه تا leaf آیی که در آن حذف/ درج صورت گرفته است، را بررسی خواهد کرد. مراحل این الگوریتم عبارتند از:
1. جستجو برای یافتن گره پوشاننده
2. اگر چنین گره ایی پیدا شد و برای اضافه کردن آیتم جدید، جا داشت، مقدار جدید به این گره اضافه شده و الگوریتم متوقف می شود.در غیر این صورت،کمترین عنصر از گره بر داشته شده و مقداری که باید درج شود ، به آن اضافه شده و به عنوان کمترین عنصرقرار داده می شود.سپس به سراغ leafی که بزرگترین حدِ پائین را برای گره در بر گیرنده عنصر درج شونده، دارا می باشد، رفته و آن کمترین عنصر را که از گره پوشا برداشته بودیم ، به آن اضافه می کنیم،که از این پس به عنوان بزرگترین حد پائین برای گره پوشا، محسوب خواهد شد.
3. اگر در جستجوی درخت، چنین گره ایی پیدا نشد، مقدار درج شونده، به آخرین گره در مسیر جسنجو- که یا leaf است و یا half-leaf - اضافه خواهد شد،اگر در آن جا شود که به عنوان عنصر حداقل/حداکثر جدید برای آن گره محسوب خواهد شد،در غیر این صورت،leaf جدیدی ساخته و عنصر درج شونده به عنوان اولین عنصر ِ آن، به آن اضافه خواهد شد.
4. اگر leaf جدیدی به درخت اضافه شود، توارن درخت باید مورد بررسی قرار بگیرد بدین نحو که: در مسیر جستجو از leaf تا ریشه، هر گره بررسی شده و اگر تفاوت عمقِ دو زیر درخت آن، بیش از یک سطح بود، باید چرخش صورت بگیرد.با انجام یک چرخش، توازن درخت تصحیح شده و عملیات متوقف می شود.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 54 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
