Skipping indexy ClickHouse: bloom, set, minmax

Sekundární (skipping) indexy v ClickHouse: když index podle ORDER BY nestačí

V běžných databázích (PostgreSQL, MySQL) je index struktura, která ukazuje přesně na řádky splňující podmínku. B-strom říká: „Hodnota user_id = 123 je v řádku č. 45678“.

V ClickHouse funguje hlavní index (sparse index podle ORDER BY) jinak. Ukládá hodnoty pouze pro každý 8192. řádek (granulu) a dokáže efektivně odřezávat celé bloky dat pro sloupce, které jsou na začátku ORDER BY.

Ale co když potřebuješ vyhledávat podle sloupce, který není v ORDER BY? Například chceš najít všechny sázky s určitou IP adresou, ale máš ORDER BY = (user_id, created_at). ClickHouse bude muset přečíst všechny granule a IP odfiltrovat až po načtení. Tomu se říká full scan.

Sekundární (skipping) indexy tento problém řeší. Neukazují na konkrétní řádky, ale říkají: „V tomto bloku N granulí určitě není taková hodnota, můžeš ho přeskočit.“ Pokud index řekne „možná“ – ClickHouse blok stejně přečte.

Přirovnání ze života: Představ si, že hledáš knihu se zeleným obalem v knihovně. Hlavní index (katalog podle příjmení autora) nepomáhá. Ale procházíš kolem polic a rychle se podíváš: „Na této polici jsou všechny knihy modré – přeskočím. Na této polici jsou zelené – zkontroluji.“ Skipping index je jako barevné označení polic, ne přesný ukazatel.

Proč se jim říká skipping? Protože hlavní práce indexu je přeskočit (skip) bloky, které určitě nejsou potřeba. Čím více bloků je přeskočeno, tím rychlejší dotaz.

Důležité omezení: Skipping indexy fungují pouze na úrovni granulí. Nemohou najít přesnou pozici řádku uvnitř granule. Index je tedy užitečný, když se hledaná hodnota vyskytuje zřídka (nízká selektivita). Pokud 80 % řádků splňuje podmínku – stejně budeš muset přečíst všechno.

2. INDEX ... TYPE minmax – pro rozsahové dotazy

Nejjednodušší skipping index je minmax. Ukládá pro každou skupinu granulí minimální a maximální hodnotu sloupce.

CREATE TABLE player_events
(
    user_id     UInt64,
    event_time  DateTime,
    amount      Decimal(18,2),
    outcome     String      -- 'win', 'loss', 'push'
)
ENGINE = MergeTree()
ORDER BY (user_id, event_time)              -- hlavní pořadí
INDEX idx_outcome_minmax outcome TYPE minmax GRANULARITY 4;

Rozbor parametrů:

• INDEX idx_outcome_minmax – název indexu (vymysli si vlastní, ale smysluplný).
• outcome – sloupec, podle kterého se index vytváří.
• TYPE minmax – typ indexu: ukládá min a max hodnoty ve skupině granulí.
• GRANULARITY 4 – kolik granulí (po 8192 řádcích) se spojí do jedné skupiny pro index. Zde 4 × 8192 = 32768 řádků na jeden záznam v indexu.

Jak to funguje v dotazu:

-- Hledáme události s určitým výsledkem
SELECT * FROM player_events 
WHERE outcome = 'win' AND event_time >= '2025-06-01';

ClickHouse přečte index idx_outcome_minmax:

• Skupina 1: min='loss', max='push' → není 'win' → přeskočíme 32768 řádků.
• Skupina 2: min='loss', max='win' → je 'win' → přečteme tuto skupinu.
• Skupina 3: min='win', max='win' → pouze 'win' → přečteme.

Kdy je minmax efektivní:

• Sloupce s monotónní změnou (čas, ID, teplota).
• Sloupce s malým počtem unikátních hodnot, ale nerovnoměrně rozložených.
• Dotazy s rozsahem (BETWEEN, >=, <=).

Kdy je zbytečný:

• Hodnoty jsou náhodné (např. hash, UUID). Min a max budou pokrývat celý rozsah, index nic neodřízne.

3. INDEX ... TYPE set – pro rovnost podle sloupců s malou kardinalitou

set index ukládá unikátní hodnoty pro skupinu granulí. Pokud hledaná hodnota v této množině není – skupina se přeskočí.

CREATE TABLE bets
(
    user_id     UInt64,
    sport_id    UInt8,      -- celkem 20 sportů
    amount      Decimal(18,2),
    created_at  DateTime
)
ENGINE = MergeTree()
ORDER BY (created_at, user_id)
INDEX idx_sport sport_id TYPE set(10) GRANULARITY 2;

Parametry:

• set(10) – maximální počet unikátních hodnot, které index pro skupinu uloží. Pokud se ve skupině vyskytne více než 10 unikátních sport_id, index si zapamatuje jen 10 (a může dát falešný signál). Vyber číslo o něco větší, než je očekávaná kardinalita sloupce.

Jak to funguje:

-- Dotaz na konkrétní sport
SELECT sum(amount) FROM bets WHERE sport_id = 1;

Index idx_sport pro každou skupinu granulí ví, která sport_id se v ní vyskytují. Pokud ve skupině není sport_id=1 – přeskočíme celou skupinu. Pokud je – přečteme.

Kdy je set efektivní:

• Kardinalita sloupce je nízká (do stovek hodnot).
• Dotazy na rovnost (=, IN).
• Data jsou dobře seskupena v granulích (např. všechny fotbalové sázky za hodinu leží kompaktně).

Příklad z gamingu: Tabulka sázek s ORDER BY (created_at, user_id). Sloupec sport_id (20 hodnot) není v ORDER BY. Index set na sport_id umožní rychle najít všechny sázky na hokej, aniž by se skenovalo všechno.

4. bloom_filter index – pro textové sloupce s vysokou kardinalitou

Bloom filter (Bloomův filtr) je pravděpodobnostní datová struktura. Dokáže říct „hodnota ve skupině určitě není“ nebo „hodnota možná je“. Nikdy neřekne „určitě je“ – může se splést jen směrem k falešnému signálu.

CREATE TABLE player_events
(
    user_id     UInt64,
    ip_address  String,          -- miliony unikátních IP
    event_type  String,
    created_at  DateTime
)
ENGINE = MergeTree()
ORDER BY (user_id, created_at)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 3;

Parametry:

• bloom_filter(0.01) – pravděpodobnost falešného signálu (false positive rate) 1 %. Čím menší číslo, tím přesnější index, ale zabírá více místa. Obvykle se používá 0.01 (1 %) nebo 0.001 (0,1 %).
• GRANULARITY 3 – 3 granule (3 × 8192 = 24576 řádků) na jeden záznam v indexu.

Jak to funguje:

-- Najít všechny události z podezřelé IP
SELECT * FROM player_events WHERE ip_address = '192.168.1.100';

Index pro každou skupinu granulí zkontroluje pomocí bloom filteru: „Může být v této skupině IP=192.168.1.100?“ Pokud je odpověď „ne“ – skupina se přeskočí. Pokud „ano“ (včetně falešných signálů) – skupina se přečte.

Kdy je bloom filter efektivní:

• Sloupce s vysokou kardinalitou (IP adresy, email, user_agent).
• Dotazy na přesnou shodu.
• Hledané hodnoty jsou vzácné (např. konkrétní IP z 10 milionů).

Proč minmax není vhodný pro IP: Kvůli náhodnému rozložení budou min a max IP ve skupině pokrývat téměř celý rozsah, odřezání nefunguje.

Reálný příklad – hledání multiúčtů (jedna IP, mnoho user_id):

-- Najít všechny uživatele z dané IP
SELECT DISTINCT user_id FROM player_events 
WHERE ip_address = '192.168.1.100';

Bez indexu – plné skenování. S bloom_filter na ip_address – rychlé, i když se IP vyskytuje v 0,1 % řádků.

5. ngrambf_v1 – pro LIKE/ILIKE vyhledávání v textech

Někdy je potřeba hledat podle části řetězce: WHERE player_name LIKE '%John%'. Běžné indexy nepomáhají, protože % na začátku zakazuje použití B-stromu.

ngrambf_v1 rozdělí řetězec na n-gramy – podřetězce délky N. Například pro N=3, 'Johny' → 'Joh', 'ohn', 'hny'. Index vytvoří bloom filter na těchto n-gramech.

CREATE TABLE players
(
    player_id   UInt64,
    player_name String,
    country     String
)
ENGINE = MergeTree()
ORDER BY player_id
INDEX idx_name player_name TYPE ngrambf_v1(3, 500000, 2, 0.01) GRANULARITY 4;

Parametry ngrambf_v1:

• 3 – délka n-gramu (obvykle 2–4). Čím větší, tím přesnější, ale více paměti.
• 500000 – velikost bloom filteru v bajtech na jeden záznam indexu.
• 2 – počet hashovacích funkcí (obvykle 2–4).
• 0.01 – pravděpodobnost falešného signálu.

Jak použít v dotazu:

-- Najít hráče se jménem obsahujícím 'Alex'
SELECT * FROM players WHERE player_name LIKE '%Alex%';

Index rozdělí 'Alex' na n-gramy ('Ale', 'lex') a zkontroluje, zda jsou tyto n-gramy ve skupinách. Pokud skupina neobsahuje žádný z těchto n-gramů – přeskočí se.

