Aké sú náklady na operáciu spojenia zoradenia v databázovom dotaze?

Náklady na operáciu spojenia so triedením sa zvyčajne rozdelia na náklady na triedenie a náklady na zlúčenie. Dominantným faktorom je zvyčajne triedenie. Poďme to rozobrať:

1. Náklady na triedenie:

* Algoritmus: Databázy zvyčajne používajú externé zlúčenie. Je to preto, že spojené vzťahy sú často príliš veľké na to, aby sa zmestili do pamäti.

* I/O Cena (dominantný faktor):

* Externé triedenie zlúčenia zahŕňa viaceré priechody cez údaje.

* Počet prihrávok: Počet prechodov závisí od veľkosti vzťahov a množstva dostupnej pamäte („vyrovnávacia pamäť“). Povedzme, že máme:

* `B` =počet blokov (stránok) vo vzťahu.

* `M` =počet dostupných pamäťových blokov (veľkosť vyrovnávacej pamäte).

* Počet prechodov je približne `log_m (b)` alebo o niečo viac, ak chcete byť mimoriadne presný.

* I/O Cena za priechod: Každý priechod znie a píše celý vzťah, takže stojí „2B` I/O operácie (B pre čítanie a B na písanie).

* Celkové náklady na I/O na triedenie: `2b * Počet priechodov =2b * log_m (b)`. Podrobnejšie sú náklady na triedenie pre každý vzťah `R` a` S`:

* Zoradenie (r) =2 * `b (r)` * log m (`B (r)`) (kde `b (r)` je počet blokov pre vzťah R)

* Zoradenie (s) =2 * `b (s)` * log m (`B (s)`) (kde `b (s)` je počet blokov pre vzťahy)

* CPU Cena: Zatiaľ čo triedenie je primárne viazané I/O, sú tu spojené náklady na CPU s porovnávaním n -potrieb, zlúčením zoradených zjazdov atď. Tieto náklady sú zvyčajne nižšie ako náklady na I/O a často sa ignorujú v zjednodušených modeloch nákladov.

2. Zlúčené náklady:

* I/O Cena: Po triedení vzťahov si fáza zlúčenia vyžaduje prečítanie každého bloku oboch zoradených vzťahov raz.

* `B (r) + b (s)` (kde `b (r)` a `b (s)` je počet blokov pre vzťahy r a s)

* CPU Cena: Náklady na CPU na porovnanie nínov počas fázy zlúčenia sú relatívne malé v porovnaní s triedením a nákladmi na I/O.

Celkové náklady:

Celkové náklady na spojenie zoradenia sú zhruba súčtom nákladov na triedenie a zlúčiacich nákladov:

Cena ≈ 2 * b (r) * log m (B (r)) + 2 * b (s) * log m (B (s)) + b (r) + b (s)

Zjednodušený náklady (bežná aproximácia):

Ak dominuje náklady na triedenie (čo je zvyčajne prípad), zjednodušená aproximácia je:

Cena ≈ 2 * b (r) * log m (B (r)) + 2 * b (s) * log m (B (s))

Dôležité úvahy:

* pamäť (m): Množstvo dostupnej pamäte výrazne ovplyvňuje počet prihrávok potrebných na triedenie. Viac pamäte znamená menej prihrávok a nižšie náklady.

* vopred osvedčené údaje: Ak je niektorý z vzťahov * už * zoradený na kľúč pripojenia, môžete preskočiť krok zoradenia pre tento vzťah. To dramaticky znižuje náklady. Cena sa stávajú nákladmi na triedenie iba netriedeného vzťahu plus zlúčiacich nákladov.

* duplikáty: Ak kľúče spojenia obsahujú duplikáty, fáza zlúčenia môže byť zložitejšia a potenciálne vyžaduje ďalšie I/O a CPU. Vzorec predpokladá, že duplicitná manipulácia je začlenená do každého čítania bloku.

* Veľkosť bloku: Veľkosť bloku (veľkosť stránky) ovplyvňuje počet blokov vo vzťahu.

* Model nákladov: Presný vzorec použitý na odhad nákladov sa medzi databázovými systémami líši. Niektoré môžu zahŕňať jasnejšie náklady CPU, časy hľadania disku, atď. Toto je zjednodušený model na pochopenie relatívnych nákladov.

* hash sa pripojte vs. V mnohých prípadoch je hash spojený efektívnejší ako spojenie zo triedenia, najmä ak jeden zo vzťahov zapadá výlučne do pamäte. Spojenie triedenia však môže byť efektívnejšie, keď sú údaje už triedené, alebo keď údaje nie sú rovnomerne rozdelené.

* hybridné prístupy: Niektoré databázy používajú hybridné prístupy, ktoré kombinujú aspekty spojenia hash a spojenia zoradenia.

* Skutočný výkon: Toto sú teoretické náklady. Skutočný výkon môže byť ovplyvnený faktormi, ako je výkon I/O disku, rýchlosť CPU, súbežnosť a ladenie databázy.

Príklad:

Povedzme:

* `B (r) =1000` bloky

* `B (s) =500` bloky

* `M =100` bloky pamäte

Potom:

* log 100 (1000) ≈ 1,5

* log 100 (500) ≈ 1,35

Odhadované náklady ≈ 2 * 1 000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500

≈ 3000 + 1350 + 1500

≈ 5850 I/O operácií.

Je to len odhad a skutočné náklady v reálnom databázovom systéme by sa mohli líšiť. Relatívne porovnanie je, že náklady na triedenie sú vyššie ako náklady na zlúčenie.

Stručne povedané, v súvislosti s mergou nákladov na triedenie dominuje náklady I/O na triedenie vzťahov. Počet prihrávok potrebných na triedenie závisí od veľkosti vzťahov a množstva dostupnej pamäte. Zníženie veľkosti vzťahov (napr. Filtrovaním alebo projekciou) alebo zvýšením dostupnej pamäte môže významne zlepšiť výkon.

• Predchádzajúca strana: Aké kroky sú potrebné na získanie prístupu Oracle pre nových zamestnancov? 
• Ďalšia strana: Aký je význam operácie vonkajšej únie v databázových dopytoch a ako sa líši od iných typov?