---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.16.0
kernelspec:
  name: python3
  display_name: Python 3
---

# Index et performance

Un index est une structure de données auxiliaire qui permet au moteur SQL de localiser rapidement les lignes sans parcourir toute la table. Bien utilisés, les index peuvent réduire le temps de requête de plusieurs ordres de grandeur. Mal gérés, ils ralentissent les écritures et occupent inutilement de l'espace.

```{code-cell} python
:tags: [hide-input]

import sqlite3
import pandas as pd
import time
import matplotlib.pyplot as plt
import matplotlib.ticker as mticker
import seaborn as sns

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)
```

## Full table scan vs index scan

```{prf:definition}
:label: ch10-def-full-scan
Un **full table scan** (parcours séquentiel) consiste à lire chaque ligne de la table une par une pour trouver celles qui satisfont le prédicat. Sa complexité est **O(n)** — le temps de réponse croît linéairement avec le nombre de lignes.
```

```{prf:definition}
:label: ch10-def-index-scan
Un **index scan** utilise une structure auxiliaire (typiquement un B-tree) pour localiser directement les lignes pertinentes. Sa complexité est **O(log n)** pour la recherche dans l'index, plus le coût d'accès aux lignes trouvées.
```

```{prf:remark}
:label: ch10-rem-quand-full-scan-ok
Le full table scan n'est pas toujours mauvais. Si la requête retourne une grande fraction des lignes (> 20-30 %), le moteur peut choisir délibérément le full scan car l'accès séquentiel est plus efficace que de nombreux accès aléatoires via l'index.
```

## Structure B-tree

```{prf:definition}
:label: ch10-def-btree
Un **arbre B** (*Balanced Tree*) est la structure la plus courante pour les index SQL. C'est un arbre de recherche équilibré dont les nœuds internes contiennent des clés de guidage et les feuilles contiennent les valeurs réelles (clés d'index + pointeurs vers les lignes). Propriétés :
- Hauteur O(log n) — chaque recherche traverse au plus log₂(n) nœuds.
- Les feuilles sont liées entre elles, permettant des parcours de plages efficaces.
- Toutes les insertions/suppressions maintiennent l'équilibre par division et fusion de nœuds.
```

```{prf:remark}
:label: ch10-rem-btree-operations
Coût des opérations sur un B-tree de n éléments :
- Recherche exacte : O(log n)
- Parcours de plage `BETWEEN a AND b` : O(log n + k) où k = nombre de résultats
- Insertion / suppression : O(log n) avec rééquilibrage
```

## Types d'index

```{prf:definition}
:label: ch10-def-types-index
SQLite supporte plusieurs types d'index :
- **Index simple** : sur une seule colonne — `CREATE INDEX idx ON t(col)`.
- **Index composite** : sur plusieurs colonnes — `CREATE INDEX idx ON t(col1, col2)`. L'ordre des colonnes est crucial (préfixe gauche).
- **Index unique** : garantit l'unicité en plus de l'accès rapide — `CREATE UNIQUE INDEX`.
- **Index partiel** : n'indexe qu'un sous-ensemble de lignes — `CREATE INDEX idx ON t(col) WHERE condition`.
- **Covering index** : contient toutes les colonnes nécessaires à la requête, évitant l'accès à la table principale.
```

```{prf:example}
:label: ch10-ex-index-composite-prefixe
Un index composite `(departement, annee)` peut accélérer les requêtes filtrant sur `departement` seul ou sur `(departement, annee)`, mais **pas** celles filtrant uniquement sur `annee`. C'est la règle du **préfixe gauche** (*leftmost prefix rule*).
```

## Mise en place du jeu de données