Omezení:

• Funguje pouze s LIKE a ILIKE (nezávislé na velikosti písmen).
• Vyžaduje, aby hledaný řetězec byl delší než n-gram (alespoň 3 znaky).
• Není vhodný pro hledání krátkých řetězců (např. 'a').

Kdy použít: Hledání podle přezdívek hráčů, části emailu, adres. V gamingu – hledání hráče podle části jména pro podporu.

6. tokenbf_v1 – pro vyhledávání podle tokenů (slov)

tokenbf_v1 je podobný ngrambf_v1, ale rozděluje řetězec ne na překrývající se kusy, ale na tokeny – slova oddělená mezerami, interpunkcí, číslicemi.

CREATE TABLE logs
(
    log_time    DateTime,
    message     String,
    user_agent  String
)
ENGINE = MergeTree()
ORDER BY log_time
INDEX idx_msg message TYPE tokenbf_v1(500000, 2, 0.01) GRANULARITY 2;

Parametry tokenbf_v1:

• 500000 – velikost bloom filteru v bajtech.
• 2 – počet hashovacích funkcí.
• 0.01 – pravděpodobnost falešného signálu.

Jak to funguje:

Pro řetězec "User 123 logged in from Ukraine" tokeny: 'User', '123', 'logged', 'in', 'from', 'Ukraine'.

-- Najít všechny logy s chybovou hláškou
SELECT * FROM logs WHERE message LIKE '%error%';

Index rozdělí 'error' na tokeny (prostě 'error') a zkontroluje přítomnost tohoto tokenu ve skupinách.

Kdy je tokenbf_v1 lepší než ngrambf_v1:

• Hledání podle celých slov (ne částí).
• Anglické texty, logy, user_agent.
• Méně falešných signálů než u ngrambf_v1.

Příklad z gamingu: Hledání v logách sázek zpráv s 'fraud' nebo 'suspicious'.

7. Jak zkontrolovat, že se index používá – EXPLAIN indexes=1

Vytvořil jsi index, ale funguje? ClickHouse poskytuje příkaz EXPLAIN indexes = 1.

-- Zapneme analýzu použití indexů
EXPLAIN indexes = 1
SELECT user_id, amount FROM bets 
WHERE sport_id = 1 AND created_at >= '2025-06-01';

Příklad výstupu:

Expression
  ...
  ReadFromMergeTree
    Indexes:
      PrimaryKey
        Condition: (created_at >= '2025-06-01')
        Used keys: (created_at)
        Granules: 150 / 12000
      Skip
        Name: idx_sport
        Type: set
        Condition: sport_id = 1
        Granules: 80 / 12000

Co znamenají čísla:

• Granules: 150 / 12000 – primární klíč odřízl 11850 granulí, zbylo 150.
• Skip ... Granules: 80 / 150 – skipping index dále odřízl 70 granulí, zbylo 80.
• Konečný zisk: 12000 → 80 přečtených granulí.

Pokud se index nepoužívá:

• Nezobrazuje se v sekci Skip – buď není vytvořen, nebo dotaz neodpovídá typu indexu.
• Granules: 12000 / 12000 – čteme vše, index nepomohl.

Proč se index nemusí použít:

• Typ indexu neodpovídá operátoru (minmax pro = není efektivní).
• Granularita je příliš velká (index je hrubý).
• Hledaná hodnota se vyskytuje téměř všude (index nemůže bloky přeskočit).

8. Kdy skipping indexy NEPOMÁHAJÍ

Situace 1: Vysoká kardinalita + náhodné rozložení

Pokud má sloupec user_id (miliony hodnot) a ORDER BY nezačíná user_id, skipping index (dokonce i bloom_filter) bude bloky odřezávat špatně. Protože hodnota user_id=123 může být rozptýlena po celé tabulce.

Situace 2: Dotaz bez filtrování podle „dobrých“ sloupců

Indexy na sport_id nepomohou, pokud je v WHERE pouze amount > 1000 a na amount není index.

Situace 3: Příliš velká GRANULARITY

Pokud GRANULARITY = 64 (524k řádků na skupinu) a tvoje tabulka obsahuje 10 milionů řádků, bude skupin jen ~20. Přeskočit lze jen 20 bloků, což je málo.

Situace 4: Hledaná hodnota se vyskytuje v 50 %+ řádků

Skipping indexy jsou dobré pro vzácné hodnoty. Pokud polovina řádků splňuje podmínku, indexy budou říkat „možná“ téměř pro všechny bloky a přečteš všechno.

Situace 5: Index je příliš malý

-- Špatně: příliš malý bloom filter (10000 bajtů)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 4;

