Mikrozadanie 13

back

Treść

W bazie danych są następujące tabele: Wojewodztwo(nr, nazwa, stolica), Gmina(nr, nazwa, liczba_mieszkancow, rodzaj, nr_wojewodztwa). W takiej bazie danych ma zostać wykonane następujące zapytanie:

SELECT G.nazwa, (SELECT nazwa FROM Wojewodztwo WHERE nr = G.nr_wojewodztwa) nazwa_woj  
FROM Gmina G  
WHERE G.rodzaj = ‘wiejska’ AND  
G.liczba_mieszkancow > (SELECT AVG(liczba_mieszkancow)  
                        FROM Gmina G1  
                        WHERE G1.nr_wojewodztwa = G.nr_wojewodztwa)  
ORDER BY nazwa_woj, nazwa;

Zaproponuj jak najlepszy plan realizacji tego zapytania i oszacuj sumaryczną liczbę przeczytanych i zapisanych bloków, biorąc pod uwagę następujące założenia:

• w pamięci operacyjnej jest miejsce na $51$ bloków;
• w jednym bloku mieści się $51$ rekordów tabeli Wojewodztwo albo $35$ rekordów tabeli Gmina;
• w tabeli Wojewodztwo jest $16$ rekordów, a w tabeli Gmina $2477$ rekordów;
• nie wolno korzystać z żadnych indeksów ani innych pomocniczych struktur danych.

Wzorcówka

Tabelę województw możemy zmieścić w jednym bloku pamięci. Sortujemy ją po nazwach. Teraz możemy posortować gminy po nazwach województw i nazwach gmin. Gminy zajmują $\lceil {2477 / 35} \rceil = 71$ bloków, więc potrzebujemy dwóch etapów. Możemy do tego użyć as few as $9$ bloków, bo już $9^2 = 81 > 71$, mamy więc mnóstwo wolnej pamięci.
Przy pierwszym odczycie dojoinowujemy nazwy województw, co jest darmowe, bo mamy je już w pamięci. Możemy też w bloku obok od razu liczyć sobie średnią mieszkańców dla każdego województwa (akumulować sumę mieszkańców i liczbę gmin). Przy końcowym etapie mamy więc posortowane gminy i blok z średnimi liczbami mieszkańców dla każdego województwa. Możemy łatwo przeprowadzić selekcję po rodzaju przy pierwszym etapie sorta, a porównanie z średnią przy ostatnim kroku sortowania. Wynik sortowania od razu zapisujemy jako output.

Koszt to przeczytanie tabeli województw i dwuetapowy sort na gminach, czyli $1 + 4 \cdot 71 = 285$ I/O.

Uwagi

• Najpopularniejszym błędem było sortowanie dwa razy, najpierw po numerze województwa, wykonanie filtrów z średnimi itp. a potem ponownie po nazwie województwa. Możemy od razu dojoinować nazwy i posortować po nich, a średnie policzyć niezależnie na boku w jednym bloku.
• Dużo przeszacowań wynikało z niepotrzebnych zapisów i odczytów. Pipelining/strumieniowanie jest kluczową strategią przy planach fizycznych, jak już odczytujemy krotki to chcemy wepchnąć tam tyle operacji ile tylko się da, żeby jakoś usprawiedliwić koszt odczytu.

back