Index de saut ClickHouse : bloom, set, minmax

Index secondaires (saut) dans ClickHouse : quand ORDER BY ne suffit pas

1. Comment fonctionnent les index de saut — Sauter des blocs de données

Dans les bases de données traditionnelles (PostgreSQL, MySQL), un index est une structure qui pointe exactement vers les lignes satisfaisant une condition. Un B-tree dit : « La valeur user_id = 123 se trouve à la ligne #45678 ».

Dans ClickHouse, l'index primaire (index sparse par ORDER BY) fonctionne différemment. Il stocke les valeurs uniquement pour chaque 8192e ligne (granule) et peut élaguer efficacement des blocs entiers de données pour les colonnes qui apparaissent tôt dans le ORDER BY.

Mais que faire si vous devez rechercher par une colonne qui n'est pas dans ORDER BY ? Par exemple, vous voulez trouver tous les paris avec une adresse IP spécifique, mais votre ORDER BY est (user_id, created_at). ClickHouse devra lire tous les granules et filtrer l'IP après la lecture. C'est ce qu'on appelle un scan complet.

Les index secondaires (saut) résolvent ce problème. Ils ne pointent pas vers des lignes spécifiques mais disent : « Dans ce bloc de N granules, il n'y a définitivement pas cette valeur — vous pouvez le sauter. » Si l'index dit « peut-être » — ClickHouse lit quand même le bloc.

Analogie concrète : Imaginez que vous cherchez un livre à couverture verte dans une bibliothèque. L'index principal (catalogue par nom d'auteur) ne vous aide pas. Mais vous passez devant les étagères et jetez un coup d'œil rapide : « Tous les livres sur cette étagère sont bleus — on saute. Cette étagère en a des verts — je vérifie. » Un index de saut est comme des étagères codées par couleur, pas un pointeur précis.

Pourquoi les appelle-t-on « saut » ? Parce que le travail principal de l'index est de sauter les blocs qui ne sont définitivement pas nécessaires. Plus on saute de blocs, plus la requête est rapide.

Limitation importante : Les index de saut fonctionnent uniquement au niveau du granule. Ils ne peuvent pas trouver la position exacte d'une ligne dans un granule. Par conséquent, l'index est utile lorsque la valeur recherchée est rare (faible sélectivité). Si 80 % des lignes correspondent à la condition — vous devrez quand même tout lire.

2. INDEX ... TYPE minmax — Pour les requêtes de plage

L'index de saut le plus simple est minmax. Il stocke la valeur minimale et maximale d'une colonne pour chaque groupe de granules.

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)              -- ordre primaire
INDEX idx_outcome_minmax outcome TYPE minmax GRANULARITY 4;

Détail des paramètres :

• INDEX idx_outcome_minmax — nom de l'index (choisissez le vôtre, mais donnez-lui un sens).
• outcome — colonne sur laquelle l'index est construit.
• TYPE minmax — type d'index : stocke les valeurs min et max dans un groupe de granules.
• GRANULARITY 4 — combien de granules (chacun de 8192 lignes) sont combinés en un groupe pour l'index. Ici 4 × 8192 = 32768 lignes par entrée d'index.

Comment cela fonctionne dans une requête :

-- Trouver les événements avec un résultat spécifique
SELECT * FROM player_events 
WHERE outcome = 'win' AND event_time >= '2025-06-01';

ClickHouse lit l'index idx_outcome_minmax :

• Groupe 1 : min='loss', max='push' → pas de 'win' → sauter 32768 lignes.
• Groupe 2 : min='loss', max='win' → contient 'win' → lire ce groupe.
• Groupe 3 : min='win', max='win' → seulement 'win' → lire.

Quand minmax est efficace :

• Colonnes avec des changements monotones (temps, ID, température).
• Colonnes avec peu de valeurs uniques mais inégalement réparties.
• Requêtes de plage (BETWEEN, >=, <=).

Quand il est inutile :

• Valeurs aléatoires (ex. hash, UUID). Min et max couvriront toute la plage, l'index ne sautera rien.

3. INDEX ... TYPE set — Pour l'égalité sur des colonnes à faible cardinalité

Un index set stocke les valeurs uniques pour un groupe de granules. Si la valeur recherchée n'est pas dans cet ensemble — le groupe est sauté.

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

Paramètres :