Malý bloom filter dává mnoho falešných signálů (často říká „možná“, i když ve skutečnosti není). Index přestane bloky přeskakovat.

9. Cena skipping indexů – paměť a rychlost vkládání

Každý index má svou cenu. Nevytvářej indexy „pro jistotu“.

Cena č. 1: Dodatečné místo na disku

• minmax – velmi levné (8 bajtů na skupinu na sloupec).
• set(100) – dražší, ale v řádu tisíců bajtů na skupinu.
• bloom_filter – drahé: při velikosti 500k bajtů a GRANULARITY=1, pro tabulku s 10k skupinami = 5 GB jen na index.

Cena č. 2: Zpomalení INSERT

Při každém vkládání ClickHouse aktualizuje všechny indexy pro každou granuli. 5 indexů na tabulku může zpomalit vkládání 2-3krát.

Pravidlo:

• Ne více než 2-3 skipping indexy na velkou tabulku (miliardy řádků).
• Indexy pouze na sloupce, podle kterých se skutečně často filtruje.
• Pro testovací zátěž – experimentuj. Pro produkci – měř.

Jak odhadnout cenu indexu:

-- Podíváme se na velikost indexů v tabulce
SELECT 
    table,
    index_name,
    formatReadableSize(index_size) AS size
FROM system.indexes
WHERE table = 'bets';

Pokud se velikost indexu blíží velikosti dat – možná jsi to přehnal.

10. Reálný příklad: fraud detection podle IP adresy

Představ si, že ve tvém casinu skupina hráčů používá jednu IP adresu pro multiúčty (zakázáno pravidly). Potřebuješ najít všechny, kteří přistupovali z podezřelé IP.

Tabulka událostí:

• 500 milionů řádků.
• ORDER BY = (user_id, event_time) – rychlé dotazy podle uživatele.
• Častý dotaz: SELECT user_id FROM events WHERE ip_address = 'x.x.x.x'.

Řešení – bloom_filter index:

CREATE TABLE player_events
(
    user_id     UInt64,
    event_time  DateTime,
    ip_address  String,
    event_type  String,   -- 'login', 'bet', 'withdraw'
    amount      Decimal(18,2)
)
ENGINE = MergeTree()
PARTITION BY toYYYYMM(event_time)
ORDER BY (user_id, event_time)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 4;

Srovnání výkonu:

Scénář	Bez indexu	S bloom_filter (0.01)
Doba dotazu na vzácnou IP (0,001 % řádků)	60 sekund (full scan 500M)	0,3 sekundy
Doba dotazu na častou IP (5 % řádků)	60 sekund	45 sekund (index málo pomáhá)
Velikost tabulky (komprimované)	100 GB	108 GB (+8 %)
Doba INSERT (10k řádků/s)	0,5 ms na dávku	0,7 ms na dávku (+40 %)

Jak napsat dotaz pro antifraud:

-- Najít všechny uživatele, kteří kdy použili podezřelou IP
SELECT DISTINCT user_id 
FROM player_events 
WHERE ip_address = '192.168.1.100'   -- bloom_filter pomáhá
AND event_time >= today() - 30;      -- oddíly odříznou stará data

-- Pak zkontrolovat, kolik různých účtů používá tuto IP
SELECT count(DISTINCT user_id) AS suspicious_accounts
FROM player_events 
WHERE ip_address = '192.168.1.100';

Proč bloom_filter, a ne minmax:

• IP adresy jsou rozloženy náhodně, min/max ve skupině budou téměř vždy pokrývat celý rozsah.
• Bloom filter je ideální pro kontrolu příslušnosti k množině.

Co dál

Teď znáš všechny typy sekundárních indexů v ClickHouse. Další témata:

• Kombinování indexů – jak několik skipping indexů pracuje dohromady.
• Nastavení granularity – jak zvolit optimální velikost granule pro různé typy dat.
• Indexy v distribuovaných tabulkách – jak skipping indexy fungují v clusteru.

Shrnutí: Skipping indexy v ClickHouse nejsou stříbrná kulka. Nepracují jako B-stromy v PostgreSQL. Ale pro správné scénáře (vzácné hodnoty, bloom filter, n-gramy) promění plná skenování v bleskové dotazy. Hlavní pravidla:

• Nevytvářej indexy, dokud neuvidíš problém (full scan).
• Začínej s bloom_filter pro vysoce kardinální sloupce, s set pro nízko kardinální.
• Vždy kontroluj EXPLAIN indexes = 1.
• Pamatuj na cenu: místo na disku + zpomalení INSERT.

---

← Předchozí: Materializovaná zobrazení v ClickHouse: síla inkrementálního zpracování

— Editorial Team