PA152: Efektivní využívání DB 7. Třídění Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2013 2 Použití algoritmů třídění (sorting)  Výsledek SELECT … ORDER BY  Provedení spojení SELECT … r JOIN s  Odstranění duplicit SELECT DISTINCT … PA152, Vlastislav Dohnal, FI MUNI, 2013 3 Předpoklady  Operační paměť Omezená velikost – M bloků  Data uložena na disku Vstup (relace) je čtený z disku  Výsledek zůstává v paměti Výstup je obvykle dále zpracováván  Náklady na třídění (sorting) Počet čtení z disku PA152, Vlastislav Dohnal, FI MUNI, 2013 4 Třídění v paměti  Mnoho algoritmů BubbleSort – O(n2) QuickSort – Θ(n log n) MergeSort – O(n log n) InsertSort – O(n2) HeapSort – O(n log n) RadixSort – O(kn) Counting Sort – O(k+n) … PA152, Vlastislav Dohnal, FI MUNI, 2013 5 Příklady  Counting Sort  Malý počet různých hodnot  Potřebujeme seřadit 100 známek (A-F)  Vytvoříme pole pro jednotlivé známky  Spočítáme počty jednotlivých známek  Zapíšeme výsledek  Radix Sort  Rekurzivní řazení po jednotlivých bajtech (bitech)  Postupně po bajtech aplikuj Counting Sort  První průchod zjistí počty  Druhý průchod umístí data na správné místo PA152, Vlastislav Dohnal, FI MUNI, 2013 6 Vlastnosti třídících algoritmů  Data v operační paměti  Většinou třídí na místě (in-place)  Potřebují málo další paměti (log n) PA152, Vlastislav Dohnal, FI MUNI, 2013 7 Malá operační paměť  Komprese dat Zpracovávat pouze klíče s ukazateli na záznam, nikoli celé záznamy Ok, ale při výstupu stejně musím záznamy číst  náhodné čtení  Virtualizace paměti Většinou pomalé  příliš mnoho V/V  Úprava algoritmu Spojení více algoritmů Většinou se používá MergeSort a QuickSort PA152, Vlastislav Dohnal, FI MUNI, 2013 8 Převzato z Wikipedia.org, MergeSort Algorithm MergeSort – v paměti  Princip „rozděl a panuj“ Rozděluj na poloviny  Až na jednotlivé klíče Spojuj uspořádané části  Lineární průchod oběma částmi  Nejmenší dávám na výstup  O(n log n) PA152, Vlastislav Dohnal, FI MUNI, 2013 9 MergeSort – varianta pro disk  Dvoufázové třídění, vícecestné slévání  Two-Phase Multiway MergeSort  Princip 1. Rozděl na dávky o velikosti volné RAM 2. Postupně dávky v paměti uspořádej 1. a zapiš je na disk 3. Všechny dávky čti a naráz spojuj PA152, Vlastislav Dohnal, FI MUNI, 2013 10 Dvoufázový MergeSort  Příklad Relace 100 mil. záznamů, každý 100 bajtů Blok má 4kB, tj. 40 záznamů  Relace uložena na 2 500 000 blocích (9,5 GB) Operační paměť pro třízení  12 800 bloků (50MB)  Fáze 1 2 500 000 / 12 800 dávek = 196 dávek  Poslední má pouze 4 000 bloků V/V: 2 500 000 čtení + 2 500 000 zápisů PA152, Vlastislav Dohnal, FI MUNI, 2013 11 Dvoufázový MergeSort  Fáze 2 Původní spojování po dvou dávkách je pomalé!  Tj. log2(počet dávek) čtení a zápis celé relace  Pro 196 dávek – 8 čtení a zápis celého souboru Vícecestné spojování  Čti všechny dávky po jednom bloku  Proveď spojení do výstupního bloku PA152, Vlastislav Dohnal, FI MUNI, 2013 12 Dvoufázový MergeSort  Fáze 2 Opakuj  Najdi nejmenší hodnotu ze všech dávek  Zapiš hodnotu do výstupního bloku  Plný blok  zápis na disk  Prázdný blok dávky  načtení dalšího bloku Výsledkem 1 čtení a 1 zápis pro celou relaci.  Tj. 2 500 000 čtení + 2 500 000 zápisů  Celkově 4B(R) náhodných V/V, tj. O(n) PA152, Vlastislav Dohnal, FI MUNI, 2013 13 Dvoufázový MergeSort – omezení  Parametry M – operační paměť v blocích B(R) – velikost relace R v blocích  Omezení Max. délka dávky: M Max. počet dávek: M-1 Max. velikost relace: M(M-1)  Náš příklad: 100B záznam, 50MB paměti Max. 163 827 200 bloků (625GB) Max. 6 553 088 000 záznamů  Pokud je to málo, lze zobecnit na 3fázový, …