Co je sloupcový strom?

Třída TreeColumn implementuje sloupce komponenty TreeList.

syntax

PP.initClass(PP.Ui.TreeColumn, PP.Ui.Control, „TreeColumn“);

Návrhář

Název konstruktoru	Krátký popis
StromSloupec	Konstruktor TreeColumn vytvoří instanci třídy TreeColumn.

Vlastnosti

Název vlastnosti	Krátký popis
Titulek	Vlastnost Caption nastavuje popisek sloupce.
Upravitelné	Vlastnost Editable určuje, zda lze sloupec upravovat.
Metoda formátu	Vlastnost FormatMethod nastavuje funkci použitou k formátování prvků sloupce.
Skrytý	Vlastnost Hideable určuje, zda lze sloupec skrýt.
JePovoleno	Vlastnost IsEnabled určuje, zda je sloupec povolen.
MinWitch	Vlastnost MinWidth nastavuje minimální šířku sloupce.
Majitel	Vlastnost Owner nastavuje nadřazený prvek sloupce.
Metoda řazení	Vlastnost SortMethod nastavuje funkci použitou k řazení prvků sloupce.
Typ	Vlastnost Type určuje typ prvků sloupce během řazení.
Viditelná šířka	Vlastnost VisibleWidth určuje viditelnou šířku sloupce stromu.

Metody

Název metody	Krátký popis
appendToDom	Metoda appendToDom přidá sloupec do stromové struktury DOM.
získat šířku titulku	Metoda getCaptionWidth vrací šířku záhlaví sloupce stromu.
jeCaptionReduced	Metoda isCaptionReduced vrací znaménko zmenšení šířky záhlaví sloupce stromu.
zmenšit šířku titulku o	Metoda reduceCaptionWidthBy zkracuje popisek sloupce stromu bez ovlivnění šířky obsahu sloupce.
odstranitZDomu	Metoda removeFromDom odstraní sloupec ze stromové struktury DOM.
aktualizaceObsah	Metoda updateContent aktualizuje obsah sloupce stromu.

dění

Název události	Krátký popis
ŠířkaZměněna	K události WidthChanged dochází, když se změní šířka sloupce.

Vlastnosti zděděné z třídy Control

Název vlastnosti	Krátký popis
kotvy	Vlastnost Anchors určuje pozici komponenty umístěné uvnitř kontejneru.
Animace	Vlastnost Animation definuje parametry animace pro komponentu.
Spodní část	Vlastnost Bottom určuje spodní odsazení při umístění komponenty do LayoutPanel .
Obsah	Vlastnost Content definuje obsah komponenty.
Kontextová nabídka	Vlastnost ContextMenu definuje kontextovou nabídku pro komponentu.
Data	Vlastnost Data je určena k ukládání libovolných uživatelských dat.
Povoleno	Vlastnost Enabled určuje, zda je komponenta k dispozici pro použití.
Výška	Vlastnost Height definuje výšku komponenty.
Je zprava doleva	Vlastnost IsRTL určuje, zda jsou prvky komponenty umístěny na pravém okraji.
Je viditelný	Vlastnost IsVisible určuje, zda je komponenta viditelná.
Levý	Vlastnost Left určuje levé odsazení při umístění komponenty do GridPanel .
Neprůhlednost	Vlastnost Opacity určuje průhlednost komponenty.
Rodič	Vlastnost Parent určuje nadřazenou komponentu ovládacího prvku.
NadřazenýUzel	Vlastnost ParentNode definuje nadřazený uzel DOM.
Klíč zdroje	Vlastnost ResourceKey definuje klíč prostředku pro komponentu.
Právo	Vlastnost Right určuje pravý okraj při umístění komponenty uvnitř LayoutPanel .
Střídat	Vlastnost Rotate určuje úhel natočení komponenty.
Zobrazit popisek nástroje	Vlastnost ShowToolTip určuje, zda lze zobrazit popisek komponenty.
Styl	Vlastnost Style definuje styl komponenty.
TabIndex	Vlastnost TabIndex určuje pořadí tabulací ovládacího prvku v jeho kontejneru.
štítek	Vlastnost Tag definuje objekt JSON přidružený ke komponentě.
ToolTip	Vlastnost ToolTip určuje text popisku komponenty.
Vrchní část	Vlastnost Top určuje horní odsazení při umístění komponenty do GridPanel .
Hodnota	Vlastnost Value definuje hodnotu komponenty.
Šířka	Vlastnost Width určuje šířku komponenty.