```{code-cell} python
def creer_grande_table(n=100_000):
    """Crée une base SQLite en mémoire avec n lignes dans la table employes."""
    conn = sqlite3.connect(":memory:")
    conn.execute("PRAGMA cache_size = -64000")   # 64 MB cache
    conn.executescript(f"""
    CREATE TABLE employes (
        id           INTEGER PRIMARY KEY,
        nom          TEXT NOT NULL,
        departement  TEXT NOT NULL,
        ville        TEXT NOT NULL,
        salaire      REAL NOT NULL,
        annee_entree INTEGER NOT NULL,
        score        INTEGER NOT NULL
    );
    """)

    import random, string
    random.seed(42)
    depts = ['Informatique','Marketing','Finance','RH','Logistique','Commercial','Direction']
    villes = ['Paris','Lyon','Marseille','Toulouse','Bordeaux','Nantes','Strasbourg','Lille']

    def rand_nom():
        return ''.join(random.choices(string.ascii_uppercase, k=1)) + \
               ''.join(random.choices(string.ascii_lowercase, k=random.randint(4, 9)))

    rows = [
        (i, rand_nom(), random.choice(depts), random.choice(villes),
         round(random.uniform(30000, 120000), 2),
         random.randint(2000, 2024), random.randint(0, 100))
        for i in range(1, n+1)
    ]

    conn.executemany(
        "INSERT INTO employes VALUES (?,?,?,?,?,?,?)", rows
    )
    conn.commit()
    return conn

conn = creer_grande_table(100_000)
print("Table créée avec", pd.read_sql("SELECT COUNT(*) AS n FROM employes", conn).iloc[0,0], "lignes")
```

## EXPLAIN QUERY PLAN

```{prf:definition}
:label: ch10-def-explain-query-plan
`EXPLAIN QUERY PLAN` est une directive SQLite qui affiche le **plan d'exécution** choisi par le moteur sans exécuter la requête. Elle indique notamment si le moteur réalise un full table scan (`SCAN`) ou utilise un index (`SEARCH ... USING INDEX`).
```

```{code-cell} python
# Plan sans index
print("=== SANS index ===")
plan = conn.execute("""
EXPLAIN QUERY PLAN
SELECT * FROM employes WHERE departement = 'Finance' AND annee_entree = 2020
""").fetchall()
for row in plan:
    print(row)
```

```{code-cell} python
# Création des index
conn.execute("CREATE INDEX idx_dept ON employes(departement)")
conn.execute("CREATE INDEX idx_dept_annee ON employes(departement, annee_entree)")
conn.execute("CREATE UNIQUE INDEX idx_id ON employes(id)")
conn.execute("CREATE INDEX idx_salaire ON employes(salaire)")
# Index partiel : uniquement les hauts salaires
conn.execute("CREATE INDEX idx_haut_salaire ON employes(salaire) WHERE salaire > 90000")
conn.commit()

print("=== AVEC index ===")
plan_idx = conn.execute("""
EXPLAIN QUERY PLAN
SELECT * FROM employes WHERE departement = 'Finance' AND annee_entree = 2020
""").fetchall()
for row in plan_idx:
    print(row)
```

## Mesure des performances avec et sans index

```{code-cell} python
def mesurer_temps(conn, requete, iterations=5):
    """Mesure le temps médian d'exécution d'une requête sur plusieurs itérations."""
    temps = []
    for _ in range(iterations):
        t0 = time.perf_counter()
        conn.execute(requete).fetchall()
        temps.append(time.perf_counter() - t0)
    return min(temps)   # minimum pour réduire le bruit


# Base sans index
conn_sans = creer_grande_table(100_000)
# Base avec index
conn_avec = creer_grande_table(100_000)
conn_avec.execute("CREATE INDEX idx_dept ON employes(departement)")
conn_avec.execute("CREATE INDEX idx_dept_annee ON employes(departement, annee_entree)")
conn_avec.execute("CREATE INDEX idx_salaire ON employes(salaire)")
conn_avec.commit()

requetes = {
    "Filtre dept = 'Finance'":
        "SELECT * FROM employes WHERE departement = 'Finance'",
    "Filtre dept + annee":
        "SELECT * FROM employes WHERE departement = 'Finance' AND annee_entree = 2020",
    "Plage salaire [60k-80k]":
        "SELECT * FROM employes WHERE salaire BETWEEN 60000 AND 80000",
    "COUNT(*) par dept":
        "SELECT departement, COUNT(*) FROM employes GROUP BY departement",
}

resultats = []
for label, req in requetes.items():
    t_sans = mesurer_temps(conn_sans, req) * 1000
    t_avec = mesurer_temps(conn_avec, req) * 1000
    resultats.append({
        "Requête": label,
        "Sans index (ms)": round(t_sans, 2),
        "Avec index (ms)": round(t_avec, 2),
        "Accélération": round(t_sans / t_avec, 1) if t_avec > 0 else "—"
    })

df_perf = pd.DataFrame(resultats)
df_perf
```

