Stromy v SQL

Indexy lze také vytvořit na více sloupcích tabulky. Pokud máte například tabulku:

VYTVOŘIT TABULKU test2 (major int, minoritní int, name varchar);

(předpokládejme, že do něj vložíte obsah adresáře /dev) a často spouštíte dotazy jako:

SELECT jméno FROM test2 WHERE hlavní = константа A vedlejší = константа;

pak má smysl definovat index pokrývající jak hlavní, tak i vedlejší sloupce. Například:

VYTVOŘIT INDEX test2_mm_idx ON test2 (hlavní, vedlejší);

V současné době mohou být kompozitní pouze indexy typu B-tree, GiST, GIN a BRIN. Možnost vytvořit index na více klíčových sloupcích je nezávislá na možnosti přidat do indexu neklíčové sloupce (INCLUDE). Počet sloupců v indexu je omezen na 32, včetně sloupců INCLUDE. (Tento limit lze změnit při kompilaci PostgreSQL.)

Kompozitní index B-stromu lze použít s omezeními na libovolnou podmnožinu sloupců indexu, ale nejúčinnější je s omezeními na úvodní (levé) sloupce. Přesné pravidlo je, že oblast skenovaného indexu je určena omezeními rovnosti na úvodních sloupcích a omezeními nerovnosti na prvním sloupci, který není zahrnut v omezení rovnosti. Omezení sloupců napravo od nich jsou také kontrolována oproti indexu, takže přístup k tabulce je odložen, ale to neovlivňuje velikost oblasti skenovaného indexu. Pokud například existuje index na sloupcích (a, b, c) a je splněna podmínka WHERE a = 5 AND b >= 42 AND c < 77, bude index skenován od první položky s a = 5 a b = 42 do poslední položky s a = 5. Položky indexu s c >= 77 nebudou brány v úvahu, ale budou i tak skenovány. Tento index lze v principu použít v dotazech s omezeními na b a/nebo c, bez omezení na sloupec a, ale bude prohledán celý index, takže ve většině případů plánovač upřednostní prohledání celé tabulky před použitím indexu.

Kompozitní index GiST lze použít s podmínkami zahrnujícími jakoukoli podmnožinu sloupců indexu. Podmínky zahrnující další sloupce omezují záznamy vrácené indexem, ale omezení prvního sloupce primárně určuje oblast indexu, která je prohledávána. Index GiST bude relativně neefektivní, pokud jeho první sloupec obsahuje pouze několik odlišných hodnot, i když další sloupce poskytují mnoho odlišných hodnot.

Kompozitní index GIN lze použít v podmínkách zahrnujících jakoukoli podmnožinu sloupců indexu. Na rozdíl od indexů GiST nebo B-stromů se jeho výkon vyhledávání nemění v závislosti na tom, které z jeho sloupců jsou použity v podmínkách dotazu.

Kompozitní index BRIN lze použít v dotazovacích podmínkách s libovolnou podmnožinou sloupců indexu. Stejně jako u indexu GIN a na rozdíl od B-stromů nebo GiST se jeho výkon vyhledávání nemění v závislosti na tom, které z jeho sloupců jsou použity v dotazovacích podmínkách. Jediným důvodem, proč mít v jedné tabulce více indexů BRIN namísto jednoho kompozitního indexu, je použití různých parametrů úložiště pages_per_range.

Každý sloupec musí být samozřejmě použit s operátory odpovídajícími typu indexu; omezení s jinými operátory nebudou brána v úvahu.

Složené indexy by se měly používat uvážlivě. Ve většině případů bude index s jedním sloupcem fungovat dostatečně dobře a ušetří čas a místo. Indexy s více než třemi sloupci pravděpodobně nebudou užitečné, pokud se tabulka nepoužívá velmi konzistentně. Diskusi o výhodách různých konfigurací indexů naleznete v části 11.5 a 11.9.

Strom je speciální druh orientovaného grafu. Grafy jsou datové struktury složené z uzlů propojených oblouky. Každý oblouk představuje jednosměrný vztah mezi dvěma uzly. V organizačním schématu jsou uzly zaměstnanci a každý oblouk popisuje vztahy podřízenosti. V kusovníku jsou uzly moduly (nakonec se zobrazují jako jednotlivé části) a oblouky popisují vztah „vyrobeno z“.

Vrchol stromu se nazývá kořen. V organizačním diagramu je to největší výčnělek; v kusovníku je to sestavený díl. Binární strom je strom, ve kterém uzel může mít nejvýše dva potomky; obecně je n-rozměrný strom takový, ve kterém uzel může mít nejvýše n potomků.

Uzly stromu, které nemají žádné podstromy, se nazývají listy. V kusovníku se jedná o nejmenší části, na které lze součást rozebrat. Potomci neboli děti nadřazeného uzlu jsou všechny uzly v podstromu, který má nadřazený uzel jako svůj kořen.

Stromy se často zobrazují jako diagramy. (Viz obrázek 1) Dalším způsobem, jak reprezentovat stromy, je zobrazit je jako vnořené množiny (viz obrázek 2); to je základ pro reprezentaci stromů pomocí vnořených množin v SQL, kterou používám.

V SQL jsou jakékoli vztahy explicitně popsány daty. Typickým způsobem reprezentace stromů je vložení matice sousednosti do tabulky. To znamená, že jeden sloupec je nadřazený uzel a druhý sloupec ve stejném řádku je podřízený uzel (dvojice představuje oblouk v grafu). Uvažujme například organizační schéma společnosti se šesti zaměstnanci:

VYTVOŘENÍ TABULKY Personál (zaměstnanci PRIMÁRNÍ KLÍČ CHAR(20), šéfe ODKAZY NA CHAR(20) Personál (zaměstnanci), plat DECIMÁLNÍ(6,2) NENÍ NULL ); personál: Plat vedoucího zaměstnance ============================= 'Jerry' NULL 1000.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 900.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00

Tento model má výhody i nevýhody. HLAVNÍ KLÍČ je prázdný, ale sloupec „boss“ je na něm funkčně závislý, takže máme problémy s normalizací. POMOC REFERENCES neumožňuje zadat šéfa, který není zaměstnancem. Co se ale stane, když si „Jerry“ změní jméno na „Geraldo“, aby získal televizní talk show? Musíte také provést kaskádové změny v řádcích „Bert“ a „Chuck“.

Další nevýhodou tohoto modelu je obtížné odvodit cestu. Pro nalezení jména šéfa pro každého zaměstnance se používá dotaz se samospojením, například takto:

SELECT B1.emp, 'šéfové', E1.emp Z Personál AS B1, Personál AS E1 KDE B1.emp = E1.boss;

Ale něco tu chybí. Tento dotaz vám poskytne pouze bezprostřední nadřízené zaměstnanců. Šéf vašeho šéfa má také pravomoc nad vámi a tak dále ve stromové struktuře. Chcete-li se dostat o dvě úrovně výše ve stromové struktuře, museli byste napsat složitější dotaz se samospojením, například takto:

SELECT B1.emp, 'šéfové', E2.emp Z Personál AS B1, Personál AS E1, Personál AS E2 KDE B1.emp = E1.boss A AUTOMATIZACI E1.emp = E2.boss;

Chcete-li se ve stromové struktuře dostat o více než dvě úrovně hlouběji, jednoduše rozbalte vzor:

SELECT B1.emp, 'šéfové', E3.emp Z Personál AS B1, Personál AS E1, Personál AS E2, Personál AS E3 KDE B1.emp = E1.boss A AUTOMATIZACI E1.emp = E2.šéf A E2.emp = E3.šéf;

Bohužel nemáte tušení, jak hluboký je strom, takže musíte tento dotaz dále rozšiřovat, dokud nezískáte prázdnou množinu.

Listy nemají potomky. V tomto modelu je poměrně snadné je najít: Jsou to zaměstnanci, kteří nejsou šéfem nikoho jiného ve firmě:

SELECT * Z Personál AS E1 KDE NEEXISTUJE( SELECT * Z Personál AS E2 KDE E1.emp = E2.šéf);

V kořeni stromu je boss NULL:

SELECT * Z Personál KDE šéf IS NULL;

Skutečné problémy nastávají při pokusu o výpočet hodnot nahoru a dolů ve stromové struktuře. Jako cvičení napište dotaz, který sečte plat každého zaměstnance a jeho podřízených; výsledek je:

Celkové platy Plat vedoucího zaměstnance ============================= 'Jerry' NULL 4900.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 3000.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00

Model s více stromy.

Dalším způsobem, jak reprezentovat stromy, je zobrazit je jako vnořené množiny. Toto je vhodnější model, protože SQL je jazyk orientovaný na množiny. Kořen stromu je množina, která obsahuje všechny ostatní množiny, a vztah rodič-dítě je popsán členstvím podřízené množiny v nadřazené množině.

Existuje několik způsobů, jak transformovat organizační schéma do vnořených sad. Jedním ze způsobů je představit si, že přesouváte podřízené „ovály“ uvnitř jejich rodičů a používáte okrajové čáry jako lana. Kořen je největší ovál a obsahuje všechny ostatní uzly. Listy jsou nejvnitřnější ovály, které uvnitř nic neobsahují, a vnoření odpovídá hierarchickým vztahům. Toto je přirozená reprezentace modelu „kusovky“, protože finální blok je fyzicky vyroben z vnořených komponent a rozkládá se na jednotlivé části.

Dalším přístupem je představit si malého červa, který se plazí po „uzlech a obloucích“ stromu. Červ začíná na vrcholu, u kořene, a obejde celý strom.

Ale teď si představme silnějšího červa s počítadlem, které začíná na jedničce. Když červ dorazí k uzlu, umístí číslo do buňky na straně, kterou navštívil, a zvýší hodnotu počítadla. Každý uzel dostane dvě čísla, jedno pro pravou stranu a jedno pro levou stranu.

To dává předvídatelné výsledky, které můžete použít k vytváření dotazů. Tabulka Personnel vypadá takto s čísly vlevo a vpravo ve tvaru:

VYTVOŘENÍ TABULKY Personál (zaměstnanci PRIMÁRNÍ KLÍČ CHAR(10), plat DECIMÁLNÍ(6,2) NENÍ NULL, vlevo, odjet CELÉ ČÍSLO NENÍ NULL, že jo CELÉ ČÍSLO NENÍ NULL); Personál plat zaměstnance vlevo vpravo ============================== 'Jerry' 1000.00 1 12 'Bert' 900.00 2 3 'Chuck' 900.00 4 11 'Donna' 800.00 5 6 'Eddie' 700.00 7 8 'Fred' 600.00 9 10

Kořen má vždy v levém sloupci 1 a v pravém sloupci dvojnásobný počet uzlů (2*n). To je snadné pochopit: červ musí navštívit každý uzel dvakrát, jednou na levé straně a jednou na pravé straně, takže konečný počet musí být dvojnásobkem počtu uzlů v celém stromu.

V modelu vnořených množin je rozdíl mezi levou a pravou hodnotou listů vždy 1. Představte si červa, který se při lezení po stromě otáčí kolem listu. Všechny listy tedy můžete najít pomocí následujícího jednoduchého dotazu:

SELECT * Z Personál KDE (pravá - levá) = 1;

Pomocí tohoto triku můžete zrychlit dotazy: vytvořte v levém sloupci unikátní index a poté dotaz přepište tak, abyste index využili:

SELECT * Z Personál KDE vlevo = (vpravo - 1);

Důvodem zvýšení výkonu je, že SQL může použít index v levém sloupci, i když není použit ve výrazu. Nepoužívejte (left – right) = 1, protože to zneužívá index.

V modelu vnořených množin jsou cesty zobrazeny jako vnořené množiny, které jsou reprezentovány čísly vnořených množin a predikáty BETWEEN. Například pro nalezení všech nadřízených určitého zaměstnance byste napsali:

SELECT :myworker, B1.emp, (zprava - zleva) AS výška Z Personál AS B1, Personál AS E1 KDE E1.levo MEZI B1.levo A AUTOMATIZACI B1.vpravo A AUTOMATIZACI E1.pravá MEZI B1.levou A AUTOMATIZACI B1.vpravo A AUTOMATIZACI E1.emp = :mujpracovník;

Čím vyšší je výška, tím dále je šéf od zaměstnance v hierarchii. Model vnořených množin využívá skutečnosti, že každá obsahující množina je větší (kde velikost = (pravá – levá)) než množiny, které obsahuje. Kořen bude mít samozřejmě vždy největší velikost.

Úroveň, tedy počet oblouků mezi dvěma danými uzly, se vypočítává poměrně snadno. Například k nalezení úrovní mezi daným pracovníkem a manažerem můžete použít:

SELECT E1.zap., B1.zap. COUNT(*) - 1 AS úrovní Z Personál AS B1, Personál AS E1 KDE E1.levý MEZI B1.levý A AUTOMATIZACI B1.vpravo A AUTOMATIZACI E1.vpravo MEZI B1.levý A AUTOMATIZACI B1.vpravo A AUTOMATIZACI E1.node = :myworker A AUTOMATIZACI B1.node = :mujmanažer;

(COUNT(*) – 1) se používá k přímému odstranění dvojitého indexu uzlu, jako by byl na jiné úrovni, protože uzel je od sebe odstraněn o nulu úrovní.

Z tohoto vzoru můžete vytvářet další dotazy. Například chcete-li najít společné nadřízené dvou zaměstnanců, spojte cesty a najděte uzly, které mají (COUNT(*) > 1). Chcete-li najít nejbližší společné předky dvou uzlů, spojte cesty, najděte uzly, které mají (COUNT(*) > 1), a vyberte ten s nejmenší hloubkou.