Pokud projekt používá kompozitní index B-stromu, je důležité nejen „vytvořit index“, ale udělat to správně – jinak se dotazy nejen nezrychlí, ale mohou dokonce začít pracovat pomaleji. Vyvstává logická otázka: jak zvolit pořadí sloupců, aby index skutečně fungoval efektivně? Hrubou silou? Intuicí? Selektivitou?

V tomto článku vám povím, jak přistupovat ke konstrukci kompozitních indexů v PostgreSQL, co vlastně ovlivňuje pořadí sloupců. Také si rozebereme jednoduché pravidlo ESR, které pomáhá zjednodušit výběr a dosáhnout stabilního zvýšení výkonu na všech stanovištích.

V každém článku se snažím uvést historický odkaz na dané téma – tentokrát si připomeneme Eulera jako průkopníka ve strukturování informace.

Jsem Dmitrij Denisenko, softwarový vývojář. Chci se s vámi podělit a pohovořit o zajímavých momentech ve fázích vývoje.

Úvod – Jak funguje vyhledávání v indexu B-stromu

Abychom pochopili, jak správně vytvořit kompozitní index, nejprve si vysvětlíme, co je B-strom v PostgreSQL.

V ideálním případě se můžete podívat na oficiální kód od týmu PostgreSQL, ale zde se chci více věnovat hlavnímu tématu a nezacházet do detailů.

B-strom nebo vícesměrný vyvážený strom (nikdo přesně neví, co B v B-tree znamená: existují verze jako balanced, broad nebo jednoduše Bayer, pojmenované po autorovi). V PostgreSQL je reprezentován 3 hlavními prvky:

• Kořenový uzel
• Vnitřní uzly
• Listové uzly

Pro hlubší pochopení kořenového uzlu a interních uzlů doporučuji přečíst si informace ve specializovaných článcích, mají tam fajn vychytávky ve formě metainformací. Myslím si ale, že je to nezbytné pro lidi, kteří přímo pracují s DB, nechme to na základy nastavení této infrastruktury na projektu.

Zajímají nás koncové uzly a logika vyhledávání v nich.

Listový uzel je stránka stromu na nejnižší úrovni, která obsahuje skutečná data indexu. V listu jsou data uložena prostřednictvím stránky, což je speciální blok, který ukládá informace o klíčích indexu a TID (obvykle 8 KB). Samotný PostgreSQL ukládá listy jako dvojitě propojený seznam (to bude důležité níže).

Nejprve si uveďme příklad, jak vypadá strom s 1 indexovým sloupcem.

-- Таблица CREATE TABLE IF NOT EXISTS public.bank_transactions ( id integer NOT NULL DEFAULT nextval('bank_transactions_id_seq'::regclass), sender_id integer NOT NULL, receiver_id integer NOT NULL, amount numeric(12,2) NOT NULL, transaction_date date NOT NULL, payment_type text COLLATE pg_catalog."default" NOT NULL DEFAULT 'СБП'::text )

INSERT INTO bank_transactions (sender_id, receiver_id, amount, transaction_date, payment_type) SELECT (random() * 100000)::int, -- sender_id (random() * 100000)::int, -- receiver_id ROUND((random() * 50000)::numeric, 2), -- amount DATE '2023-01-01' + (random() * 365)::int, -- transaction_date (ARRAY['СБП', 'SWIFT', 'ВНУТРЕННИЙ', 'Межбанк'])[floor(random() * 4)::int + 1] -- payment_type FROM generate_series(1, 1000000); 

Nyní zkusme najít sender_id = 444.

-- Запрос EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bank_transactions WHERE bank_transactions.sender_id = 444 -- План Gather (cost=1000.00..15098.43 rows=11 width=36) (actual time=0.203..47.653 rows=6 loops=1) Workers Planned: 2 Workers Launched: 2 Buffers: shared hit=7749 read=1140 -> Parallel Seq Scan on bank_transactions (cost=0.00..14097.33 rows=5 width=36) (actual time=0.692..20.904 rows=2 loops=3) Filter: (sender_id = 444) Rows Removed by Filter: 333331 Buffers: shared hit=7749 read=1140 Planning: Buffers: shared hit=5 Planning Time: 0.433 ms Execution Time: 47.677 ms

Zde vidíme, že SQL jednoduše spustil Seq Scan přes celou tabulku, zahodil spoustu řádků (řádky odstraněné filtrem) a nakonec nám dal 6 řádků. To znamená, že k nalezení potřebného řádku musel přečíst a zahodit spoustu řádků.