```{code-cell} python
:tags: [hide-input]

# Visualisation
fig, ax = plt.subplots(figsize=(11, 5))

x = range(len(df_perf))
width = 0.35
palette = sns.color_palette("muted")

bars_sans = ax.bar([i - width/2 for i in x], df_perf["Sans index (ms)"],
                   width, label="Sans index", color=palette[3], alpha=0.85)
bars_avec = ax.bar([i + width/2 for i in x], df_perf["Avec index (ms)"],
                   width, label="Avec index", color=palette[0], alpha=0.85)

ax.set_xticks(list(x))
ax.set_xticklabels(df_perf["Requête"], rotation=15, ha="right")
ax.set_ylabel("Temps d'exécution (ms)")
ax.set_title("Comparaison des temps de requête : avec vs sans index (100 000 lignes)")
ax.legend()
ax.yaxis.set_major_formatter(mticker.FuncFormatter(lambda v, _: f"{v:.1f} ms"))

# Annoter les facteurs d'accélération
for i, row in df_perf.iterrows():
    if isinstance(row["Accélération"], (int, float)):
        ax.text(i, max(row["Sans index (ms)"], row["Avec index (ms)"]) + 0.2,
                f"×{row['Accélération']}", ha="center", va="bottom",
                fontsize=9, color="firebrick", fontweight="bold")

plt.show()
```

## Règles d'utilisation des index

```{prf:definition}
:label: ch10-def-regles-index
**Quand créer un index :**
- Colonnes fréquemment utilisées dans `WHERE`, `JOIN ... ON`, `ORDER BY`, `GROUP BY`.
- Colonnes avec haute cardinalité (beaucoup de valeurs distinctes) — un index sur un booléen est rarement utile.
- Colonnes de clé étrangère (SQLite n'en crée pas automatiquement).
```

```{prf:remark}
:label: ch10-rem-index-ecriture
Chaque index doit être **maintenu** lors de chaque `INSERT`, `UPDATE`, `DELETE`. Sur une table très écrite, un excès d'index dégrade significativement les performances en écriture. Il faut trouver le bon équilibre selon le ratio lecture/écriture de l'application.
```

```{prf:example}
:label: ch10-ex-index-inutilise
Un index n'est pas utilisé si :
- La requête applique une **fonction** sur la colonne indexée : `WHERE UPPER(nom) = 'ALICE'` ignore l'index sur `nom`.
- La requête utilise un prédicat de type `LIKE '%motif'` (joker au début).
- La sélectivité est trop faible (ex: colonne booléenne — le moteur préfère le full scan).
- Le type de données ne correspond pas exactement (comparaison implicite de types).
```

```{code-cell} python
# Démonstration : index inutilisé à cause d'une fonction
print("=== Index SUR salaire — utilisé ===")
plan1 = conn_avec.execute("""
EXPLAIN QUERY PLAN SELECT * FROM employes WHERE salaire > 90000
""").fetchall()
for r in plan1: print(r)

print("\n=== Index inutilisé (fonction sur la colonne) ===")
plan2 = conn_avec.execute("""
EXPLAIN QUERY PLAN SELECT * FROM employes WHERE CAST(salaire AS INTEGER) > 90000
""").fetchall()
for r in plan2: print(r)
```

## ANALYZE et statistiques

```{prf:definition}
:label: ch10-def-analyze
La commande **`ANALYZE`** lit les tables et les index pour collecter des statistiques (distribution des valeurs, cardinalité) stockées dans la table système `sqlite_stat1`. L'optimiseur utilise ces statistiques pour choisir le meilleur plan d'exécution.
```

