Korelované vnořené dotazy

Z PostgreSQL
Skočit na navigaci Skočit na vyhledávání

proč je nepoužívat a čím je nahradit

Tento článek navazuje na předchozí článek LEFT INNER JOIN a pokračuje v popisu tzv. korelovaných poddotazů (Correlated subqueries). Korelované poddotazy v SQL zásadně rozšiřují funkcionalitu SQL. Musím však dodat, že zpracování SQL dotazu obsahující korelovaný poddotaz bude poměrně náročné, a že prakticky ve všech případech existují efektivnější způsoby, jak danou úlohu vyřešit bez použití korelovaného poddotazu. Korelované poddotazy sehrály velkou roli v době před zavedením uložených procedur do SQL a před zavedením analytických dotazů. To jsou právě ty funkce, kterými můžeme korelované dotazy efektivně nahradit. Pozn. v řadě aplikací jsou vnořené korelované (někdy také vázané) dotazy používané k všeobecné spokojenosti. Problémy nastávají s opravdu velkými tabulkami a nebo když se hraje o milisekundy (typicky zatížené www aplikace).

Korelované poddotazy

Jedná se o poddotazy obsahující hodnotu vnějšího dotazu. Tato hodnota je dostupná pomocí aliasu. Nekorelovaný poddotaz je na vnějším dotazu nezávislý - vyhodnocuje se pouze jednou. Korelovaný poddotaz se vyhodnocuje opakovaně pro každý řádek vnějšího dotazu. Mějme tabulku zaměstnanců obsahující sloupce příjmení, profese, mzda. Pro zobrazení zaměstnance s nejvyšší mzdou použiji dotaz s poddotazem:

SELECT * 
   FROM zamestnanci
  WHERE mzda = (SELECT MAX(mzda)
                   FROM zamestnanci);

Při zpracování tohoto dotazu se získá nejprve maximální mzda, která se použije jako filtr pro zobrazení záznamů. Pokud bych chtěl zobrazit zaměstnance s nejvyšší mzdou podle profese, použiji korelovaný poddotaz:

SELECT *
   FROM zamestnanci z1
  WHERE mzda = (SELECT MAX(mzda)
                   FROM zamestnanci z2
                  WHERE z1.profese = z2.profese);

V tomto případě se pro každý řádek tabulky z1 vyhodnotí poddotaz. Výsledkem tohoto poddotazu je opět maximální mzda - v tomto případě však určená pouze pro jednu konkrétní profesi. Maximální mzda v oddělení se porovná se skutečnou mzdou zaměstnance a pokud se tyto hodnoty rovnají, tak se tento řádek tabulky zobrazí. Všimněte si, že k hodnotě z vnějšího dotazu přistupuji prostřednictvím aliasu (z1.profese). Poddotaz vidí ven, naopak dotaz vidí pouze výsledek poddotazu, tj. ve vnějším dotazu se nelze odkazovat na vnitřek poddotazu.

Korelované poddotazy jsou poměrně elegantní, co se týká zápisu, a poměrně neefektivní, co se týká zpracování. V případě maximální mzdy zaměstnanců se pro zaměstnance jedné profese opakovaně dohledává maximální mzda. Za eleganci se platí. Často se ovšem korelovaným poddotazům můžeme vyhnout. V následujícím textu si ukážeme jak.

Použití korelovaných dotazů pro zobrazení pořadí a mezisoučtů

Pro demonstraci této třídy korelovaných dotazů si vytvořím tabulku history:

postgres=# create table history(id serial PRIMARY KEY, sale_date date, product varchar, sale_price integer);
NOTICE:  CREATE TABLE will create implicit sequence "history_id_seq" for serial column "history.id"
CREATE TABLE

postgres=# select * from history;
 id | sale_date  | product | sale_price 
----+------------+---------+------------
  1 | 2007-10-10 | mleko   |         10
  2 | 2007-10-10 | pecivo  |          3
  3 | 2007-10-11 | maso    |         30
  4 | 2007-10-11 | mleko   |         12
  5 | 2007-10-11 | mouka   |         20
  6 | 2007-10-12 | pecivo  |          4
  7 | 2007-10-13 | pecivo  |          3
  8 | 2007-10-13 | maso    |         30
(8 rows)

První úlohou je určení mezisoučtů pro jednotlivé produkty. Určení mezisoučtů a pořadí je tou úlohou, kterou nelze řešit neprocedurálně jinak než s využitím korelovaných poddotazů nebo SELF JOINu.

