Основни методи за достъп до данните
Изтегляне 58.11 Kb.
|
- Навигация на страницата:
- Индексен достъп (Index Scans)
- Join алгоритми
- Nested loops
- External mergesort
- Anti hash join
- Semi hash join
- Оптимизации/модификации на join алгоритъмите
- Операции по сортиране
Основни методи за достъп до даннитеПълно сканиране на релацията (Full Table Scans)Този метод за достъп чете всички кортежи на релацията като филтрира тези, който не удовлетворяват критерия за селекция. Индексен достъп (Index Scans)При този метод на достъп, за да се прочетат кортежите на една релация се използва допълнителна структура нар. „индекс”. Целта е да се избегне последователното сканиране на цялата релация и да се осъществи по-директен достъп до необходимото множество от кортежи. Пълното сканиране на релацията е по-добро от индексното, когато се интересуваме от значителна част от кортежите на релацията. В такъв случай броят на В/И операции, чрез пълно сканиране на таблицата е по-малък, отколкото при използване на индекс. Оптимизаторът използва пълно сканиране в следните ситуации:
Join алгоритмиСъществуват 3 фундаментални алгоритъма за осъществяване на операцията по свързване на 2 релации с цел получаване на общ резултат: Nested loops, Merge join и Hash join Nested loopsТова е най-простият алгоритъм за свързване. За всеки кортеж от т.нар. външната (или driving релация) се сканира цялата вътрешна релация и всички кортежи, които отговарят на условието за свързване се добавят към резултата. For each tuple in R as r do For each tuple in S as s do If r and s satisfy the join condition Then output the tuple Алгоритъмът може да се използва за всякакъв вид съединения (както с равенство, така и без равенство). Коя от двете релации ще е външна и коя вътрешна обикновено е от значение, тъй като Nested Loops се използва, когато методът на достъп до вътрешната таблица е зависим от външната – например върху свързващата колона от вътрешната таблица има изграден индекс. Ако методите на достъп до данните на двете релации са независими, в крайна сметка се стига до Декартово произведение, което е неефективно. Nested Loops се предпочита при свързване на малък брой редове и при наличие на индексен достъп до данните. Примерен фрагмент от план за изпълнение на заявка с NESTED LOOPS: N  ESTED LOOPS
RELATION ACCESS (…) OF our_outer_relation RELATION ACCESS (…) OF our_inner_ relation При индексен достъп до данните: NESTED LOOPS RELATION ACCESS OF our_outer_relation INDEX (... SCAN) OF outer_relation _index (…..) RELATION ACCESS OF our_inner_relation INDEX (RANGE SCAN) OF inner_ relation_index (NON-UNIQUE) Merge joinАко и двете релации са сортирани по свързващия атрибут (join атрибута), то свързването може да се осъществи по следния начин:
Ако един или повече релации, участващи в merge join алгоритъма са вече сортирани допълнително сортиране не е необходимо. В противен случай СУБД трябва да извърши сортирането, обикновено използвайки оптимизирани методи за сортиране (т.нар. external методи) за да избегнат скъпите В/И операции. External сортиране се налага, когато данните, които трябва да бъдат сортирани не се побират в основната памет (обикновено RAM) и трябва да се използва по-бавен тип памет (обикновено HDD). External mergesortЕдин пример за външно сортиране е външния mergesort алгоритъм. Например за сортиране на 900 MB данни се използват само 100 MB RAM:
Понякога се постига до добра ефективност, ако големината на изходния буфер се увеличи. В горният пример се използва едно фазово сливане. Ако отношението на големината на данните към основната памет е голямо се предпочита много фазово сортиране. Например сортира се само първата половина на сортираните парчета, след това другата половина и накрая 2-те сортирани части. Точният номер зависи от отношението на големината на данните към основната памет и физическите характеристики на твърдия диск (transfer rate и seeking time). M   ERGE (JOIN)
SORT (JOIN) RELATION ACCESS (…) OF relation_A SORT (JOIN) RELATION ACCESS (…) OF relation_B Достъпа да релациите (стъпка 4 и 5) могат да се базират на индексен достъп, ако има филтриращи предикати (nonjoin predicates, например name = ‘Ivan’ ), който могат да използват индекс. Въпреки това този алгоритъм често се използва пълно сканиране (full table scan) на двата релации. Коя релация ще бъде сортирана първа (и ще бъде обявена за външна според по-горния алгоритъм) и коя втора е без значение. Merge join алгоритъмът е по-ефективен от индексния nested loops, ако броят на кортежите удовлетворяващи условието за свързване е голямата част от общия брой кортежи в двете релации.
Hash joinПрилагането на hash join алгоритъмът при вътрешно съединение на две релации (inner join) протича по следната схема:
Hash join алгоритъма може да се приложи само ако свързването е с равенство (equi-join). Предимството на алгоритъма се изразява в това, че таблиците се обхождат по веднъж и не е необходимо никакво сортиране. Най-добра ефективност се постига, когато hash таблицата се побира в оперативната памет. Разработени са различни модификации и варианти (например Grace Join или Hybrid Hash Join), когато по-малката таблица не се побира в паметта. Някои СУБД разделят релациите на части и за всяка част прилагат hash join алгоритъма, като по този начин си гарантират, че изградената hash таблица ще се побере в ОП. H RELATION ACCESS (..) OF relation_A RELATION ACCESS (..) OF relation_B Използването на Hash join алгоритъмът се предпочита при свързване на 2 релации, ако свързването е с равенство и е изпълнено поне едно от следните условия:
Оптимизации/модификации на hash join алгоритъма: Anti hash joinИзползва се, когато имаме anti-join предикат (предикат селектиращ стойности от една релация, когато се търсят кортежите нямащи съответствие в другата релация – например при използването на NOT IN ). При този вариант hash таблицата се изгражда като първа стъпка, но при сканиране на другата релация в резултатът се включват кортежите и, които попадат в празен „bucket” на hash таблица или в пък попадат на непразен „bucket”, в които няма кортеж със съответната стойност на join атрибута. Semi hash joinИзползва се, когато имаме semi-join предикат (предикат селектиращ стойности от една релация, когато се търсят кортежите, който имат съответствие в другата релация, но не е необходимо да се знаят точно кои и колко точно са тези съответствия – например при използването на EXISTS ). При този вариант hash таблицата се изгражда като първа стъпка, но при сканиране на другата таблица веднага щом се открие, че кортежът има съответствие, то той се включва в резултата. Оптимизации/модификации на join алгоритъмите:Варианти на Semi и Anti съществуват и за другите join алгоритми. Например при semi-nested loops модификацията се излиза от втория цикъл веднага щом се открие съответствие и кортежът на външната таблица се включва в резултата. Всички алгоритми имат и варианти за изпълнение на външни съединения (outer joins) Операции по сортиранеНай-често следните операции изискват сортиране на данните:
Препоръки:
Преглед на плана за изпълнение
Каталог: InaNaidenova -> DataBase3 DataBase3 -> Бази от данни Упражнение 11 InaNaidenova -> Execute immediate dynamic string [into {define variable [, define variable] Изтегляне 58.11 Kb. Сподели с приятели:
|
ASH JOIN