ClickHouse-Skipping-Indizes: Bloom, Set, Minmax

Sekundäre (Skip-)Indizes in ClickHouse: Wenn der ORDER BY-Index nicht ausreicht

1. Wie Skip-Indizes funktionieren – Überspringen von Datenblöcken

In traditionellen Datenbanken (PostgreSQL, MySQL) ist ein Index eine Struktur, die exakt auf die Zeilen zeigt, die eine Bedingung erfüllen. Ein B-Baum sagt: „Wert user_id = 123 befindet sich in Zeile #45678".

In ClickHouse arbeitet der Primärindex (sparse Index nach ORDER BY) anders. Er speichert Werte nur für jede 8192. Zeile (Granula) und kann ganze Blöcke von Daten für Spalten, die früh im ORDER BY stehen, effizient ausschließen.

Aber was, wenn Sie nach einer Spalte suchen müssen, die nicht im ORDER BY steht? Zum Beispiel möchten Sie alle Wetten mit einer bestimmten IP-Adresse finden, aber Ihr ORDER BY ist (user_id, created_at). ClickHouse muss dann alle Granula lesen und die IP nach dem Lesen filtern. Das nennt man einen Full Scan.

Sekundäre (Skip-)Indizes lösen dieses Problem. Sie zeigen nicht auf bestimmte Zeilen, sondern sagen: „In diesem Block von N Granula gibt es diesen Wert definitiv nicht – Sie können ihn überspringen." Wenn der Index „vielleicht" sagt, liest ClickHouse den Block trotzdem.

Analogie aus der realen Welt: Stellen Sie sich vor, Sie suchen in einer Bibliothek ein Buch mit grünem Einband. Der Hauptindex (Katalog nach Autorennamen) hilft nicht. Aber Sie gehen an Regalen vorbei und werfen einen kurzen Blick: „Alle Bücher in diesem Regal sind blau – überspringen. Dieses Regal hat grüne – ich schaue nach." Ein Skip-Index ist wie farbcodierte Regale, kein präziser Zeiger.

Warum heißen sie Skip-Indizes? Weil die Hauptaufgabe des Index darin besteht, Blöcke zu überspringen, die definitiv nicht benötigt werden. Je mehr Blöcke übersprungen werden, desto schneller die Abfrage.

Wichtige Einschränkung: Skip-Indizes arbeiten nur auf Granula-Ebene. Sie können die genaue Zeilenposition innerhalb eines Granulums nicht finden. Daher ist der Index nützlich, wenn der gesuchte Wert selten ist (niedrige Selektivität). Wenn 80 % der Zeilen die Bedingung erfüllen, müssen Sie trotzdem alles lesen.

2. INDEX ... TYPE minmax – Für Bereichsabfragen

Der einfachste Skip-Index ist minmax. Er speichert den minimalen und maximalen Wert einer Spalte für jede Gruppe von Granula.

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)              -- primäre Ordnung
INDEX idx_outcome_minmax outcome TYPE minmax GRANULARITY 4;

Aufschlüsselung der Parameter:

• INDEX idx_outcome_minmax – Indexname (frei wählbar, aber aussagekräftig).
• outcome – Spalte, auf der der Index aufgebaut wird.
• TYPE minmax – Indextyp: speichert Min- und Max-Werte in einer Gruppe von Granula.
• GRANULARITY 4 – Wie viele Granula (jeweils 8192 Zeilen) zu einer Gruppe für den Index zusammengefasst werden. Hier 4 × 8192 = 32768 Zeilen pro Indexeintrag.

Wie es in einer Abfrage funktioniert:

-- Ereignisse mit einem bestimmten Ergebnis finden
SELECT * FROM player_events 
WHERE outcome = 'win' AND event_time >= '2025-06-01';

ClickHouse liest den Index idx_outcome_minmax:

• Gruppe 1: min='loss', max='push' → kein 'win' → 32768 Zeilen überspringen.
• Gruppe 2: min='loss', max='win' → enthält 'win' → diese Gruppe lesen.
• Gruppe 3: min='win', max='win' → nur 'win' → lesen.

Wann minmax effektiv ist:

• Spalten mit monotonen Änderungen (Zeit, ID, Temperatur).
• Spalten mit wenigen eindeutigen Werten, aber ungleichmäßig verteilt.
• Bereichsabfragen (BETWEEN, >=, <=).

Wann es nutzlos ist:

• Zufällige Werte (z. B. Hash, UUID). Min und Max decken den gesamten Bereich ab, der Index überspringt nichts.

3. INDEX ... TYPE set – Für Gleichheit auf Spalten mit niedriger Kardinalität

Ein set-Index speichert eindeutige Werte für eine Gruppe von Granula. Wenn der gesuchte Wert nicht in dieser Menge ist, wird die Gruppe übersprungen.

CREATE TABLE bets
(
    user_id     UInt64,
    sport_id    UInt8,      -- nur 20 Sportarten
    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;

Parameter:

• set(10) – die maximale Anzahl eindeutiger Werte, die der Index für eine Gruppe speichert. Wenn eine Gruppe mehr als 10 eindeutige sport_id-Werte enthält, merkt sich der Index nur 10 (und kann zu einem falschen Positiv führen). Wählen Sie eine Zahl, die etwas größer ist als die erwartete Spaltenkardinalität.

Wie es funktioniert:

-- Abfrage für eine bestimmte Sportart
SELECT sum(amount) FROM bets WHERE sport_id = 1;

Der Index idx_sport weiß für jede Gruppe von Granula, welche sport_id-Werte vorkommen. Wenn eine Gruppe sport_id=1 nicht enthält – überspringe die gesamte Gruppe. Wenn doch – lies sie.

Wann set effektiv ist:

• Spaltenkardinalität ist niedrig (bis zu Hunderten von Werten).
• Gleichheitsabfragen (=, IN).
• Daten sind gut innerhalb von Granula gruppiert (z. B. alle Fußballwetten einer Stunde kompakt gespeichert).

Glücksspiel-Beispiel: Eine Wetten-Tabelle mit ORDER BY (created_at, user_id). Spalte sport_id (20 Werte) ist nicht im ORDER BY. Ein set-Index auf sport_id ermöglicht es, schnell alle Hockey-Wetten zu finden, ohne alles zu scannen.

4. bloom_filter-Index – Für String-Spalten mit hoher Kardinalität

Bloom-Filter ist eine probabilistische Datenstruktur. Sie kann sagen „der Wert ist definitiv nicht in der Gruppe" oder „der Wert könnte vorhanden sein". Sie sagt nie „definitiv vorhanden" – sie kann nur auf der Seite der falschen Positive irren.

CREATE TABLE player_events
(
    user_id     UInt64,
    ip_address  String,          -- Millionen eindeutiger IPs
    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;

Parameter:

• bloom_filter(0.01) – Falsch-Positiv-Rate von 1 %. Je kleiner die Zahl, desto genauer der Index, aber er benötigt mehr Speicher. Üblich sind 0.01 (1 %) oder 0.001 (0.1 %).
• GRANULARITY 3 – 3 Granula (3 × 8192 = 24576 Zeilen) pro Indexeintrag.

Wie es funktioniert:

-- Alle Ereignisse von einer verdächtigen IP finden
SELECT * FROM player_events WHERE ip_address = '192.168.1.100';

Der Index prüft für jede Gruppe von Granula per Bloom-Filter: „Könnte diese Gruppe IP=192.168.1.100 enthalten?" Wenn „nein" – wird die Gruppe übersprungen. Wenn „ja" (einschließlich falscher Positive) – wird die Gruppe gelesen.

Wann bloom_filter effektiv ist:

• Spalten mit hoher Kardinalität (IP-Adressen, E-Mail, user_agent).
• Exakte Übereinstimmungs-Abfragen.
• Gesuchte Werte sind selten (z. B. eine bestimmte IP von 10 Millionen).

Warum minmax für IP nicht geeignet ist: Aufgrund der zufälligen Verteilung decken min und max IP in einer Gruppe fast den gesamten Bereich ab, sodass kein Ausschluss funktioniert.

Praxisbeispiel – Multi-Account-Erkennung (eine IP, viele user_ids):

-- Alle Benutzer von einer bestimmten IP finden
SELECT DISTINCT user_id FROM player_events 
WHERE ip_address = '192.168.1.100';

Ohne Index – Full Scan. Mit bloom_filter auf ip_address – schnell, selbst wenn die IP in 0.1 % der Zeilen vorkommt.

5. ngrambf_v1 – Für LIKE/ILIKE-Suche auf Strings

Manchmal muss man nach einer Teilzeichenkette suchen: WHERE player_name LIKE '%John%'. Normale Indizes helfen nicht, weil % am Anfang die B-Baum-Nutzung verhindert.

ngrambf_v1 zerlegt den String in N-Gramme – Teilzeichenketten der Länge N. Zum Beispiel für N=3: 'Johny' → 'Joh', 'ohn', 'hny'. Der Index baut einen Bloom-Filter auf diesen N-Grammen auf.

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;

Parameter von ngrambf_v1:

• 3 – N-Gramm-Länge (normalerweise 2–4). Größer bedeutet genauer, aber mehr Speicher.
• 500000 – Bloom-Filter-Größe in Bytes pro Indexeintrag.
• 2 – Anzahl der Hash-Funktionen (normalerweise 2–4).
• 0.01 – Falsch-Positiv-Wahrscheinlichkeit.

Wie man es in einer Abfrage verwendet:

-- Spieler finden, deren Name 'Alex' enthält
SELECT * FROM players WHERE player_name LIKE '%Alex%';

Der Index zerlegt 'Alex' in N-Gramme ('Ale', 'lex') und prüft, ob diese N-Gramme in Gruppen existieren. Wenn eine Gruppe keines dieser N-Gramme hat, wird die Gruppe übersprungen.

Einschränkungen:

• Funktioniert nur mit LIKE und ILIKE (Groß-/Kleinschreibung ignorierend).
• Der Suchstring muss länger als das N-Gramm sein (mindestens 3 Zeichen).
• Nicht geeignet für kurze Strings (z. B. 'a').

Wann verwenden: Suche nach Spieler-Spitznamen, Teil-E-Mail, Adressen. Im Glücksspiel – einen Spieler anhand eines Teils seines Namens für den Kundensupport finden.

6. tokenbf_v1 – Für Token (Wort)-Suche

tokenbf_v1 ähnelt ngrambf_v1, zerlegt den String jedoch nicht in überlappende Teile, sondern in Tokens – Wörter, getrennt durch Leerzeichen, Satzzeichen, Ziffern.

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;

Parameter von tokenbf_v1:

• 500000 – Bloom-Filter-Größe in Bytes.
• 2 – Anzahl der Hash-Funktionen.
• 0.01 – Falsch-Positiv-Wahrscheinlichkeit.

Wie es funktioniert:

Für den String "User 123 logged in from Ukraine" Tokens: 'User', '123', 'logged', 'in', 'from', 'Ukraine'.

-- Alle Logs finden, die einen Fehler erwähnen
SELECT * FROM logs WHERE message LIKE '%error%';

Der Index zerlegt 'error' in Tokens (nur 'error') und prüft das Vorhandensein dieses Tokens in Gruppen.

Wann tokenbf_v1 besser ist als ngrambf_v1:

• Suche nach ganzen Wörtern (nicht Teilen).
• Englische Texte, Logs, user_agent.
• Weniger falsche Positive als ngrambf_v1.

Glücksspiel-Beispiel: Suche in Wett-Logs nach Nachrichten, die 'fraud' oder 'suspicious' enthalten.

7. Wie man prüft, ob ein Index verwendet wird – EXPLAIN indexes=1

Sie haben einen Index erstellt, aber funktioniert er? ClickHouse bietet den Befehl EXPLAIN indexes = 1.

-- Indexnutzungsanalyse aktivieren
EXPLAIN indexes = 1
SELECT user_id, amount FROM bets 
WHERE sport_id = 1 AND created_at >= '2025-06-01';

Beispielausgabe:

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

Was die Zahlen bedeuten:

• Granules: 150 / 12000 – Primärschlüssel hat 11850 Granula ausgeschlossen, 150 bleiben.
• Skip ... Granules: 80 / 150 – Skip-Index hat weitere 70 Granula ausgeschlossen, 80 bleiben.
• Endgültiger Gewinn: 12000 → 80 gelesene Granula.

Wenn der Index nicht verwendet wird:

• Nicht im Abschnitt Skip angezeigt → entweder nicht erstellt oder die Abfrage passt nicht zum Indextyp.
• Granules: 12000 / 12000 – alles wird gelesen, Index hat nicht geholfen.

Warum ein Index möglicherweise nicht verwendet wird:

• Indextyp passt nicht zum Operator (minmax für = ist ineffektiv).
• Granularität ist zu groß (grober Index).
• Der gesuchte Wert kommt fast überall vor (Index kann keine Blöcke überspringen).

8. Wann Skip-Indizes NICHT helfen

Szenario 1: Hohe Kardinalität + zufällige Verteilung

Wenn die Spalte user_id (Millionen von Werten) und ORDER BY nicht mit user_id beginnt, wird ein Skip-Index (selbst bloom_filter) Blöcke schlecht ausschließen. Denn der Wert user_id=123 kann über die gesamte Tabelle verstreut sein.

Szenario 2: Abfrage ohne Filterung auf „guten" Spalten

Indizes auf sport_id helfen nicht, wenn WHERE nur amount > 1000 enthält und es keinen Index auf amount gibt.

Szenario 3: Zu große GRANULARITY

Wenn GRANULARITY = 64 (524k Zeilen pro Gruppe) und Ihre Tabelle 10 Millionen Zeilen hat, gibt es nur ~20 Gruppen. Sie können nur 20 Blöcke überspringen, was vernachlässigbar ist.

Szenario 4: Der gesuchte Wert kommt in 50 %+ der Zeilen vor

Skip-Indizes sind gut für seltene Werte. Wenn die Hälfte der Zeilen die Bedingung erfüllt, sagen die Indizes für fast alle Blöcke „vielleicht", und Sie lesen alles.

Szenario 5: Index ist zu klein

-- Schlecht: zu kleiner Bloom-Filter (10000 Bytes)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 4;

Ein kleiner Bloom-Filter erzeugt viele falsche Positive (sagt oft „vielleicht", obwohl nicht). Der Index hört auf, Blöcke zu überspringen.

9. Kosten von Skip-Indizes – Speicher und Einfügegeschwindigkeit

Jeder Index hat Kosten. Erstellen Sie keine Indizes „nur für den Fall".

Kosten #1: Zusätzlicher Speicherplatz

• minmax – sehr günstig (8 Bytes pro Gruppe pro Spalte).
• set(100) – teurer, aber innerhalb von Tausend Bytes pro Gruppe.
• bloom_filter – teuer: bei 500k Bytes und GRANULARITY=1, für eine Tabelle mit 10k Gruppen = 5 GB allein für den Index.

Kosten #2: Langsamere INSERTs

Bei jedem Einfügen aktualisiert ClickHouse alle Indizes für jedes Granulum. 5 Indizes auf einer Tabelle können Einfügungen um das 2- bis 3-fache verlangsamen.

Faustregel:

• Nicht mehr als 2-3 Skip-Indizes auf einer großen Tabelle (Milliarden von Zeilen).
• Indizes nur auf Spalten, die häufig gefiltert werden.
• Für Test-Workloads – experimentieren. Für Produktion – messen.

Wie man die Indexkosten abschätzt:

-- Indexgrößen in einer Tabelle prüfen
SELECT 
    table,
    index_name,
    formatReadableSize(index_size) AS size
FROM system.indexes
WHERE table = 'bets';

Wenn die Indexgröße nahe an der Datengröße liegt, haben Sie es möglicherweise übertrieben.

10. Praxisbeispiel: Betrugserkennung per IP-Adresse

Stellen Sie sich vor, in Ihrem Casino verwendet eine Gruppe von Spielern eine IP-Adresse für Multi-Accounting (gegen die Regeln). Sie müssen alle finden, die sich von einer verdächtigen IP aus eingeloggt haben.

Ereignistabelle:

• 500 Millionen Zeilen.
• ORDER BY = (user_id, event_time) – schnelle Abfragen nach Benutzer.
• Häufige Abfrage: SELECT user_id FROM events WHERE ip_address = 'x.x.x.x'.

Lösung – 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;

Leistungsvergleich:

Szenario	Ohne Index	Mit bloom_filter (0.01)
Abfragezeit für seltene IP (0.001 % Zeilen)	60 Sekunden (Full Scan 500M)	0.3 Sekunden
Abfragezeit für häufige IP (5 % Zeilen)	60 Sekunden	45 Sekunden (Index hilft wenig)
Tabellengröße (komprimiert)	100 GB	108 GB (+8 %)
INSERT-Zeit (10k Zeilen/s)	0.5 ms pro Batch	0.7 ms pro Batch (+40 %)

Wie man eine Anti-Betrugs-Abfrage schreibt:

-- Alle Benutzer finden, die jemals eine verdächtige IP verwendet haben
SELECT DISTINCT user_id 
FROM player_events 
WHERE ip_address = '192.168.1.100'   -- bloom_filter hilft
AND event_time >= today() - 30;      -- Partitionen schließen alte Daten aus

-- Dann prüfen, wie viele verschiedene Konten diese IP verwenden
SELECT count(DISTINCT user_id) AS suspicious_accounts
FROM player_events 
WHERE ip_address = '192.168.1.100';

Warum bloom_filter, nicht minmax:

• IP-Adressen sind zufällig verteilt; min/max in einer Gruppe decken fast immer den gesamten Bereich ab.
• Bloom-Filter ist ideal für Mengenzugehörigkeitsprüfungen.

Was kommt als Nächstes

Jetzt kennen Sie alle Typen von sekundären Indizes in ClickHouse. Nächste Themen:

• Kombinieren von Indizes – wie mehrere Skip-Indizes zusammenarbeiten.
• Optimierung der Granularität – wie man die optimale Granulagröße für verschiedene Datentypen wählt.
• Indizes in verteilten Tabellen – wie Skip-Indizes in einem Cluster funktionieren.

Fazit: Skip-Indizes in ClickHouse sind kein Allheilmittel. Sie funktionieren nicht wie B-Bäume in PostgreSQL. Aber für die richtigen Szenarien (seltene Werte, Bloom-Filter, N-Gramme) verwandeln sie Full Scans in blitzschnelle Abfragen. Wichtige Regeln:

• Erstellen Sie keine Indizes, bevor Sie ein Problem sehen (Full Scan).
• Beginnen Sie mit bloom_filter für Spalten mit hoher Kardinalität, set für niedrige Kardinalität.
• Überprüfen Sie immer mit EXPLAIN indexes = 1.
• Denken Sie an die Kosten: Speicherplatz + INSERT-Verlangsamung.

---

← Vorherige: Materialisierte Sichten in ClickHouse: Die Macht der inkrementellen Verarbeitung

— Editorial Team