-- mezisoučty
postgres=# SELECT sale_date, product, sale_price, 
                  COALESCE((SELECT SUM(sale_price) 
                               FROM history 
                              WHERE product = o.product 
                                AND id <= o.id), 0) AS total
              FROM history o;
 sale_date  | product | sale_price | total
------------+---------+------------+----------
 2007-10-10 | mleko   |         10 |       10
 2007-10-10 | pecivo  |          3 |        3
 2007-10-11 | maso    |         30 |       30
 2007-10-11 | mleko   |         12 |       22
 2007-10-11 | mouka   |         20 |       20
 2007-10-12 | pecivo  |          4 |        7
 2007-10-13 | pecivo  |          3 |       10
 2007-10-13 | maso    |         30 |       60
(8 rows)

Pro každý produkt v tabulce history (pro každý řádek) poddotazem spočítám sumu(sale_price) všech starších záznamů pro daný produkt včetně posledního záznamu. Na rychlost provádění dotazů obsahujících korelované poddotazy obvykle mají zásadní vliv indexy. Je důležité, aby korelovaný poddotaz byl podporován indexem. Nutnost indexu je právě jeden z důvodů proč se tomuto druhu dotazu vyhnout. Každý index zpomalí aktualizaci tabulky - kromě vlastní tabulky je nutné aktualizovat i index (a to může být samo o sobě náročnější než-li aktualizace samotné tabulky). V tomto příkladě bych vytvořil dva indexy - pro sloupec id a product (id index má - je primárním klíčem). Pokud je k dispozici index, pak může být do jisté velikosti (dokud se celá tabulka vejde do vyrovnávací paměti) velice rychlý.

Další možností je SELF JOIN, který nevyžaduje index, a v často může být rychlejší než korelovaný poddotaz. Opět, při větším počtu řádků, se rychlost provádění citelně zpomaluje (jakmile se v prováděcím plánu objeví nested-loop, tak výkon odpovídá korelovanému poddotazu):

SELECT t1.sale_date, t1.product, t1.sale_price, sum(t2.sale_price) 
   FROM history t1 
        INNER JOIN 
        history t2 
        ON t1.id >= t2.id and t1.product = t2.product
  GROUP BY t1.id, t1.sale_date, t1.product, t1.sale_price
  ORDER BY t1.id

Pokud nemám k dispozici analytické dotazy, tak tyto korelované poddotazy lze efektivně nahradit pouze klientským kódem nebo uloženou procedurou, která generuje tabulku. Pozn. V relační algebře nelze uvažovat o číslech řádků nebo o mezisoučtech, a proto SQL (ve shodě s relační algebrou) tyto úlohy nepodporovalo. To bylo úkolem klientské aplikace - databáze pouze poskytovala data. To se změnilo, SQL dnes obsahuje několik funkcí, které nemají oporu v relační algebře (což některé autory vede k jistému znechucení aktuálním vývojem SQL). Jedním z nerelačních rozšíření jsou uložené procedury. Pro tento typ úlohy je vhodnější externí SP v plperl. V Perlu mám k dispozici hash tabulky, do kterých mohu ukládat mezisoučty pro produkty.

CREATE OR REPLACE FUNCTION report1(out sale_date date, out product varchar,
                                  out sale_price integer, out total integer)
RETURNS SETOF record AS $$
    my $row, %total = ();
    my $sth = spi_query("SELECT * FROM history ORDER BY id");
    while (defined ($row = spi_fetchrow($sth))) {
        $total{ $row->{product} } = 0 if !defined($row->{product});
        $total{ $row->{product}} += $row->{sale_price};
        return_next({
                    sale_date => $row->{sale_date},
                    product => $row->{product},
                    sale_price => $row->{sale_price},
                    total => $total{ $row->{product} }
        });
    }
    return;
$$ LANGUAGE plperl;
postgres=# SELECT * FROM report1();
 sale_date  | product | sale_price | total
------------+---------+------------+-------
 2007-10-10 | mleko   |         10 |    10
 2007-10-10 | pecivo  |          3 |     3
 2007-10-11 | maso    |         30 |    30
 2007-10-11 | mleko   |         12 |    22
 2007-10-11 | mouka   |         20 |    20
 2007-10-12 | pecivo  |          4 |     7
 2007-10-13 | pecivo  |          3 |    10
 2007-10-13 | maso    |         30 |    60
(8 rows)

Další úlohou je číslování pořadí (ranking). V této úloze potřebuji pouze jeden mezisoučet. Tudíž mohu použít plpgsql:

postgres=# 
CREATE OR REPLACE FUNCTION report2(out sale_date date, out product varchar, 
                                   out sale_price integer, out rank integer) 
RETURNS SETOF record AS $$
  DECLARE r record; 
          last_product varchar; 
BEGIN 
  FOR r IN SELECT * FROM history ORDER BY history.product, history.id 
  LOOP 
    IF last_product IS DISTINCT FROM r.product THEN 
      product := r.product; rank := 0; last_product := r.product;
    ELSE
      rank := rank + 1;
    END IF; 
    sale_date := r.sale_date; sale_price := r.sale_price;
    RETURN NEXT; 
  END LOOP; 
  RETURN; 
END; $$ LANGUAGE plpgsql; 
CREATE FUNCTION
Time: 5,040 ms
postgres=# SELECT * FROM report2();
 sale_date  | product | sale_price | rank 
------------+---------+------------+------
 2007-10-11 | maso    |         30 |    1
 2007-10-13 | maso    |         30 |    2
 2007-10-10 | mleko   |         10 |    1
 2007-10-11 | mleko   |         12 |    2
 2007-10-11 | mouka   |         20 |    1
 2007-10-10 | pecivo  |          3 |    1
 2007-10-12 | pecivo  |          4 |    2
 2007-10-13 | pecivo  |          3 |    3
(8 rows)

Tato uložená procedura je ukázkou vhodného použití kurzoru (v tomto případě implicitního - zapouzdřeného konstrukcí FOR). Místo opakovaného čtení tabulky history (počet čtení odpovídá počtu řádků), které si vynucuje korelovaný poddotaz, čtu tabulku pouze jednou. To je významná úspora. Již při těchto 8 řádcích je funkce report2 stejně rychlá jako korelovaný dotaz - s rostoucím počtem řádků bude korelovaný dotaz znatelně pomalejší než funkce. Ekvivalentní SQL příkaz je:

-- řazeno podle sale_date, nikoliv podle sale_price!
postgres=# SELECT sale_date, product, sale_price, 
                  (SELECT COUNT(sale_price) 
                      FROM history 
                     WHERE product = o.product 
                       AND id <= o.id) AS rank 
              FROM history o 
              ORDER BY product, id;
 sale_date  | product | sale_price | rank 
------------+---------+------------+------
 2007-10-11 | maso    |         30 |    1
 2007-10-13 | maso    |         30 |    2
 2007-10-10 | mleko   |         10 |    1
 2007-10-11 | mleko   |         12 |    2
 2007-10-11 | mouka   |         20 |    1
 2007-10-10 | pecivo  |          3 |    1
 2007-10-12 | pecivo  |          4 |    2
 2007-10-13 | pecivo  |          3 |    3
(8 rows)

Kromě toho, že tento dotaz obsahuje korelovaný poddotaz, vrací deformované výsledky v případě výskytu duplicitních hodnot (více v článku how do i return row numbers with my query).

Generování kontingenční tabulky

Kontingenční tabulka slouží k vizualizaci závislosti dvou atributů. Kontingenční tabulky známe hlavně ze tabulkových procesorů - v OSS relačních databázích se s nimi setkáváme zřídka. S vytvářením kontingenčních tabulek je spojen jeden problém. Počet sloupců je určen počtem unikátních hodnot vybraného atributu. V příkazu SELECT však sloupce určujeme dopředu, před vlastním provedením dotazu - tudíž kontingenční tabulku nemůžeme vytvořit jedním SQL dotazem (komerční databáze obsahují proprietární SQL příkazy, které generování kontingenčních tabulek podporují). K zapouzdření SQL dotazů se poměrně dobře hodí uložené procedury. Jedna ze starších metod používala korelované poddotazy.

Příklad: Sestavte kontingenční tabulku zobrazující celkový prodej jednotlivých produktů po dnech:

-- první dotaz: počet produktu
postgres=# SELECT distinct product from history;
 product 
---------
 maso
 mleko
 mouka
 pecivo 
(4 rows)
-- druhý dotaz: křížová tabulka
postgres=# SELECT sale_date, 
                  (SELECT sum(sale_price) FROM history WHERE sale_date = o.sale_date AND product = 'maso') AS maso, 
                  (SELECT sum(sale_price) FROM history WHERE sale_date = o.sale_date AND product = 'mleko') AS mleko, 
                  (SELECT sum(sale_price) FROM history WHERE sale_date = o.sale_date AND product = 'mouka') AS mouka, 
                  (SELECT sum(sale_price) FROM history WHERE sale_date = o.sale_date AND product = 'pecivo') AS pecivo , 
                  (SELECT sum(sale_price) FROM history WHERE sale_date = o.sale_date) AS total
              FROM history o
             GROUP BY sale_date
             ORDER BY 1;
 sale_date  | maso | mleko | mouka | pecivo  | total 