Přidejme index podle sender_id a uvidíme, jak se plán změní.

-- Индекс CREATE INDEX idx_sender_id ON bank_transactions (sender_id); -- План Bitmap Heap Scan on bank_transactions (cost=4.51..47.49 rows=11 width=36) (actual time=0.036..0.043 rows=6 loops=1) Recheck Cond: (sender_id = 444) Heap Blocks: exact=6 Buffers: shared hit=6 read=3 -> Bitmap Index Scan on idx_sender_id (cost=0.00..4.51 rows=11 width=0) (actual time=0.032..0.032 rows=6 loops=1) Index Cond: (sender_id = 444) Buffers: shared read=3 Planning: Buffers: shared hit=15 read=1 Planning Time: 0.725 ms Execution Time: 0.061 ms

Prohledávání indexu bitmap – vyhledá všechny řádky v indexu B-stromu, kde sender_id = 5203, získá seznam TID (ukazatel na fyzické umístění řádku v tabulce).
Skenování haldy bitmap — Seznam TID přejde do tabulky (haldy) a zkontroluje, zda v tabulce existují takové řádky.

Skvělé, chápeme, co a jak udělat s indexem s 1 sloupcem.
Nyní si pojďme vysvětlit, jak to funguje u kompozitních indexů.

V kompozitních indexech ukládá Page klíč indexu ve formě sloupců, které v indexu zadáme.

Naším úkolem je nyní najít odesílatele pro konkrétní datum. Uděláme to bez indexu (a ten starý smažeme).

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bank_transactions WHERE bank_transactions.sender_id = 444 AND bank_transactions.transaction_date = '2023-09-24' --План Gather (cost=1000.00..16139.10 rows=1 width=36) (actual time=0.203..54.237 rows=1 loops=1) Workers Planned: 2 Workers Launched: 2 Buffers: shared hit=7877 read=1012 -> Parallel Seq Scan on bank_transactions (cost=0.00..15139.00 rows=1 width=36) (actual time=9.925..26.461 rows=0 loops=3) Filter: ((sender_id = 444) AND (transaction_date = '2023-09-24'::date)) Rows Removed by Filter: 333333 Buffers: shared hit=7877 read=1012 Planning: Buffers: shared hit=5 dirtied=1 Planning Time: 0.443 ms Execution Time: 54.256 ms

Totéž, úplné sekvenční skenování všech řádků v řadě, abyste našli ten, který potřebujete.
Přidejme index (výběr podle selektivity)

-- Индекс CREATE INDEX idx_sender_date ON bank_transactions(sender_id, transaction_date); -- План Index Scan using idx_sender_date on bank_transactions (cost=0.42..8.45 rows=1 width=36) (actual time=0.046..0.046 rows=1 loops=1) Index Cond: ((sender_id = 444) AND (transaction_date = '2023-09-24'::date)) Buffers: shared hit=1 read=3 Planning: Buffers: shared hit=18 read=1 Planning Time: 1.122 ms Execution Time: 0.062 ms

Zde jsme prošli Index Scan a rychle našli vše, co jsme potřebovali.
Než si to ukážeme, poznamenám, že vyhledávání se provádí v pořadí uvedeném v indexu. To znamená, že PostgreSQL používá pořadí sloupců v indexu zleva doprava: nejprve sender_id a poté transaction_date.

Všimněte si, že kdybychom datum zařadili jako první, dostali bychom koncové uzly podle data a seznam by vypadal mnohem větší, možná by tam bylo několik koncových uzlů s daty a operacemi na nich.

Praktická část – ESR jako pravidlo při sestavování indexu

Není možné vytvořit univerzální index, který bude fungovat stejně rychle pro všechny úlohy; pokud ho uděláte univerzálním, neposkytne maximální nárůst rychlosti.

V realitě vývoje je obvykle na výběr jedno nebo druhé řešení, protože index není vzduch a zabírá jak paměť, tak ovlivňuje výkon. Chci hned říct, že sestavení indexu je super aplikovaná záležitost, řešení pro jednu databázi nemusí být vhodná pro řešení v jiné. Ale po anglickém internetu koluje pravidlo (setkal jsem se s ním mimochodem i v jiných ruskojazyčných článcích na Habru) ESR (Equality, Sort, Range).

ESR – označuje, že v složených klíčích pro B-strom jsou nejprve sloupce s ekvivalencí, poté řazení a nakonec rozsahy.

