Le blog de Pacman

Pour la définition des index composites, on rencontre souvent la recommandation :
"En premières positions, les colonnes les plus sélectives !"
Bien entendu, ça dépend du contexte... mais certaines personnes prennent cette règle comme vérité ultime.

Cet article s'attache donc à donner quelques arguments pour faire le contraire (encore une fois, ce ne seront pas des règles absolues, mais vraiment en fonction du cas concret...) :

1. Le skip scan (A partir de Oracle 9i)
2. La compression d'index (A partir de Oracle 8i)
3. L'amélioration du clustering factor

(Euh par contre, je retravaillerai la mise en forme une autre fois)

1) L'index skip scan :
Dans les versions antérieures à 9i, un index composite ne pouvait être utilisé que si les prédicats de filtres / jointures s'appuient sur la première colonne de cet index.
Cependant, si la recherche porte sur la deuxième colonne d'un index, et qu'il y a peu de valeurs distinctes sur la première, il peut être très avantageux de tenter toutes les combinaisons de la première colonne avec la valeur recherchée sur la seconde.
C'est le principe de l'index skip scan.
Exemple en "image" :

- Trois catégories, 10000 valeurs par catégorie
SQL> CREATE TABLE test_iss AS
  2  SELECT 'A' AS categ, level AS n FROM DUAL CONNECT BY level <= 10000 UNION ALL
  3  SELECT 'B' AS categ, level AS n FROM DUAL CONNECT BY level <= 10000 UNION ALL
  4  SELECT 'C' AS categ, level AS n FROM DUAL CONNECT BY level <= 10000
  5  /

Table créée.

SQL> CREATE INDEX test_iss_i1 ON test_iss(categ, n) COMPUTE STATISTICS
  2  /

Index créé.

SQL> exec dbms_stats.gather_table_stats(NULL, 'TEST_ISS')

Procédure PL/SQL terminée avec succès.

SQL> EXPLAIN PLAN FOR SELECT * FROM test_iss WHERE n = 1234
  2  /

Explicité.

SQL> SELECT * FROM TABLE(dbms_xplan.display)
  2  /

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 2032351434

--------------------------------------------------------------------------------
| Id  | Operation        | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT |             |     3 |    15 |     4   (0)| 00:00:01 |
|*  1 |  INDEX SKIP SCAN | TEST_ISS_I1 |     3 |    15 |     4   (0)| 00:00:01 |
--------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("N"=1234)
       filter("N"=1234)

14 ligne(s) sélectionnée(s).


Bien entendu, pour cette recherche, l'index avec la colonne "n" en première position aurait été plus efficace.
Mais en s'appuyant sur l'index de l'exemple, on couvre un plus grand nombre de requêtes tout en limitant le nombre d'index créés.

2) La compression d'indexes
Un index associe à une valeur de clef (éventuellement composite) l'adresse "physique" de la ligne dans la table (le rowid).
Les valeurs des clefs sont triées. Donc, potentiellement, dans les blocs feuilles, Les "préfixes" de ces valeurs peuvent se répéter un grand nombre de fois...
Dans l'exemple précédent, ça donnerait :
A;1 -> rowid1
A;2 -> rowid2
...
A;10000 -> rowid10000

Depuis Oracle 8.1, il est possible d'exploiter ces répétitions en les factorisant : c'est la compression d'index.
Ce que cela apporte ? Un index plus petit, et donc une économie de lecture de blocs pour les opérations de masse ! (soit sur les INDEX RANGE SCAN, mais aussi sur les INDEX FAST FULL SCAN)
(Bien entendu, si on ne cible qu'une seule valeur, ça ne change pas grand chose...)

Un petit exemple sur une table réelle.
La table HISTO_PTF est alimentée mensuellement pour historiser les performances des portefeuilles.
L'index de clef primaire est (ID_PTF , DATE_HISTO) : ID_PTF est la colonne la plus sélective (19000 valeurs distinctes sur 240000 lignes au total), alors que la colonne DT_HISTO comporte l'est très peu (13)
C'est donc un excellent exemple pour montrer l'effet de la compression : créer l'index par colonnes permutées.

SQL> CREATE INDEX test_col_ind ON histo_ptf(DATE_HISTO, ID_PTF) COMPRESS 1 COMPUTE STATISTICS
  2  /
Index created.

SQL> SELECT index_name, compression, leaf_blocks FROM dba_indexes WHERE table_name = 'HISTO_PTF'
  2  /

INDEX_NAME                     COMPRESS LEAF_BLOCKS
------------------------------ -------- -----------
PK_HISTO_PTF                   DISABLED        1941
TEST_COMP                      ENABLED         1239

36 % de gain !

3) Le clustering factor
Le clustering factor (CF) d'un index mesure la corrélation entre l'ordre des valeurs des clefs de l'index et l'ordre des lignes dans la table.
Lorsque le CF est proche du nombre de lignes dans la table, la corrélation est quasi nulle.
A l'inverse, lorsque le CF est proche du nombre de blocs, les lignes sont à peu près rangées dans le même ordre que les valeurs de la clef.

A quoi ça sert ?
Imaginez que vous devez récupérer un grand nombre de lignes dans une table en suivant un index.
A chaque lecture d'une valeur, vous devrez lire la ligne dans la table.
Si la corrélation CF est forte, vous devrez charger beaucoup moins de blocs.
A l'inverse, si vous devez en lire beaucoup, il sera peut être plus rentable de lire directement la table en entier !
Cette donnée statistique (toujours le CF) est utilisée par l'optimiseur pour évaluer le nombre de blocs à lire pour une requête.

Le lien avec la sélectivité des colonnes sur les indexes composites ?
Certaine colonnes peu sélectives représentent des catégories, ou des groupements de lignes.
Par exemple, si vous votre table stocke des factures contenant des références produit, il se peut que la référence produit soit plus sélective (pour peu que vous distribuiez une grande diversité de produits). Cependant, les lignes dans la table seront regroupées par référence facture, puisque celles-ci risquent d'être saisies en un bloc.

Pour visualiser la chose, nous reprendrons l'exemple du 2) : les performances sont historisée chaque mois, et donc l'insertion est faite par date.

SQL> SELECT index_name, clustering_factor FROM dba_indexes WHERE table_name = 'HISTO_PTF'
  2  /

INDEX_NAME                     CLUSTERING_FACTOR
------------------------------ -----------------
PK_HISTO_RISQUE_PTF                       232337
TEST_COMP                                   3090

SQL> SELECT index_name, clustering_factor FROM dba_indexes WHERE table_name = 'HISTO_PTF'
  2  /

INDEX_NAME                     CLUSTERING_FACTOR
------------------------------ -----------------
PK_HISTO_RISQUE_PTF                       232337
TEST_COMP                                   3090

L'index de test présente un CF parfait, l'autre le pire CF qu'on puisse imagine...
Ca en jette, non ?

Voilà voilà, j'ai toujours rêvé d'avoir un journal intime, et de le laisser traîner un peu partout pour que tout le monde puisse le lire.
C'est bien à ça que ça sert, un blog ?
J'ai enfin fait le pas. Je suis tellement heureux que je vais m'ouvrir une bière (et changer de caleçon éventuellement).

Bref plus sérieusement, j'ai vu qu'un collègue de forum avait créé un blog pour y poster des petits tours de magie en SQL...

Donc ici, à part mes élucubrations et les expressions de mes perversions les plus étranges, on va parler d'Oracle et de SQL.