------------+------+-------+-------+---------+-------
 2007-10-10 |      |    10 |       |       3 |    13
 2007-10-11 |   30 |    12 |    20 |         |    62
 2007-10-12 |      |       |       |       4 |     4
 2007-10-13 |   30 |       |       |       3 |    33
(4 rows)

Tento dotaz pro každý řádek výstupní tabulky provádí pět sekvenční čteních tabulky history. Mnohem efektivnější řešení používá konstrukci CASE. Následující dotaz generuje pouze jedno sekvenční čtení tabulky history (a opět již na této triviální testovací množině je rychlejší):

postgres=# SELECT sale_date, 
                  sum(CASE WHEN product = 'maso' THEN sale_price ELSE NULL END) AS maso, 
                  sum(CASE WHEN product = 'mleko' THEN sale_price ELSE NULL END) AS mleko, 
                  sum(CASE WHEN product = 'mouka' THEN sale_price ELSE NULL END) AS mouka, 
                  sum(CASE WHEN product = 'pecivo' THEN sale_price ELSE NULL END) AS pecivo , 
                  sum(sale_price) AS total 
              FROM history 
             GROUP BY sale_date
             ORDER BY 1;
 sale_date  | maso | mleko | mouka | pecivo  | total 
------------+------+-------+-------+---------+-------
 2007-10-10 |      |    10 |       |       3 |    13
 2007-10-11 |   30 |    12 |    20 |         |    62
 2007-10-12 |      |       |       |       4 |     4
 2007-10-13 |   30 |       |       |       3 |    33
(4 rows)

Výběr prvních (posledních) n produktů s každé skupiny

Toto je v praxi poměrně často používaná úloha: zobrazení zaměstnanců s nejvyšší mzdou v rámci daného oddělení (nejvíce odpracovanými hodinami, ..), zobrazení nejprodávanějších produktů dle kategorií zboží, zobrazení nejúspěšnějších (nejhorších) prodejců dle krajů, atd. Ve starších verzích SQL bylo jediným řešením použití korelovaného dotazu (viz dotaz ze začátku článku na nejlépe placené zaměstnance dle profese). Počínaje SQL:2000 jsou dostupná efektivnější a troufám si konstatovat i čitelnější způsoby řešení (Beru, že čitelnost je dost subjektivní záležitost). Výběr prvního nebo posledního produktu bez použití korelovaných poddotazů je poměrně jednoduchá záležitost. O něco komplikovanější je výběr prvních (posledních) n produktů, nicméně i zde lze zápisem zvýšit efektivitu.

Vytvořím si a naplním tabulku zaměstnanců:

postgres=# CREATE TABLE zamestnanci(prijmeni varchar, profese varchar, mzda integer);
CREATE TABLE
Time: 150,210 ms
postgres=# INSERT INTO zamestnanci  
              VALUES('Stěhule','analytik',10000),
                    ('Kůs','analytik',15000),
                    ('Nováková','asistentka',8000),
                    ('Vlčková','asistentka', 10000),
                    ('Kabuďa','PR',16000),
                    ('Jirkovský','analytik',7000);
INSERT 0 6
Time: 3,410 ms
postgres=# select * from zamestnanci;
 prijmeni  |  profese   | mzda  
-----------+------------+-------
 Stěhule   | analytik   | 10000
 Kůs       | analytik   | 15000
 Nováková  | asistentka |  8000
 Vlčková   | asistentka | 10000
 Kabuďa    | PR         | 16000
 Jirkovský | analytik   |  7000
(6 rows)

Přehled nejlépe placených zaměstnanců podle profesí získám dotazem:

postgres=# SELECT * 
              FROM zamestnanci z 
             WHERE mzda = (SELECT max(mzda) 
                              FROM zamestnanci 
                             WHERE z.profese = profese); 
 prijmeni |  profese   | mzda  
----------+------------+-------
 Kůs      | analytik   | 15000
 Vlčková  | asistentka | 10000
 Kabuďa   | PR         | 16000
(3 rows)

Tento SQL dotaz lze přepsat bez korelovaného poddotazu použitím vícesloupcových (řádkových) predikátů nebo připojením derivované tabulky.

