Основни методи за достъп до данните



Дата24.09.2016
Размер58.11 Kb.

Основни методи за достъп до данните




Пълно сканиране на релацията (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:
NESTED 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 атрибута), то свързването може да се осъществи по следния начин:

  1. За всеки кортеж във външната релация:

    • Разглежда се текущата „група” от кортежи на вътрешната релация; групата се състои от разположените един до друг кортежи от вътрешната релация с една и съща стойност на свързващия атрибут;

    • Всеки кортеж от текущата вътрешна група, удовлетворяващ условието за свързване се добавя към крайния резултат. След като вътрешната група се изчерпи, вътрешното и външното сканиране могат да продължат към следващата група.

Ако един или повече релации, участващи в merge join алгоритъма са вече сортирани допълнително сортиране не е необходимо. В противен случай СУБД трябва да извърши сортирането, обикновено използвайки оптимизирани методи за сортиране (т.нар. external методи) за да избегнат скъпите В/И операции. External сортиране се налага, когато данните, които трябва да бъдат сортирани не се побират в основната памет (обикновено RAM) и трябва да се използва по-бавен тип памет (обикновено HDD).

External mergesort


Един пример за външно сортиране е външния mergesort алгоритъм. Например за сортиране на 900 MB данни се използват само 100 MB RAM:

  1. Четат се 100 MB от данните в основната памет и се сортират чрез някакъв конвенционален метод (обикновено QuickSort).

  2. Записват се сортираните данни на диска.

  3. Повтарят се стъпки 1 и 2 докато данните се сортират на по 100 MB-тови парчета, които трябва да бъдат слети в един общ изходен файл/обект;

  4. Четат се първите 10 MB от всяко сортирано парче (ще ги наричаме изходни буфери) във основната памет (общо 90 MB), а останалите 10 MB се оставят за изходен буфер.

  5. Изпълнява са т.нар „9-way merging” и резултатът се записва в изходния буфер. Когато буферът се напълни, той се записва в крайния сортиран файл. Ако някой от 9-те входни буфера се изпразни се прочитат следващите 10 MB от 100 MB на съответното парче или се маркира като изчерпано, ако вече няма данни за четене от него.

Понякога се постига до добра ефективност, ако големината на изходния буфер се увеличи. В горният пример се използва едно фазово сливане. Ако отношението на големината на данните към основната памет е голямо се предпочита много фазово сортиране. Например сортира се само първата половина на сортираните парчета, след това другата половина и накрая 2-те сортирани части. Точният номер зависи от отношението на големината на данните към основната памет и физическите характеристики на твърдия диск (transfer rate и seeking time).
MERGE (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 таблица (в паметта) от кортежите на по-малката релация, чрез прилагане на hash функция към свързващите (join) атрибути;

  • сканира се по-голямата релация и се формира резултатната релация чрез обхождане на съответния „bucket” от hash таблица;

Hash join алгоритъма може да се приложи само ако свързването е с равенство (equi-join). Предимството на алгоритъма се изразява в това, че таблиците се обхождат по веднъж и не е необходимо никакво сортиране. Най-добра ефективност се постига, когато hash таблицата се побира в оперативната памет. Разработени са различни модификации и варианти (например Grace Join или Hybrid Hash Join), когато по-малката таблица не се побира в паметта. Някои СУБД разделят релациите на части и за всяка част прилагат hash join алгоритъма, като по този начин си гарантират, че изградената hash таблица ще се побере в ОП.

HASH JOIN


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)


Операции по сортиране


Най-често следните операции изискват сортиране на данните:


  • UNIQUE /DISTINCT

  • GROUP BY ( в някои СУБД се реализира и с hash функция)

  • ORDER BY

  • MERGE JOIN

Препоръки:





  • Избягвайте (когато е възможно) DISTINCT и GROUP BY;

  • Използвайте (когато е възможно) UNION ALL веместо UNION;

  • Предпочитайте употребата на AND и = при съставяне на свързващите и селектиращи предикати;

  • Избягвайте трансформацията на колони в WHERE клаузата (например UPPER(name) = ‘JHON’ );

  • Избягвайте “mixed-mode” изрази ( изрази, в които участват различни типове данни ) и внимавайте за имплицитна конверсия на типове;

  • Използвайте EXISTS вместо IN (тази препоръка важи при използване на СУБД Oracle);


Преглед на плана за изпълнение


  1. Добре ли се използват филтрите

  2. Редът на таблиците при свързване - първата стъпка връща възможно най-малко редове на втората и т.н. по същото правило

  3. Подходящ ли е използвания join метод

  4. Използват ли се ефективно изгледите

  5. Разгледайте предикатите в SQL оператора и броят на върнатите редове


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница