Modelování hierarchických struktur v relační databázi

Jan @Novoj Novotný

Online verze prezentace
http://bit.ly/javadays2020

Sledujte prezentaci se mnou
http://bit.ly/javadays2020

Pohrejte si s kódem
https://github.com/novoj/JavaDays2020.git

O mně

Použití v e-commerce

Nejčastější použití

Více-úrovňová menu (zobraz hierarchii).

Nejčastější použití

Drobečková navigace (vypiš nadřízené).

Nejčastější použití

Výpis návazných produktů v omezené sekci stromu.

Reprezentace vazbou na rodiče

Naivní návrh datové struktury, byť hojně používaný v literatuře.


CREATE TABLE category(
    category_id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(64) NOT NULL,
    parent INT DEFAULT NULL
);
  • ne všechny databáze podporují hierarchické dotazy
  • špatně implementovaná rekurze je na větších datech příliš pomalá

Emulace reálného stavu

V praxi pracujeme s mnohem rozsáhlejšími daty a proto si pojďme devinovat situaci, která se alespoň velmi vzdáleně podobá reálným případům z praxe.

Ukážeme si reálné SQL dotazy nad Oracle 11g databází.

Zkuste si je sami: https://github.com/novoj/JavaDays2020.git

Hierarchické dotazy v Oracle DB

VYPIŠ KATEGORIE S ALESPOŇ JEDNÍM PRODUKTEM V PODKATEGORIÍCH SEKCE


// zajímají nás kategorie
select distinct TC.* from T_CATEGORY TC

// přes M:N vazbu produktu na kategorii
     left join T_PRODUCT_CATEGORY TPC on TC.CATEGORY_ID = TPC.CATEGORY_ID
     left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// s vyloučením kategorií bez produktů
where TP.PRODUCT_ID is not null

// a hierarchickým dotazem od kategorie s ID = 2 s rekurzí přes podřízené
start with TC.CATEGORY_ID = 2
connect by prior TC.CATEGORY_ID = TC.PARENT;

S přibližným výsledkem:


1000 rows retrieved starting from 1 in 133 ms (execution: 9 ms, fetching: 124 ms)

Zdroj: Oracle tutorial

Hierarchické dotazy v Oracle DB

VYPIŠ KATEGORIE S ALESPOŇ JEDNÍM PRODUKTEM V PODKATEGORIÍCH SEKCE


// zajímají nás kategorie
SELECT distinct t3.* FROM T_CATEGORY t1

// otrocky připojme X podřízených úrovní kategorií
         LEFT JOIN T_CATEGORY t2 ON t2.parent = t1.category_id
         LEFT JOIN T_CATEGORY t3 ON t3.parent = t2.category_id

// s M:N vazbou produktu na kategorii
         LEFT JOIN T_PRODUCT_CATEGORY TPC on t1.CATEGORY_ID = TPC.CATEGORY_ID OR t2.CATEGORY_ID = TPC.CATEGORY_ID OR t3.CATEGORY_ID = TPC.CATEGORY_ID
         LEFT JOIN T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// s vyloučením kategorií bez produktů a nastavením úvodní kategorie na ID = 2
where TP.PRODUCT_ID is not null
      and t1.CATEGORY_ID = 2

S přibližným výsledkem:


1000 rows retrieved starting from 1 in 148 ms (execution: 12 ms, fetching: 136 ms)
  • špatně škáluje na velkých datech
  • limitováno na předem daný počet úrovní zanoření
  • nepraktické z více ohledů

Hierarchické dotazy v Oracle DB

VYPIŠ KATEGORIE S POČTEM PRODUKTŮ V NICH


// zajímají nás kategorie a počet produktů v nich
select TC.*, A.PRODUCT_COUNT from T_CATEGORY TC
 inner join (

// zde můžeme získat pouze sloupce, které jsou použité v GROUP by sekci
    select t1.CATEGORY_ID, count(0) as PRODUCT_COUNT
        from T_CATEGORY t1

// přes M:N vazbu produktu na kategorii
             left join T_PRODUCT_CATEGORY TPC on t1.CATEGORY_ID = TPC.CATEGORY_ID
             left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// s vyloučením kategorií bez produktů a nastavením úvodní kategorie na ID = 2
    where TP.PRODUCT_ID is not null
    start with t1.CATEGORY_ID = 2
    connect by prior t1.CATEGORY_ID = t1.PARENT

// seskupit podle kategorie
    group by t1.CATEGORY_ID
    having count(0) > 0

 ) a on a.CATEGORY_ID = TC.CATEGORY_ID

S přibližným výsledkem:


100 rows retrieved starting from 1 in 224 ms (execution: 153 ms, fetching: 71 ms)

Hierarchické dotazy v Oracle DB

VYPIŠ NADŘÍZENÉ KATEGORIE


// zajímají nás kategorie
select * from T_CATEGORY TC

// nadřízené kategorii s ID = 4
start with TC.CATEGORY_ID = 4

// s obrácenou rekurzivní vazbou
connect by prior TC.PARENT = TC.CATEGORY_ID;

S přibližným výsledkem:


5 rows retrieved starting from 1 in 63 ms (execution: 6 ms, fetching: 57 ms)

Zdroj: Oracle tutorial

Reprezentace formou skládané cesty


CREATE TABLE category(
    category_id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(64) NOT NULL,
    path VARCHAR(512) DEFAULT '/'
);

Ukázka dat

Reprezentace formou skládané cesty

Výhody Nevýhody
  • vyhneme se rekurzi
  • překvapivě relativně i rychlé i na větších datech
  • nadřízené položky jsou zakódované v cestě
  • vyžaduje větší prostor na disku
  • komplikovaně se udržuje při přesunech ve stromu

Reprezentace formou skládané cesty

VYPIŠ KATEGORIE S ALESPOŇ JEDNÍM PRODUKTEM V PODKATEGORIÍCH SEKCE


// zajímají nás kategorie
select distinct TC.* from T_CATEGORY TC

// přes M:N vazbu produktu na kategorii
         left join T_PRODUCT_CATEGORY TPC on TC.CATEGORY_ID = TPC.CATEGORY_ID
         left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// s vyloučením kategorií bez produktů
where TP.PRODUCT_ID is not null

// jejichž cesta začíná cestou nadřízené kategorie
      and TC.PATH like '/0/1/2/%';

S přibližným výsledkem:


1000 rows retrieved starting from 1 in 108 ms (execution: 4 ms, fetching: 104 ms)

Reprezentace formou skládané cesty

VYPIŠ KATEGORIE S POČTEM PRODUKTŮ V NICH


// zajímají nás kategorie a počet produktů v nich
select TC.*, A.PRODUCT_COUNT from T_CATEGORY TC
    inner join (

// zde můžeme získat pouze sloupce, které jsou použité v GROUP by sekci
        select T_CATEGORY.CATEGORY_ID, count(0) as PRODUCT_COUNT
        from T_CATEGORY

// přes M:N vazbu produktu na kategorii
                 left join T_PRODUCT_CATEGORY TPC on T_CATEGORY.CATEGORY_ID = TPC.CATEGORY_ID
                 left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// jejichž cesta začíná cestou nadřízené kategorie
        where TP.PRODUCT_ID is not null
              and T_CATEGORY.PATH like '/0/1/2/%'

// seskupit podle kategorie
        group by T_CATEGORY.CATEGORY_ID
        having count(0) > 0
    ) a on a.CATEGORY_ID = TC.CATEGORY_ID

S přibližným výsledkem:


100 rows retrieved starting from 1 in 144 ms (execution: 73 ms, fetching: 71 ms)

Reprezentace formou skládané cesty

VYPIŠ NADŘÍZENÉ KATEGORIE


// zajímají nás kategorie
select * from T_CATEGORY
    where CATEGORY_ID in (

// rozděl cestu na jednotlivé fragmenty
    select regexp_substr(a.PATH, '[^/]+', 1, level)
    from (

            // nadřízené kategorii s ID = 4
            select concat(PATH, concat('/', concat(CATEGORY_ID, '/'))) as PATH
                        from T_CATEGORY where CATEGORY_ID = 4
    ) a

// fragmenty převeď na řádkovou reprezentaci (černá magie)
    connect BY regexp_substr(a.PATH, '[^/]+', 1, level) is not null)

// setřídit podle úrovně zanoření sestupně
order by LVL desc;

S přibližným výsledkem:


5 rows retrieved starting from 1 in 111 ms (execution: 83 ms, fetching: 28 ms)

Zdroj: Oracle tutorial

Modified Preorder Tree Traversal (MPTT) algoritmus

Odlišný pohled na hierarchická data formou do sebe zanořených množin.

→

Modified Preorder Tree Traversal (MPTT) algoritmus

U každého uzlu se definují levé a pravé hranice, které jsou větší než levé a pravé hranice všech jejich dětí.

Modified Preorder Tree Traversal (MPTT) algoritmus

Mapování v následující relační struktuře:

Získej všechny podřízené uzly konkrétního uzlu


select * from MPTT where left >= node.left and right <= node.right

Získej všechny nadřízené uzly konkrétního uzlu


select * from MPTT where left <= node.left and right => node.right

Modified Preorder Tree Traversal (MPTT) algoritmus

Pro další typy dotazů je vhodné rozšířit MPTT informace o úroveň zanoření a počet dětí.

Získej uzly podřízené konkrétního uzlu do hloubky Y


select * from MPTT
         where left  >= node.left and
               right <= node.right and
               level >= node.level and
               level <= node.level + Y

Získej uzly nadřízené konkrétnímu uzlu do hloubky Y


select * from MPTT
         where left <= node.left and
               right => node.right and
               level >= node.level and
               level <= node.level + Y

Získej všechny podřízené "koncové" uzly konkrétního uzlu


select * from MPTT a
         where left <= node.left and
               right => node.right and
               node.numberOfChildren = 0

Modified Preorder Tree Traversal (MPTT) algoritmus

Nevýhody

  1. zápisy do datové struktury jsou drahé.
    S každým zápisem je třeba zaktualizovat hranice ve velké části stromu.
  2. zhoršená čitelnost pro vývojáře - z hranic není ihned patrné umístění ve stromu

Běžné operace se stromem:

  • přidání nového uzlu
  • změna pořadí uzlu mezi "sourozenci"
  • odstranění uzlu
  • přesun uzlu včetně podstromu na jiné místo v hierarchii

Modified Preorder Tree Traversal (MPTT) algoritmus

VYPIŠ KATEGORIE S ALESPOŇ JEDNÍM PRODUKTEM V PODKATEGORIÍCH SEKCE


// zajímají nás kategorie
select distinct TC.* from T_CATEGORY TC

// přes M:N vazbu produktu na kategorii
    left join T_PRODUCT_CATEGORY TPC on TC.CATEGORY_ID = TPC.CATEGORY_ID
    left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// pouze kategorie jejichž hranice leží uvnitř intevalu
where TC.LEFT >= 3 and TC.RIGHT <= 21052

// s vyloučením kategorií bez produktů
      and TP.PRODUCT_ID is not null;

S přibližným výsledkem:


1000 rows retrieved starting from 1 in 91 ms (execution: 5 ms, fetching: 86 ms)

Modified Preorder Tree Traversal (MPTT) algoritmus

VYPIŠ KATEGORIE S ALESPOŇ JEDNÍM PRODUKTEM V PODKATEGORIÍCH SEKCE

Pokud de-normalizujeme strukturu tabulek a uložíme hranice blíže k produktu, potom:


// zajímají nás kategorie
select distinct TC.* from T_CATEGORY TC

// s vazbou na produkty
    inner join T_PRODUCT TP on TC.LEFT = TP.LEFT and TC.RIGHT = TP.RIGHT

// jejichž hranice leží uvnitř intevalu
where TP.LEFT >= 3 and TP.RIGHT <= 21052

Poznámka: de-normalizací jsme zároveň porušili M:N vazbu, ale tento příklad je zde pouze pro ilustraci

S přibližným výsledkem:


1000 rows retrieved starting from 1 in 85 ms (execution: 4 ms, fetching: 81 ms)

Modified Preorder Tree Traversal (MPTT) algoritmus

VYPIŠ KATEGORIE S POČTEM PRODUKTŮ V NICH


// zajímají nás kategorie a počet produktů v nich
select TC.*, A.PRODUCT_COUNT from T_CATEGORY TC
    inner join (

// zde můžeme získat pouze sloupce, které jsou použité v GROUP by sekci
        select T_CATEGORY.CATEGORY_ID, count(0) as PRODUCT_COUNT
               from T_CATEGORY

// přes M:N vazbu produktu na kategorii
               left join T_PRODUCT_CATEGORY TPC on T_CATEGORY.CATEGORY_ID = TPC.CATEGORY_ID
               left join T_PRODUCT TP on TP.PRODUCT_ID = TPC.PRODUCT_ID

// jejichž hranice leží uvnitř intevalu
            where T_CATEGORY.LEFT >= 3 and T_CATEGORY.RIGHT <= 21052
                  and TP.PRODUCT_ID is not null

// seskupit podle kategorie
            group by T_CATEGORY.CATEGORY_ID
            having count(0) > 0
    ) a on a.CATEGORY_ID = TC.CATEGORY_ID

S přibližným výsledkem:


100 rows retrieved starting from 1 in 133 ms (execution: 49 ms, fetching: 84 ms)

Modified Preorder Tree Traversal (MPTT) algoritmus

VYPIŠ KATEGORIE S POČTEM PRODUKTŮ V NICH

Pokud de-normalizujeme strukturu tabulek a uložíme hranice blíže k produktu, potom:


// zajímají nás kategorie a počet produktů v nich
select TC.*, A.PRODUCT_COUNT from T_CATEGORY TC
    inner join (

// které se váží na hranice produktů
        select left, right, count(0) as PRODUCT_COUNT from T_PRODUCT TP

// jejichž hranice leží uvnitř intevalu
        where TP.LEFT >= 3 and TP.RIGHT <= 21052

// seskupeno dle hranic (pouze ty a počet nás zajímají)
        group by left, RIGHT

// sloučeno dle shodných hranic
    ) a on TC.LEFT = a.LEFT and TC.RIGHT = a.RIGHT

