Skipping indeksy ClickHouse: bloom, set, minmax

Indeksy wtórne (skipping) w ClickHouse: gdy indeks po ORDER BY nie wystarcza

W tradycyjnych bazach danych (PostgreSQL, MySQL) indeks to struktura, która wskazuje dokładnie na wiersze spełniające warunek. B-drzewo mówi: „Wartość user_id = 123 znajduje się w wierszu nr 45678”.

W ClickHouse główny indeks (sparse index po ORDER BY) działa inaczej. Przechowuje wartości tylko dla co 8192. wiersza (granuli) i może efektywnie odcinać całe bloki danych dla kolumn znajdujących się na początku ORDER BY.

Ale co, jeśli potrzebujesz wyszukiwać po kolumnie, która nie wchodzi w skład ORDER BY? Na przykład chcesz znaleźć wszystkie zakłady z określonym adresem IP, ale masz ORDER BY = (user_id, created_at). ClickHouse będzie musiał odczytać wszystkie granule i odfiltrować IP dopiero po odczycie. To się nazywa full scan.

Indeksy wtórne (skipping) rozwiązują ten problem. Nie wskazują konkretnych wierszy, ale mówią: „W tym bloku N granuli na pewno nie ma takiej wartości, możesz go pominąć”. Jeśli indeks mówi „może być” — ClickHouse i tak odczytuje blok.

Analogia z życia: Wyobraź sobie, że szukasz książki z zieloną okładką w bibliotece. Główny indeks (katalog według nazwiska autora) nie pomaga. Ale przechodzisz obok półek i szybko sprawdzasz: „Na tej półce wszystkie książki są niebieskie — pomijam. Na tej półce są zielone — sprawdzę”. Indeks skipping to jak kolorowe oznaczenia półek, a nie dokładny wskaźnik.

Dlaczego nazywają się skipping? Ponieważ głównym zadaniem indeksu jest pominięcie (skip) bloków, które na pewno nie są potrzebne. Im więcej bloków pominięto, tym szybsze zapytanie.

Ważne ograniczenie: Indeksy skipping działają tylko na poziomie granuli. Nie mogą znaleźć dokładnej pozycji wiersza wewnątrz granuli. Dlatego indeks jest przydatny, gdy poszukiwana wartość występuje rzadko (niska selektywność). Jeśli 80% wierszy spełnia warunek — i tak trzeba odczytać wszystko.

2. INDEX ... TYPE minmax — dla zapytań zakresowych

Najprostszy indeks skipping — minmax. Przechowuje dla każdej grupy granuli minimalną i maksymalną wartość kolumny.

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)              -- główny porządek
INDEX idx_outcome_minmax outcome TYPE minmax GRANULARITY 4;

Omówienie parametrów:

• INDEX idx_outcome_minmax — nazwa indeksu (wymyśl sam, ale sensownie).
• outcome — kolumna, na której budowany jest indeks.
• TYPE minmax — typ indeksu: przechowuje min i max wartości w grupie granuli.
• GRANULARITY 4 — ile granuli (po 8192 wierszy każda) jest łączonych w jedną grupę dla indeksu. Tutaj 4 × 8192 = 32768 wierszy na jeden wpis w indeksie.

Jak to działa w zapytaniu:

-- Szukamy zdarzeń z określonym wynikiem
SELECT * FROM player_events 
WHERE outcome = 'win' AND event_time >= '2025-06-01';

ClickHouse odczytuje indeks idx_outcome_minmax:

• Grupa 1: min='loss', max='push' → brak 'win' → pomijamy 32768 wierszy.
• Grupa 2: min='loss', max='win' → jest 'win' → odczytujemy tę grupę.
• Grupa 3: min='win', max='win' → tylko 'win' → odczytujemy.

Kiedy minmax jest efektywny:

• Kolumny o monotonicznej zmianie (czas, ID, temperatura).
• Kolumny z małą liczbą unikalnych wartości, ale rozłożonych nierównomiernie.
• Zapytania z zakresem (BETWEEN, >=, <=).

Kiedy jest bezużyteczny:

• Wartości są losowe (np. hash, UUID). Min i max będą pokrywać cały zakres, indeks niczego nie pominie.

3. INDEX ... TYPE set — dla równości na kolumnach o małej kardynalności

Indeks set przechowuje unikalne wartości dla grupy granuli. Jeśli szukanej wartości nie ma w tym zbiorze — grupa jest pomijana.