-- dotaz používající nekorelovaný poddotaz s více sloupcovým predikátem
SELECT * 
   FROM zamestnanci z 
  WHERE (mzda, profese) IN (SELECT max(mzda), profese 
                               FROM zamestnanci 
                              GROUP BY profese);
-- použití derivované tabulky
SELECT z.* 
   FROM zamestnanci z 
        JOIN 
        (SELECT max(mzda), profese 
            FROM zamestnanci 
           GROUP BY profese) d 
        ON z.profese = d.profese and z.mzda = d.max;

Problém nastává pokud nás zajímá prvních n (posledních n) záznamů. Pak už se korelovaných dotazů nezbavíme. Seznam prvních dvou nejlépe placených zaměstnanců získám dotazem:

postgres=# SELECT * 
              FROM zamestnanci z 
             WHERE mzda IN (SELECT mzda 
                               FROM zamestnanci 
                              WHERE z.profese = profese
                              ORDER BY mzda DESC
                              LIMIT 2) 
             ORDER BY profese ASC, mzda DESC; 
 prijmeni |  profese   | mzda  
----------+------------+-------
 Kůs      | analytik   | 15000
 Stěhule  | analytik   | 10000
 Vlčková  | asistentka | 10000
 Nováková | asistentka |  8000
 Kabuďa   | PR         | 16000
(5 rows)

Pokud si uvědomíme, že profesí je několikanásobně méně než zaměstnanců můžeme dotaz přepsat:

SELECT * 
   FROM zamestnanci 
  WHERE (mzda, profese) IN (SELECT mzda, profese 
                               FROM zamestnanci z 
                              WHERE mzda IN (SELECT mzda 
                                                FROM zamestnanci 
                                               WHERE z.profese = profese 
                                               ORDER BY mzda DESC 
                                               LIMIT 2)) 
  ORDER BY profese ASC, mzda DESC;

Tento dotaz je o něco složitější, takže na malých množinách může být o něco pomalejší nežli jednodušší dotaz, který jede přes zaměstnance. Pokud bude platit, že počet profesí << počet zaměstnanců, tak tento dotaz by měl být výrazně rychlejší.

Specialita - použití kalendáře

Poměrně často se v databázi používá tabulka, která slouží jako kalendář:

     d      | dendlouze | denkratce | prac_den |   statnisvatek    
------------+-----------+-----------+----------+-------------------
 2007-12-22 | Sobota    | So        | f        | 
 2007-12-23 | Neděle    | Ne        | f        | 
 2007-12-24 | Pondělí   | Po        | f        | Štědrý den
 2007-12-25 | Úterý     | Út        | f        | 1. svátek vánoční
 2007-12-26 | Středa    | St        | f        | 2. svátek vánoční
 2007-12-27 | Čtvrtek   | Čt        | t        | 
 2007-12-28 | Pátek     | Pa        | t        | 
 2007-12-29 | Sobota    | So        | f        | 

Tato tabulka může urychlovat běh uložených procedur (je praktické tyto hodnoty nepočítat opakovaně) a také ji můžeme využívat v klasickém neprocedurálním SQL. Následující dotaz berte pouze jako malou ukázku možností jazyka SQL. Jak už bylo v tomto článku mnohokrát uvedeno - používání korelovaných poddotazů je většinou ten nejhorší způsob, a to platí i pro následující dotaz:

Příklad: Od zadaného dne odečtěte 10 pracovních dnů:

postgres=# SELECT * 
              FROM kalendar k 
             WHERE k.prac_den AND 10 = (SELECT count(*) 
                                           FROM kalendar k2 
                                          WHERE k2.d BETWEEN k.d AND date '2007-12-20' - 1 
                                                AND k2.prac_den);
     d      | dendlouze | denkratce | prac_den | statnisvatek 
------------+-----------+-----------+----------+--------------
 2007-12-06 | Čtvrtek   | Čt        | t        | 
(1 row)

Řešení záměrně ponechám bez komentáře - zkuste vysvětlit proč a jak tento dotaz funguje. Pozn. tuto úlohu lze snadno, přehledně a rychle řešit uloženou procedurou s využitím scrollable kurzorů.

Korelované poddotazy byly a jsou poměrně důležitou částí SQL (v osmdesátých a devadesátých letech nezastupitelnou). S postupným doplňováním SQL o další funkce jejich význam klesá a až na výjimky se doporučuje, se jim vyhnout.