Poznámka: de-normalizací jsme zároveň porušili M:N vazbu, ale tento příklad je zde pouze pro ilustraci

S přibližným výsledkem:


100 rows retrieved starting from 1 in 143 ms (execution: 68 ms, fetching: 75 ms)

Modified Preorder Tree Traversal (MPTT) algoritmus

VYPIŠ NADŘÍZENÉ KATEGORIE


// zajímají nás kategorie
select TC.* from T_CATEGORY TC

// jejichž hranice obklopují hranice koncové kategorie
    where TC.LEFT <= 5 and TC.RIGHT >= 15

// setřídit podle úrovně zanoření sestupně
    order by LVL desc;

S přibližným výsledkem:


5 rows retrieved starting from 1 in 43 ms (execution: 4 ms, fetching: 39 ms)

Zdroj: Oracle tutorial

Odezvy typizovaných dotazů

Měřeno na: Oracle 11g, Intel® Core™ i7-5600U CPU @ 2.60GHz × 4, RAM 32GB, Ubuntu 20.04
Absolutní hodnoty nemají smysl, klíčové v grafu jsou relativní vztahy.

Precalculated Modified Preorder Tree Traversal (PMPTT) algoritmus

Pokus o odpověď na negativa MPTT algoritmu v oblasti změn ve stromě.

  • deterministicky přiřazuje hranice kategoriím dle pořadí jejich vzniku
  • pro kategorie na nižších úrovních jsou předem definované rozsahy "bucketů", které se postupně obsazují
  • pořadí bucketů není rozhodující, zavádí se nový sloupec "order"

Zavádí ovšem tři nové limitace:

  • je nutné předem stanovit maximální počet uzlů v rámci nadřízeného uzlu
  • je nutné předem stanovit maximální počet zanořených úrovni
  • součet všech rozsahů na nejnižší úrovni musí být <= rozsah číselného datového typu

Prealokovaná struktura pro 3 úrovně o 2 položkách

Struktura je zprvu "virtuální" a postupně se zaplňuje reálnými daty:

Level 0 je limitován maximálním rozpětím datového typu Java Long. Tj. reálně např. 10 úrovní při 55 položkách. Toto množství by se dalo teoreticky dále rozšířit přechodem na unsigned long.

Open source FTW!

PMPTT knihovna je dostupná pod MIT licencí v Maven Central:


<dependency>
    <groupId>one.edee.oss</groupId>
    <artifactId>pmptt_core</artifactId>
    <version>1.0.0</version>
</dependency>
<dependency>
    <groupId>one.edee.oss</groupId>
    <artifactId>pmptt_rdbms</artifactId>
    <version>1.0.0</version>
</dependency>

Dokumentace a zdrojové kódy jsou dostupné na GitHub:

https://github.com/FgForrest/PMPTT

Open source FTW!

Použití v kódu:


// create PMPTT instance
final PMPTT pmptt = new PMPTT(new MemoryStorage());

// PMPTT instance can handle several different "hierarchies" - ie. trees
final Hierarchy hierarchy = pmptt.getOrCreateHierarchy("eshopCategories", (short) 10, (short) 51);

// fill up hierarchy with categories
final HierarchyItem tvs = hierarchy.createRootItem("Televize");
final HierarchyItem washingMachines = hierarchy.createRootItem("Pračky");
final HierarchyItem cellPhones = hierarchy.createRootItem("Mobily");
final HierarchyItem lcd = hierarchy.createItem("LCD", tvs.getCode());

// bounds are automatically computed and accessible for attaching to de-normalized structures
final Long leftBound = tvs.getLeftBound();
final Long rightBound = tvs.getRightBound();

// all hierarchy modification operations are baked in
hierarchy.removeItem(cellPhones.getCode());
hierarchy.moveItemBetweenLevelsFirst(washingMachines.getCode(), tvs.getCode());

// you can list categories top-bottom
final List<HierarchyItem> childrens = hierarchy.getChildItems(tvs.getCode());
final List<HierarchyItem> leafs = hierarchy.getLeafItems(tvs.getCode());

// or bottom up
final List<HierarchyItem> parents = hierarchy.getParentItems(lcd.getCode());

Open source FTW!

Podpora pro de-normalizované modely:


// register callback for updating bounds in custom tables
pmptt.registerChangeListener(
	new HierarchyChangeListenerAdapter() {
		@Override
		public void itemUpdated(HierarchyItem updatedItem, HierarchyItem originalItem) {
			//update bounds in other tables
		}
	}
);

Díky za pozornost

Zdroje:

Kontaktujte mě na @Novoj nebo novotnaci@gmail.com