CREATE TABLE bets
(
    user_id     UInt64,
    sport_id    UInt8,      -- tylko 20 dyscyplin
    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) — maksymalna liczba unikalnych wartości, jaką indeks będzie przechowywać dla grupy. Jeśli w grupie wystąpi więcej niż 10 unikalnych sport_id, indeks zapamięta tylko 10 (i może dać fałszywe trafienie). Wybierz liczbę nieco większą niż oczekiwana kardynalność kolumny.

Jak to działa:

-- Zapytanie o konkretną dyscyplinę
SELECT sum(amount) FROM bets WHERE sport_id = 1;

Indeks idx_sport dla każdej grupy granuli wie, jakie sport_id występują. Jeśli w grupie nie ma sport_id=1 — pomijamy całą grupę. Jeśli jest — odczytujemy.

Kiedy set jest efektywny:

• Kardynalność kolumny jest niska (do setek wartości).
• Zapytania o równość (=, IN).
• Dane są dobrze zgrupowane w granule (np. wszystkie zakłady piłkarskie z godziny leżą kompaktowo).

Przykład z gamingu: Tabela zakładów z ORDER BY (created_at, user_id). Kolumna sport_id (20 wartości) nie jest w ORDER BY. Indeks set na sport_id pozwoli szybko znaleźć wszystkie zakłady na hokej, bez skanowania wszystkiego.

4. Indeks bloom_filter — dla kolumn tekstowych o wysokiej kardynalności

Bloom filter (filtr Blooma) — probabilistyczna struktura danych. Może powiedzieć „wartości na pewno nie ma w grupie” lub „wartość prawdopodobnie jest”. Nigdy nie mówi „na pewno jest” — może się pomylić tylko w kierunku fałszywego trafienia.

CREATE TABLE player_events
(
    user_id     UInt64,
    ip_address  String,          -- miliony unikalnych 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) — prawdopodobieństwo fałszywego trafienia (false positive rate) 1%. Im mniejsza liczba, tym dokładniejszy indeks, ale zajmuje więcej miejsca. Zwykle używa się 0.01 (1%) lub 0.001 (0.1%).
• GRANULARITY 3 — 3 granule (3 × 8192 = 24576 wierszy) na jeden wpis w indeksie.

Jak to działa:

-- Znajdź wszystkie zdarzenia z podejrzanego IP
SELECT * FROM player_events WHERE ip_address = '192.168.1.100';

Indeks dla każdej grupy granuli sprawdza przez bloom filter: „Czy w tej grupie może być IP=192.168.1.100?” Jeśli odpowiedź brzmi „nie” — grupa jest pomijana. Jeśli „tak” (w tym fałszywe trafienia) — grupa jest odczytywana.

Kiedy bloom filter jest efektywny:

• Kolumny o wysokiej kardynalności (adresy IP, e-maile, user_agent).
• Zapytania o dokładne dopasowanie.
• Szukane wartości są rzadkie (np. konkretny IP z 10 milionów).

Dlaczego minmax nie nadaje się dla IP: Z powodu losowego rozkładu min i max IP w grupie będą pokrywać prawie cały zakres, odcięcie nie zadziała.

Prawdziwy przykład — wyszukiwanie multi-kont (jeden IP, wielu user_id):

-- Znajdź wszystkich użytkowników z danego IP
SELECT DISTINCT user_id FROM player_events 
WHERE ip_address = '192.168.1.100';

Bez indeksu — pełne skanowanie. Z bloom_filter na ip_address — szybko, nawet jeśli IP występuje w 0.1% wierszy.

5. ngrambf_v1 — dla wyszukiwania LIKE/ILIKE po ciągach znaków

Czasami trzeba szukać po fragmencie ciągu: WHERE player_name LIKE '%John%'. Zwykłe indeksy nie pomagają, ponieważ % na początku uniemożliwia użycie B-drzewa.

ngrambf_v1 dzieli ciąg na n-gramy — podciągi o długości N. Na przykład dla N=3, 'Johny' → 'Joh', 'ohn', 'hny'. Indeks buduje bloom filter na tych n-gramach.

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ługość n-gramu (zwykle 2–4). Im większa, tym dokładniejszy, ale więcej pamięci.
• 500000 — rozmiar bloom filter w bajtach na jeden wpis indeksu.
• 2 — liczba funkcji skrótu (zwykle 2–4).
• 0.01 — prawdopodobieństwo fałszywego trafienia.

Jak używać w zapytaniu:

-- Znajdź graczy z imieniem zawierającym 'Alex'
SELECT * FROM players WHERE player_name LIKE '%Alex%';

Indeks dzieli 'Alex' na n-gramy ('Ale', 'lex') i sprawdza, czy te n-gramy występują w grupach. Jeśli w grupie nie ma żadnego z tych n-gramów — grupa jest pomijana.

Ograniczenia:

• Działa tylko z LIKE i ILIKE (niezależny od wielkości liter).
• Wymaga, aby wyszukiwany ciąg był dłuższy niż n-gram (minimum 3 znaki).
• Nie nadaje się do wyszukiwania krótkich ciągów (np. 'a').

Kiedy używać: Wyszukiwanie po nickach graczy, fragmentach e-maili, adresach. W gamingu — wyszukiwanie gracza po fragmencie imienia dla supportu.

6. tokenbf_v1 — dla wyszukiwania po tokenach (słowach)

tokenbf_v1 jest podobny do ngrambf_v1, ale dzieli ciąg nie na nakładające się kawałki, ale na tokeny — słowa oddzielone spacjami, interpunkcją, cyframi.

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 — rozmiar bloom filter w bajtach.
• 2 — liczba funkcji skrótu.
• 0.01 — prawdopodobieństwo fałszywego trafienia.

Jak to działa:

Dla ciągu "User 123 logged in from Ukraine" tokeny: 'User', '123', 'logged', 'in', 'from', 'Ukraine'.

-- Znajdź wszystkie logi z wzmianką o błędzie
SELECT * FROM logs WHERE message LIKE '%error%';

Indeks dzieli 'error' na tokeny (po prostu 'error') i sprawdza obecność tego tokena w grupach.

Kiedy tokenbf_v1 jest lepszy od ngrambf_v1:

• Wyszukiwanie po całych słowach (a nie fragmentach).
• Teksty anglojęzyczne, logi, user_agent.
• Mniej fałszywych trafień niż w ngrambf_v1.

Przykład z gamingu: Wyszukiwanie w logach zakładów wiadomości z 'fraud' lub 'suspicious'.

7. Jak sprawdzić, czy indeks jest używany — EXPLAIN indexes=1

Stworzyłeś indeks, ale czy działa? ClickHouse udostępnia polecenie EXPLAIN indexes = 1.

-- Włączamy analizę użycia indeksów
EXPLAIN indexes = 1
SELECT user_id, amount FROM bets 
WHERE sport_id = 1 AND created_at >= '2025-06-01';

Przykładowy wynik:

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 oznaczają liczby:

• Granules: 150 / 12000 — klucz główny odciął 11850 granuli, zostało 150.
• Skip ... Granules: 80 / 150 — indeks skipping dodatkowo odciął 70 granuli, zostało 80.
• Końcowy zysk: 12000 → 80 odczytanych granuli.

Jeśli indeks nie jest używany:

• Nie pojawia się w sekcji Skip → albo nie został utworzony, albo zapytanie nie pasuje do typu indeksu.
• Granules: 12000 / 12000 — czytamy wszystko, indeks nie pomógł.

Dlaczego indeks może nie być używany:

• Typ indeksu nie odpowiada operatorowi (minmax dla = jest nieefektywny).
• Granularność jest zbyt duża (indeks jest zgrubny).
• Szukana wartość występuje prawie wszędzie (indeks nie może pominąć bloków).

8. Kiedy indeksy skipping NIE pomagają

Sytuacja 1: Wysoka kardynalność + losowy rozkład

Jeśli kolumna user_id (miliony wartości) i ORDER BY nie zaczyna się od user_id, indeks skipping (nawet bloom_filter) będzie słabo odcinać bloki. Ponieważ wartość user_id=123 może być rozrzucona po całej tabeli.

Sytuacja 2: Zapytanie bez filtrowania po „dobrych” kolumnach

Indeksy na sport_id nie pomogą, jeśli w WHERE jest tylko amount > 1000 i na amount nie ma indeksu.

Sytuacja 3: Zbyt duża GRANULARITY

Jeśli GRANULARITY = 64 (524k wierszy na grupę), a twoja tabela zawiera 10 mln wierszy, grup będzie tylko ~20. Można pominąć tylko 20 bloków, co jest mało.

Sytuacja 4: Szukana wartość występuje w 50%+ wierszy

Indeksy skipping są dobre dla rzadkich wartości. Jeśli połowa wierszy spełnia warunek, indeksy będą mówić „może być” dla prawie wszystkich bloków, i odczytasz wszystko.

Sytuacja 5: Indeks jest zbyt mały

-- Źle: zbyt mały bloom filter (10000 bajtów)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 4;

Mały bloom filter daje wiele fałszywych trafień (często mówi „może być”, gdy w rzeczywistości nie ma). Indeks przestaje pomijać bloki.