```{code-cell} python
conn_avec.execute("ANALYZE")
conn_avec.commit()

# Consulter les statistiques collectées
pd.read_sql("""
SELECT tbl, idx, stat
FROM sqlite_stat1
ORDER BY tbl, idx
""", conn_avec)
```

```{prf:remark}
:label: ch10-rem-analyze-quand
Exécuter `ANALYZE` après un chargement massif de données ou après des modifications importantes de la table. Sans statistiques à jour, l'optimiseur peut choisir un plan sous-optimal, par exemple utiliser un index peu sélectif plutôt qu'un full scan plus rapide.
```

## Pièges courants

```{prf:remark}
:label: ch10-rem-trop-index
**Trop d'index** — chaque index occupe de l'espace disque et ralentit les écritures. Sur une table fortement insérée (logs, événements), limiter les index aux stricts nécessaires.
```

```{prf:remark}
:label: ch10-rem-covering-index
**Covering index** — si une requête ne sélectionne que des colonnes déjà présentes dans l'index, le moteur n'a même pas besoin d'accéder à la table principale. Exemple : `CREATE INDEX idx_cov ON employes(departement, salaire)` permet de répondre à `SELECT salaire FROM employes WHERE departement='Finance'` sans toucher la table.
```

```{code-cell} python
# Covering index : le moteur ne lit pas la table principale
conn_avec.execute("CREATE INDEX idx_dept_sal ON employes(departement, salaire)")
conn_avec.execute("ANALYZE")
conn_avec.commit()

print("=== Covering index ===")
plan_cov = conn_avec.execute("""
EXPLAIN QUERY PLAN
SELECT departement, AVG(salaire)
FROM employes
WHERE departement IN ('Finance','Marketing')
GROUP BY departement
""").fetchall()
for r in plan_cov: print(r)
```

```{prf:example}
:label: ch10-ex-index-partiel-usage
Un **index partiel** réduit la taille de l'index en n'indexant qu'un sous-ensemble de lignes. Utile pour les requêtes fréquentes sur des lignes rares (ex: commandes non traitées, comptes actifs).
```

```{code-cell} python
# Index partiel : uniquement les scores >= 90
conn_avec.execute("DROP INDEX IF EXISTS idx_haut_score")
conn_avec.execute("CREATE INDEX idx_haut_score ON employes(score) WHERE score >= 90")
conn_avec.execute("ANALYZE")
conn_avec.commit()

print("=== Index partiel (score >= 90) ===")
plan_part = conn_avec.execute("""
EXPLAIN QUERY PLAN
SELECT nom, score FROM employes WHERE score >= 90 ORDER BY score DESC
""").fetchall()
for r in plan_part: print(r)
```

## Résumé

```{prf:definition}
:label: ch10-def-synthese
**Récapitulatif des index et de la performance :**

- Sans index, chaque requête filtrante est un **full scan O(n)**.
- Le **B-tree** est la structure d'index standard : recherche en O(log n), parcours de plages efficace.
- Types d'index : simple, composite (règle du préfixe gauche), unique, partiel, covering.
- `EXPLAIN QUERY PLAN` révèle si un index est utilisé (`SEARCH ... USING INDEX`) ou non (`SCAN`).
- Les index accélèrent les lectures mais ralentissent les écritures — chercher l'équilibre.
- `ANALYZE` met à jour les statistiques et aide l'optimiseur à choisir le bon plan.
- Pièges : fonctions sur colonnes indexées, LIKE avec joker initial, colonnes de faible cardinalité, index inutilisés.
```

| Type d'index | Cas d'usage | Avantage |
|---|---|---|
| Simple | Filtre sur une colonne | Rapide à créer, polyvalent |
| Composite | Filtres multi-colonnes | Respecter l'ordre préfixe gauche |
| Unique | Contrainte d'unicité | Double rôle : contrainte + performance |
| Partiel | Sous-ensemble de lignes | Index plus petit, plus rapide |
| Covering | Toutes colonnes dans l'index | Évite l'accès à la table |