• set(10) — le nombre maximum de valeurs uniques que l'index stockera pour un groupe. Si un groupe contient plus de 10 valeurs uniques de sport_id, l'index n'en retiendra que 10 (et peut provoquer un faux positif). Choisissez un nombre légèrement supérieur à la cardinalité attendue de la colonne.

Comment cela fonctionne :

-- Requête pour un sport spécifique
SELECT sum(amount) FROM bets WHERE sport_id = 1;

L'index idx_sport sait pour chaque groupe de granules quelles valeurs de sport_id apparaissent. Si un groupe ne contient pas sport_id=1 — sauter tout le groupe. S'il en contient — le lire.

Quand set est efficace :

• La cardinalité de la colonne est faible (jusqu'à des centaines de valeurs).
• Requêtes d'égalité (=, IN).
• Les données sont bien regroupées dans les granules (ex. tous les paris football d'une heure sont stockés de manière compacte).

Exemple dans les jeux d'argent : Une table de paris avec ORDER BY (created_at, user_id). La colonne sport_id (20 valeurs) n'est pas dans ORDER BY. Un index set sur sport_id permet de trouver rapidement tous les paris hockey sans tout scanner.

4. Index bloom_filter — Pour les colonnes de chaînes à haute cardinalité

Le filtre de Bloom est une structure de données probabiliste. Il peut dire « la valeur n'est définitivement pas dans le groupe » ou « la valeur est peut-être présente ». Il ne dit jamais « définitivement présente » — il ne peut se tromper que par des faux positifs.

CREATE TABLE player_events
(
    user_id     UInt64,
    ip_address  String,          -- des millions d'IP uniques
    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;

Paramètres :

• bloom_filter(0.01) — taux de faux positifs de 1 %. Plus le nombre est petit, plus l'index est précis, mais il prend plus de place. Généralement 0.01 (1 %) ou 0.001 (0.1 %) est utilisé.
• GRANULARITY 3 — 3 granules (3 × 8192 = 24576 lignes) par entrée d'index.

Comment cela fonctionne :

-- Trouver tous les événements d'une IP suspecte
SELECT * FROM player_events WHERE ip_address = '192.168.1.100';

L'index pour chaque groupe de granules vérifie via le filtre de Bloom : « Ce groupe pourrait-il contenir IP=192.168.1.100 ? » Si « non » — le groupe est sauté. Si « oui » (y compris les faux positifs) — le groupe est lu.

Quand le filtre de Bloom est efficace :

• Colonnes à haute cardinalité (adresses IP, email, user_agent).
• Requêtes de correspondance exacte.
• Les valeurs recherchées sont rares (ex. une IP spécifique sur 10 millions).

Pourquoi minmax n'est pas adapté pour IP : En raison de la distribution aléatoire, les IP min et max dans un groupe couvriront presque toute la plage, donc l'élagage ne fonctionnera pas.

Exemple concret — détection de multi-comptes (une IP, plusieurs user_id) :

-- Trouver tous les utilisateurs d'une IP donnée
SELECT DISTINCT user_id FROM player_events 
WHERE ip_address = '192.168.1.100';

Sans index — scan complet. Avec bloom_filter sur ip_address — rapide, même si l'IP apparaît dans 0.1 % des lignes.

5. ngrambf_v1 — Pour la recherche LIKE/ILIKE sur les chaînes

Parfois, vous devez rechercher une sous-chaîne : WHERE player_name LIKE '%John%'. Les index classiques n'aident pas car % au début empêche l'utilisation du B-tree.

ngrambf_v1 divise la chaîne en n-grammes — sous-chaînes de longueur N. Par exemple, pour N=3, 'Johny' → 'Joh', 'ohn', 'hny'. L'index construit un filtre de Bloom sur ces n-grammes.

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;

Paramètres de ngrambf_v1 :

• 3 — longueur du n-gramme (généralement 2–4). Plus grand signifie plus précis mais plus de mémoire.
• 500000 — taille du filtre de Bloom en octets par entrée d'index.
• 2 — nombre de fonctions de hachage (généralement 2–4).
• 0.01 — probabilité de faux positifs.

Comment l'utiliser dans une requête :

-- Trouver les joueurs dont le nom contient 'Alex'
SELECT * FROM players WHERE player_name LIKE '%Alex%';

L'index divise 'Alex' en n-grammes ('Ale', 'lex') et vérifie si ces n-grammes existent dans les groupes. Si un groupe n'a aucun de ces n-grammes — le groupe est sauté.

Limitations :

• Fonctionne uniquement avec LIKE et ILIKE (insensible à la casse).
• Nécessite que la chaîne recherchée soit plus longue que le n-gramme (au moins 3 caractères).
• Pas adapté aux chaînes courtes (ex. 'a').

Quand l'utiliser : Recherche par surnoms de joueurs, email partiel, adresses. Dans les jeux d'argent — trouver un joueur par une partie de son nom pour le support client.

6. tokenbf_v1 — Pour la recherche par token (mot)

tokenbf_v1 est similaire à ngrambf_v1, mais divise la chaîne non pas en morceaux qui se chevauchent, mais en tokens — mots séparés par des espaces, ponctuation, chiffres.

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;

Paramètres de tokenbf_v1 :

• 500000 — taille du filtre de Bloom en octets.
• 2 — nombre de fonctions de hachage.
• 0.01 — probabilité de faux positifs.

Comment cela fonctionne :

Pour la chaîne "User 123 logged in from Ukraine" tokens : 'User', '123', 'logged', 'in', 'from', 'Ukraine'.

-- Trouver tous les logs mentionnant une erreur
SELECT * FROM logs WHERE message LIKE '%error%';

L'index divise 'error' en tokens (juste 'error') et vérifie la présence de ce token dans les groupes.

Quand tokenbf_v1 est meilleur que ngrambf_v1 :

• Recherche de mots entiers (pas de parties).
• Textes en anglais, logs, user_agent.
• Moins de faux positifs que ngrambf_v1.

Exemple dans les jeux d'argent : Recherche dans les logs de paris des messages contenant 'fraud' ou 'suspicious'.

7. Comment vérifier qu'un index est utilisé — EXPLAIN indexes=1

Vous avez créé un index, mais fonctionne-t-il ? ClickHouse fournit la commande EXPLAIN indexes = 1.

-- Activer l'analyse d'utilisation des index
EXPLAIN indexes = 1
SELECT user_id, amount FROM bets 
WHERE sport_id = 1 AND created_at >= '2025-06-01';

Exemple de sortie :

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

Que signifient les chiffres :

• Granules: 150 / 12000 — la clé primaire a élagué 11850 granules, il en reste 150.
• Skip ... Granules: 80 / 150 — l'index de saut a encore élagué 70 granules, il en reste 80.
• Gain final : 12000 → 80 granules lus.

Si l'index n'est pas utilisé :

• Non affiché dans la section Skip → soit il n'a pas été créé, soit la requête ne correspond pas au type d'index.
• Granules: 12000 / 12000 — tout est lu, l'index n'a pas aidé.

Pourquoi un index pourrait ne pas être utilisé :

• Le type d'index ne correspond pas à l'opérateur (minmax pour = est inefficace).
• La granularité est trop grande (index grossier).
• La valeur recherchée apparaît presque partout (l'index ne peut pas sauter de blocs).

8. Quand les index de saut n'aident PAS

Scénario 1 : Haute cardinalité + distribution aléatoire

Si la colonne user_id (des millions de valeurs) et ORDER BY ne commence pas par user_id, un index de saut (même bloom_filter) élaguera mal les blocs. Parce que la valeur user_id=123 peut être dispersée dans toute la table.

Scénario 2 : Requête sans filtre sur les « bonnes » colonnes

Les index sur sport_id n'aideront pas si WHERE n'a que amount > 1000 et qu'il n'y a pas d'index sur amount.

Scénario 3 : GRANULARITY trop grande

Si GRANULARITY = 64 (524k lignes par groupe), et votre table a 10 millions de lignes, il n'y aura qu'environ 20 groupes. Vous ne pouvez sauter que 20 blocs, ce qui est négligeable.

Scénario 4 : La valeur recherchée apparaît dans 50 %+ des lignes

Les index de saut sont bons pour les valeurs rares. Si la moitié des lignes correspondent à la condition, les index diront « peut-être » pour presque tous les blocs, et vous lirez tout.

Scénario 5 : Index trop petit

-- Mauvais : filtre de Bloom trop petit (10000 octets)
INDEX idx_ip ip_address TYPE bloom_filter(0.01) GRANULARITY 4;

Un petit filtre de Bloom donne beaucoup de faux positifs (dit souvent « peut-être » alors que ce n'est pas le cas). L'index cesse de sauter des blocs.

9. Coût des index de saut — Mémoire et vitesse d'insertion

Chaque index a un coût. Ne créez pas d'index « au cas où ».

Coût #1 : Espace disque supplémentaire

• minmax — très économique (8 octets par groupe par colonne).
• set(100) — plus coûteux, mais de l'ordre de milliers d'octets par groupe.
• bloom_filter — coûteux : à 500k octets et GRANULARITY=1, pour une table avec 10k groupes = 5 Go rien que pour l'index.

Coût #2 : INSERT plus lent

À chaque insertion, ClickHouse met à jour tous les index pour chaque granule. 5 index sur une table peuvent ralentir les insertions de 2 à 3 fois.

Règle empirique :

• Pas plus de 2-3 index de saut sur une grande table (milliards de lignes).
• Index uniquement sur les colonnes fréquemment filtrées.
• Pour les charges de test — expérimentez. Pour la production — mesurez.

Comment estimer le coût d'un index :

-- Vérifier la taille des index dans une table
SELECT 
    table,
    index_name,
    formatReadableSize(index_size) AS size
FROM system.indexes
WHERE table = 'bets';

Si la taille de l'index est proche de la taille des données — vous avez peut-être exagéré.

10. Exemple concret : Détection de fraude par adresse IP

Imaginez que dans votre casino, un groupe de joueurs utilise une seule adresse IP pour le multi-comptage (contre les règles). Vous devez trouver tous ceux qui se sont connectés depuis une IP suspecte.

Table des événements :

• 500 millions de lignes.
• ORDER BY = (user_id, event_time) — requêtes rapides par utilisateur.
• Requête fréquente : SELECT user_id FROM events WHERE ip_address = 'x.x.x.x'.

Solution — index 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;

Comparaison des performances :

Scénario	Sans index	Avec bloom_filter (0.01)
Temps de requête pour IP rare (0.001% lignes)	60 secondes (scan complet 500M)	0.3 secondes
Temps de requête pour IP fréquente (5% lignes)	60 secondes	45 secondes (l'index aide peu)
Taille de la table (compressée)	100 Go	108 Go (+8%)
Temps d'INSERT (10k lignes/s)	0.5 ms par lot	0.7 ms par lot (+40%)

Comment écrire une requête anti-fraude :

-- Trouver tous les utilisateurs qui ont déjà utilisé une IP suspecte
SELECT DISTINCT user_id 
FROM player_events 
WHERE ip_address = '192.168.1.100'   -- bloom_filter aide
AND event_time >= today() - 30;      -- les partitions élaguent les anciennes données

-- Ensuite, vérifier combien de comptes différents utilisent cette IP
SELECT count(DISTINCT user_id) AS suspicious_accounts
FROM player_events 
WHERE ip_address = '192.168.1.100';

Pourquoi bloom_filter, pas minmax :

• Les adresses IP sont distribuées aléatoirement ; le min/max dans un groupe couvrira presque toujours toute la plage.
• Le filtre de Bloom est idéal pour les vérifications d'appartenance à un ensemble.

Prochaines étapes

Maintenant vous connaissez tous les types d'index secondaires de ClickHouse. Prochains sujets :

• Combinaison d'index — comment plusieurs index de saut fonctionnent ensemble.
• Réglage de la granularité — comment choisir la taille de granule optimale pour différents types de données.
• Index dans les tables distribuées — comment les index de saut fonctionnent dans un cluster.

En résumé : Les index de saut dans ClickHouse ne sont pas une solution miracle. Ils ne fonctionnent pas comme les B-trees dans PostgreSQL. Mais pour les bons scénarios (valeurs rares, filtre de Bloom, n-grammes), ils transforment les scans complets en requêtes ultra-rapides. Règles clés :

• Ne créez pas d'index avant d'avoir identifié un problème (scan complet).
• Commencez par bloom_filter pour les colonnes à haute cardinalité, set pour les colonnes à faible cardinalité.
• Vérifiez toujours avec EXPLAIN indexes = 1.
• N'oubliez pas le coût : espace disque + ralentissement des INSERT.

---

← Précédente: Vues matérialisées dans ClickHouse : la puissance du traitement incrémental

— Editorial Team