9. Koszt indeksów skipping — pamięć i szybkość wstawiania

Każdy indeks ma swoją cenę. Nie twórz indeksów „na wszelki wypadek”.

Koszt nr 1: Dodatkowe miejsce na dysku

• minmax — bardzo tanio (8 bajtów na grupę na kolumnę).
• set(100) — drożej, ale w granicach tysięcy bajtów na grupę.
• bloom_filter — drogo: przy rozmiarze 500k bajtów i GRANULARITY=1, dla tabeli z 10k grup = 5 GB tylko na indeks.

Koszt nr 2: Spowolnienie INSERT

Przy każdym wstawieniu ClickHouse aktualizuje wszystkie indeksy dla każdej granuli. 5 indeksów na tabelę może spowolnić wstawianie 2-3 razy.

Zasada:

• Nie więcej niż 2-3 indeksy skipping na dużą tabelę (miliardy wierszy).
• Indeksy tylko na kolumny, po których rzeczywiście często filtrujesz.
• Dla testowego obciążenia — eksperymentuj. Dla produkcji — mierz.

Jak oszacować koszt indeksu:

-- Sprawdzamy rozmiar indeksów w tabeli
SELECT 
    table,
    index_name,
    formatReadableSize(index_size) AS size
FROM system.indexes
WHERE table = 'bets';

Jeśli rozmiar indeksu jest bliski rozmiarowi danych — prawdopodobnie przesadziłeś.

10. Prawdziwy przykład: fraud detection po adresie IP

Wyobraź sobie, że w twoim kasynie grupa graczy używa jednego adresu IP do multi-kont (zabronione regulaminem). Trzeba znaleźć wszystkich, którzy logowali się z podejrzanego IP.

Tabela zdarzeń:

• 500 milionów wierszy.
• ORDER BY = (user_id, event_time) — szybkie zapytania po użytkowniku.
• Częste zapytanie: SELECT user_id FROM events WHERE ip_address = 'x.x.x.x'.

Rozwiązanie — indeks bloom_filter:

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;

Porównanie wydajności:

Scenariusz	Bez indeksu	Z bloom_filter (0.01)
Czas zapytania dla rzadkiego IP (0.001% wierszy)	60 sekund (full scan 500M)	0.3 sekundy
Czas zapytania dla częstego IP (5% wierszy)	60 sekund	45 sekund (indeks mało pomaga)
Rozmiar tabeli (skompresowanej)	100 GB	108 GB (+8%)
Czas INSERT (10k wierszy/s)	0.5 ms na paczkę	0.7 ms na paczkę (+40%)

Jak napisać zapytanie do antyfraudu:

-- Znajdź wszystkich użytkowników, którzy kiedykolwiek użyli podejrzanego IP
SELECT DISTINCT user_id 
FROM player_events 
WHERE ip_address = '192.168.1.100'   -- bloom_filter pomaga
AND event_time >= today() - 30;      -- partycje odcinają stare dane

-- Następnie sprawdź, ile różnych kont używa tego IP
SELECT count(DISTINCT user_id) AS suspicious_accounts
FROM player_events 
WHERE ip_address = '192.168.1.100';

Dlaczego bloom_filter, a nie minmax:

• Adresy IP są rozłożone losowo, min/max w grupie będą prawie zawsze pokrywać cały zakres.
• Bloom filter jest idealny do sprawdzania przynależności do zbioru.

Co dalej

Teraz znasz wszystkie typy indeksów wtórnych ClickHouse. Następne tematy:

• Łączenie indeksów — jak kilka indeksów skipping działa razem.
• Dostrajanie granularności — jak dobrać optymalny rozmiar granuli dla różnych typów danych.
• Indeksy w tabelach rozproszonych — jak indeksy skipping działają w klastrze.

Podsumowanie: Indeksy skipping w ClickHouse to nie srebrna kula. Nie działają jak B-drzewa w PostgreSQL. Ale dla odpowiednich scenariuszy (rzadkie wartości, bloom filter, n-gramy) zamieniają pełne skanowania w błyskawiczne zapytania. Główne zasady:

• Nie twórz indeksów, dopóki nie zobaczysz problemu (full scan).
• Zacznij od bloom_filter dla kolumn o wysokiej kardynalności, od set dla niskiej.
• Zawsze sprawdzaj EXPLAIN indexes = 1.
• Pamiętaj o koszcie: miejsce na dysku + spowolnienie INSERT.

---

← Poprzedni: Materializowane widoki w ClickHouse: potęga przetwarzania przyrostowego

— Editorial Team