Co je pravidlo ESR?

ESR = Rovnost → Seřadit → Rozsah

Při vytváření kompozitního indexu B-stromu:

• E – Rovnost: nejprve sloupce, pro které dotaz obsahuje =
• S — Seřadit: pak ty, podle kterých se provádí řazení (ORDER BY)
• R — Rozsah: a pouze na konci – sloupce s rozsahy (>,

V oficiální dokumentaci je v rámci tohoto pravidla pouze 1 odstavec.

Vícesloupcový B-stromový index lze použít s dotazovacími podmínkami, které zahrnují jakoukoli podmnožinu sloupců indexu, ale index je nejefektivnější, když existují omezení na úvodní (nejlevější) sloupce. Přesné pravidlo je, že k omezení části indexu, která se prohledává, se použijí omezení rovnosti na úvodní sloupce a jakákoli omezení nerovnosti na prvním sloupci, který nemá omezení rovnosti. Omezení na sloupcích napravo od těchto sloupců se v indexu kontrolují, takže šetří návštěvy samotné tabulky, ale nesnižují část indexu, která musí být prohledávána. Například pro index na (a, b, c) a dotazovací podmínku KDE a = 5 A b >= 42 A c < 77 by musel být index prohledáván od první položky s a = 5 a b = 42 až po poslední položku s a = 5. Položky indexu s c >= 77 by byly přeskočeny, ale i tak by musely být prohledávány. Tento index by se v principu dal použít pro dotazy, které mají omezení na b a/nebo c bez omezení na a – ale musel by se prohledat celý index, takže ve většině případů by plánovač preferoval sekvenční prohledávání tabulky před použitím indexu.

Ukažme si to v praxi

Nejprve si definujme potřebu

Z naší tabulky chceme získat odesílatele nikoli pro konkrétní datum, ale pro časové období a podle typů plateb (pro bankovní reportingovou službu je to zcela komerční úkol).

Potřeba je nalezena, nyní si představme, že záznamů není 100 000, ale mnohem více (obrovská produkční databáze s bankovními historiemi). Přijdou za námi a říkají, že dotaz je příliš pomalý a obvyklá indexace podle sender_id funguje příliš pomalu.

Přidejme další data

INSERT INTO bank_transactions (sender_id, receiver_id, amount, transaction_date, payment_type) SELECT (random() * 1_000_000)::int, -- sender_id (random() * 1_000_000)::int, ROUND((random() * 10000)::numeric, 2), DATE '2020-01-01' + (random() * 2000)::int, (ARRAY['СБП', 'SWIFT', 'ВНУТРЕННИЙ', 'Межбанк'])[floor(random() * 4)::int + 1] FROM generate_series(1, 10_000_000); 

Také přidáme 10 000 záznamů konkrétně pod každým sender_id.
Hned zdůrazním – toto je děláno výhradně pro demonstraci logiky fungování PostgreSQL pod zátěží. Záměrně nemodeluji produkční tabulku – neexistuje způsob, jak reprodukovat její objem a zdroje.
Ano, s malým množstvím dat PostgreSQL často volí optimální plány i s neoptimální strukturou indexů – optimalizátor má čas vše pečlivě doladit, najít dobrý plán a pracovat i se špatnou datovou strukturou.
To ale neznamená, že v produkčním prostředí bude všechno stejné. Je tu tvrdý boj o zdroje, cache nejsou nekonečné a plánovač nebude mít vždy šanci „zachránit“ zářezy ve struktuře indexů nebo dotazů. Co funguje v testu s 10 řádky, může snadno zhroutit produkci s miliony. Proto je důležité modelovat zátěž.

INSERT INTO bank_transactions (sender_id, receiver_id, amount, transaction_date, payment_type) SELECT sender_id, (random() * 1000000)::int, ROUND((random() * 10000)::numeric, 2), DATE '2020-01-01' + (random() * 1860)::int, (ARRAY['СБП', 'SWIFT', 'Межбанк', 'ВНУТРЕННИЙ'])[floor(random() * 4)::int + 1] FROM generate_series(1, 10000) AS sender_id, generate_series(1, 1000); -- Запрос EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM bank_transactions WHERE bank_transactions.sender_id = 444 AND bank_transactions.transaction_date < '2025-05-18' AND bank_transactions.transaction_date >'2020-04-18' AND bank_transactions.payment_type = 'СБП' -- План Seq Scan on bank_transactions (cost=0.00..871550.86 rows=3541467 width=35) (actual time=5416.344..6795.770 rows=222 loops=1) Filter: ((transaction_date < '2025-05-18'::date) AND (transaction_date >'2020-04-18'::date) AND (sender_id = 444) AND (payment_type = 'СБП'::text)) Rows Removed by Filter: 20999762 Buffers: shared hit=258 read=252001 Planning: Buffers: shared hit=3 read=2 dirtied=1 Planning Time: 1.006 ms Execution Time: 6795.867 ms

Jak data rostla, přestali jsme používat indexování podle sender_id – řádků bylo příliš mnoho (21 milionů) a bylo obtížné z nich pomocí sender_id extrahovat něco dobrého, takže se plánovač rozhodl použít běžné vyhledávání napříč všemi daty.

Při výběru pořadí sloupců v indexu je často hlavním kritériem selektivita – začněme s tímto kritériem.

1. sender_id – pole pro složení dat, lepší než prohlížení hromady plateb za dané datum
2. transaction_date – když najdeme data o uživateli, můžeme snadno iterovat přes data
3. payment_type je nejméně selektivní pole

-- Индекс CREATE INDEX idx_sender_date_type ON bank_transactions (sender_id, transaction_date, payment_type); -- План Index Scan using idx_sender_date_type on bank_transactions (cost=0.56..254.61 rows=83 width=35) (actual time=0.034..0.325 rows=222 loops=1) Index Cond: ((sender_id = 444) AND (transaction_date < '2025-05-18'::date) AND (transaction_date >'2020-04-18'::date) AND (payment_type = 'СБП'::text)) Buffers: shared hit=230 Planning Time: 0.133 ms Execution Time: 0.354 ms

Na první pohled se to zdá perfektní. Ale stojí za zamyšlení: funguje všechno opravdu tak, jak očekáváme?
Tady se musíme zamyslet nad tím, zda nám ukazují, jak to funguje zevnitř?
Zkusme vytvořit index podle ESR (v rámci každé kategorie – podle selektivity)

Přidám index bez odstranění idx_sender_date_type a nechám PostgreSQL rozhodnout, který index má použít.

-- Индекс CREATE INDEX idx_sender_type_date ON bank_transactions (sender_id, payment_type, transaction_date); -- План Index Scan using idx_sender_type_date on bank_transactions (cost=0.56..246.88 rows=83 width=35) (actual time=0.037..0.184 rows=222 loops=1) Index Cond: ((sender_id = 444) AND (payment_type = 'СБП'::text) AND (transaction_date < '2025-05-18'::date) AND (transaction_date >'2020-04-18'::date)) Buffers: shared hit=226 Planning Time: 0.108 ms Execution Time: 0.204 ms

I s plně zahřátým ukládáním do mezipaměti PostgreSQL používá méně uzlů B-stromu a provede indexový průchod rychleji, pokud pořadí sloupců v indexu odpovídá pořadí ESR

Je důležité si uvědomit, proč tomu tak je a proč se to nemusí zdát zřejmé.
Když PostgreSQL prochází index, okamžitě vybere ty potřebné a nezobrazí se nic jako „Řádky odstraněné filtrem“, pouze okamžitě vybere potřebné a nepotřebné odřízne.

Vizuálně to vypadá takto:

Závěr

Volba pořadí sloupců v kompozitním indexu B-stromu není otázkou vkusu, ale technickým a architektonickým rozhodnutím založeným na logice přístupu k datům.
Pravidlo ESR (rovnost, řazení, rozsah) — toto není magický vzorec, ale funkční princip, potvrzený plány, buffery, dobou provádění a volbou plánovače PostgreSQL (Bůh mu žehnej).
Dobře promyšlený návrh kompozitních indexů je v PostgreSQL kritickým faktorem výkonu. Pravidlo ESR nenahrazuje analýzu, ale pomáhá vytvořit efektivní strategii pro tvorbu indexů. S rostoucím objemem dat je to rozdíl mezi okamžitou odpovědí a minutovým čekáním.
Uvažovali jsme o pravidle pro dobré zátěže (připouštím, že model se může lišit od skutečných dat, zde se vše dělo skriptem a pseudonáhodně).
No, VYSVĚTLOVAT (ANALÝZOVAT, VYROVNAT) je tvůj nejlepší přítel, nevěř mi jen tak na slovo.

Toto je můj první článek, budu rád za opravy a diskuzi.