// Kradeno z https://github.com/Krejdom/school_notes/blob/master/PB154.md 

Zpracovávání dotazů

1. parsování a překlad – překlad do interní formy a následně do relační algebry, kontrola syntaxe a verifikace vztahů
2. optimalizace – vybere mezi všemi ekvivalentními plány evaluace ten s nejnižšími nároky (čas na zodpovězení dotazu: seeks, blocks transfers)
3. vyhodnocení – plán evaluace dotazů

Operace selekce

• br = počet bloků s vyhovujícími záznamy
• tT = čas na přesun bloku
• tS = doba přístupu

Algoritmus A1

• lineární prohledávání
• file scan
• projde každý blok souboru a ověří všechny záznamy, jestli nesplňují podmínku
• (br block transfers + 1 seek)

Binární vyhledávání nemá smysl, protože data nejsou seřazena.

Algoritmus A2

• primární index, rovnost klíče
• (hi + 1) * (tT + tS)

Algoritmus A3

• primární index, rovnost neklíče (více záznamů)
• hi * (tT + tS) + tS + tT*br

Algoritmus A4

• sekundární index, rovnost neklíče
• single record : (hi + 1)*(tT + tS)
• multiple records: (hi+n)*(tT+tS)

Selekce s porovnáváním

Algoritmus A5

• primární index, porovnání
• Pro A>=V najdu index první n-tice >=V a čtu relaci sekvenčne odtud
• Pro A<=V čtu po první n-tice >V

Algoritmus A6

• sekundární index, porovnání

Algoritmus A7

• konjunkce selekce s využitím indexu
• Pro každou podmínku vyber takový algoritmus, aby cost byl co nejmenší

Algoritmus A8

• konjunkce selekce s využitím složeného indexu

Algoritmus A9

• konjunkce selekce průnikem identifikátorů

Algoritmus A10

• disjunkce selekce sjednocením identifikátorů

Sorty

• quicksort pro relace, které se vejdou do paměti
• jinak externí merge sort

Externí merge-sort

1. vytvoř uspořádané části, i=0
   • načti M (velikost paměti ve stránkách) bloků relace do paměti
   • setřiď vnitřní paměťové bloky
   • zapiš data a zvyš i
2. mergni části, N<M
   • použij N bloků paměti na buffer vstupních částí + 1 blok na buffer výstup
   • načti první blok každé části do buffer stránky
   • opakuj: vyber první záznam (v setříděném pořadí) ze všech buffer stránek, zapiš jej na output buffer, smaž záznam z jeho vstupního bufferu, pokud jsou buffer stránky, načti další blok
   • dokud nejsou všechny buffer stránky prázdné

Joiny

• nested-loop join – theta join (dva for vnořené cykly)
• block nested-loop join – (čtyři vnořené for cykly – popárování bloků vnitřní a vnější relace)
• indexed nested-loop join – podobné jako nested-loop join, akorát používá k vyhledání vhodné n-tice z vnitřní relace index
• merge-join
• hash-join – equi-joiny a natural joiny

Nested-Loop Join

Slouží k výpočtu theta joinu.

pro každou n-tici tr z relace r:
    pro každou n-tici ts z relace s:
        otestuj, jestli dvojce (tr,ts) splňuje podmínku theta,
        pokud ano, přidej jejich tr.ts do výsledku

r je vnější relace a s je vnitřní relace

Block Nested-Loop Join

To stejné jako Nested-Loop Join, akorát nejdřív dvěma vnořenými cykly prochází celé bloky relací a až pak z nich prochází n-tice.

Hash-join

• Využívá se u equi-joinu a natural joinu.
• Hashovací funkce h je využitá k rozdělení n-tic z obou relací.
• Shodné atributy jsou přiřazeny do stejných bucketů, takže potom už stačí jen spojit odpovídající buckety.

Eliminace duplicit

• hashování nebo třídění

Projekce

• projekce na každé n-tici a eliminace duplicit

Agregace

• podobné jako eliminace duplicit (třídění a hashování)

Množinové operace

• třídění + merge-join nebo hash-join

Optimalizace dotazů

• dynamické programování
• Výrazy rel. alg. lze vyjádřit různými způsoby
• Existují různé algoritmy na zpracování daných operací

• Vyhodnocovací plán přesně určuje jaký algoritmus se použije, pro jakou operaci a jak je vyhodnocení koordinováno
• Optimalizace založená na náročnosti
  1. pravidla ekvivalence
  2. vyber nejlevnější plán založen na celkové náročnosti

Změna relačních výrazů

• Ekvivalentní výrazy = jestliže dostaneme stejný výsledek pro všechny platné databáze

1. Konjunktivní selekce, může být rozdělena na posloupnost selekcí

σ θ1∧θ2 (E) = σ θ1 (σ θ2 (E))

2. Operace selekce jsou komutativní

σ θ1 (σ θ2 (E)) = σ θ2 (σ θ1 (E))

3. V posloupnosti projekcí je potřebná pouze poslední. (Zbytek může být vynechán)

Π L1 (Π L2 (...(Π Ln (E))...)) = (Π Ln (E)

4. Selekce se může kombinovat s Kartézským součinem a theta join.

σ θ (E1 × E2) = E1 ⋈θ E2

σ θ1 (E1 ⋈θ2 E2) = E1 ⋈θ1∧θ2 E2

5. Theta-join (a přirozené spojení) jsou komutativní.
6. . a) Přirozené spojení jsou operace asociativní