Les statistiques de chaîne de SQL Server

Article coécrit avec Claude, qui a mené une grande partie des tests et des recherches.

Les statistiques de chaîne

Les statistiques permettent l’estimation de la cardinalité. Elles sont composées de trois éléments : l’entête, le vecteur de densité et un histogramme. Je les ai décrites dans le chapitre Les statistiques et la cardinalité du livre Optimiser SQL Server, et dans la vidéo Introduction aux statistiques dans SQL Server.

L’histogramme d’une statistique découpe les valeurs de la première colonne en 200 étapes au maximum. Il répond bien à Nom = 'Dupont' ou à Nom >= 'Ma' AND Nom < 'Mb', mal à Email LIKE '%.org' : la fin d’une chaîne ne dit rien de sa place dans l’ordre de tri. Pour ces prédicats, SQL Server 2005 a ajouté un second objet, stocké avec la statistique, que la documentation appelle string summary statistics.

DBCC SHOW_STATISTICS est la commande historique de lecture d’une statistique. Elle renvoie trois jeux de résultats : l’en-tête, le vecteur de densité et l’histogramme ; les options WITH STAT_HEADER, DENSITY_VECTOR et HISTOGRAM limitent la sortie à l’une de ces parties. Depuis SQL Server 2012 SP1, la permission SELECT sur la table et sur toutes les colonnes de la statistique suffit ; avant, il fallait être propriétaire de la table ou membre de sysadmin, db_owner ou db_ddladmin. Deux fonctions de gestion dynamique la remplacent en partie, et se prêtent mieux aux requêtes sur toute une base : sys.dm_db_stats_properties (SQL Server 2008 R2 SP2 et 2012 SP1) pour l’en-tête, et sys.dm_db_stats_histogram (SQL Server 2016 SP1 CU2) pour l’histogramme. Aucune ne donne le vecteur de densité, ni la propriété String Index, ni le contenu du résumé de chaîne : pour les statistiques de chaîne, DBCC SHOW_STATISTICS reste la seule commande documentée.

La page de documentation de DBCC SHOW_STATISTICS est pratiquement le seul endroit où Microsoft documente aujourd’hui les statistiques de chaînes. Elle dit que ces statistiques sont stockées à part de l’histogramme, qu’elles servent aux prédicats LIKE, et qu’elles sont créées sur la première colonne clé de la statistique quand elle est de type char, varchar, nchar, nvarchar, varchar(max), nvarchar(max), text ou ntext. Une phrase ajoutée fin août 2026 (d’après l’historique de la page sur GitHub) excluait les colonnes en collation UTF-8 ; depuis le 7 octobre, elle n’exclut plus que les colonnes char et varchar dans ces collations. Aucune commande documentée n’affiche le contenu du résumé.

Le reste vient de deux livres blancs, Statistics Used by the Query Optimizer in Microsoft SQL Server 2005 et sa version 2008. Ils parlent d’une « technologie brevetée » qui résume la distribution des fréquences des sous-chaînes pour les formes de motif comme 'abc%', '%abc', '%abc%', 'a_c', 'a[bc]d', indiquent qu’un ESCAPE explicite casse cette statistique et qu’une chaîne de plus de 80 caractères est réduite à ses 40 premiers et 40 derniers caractères.

Le brevet est US 6 829 602, « System and method for using a compressed trie to estimate like predicates », déposé par Microsoft en 2002. Ce n’est cité par aucune source Microsoft dans la documentation SQL Server, mais quand on observe le résumé stocké dans une statistique, on y voit exactement la structure décrite dans la patente. De plus, le moteur appelle CSelCalcTrieBased le calculateur de sélectivité qui utilise ce résumé (sortie du trace flag 2363, voir « Lire le calculateur »). Comme dans le brevet, le résumé est un trie compressé de chaînes entières, avec un compteur par nœud. Le brevet construit le trie à partir d’un ensemble représentatif de chaînes, et ramène l’estimation à la table entière : si un quart des lignes y a été inséré, l’estimation est multipliée par quatre. SQL Server, de même, ne range dans ce trie qu’une partie des chaînes de la table. Pour estimer un LIKE, l’optimiseur compte les chaînes de cet échantillon qui satisfont le motif, et multiplie la proportion obtenue par le nombre de lignes de la table : sur la table Contact.ProspectUS de PachaDataFormation, la base d’exemple que j’utilise dans mes formations et mes articles, 241 des 2 825 chaînes de l’échantillon se terminent par .org, et l’estimation vaut 1 000 000 × 241 / 2 825, soit 85 310 lignes. La section « Lire le résumé » montre comment le vérifier.

Le trie (le mot vient de retrieval, la recherche d’information) est un arbre dont chaque chemin, de la racine à un nœud, épelle une chaîne. Les chaînes Martin, Martinez et Marty y partagent un nœud Mart, qui a deux enfants, in et y ; in a lui-même un enfant, ez. Un nœud compte combien de chaînes de l’échantillon se terminent sur lui : 1 pour Martin, 1 pour Martinez, 1 pour Marty, 0 pour Mart. Dans un trie ordinaire, chaque nœud contient un seul caractère : Mart y occuperait quatre nœuds à la file, M, a, r et t, qui n’ont chacun qu’un enfant. Un trie compressé (on parle aussi d’arbre radix, ou arbre PATRICIA) fusionne ces files de nœuds à enfant unique en un seul nœud, qui contient toute la suite de caractères : Mart tient alors dans un nœud au lieu de quatre. C’est la forme du résumé de SQL Server, où les morceaux de tous les nœuds sont stockés bout à bout dans une seule suite de caractères, et où chaque nœud donne la position et la longueur du sien dans cette suite. Les chaînes qui partagent leur début, comme les noms de famille ou des codes à préfixe commun, prennent ainsi peu de place.

flowchart TD
    R(("racine")) --> M["Mart<br/>0 chaîne"]
    M --> I["in<br/>1 chaîne : Martin"]
    M --> Y["y<br/>1 chaîne : Marty"]
    I --> E["ez<br/>1 chaîne : Martinez"]

Tout ce qui suit a été mesuré sur SQL Server 2025 CU7 (17.0.4065.4), niveau de compatibilité 170, sauf mention de l’estimateur hérité.

Trouver la statistique de chaîne

Les exemples utilisent la table Contact.ProspectUS de PachaDataFormation : un million de prospects, Nom et Email en varchar, collation French_CI_AS. La table a des statistiques créées automatiquement sur ces deux colonnes (_WA_Sys_...). Le script de chargement de la base les a recalculées par UPDATE STATISTICS ... WITH FULLSCAN : elles ont lu le million de lignes (rows_sampled vaut rows dans sys.dm_db_stats_properties), et non sur l’échantillon qu’une création automatique aurait pris. Sur un million de lignes, l’échantillonnage par défaut lit assez de lignes pour remplir le résumé de chaîne : le FULLSCAN ne change pas sa taille, mais il change les chaînes retenues, donc les estimations. Ici, j’appelle DBCC SHOW_STATISTICS avec le nom de colonne à la place du nom de la statistique, c’est supporté et c’est pratique :

USE [PachaDataFormation];
GO
-- La colonne String Index vaut YES ou NO
DBCC SHOW_STATISTICS ('Contact.ProspectUS', Email) WITH STAT_HEADER;
DBCC SHOW_STATISTICS ('Contact.ProspectUS', Nom) WITH STAT_HEADER;

Aucune vue système ne montre cette information : ni sys.stats ni sys.dm_db_stats_properties, ni sys.dm_db_stats_histogram. Pour une revue de toutes les statistiques d’une base, il faut passer DBCC SHOW_STATISTICS ... WITH STAT_HEADER statistique par statistique, par exemple dans un curseur avec INSERT ... EXEC.

Si on regarde sur une colonne, par type et par collation, statistiques sur les mêmes 100 000 valeurs, calculées en FULLSCAN :

L’exclusion UTF-8 ne touche donc que char et varchar, comme le dit la documentation : un nvarchar déclaré dans la même collation conserve son résumé. Pour lui, le suffixe _UTF8 ne change d’ailleurs rien : nchar et nvarchar restent en UTF-16, quelle que soit la collation (Prise en charge d’Unicode), et seules s’appliquent les règles de comparaison du reste du nom (Latin1_General_100_CI_AS_SC). Le suffixe ne change l’encodage que des char et varchar, qui passent en UTF-8. Même chose pour une statistique créée automatiquement (_WA_Sys_...), avec l’échantillonnage par défaut.

Les prédicats qui en profitent

L’estimateur de cardinalité confie chaque prédicat à un calculateur de sélectivité, un composant interne spécialisé. Ceux qui nous intéressent ici sont CSelCalcColumnInInterval pour un intervalle lu dans l’histogramme, CSelCalcHistogramComparison pour une comparaison, CSelCalcTrieBased pour le résumé de chaîne et CSelCalcFixedFilter pour une estimation fixe. Un trace flag non documenté affiche cette information, comme le montre la section « Lire le calculateur ». Si le résumé de chaîne a été utilisé, le calculateur est CSelCalcTrieBased.

Sur Contact.ProspectUS, estimations du plan, nombres réels et calculateur utilisé :

USE [PachaDataFormation];
GO
-- Trois écritures du même filtre sur le préfixe
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE 'Mc%';
SELECT Nom FROM Contact.ProspectUS WHERE Nom >= 'Mc' AND Nom < 'Md';
SELECT Nom FROM Contact.ProspectUS WHERE LEFT(Nom, 2) = 'Mc';

-- Un suffixe
SELECT Nom FROM Contact.ProspectUS WHERE Email LIKE '%.org';
SELECT Nom FROM Contact.ProspectUS WHERE RIGHT(Email, 4) = '.org';
SELECT Nom FROM Contact.ProspectUS WHERE CHARINDEX('.org', Email) > 0;

Étonnamment, la recherche par préfixe (Nom LIKE 'Mc%') passe par le résumé de chaîne plutôt que par l’histogramme, et cela donne un meilleur résultat : pour l’intervalle équivalent, l’histogramme doit répartir les lignes des étapes où tombent les bornes, alors que le résumé a compté les chaînes de son échantillon. LEFT est estimé comme un intervalle, par un autre calcul sur l’histogramme. Sur une autre table de test, l’écart devient énorme. Elle compte un million de lignes, et les 1 000 valeurs qui commencent par QA1 sont les plus grandes de la colonne : elles tombent toutes dans la dernière étape de l’histogramme. L’intervalle s >= 'QA1' AND s < 'QA2' y est estimé à 2 lignes. LIKE 'QA1%', qui passe par le résumé, est estimé à 710 ou à 1 065 lignes, selon la reconstruction de la statistique (voir « L’échantillon »).

Pour RIGHT, la sortie du trace flag 2363 montre deux calculs : une estimation fixe de 10 %, puis une estimation d’égalité tirée de la densité de la colonne Email, presque unique, qui donne une ligne pour 85 060 réelles. CHARINDEX produit une estimation fixe de 30 % : aucune statistique ne décrit son résultat, et l’optimiseur applique 30 % à toute comparaison >, >=, < ou <= qu’il ne sait pas estimer, comme LEN(Email) > 10 ou Email > @v avec une variable locale. Email <> @v reçoit 90 % ; Email = @v est estimé par la densité. Sur une fonction de la colonne, = passe par 10 % puis par la densité, comme RIGHT (LEN(Email) = 10 : une ligne), et <> est estimé comme un < ou un > (LEN(Email) <> 10 : 510 000).

Sur le jeu de test, avec des chaînes de trois caractères placées en tête, au milieu ou en fin de chaîne, les motifs 'abc%', '%abc', '%abc%', 'a_c%', '%a[bc]_%' et NOT LIKE passent tous par le résumé. Il suit la collation : '%Vill%' et '%vïll%' donnent la même estimation sur une colonne French_CI_AI ; en _CS_AS ou _BIN2, '%zqw' et '%ZQW' sont estimés séparément, chacun assez près de la réalité.

Un motif à plusieurs jokers est estimé d’un bloc, sans hypothèse d’indépendance entre ses morceaux. Sur 100 000 lignes, AAA et BBB présents chacun dans la moitié des chaînes : quand ils ne sont jamais dans la même chaîne, '%AAA%BBB%' est estimé à 3,6 lignes pour 0 ; quand ils sont toujours ensemble, à 49 982 pour 50 000.

L’estimateur hérité (USE HINT ('FORCE_LEGACY_CARDINALITY_ESTIMATION')) lit le même résumé : mêmes estimations à la décimale pour tous les LIKE de littéraux mesurés qu’il estime par le résumé. Ses estimations sans résumé, elles, diffèrent (plus bas).

Lire le calculateur

Les noms de calculateur viennent du trace flag 2363, qui n’est pas documenté. Il écrit dans l’onglet des messages le détail du calcul de sélectivité de l’estimateur actuel, avec le trace flag 3604 :

USE [PachaDataFormation];
GO
SELECT Nom
FROM Contact.ProspectUS
WHERE Email LIKE '%.org'
OPTION (RECOMPILE, QUERYTRACEON 3604, QUERYTRACEON 2363);

Plan for computation:
  CSelCalcTrieBased
      Column: QCOL: [PachaDataFormation].[Contact].[ProspectUS].Email
Selectivity: 0.0853097

Les limites du résumé

Le résumé de chaîne ne peut pas être utilisé dans les cas suivants :

• La colonne est utilisée dans une expression ou passée dans une fonction ;
• Le motif est dans une variable locale, seul ou concaténé à des jokers, sauf avec OPTION (RECOMPILE) ;
• Le motif est de type nvarchar alors que la colonne est en varchar, qu’il s’agisse d’un littéral N'...' ou d’un paramètre ;
• Le LIKE a une clause ESCAPE, même inutile ;
• La colonne est un char ou un varchar en collation UTF-8 : ses statistiques n’ont pas de résumé ;
• La colonne n’est la première colonne d’aucune statistique ;
• Le motif ne contient aucun joker : c’est alors une égalité, estimée par l’histogramme.

Le tableau suivant montre l’estimation de différents prédicats sur une table de test d’un million de chaînes hexadécimales aléatoires, où 1 000 chaînes commencent par QA1, 10 000 contiennent QB2 et 100 000 se terminent par QC3. Toutes les écritures cherchent les 10 000 chaînes qui contiennent QB2, et toutes ont été mesurées avec la même statistique.

Les conséquences pratiques :

• Pour chercher un caractère joker, l’échapper par crochets plutôt que par ESCAPE : '%K[_]9%' est estimé par le résumé (CSelCalcTrieBased), '%K\_9%' ESCAPE '\' est estimé à 9 % ; même un ESCAPE inutile, '%QB2%' ESCAPE '\', passe de 9 936 à 90 000. Le livre blanc de 2005 indiquait déjà qu’un ESCAPE fait estimer la sélectivité sans le résumé, et c’est encore vrai sur SQL Server 2025, avec un motif littéral.
• Une fonction autour de la colonne (LOWER, UPPER, RTRIM) fait perdre le résumé. Sur une collation insensible à la casse, LOWER n’apporte rien au résultat et coûte l’estimation : 90 000 pour '%qb2%', et 3 lignes pour LOWER(s) LIKE 'qa1%', estimé par l’histogramme, contre 1 065 pour s LIKE 'QA1%' (1 000 réelles). Sur Contact.ProspectUS, LOWER(Email) LIKE '%.org' reçoit aussi l’estimation de 90 000.
• Une variable locale n’est pas lue à la compilation : l’estimation de 9 % s’applique, sauf avec OPTION (RECOMPILE). Un paramètre l’est, pour sa première valeur seulement : une procédure compilée pour '%QA1%' (estimé 1 065) a gardé ce plan pour '%QC3%', qui en ramène 100 000.
• Un motif nvarchar comparé à une colonne varchar fait aussi perdre le résumé : sur Contact.ProspectUS, Email LIKE N'%.org' reçoit l’estimation de 9 % (CSelCalcFixedFilter (0.09)), comme un paramètre @m nvarchar(20) passé par sp_executesql, alors qu’un paramètre varchar(20) donne l’estimation du résumé. Un préfixe nvarchar passe par l’histogramme, et s’en sort mal : Email LIKE N'ab%' est estimé à 430 lignes, contre 2 478 pour 'ab%', pour 2 669 réelles. SqlClient déduit NVarChar d’une String .NET quand le type du paramètre n’est pas précisé (Configuring parameters), et le pilote JDBC envoie les chaînes en Unicode tant que sendStringParametersAsUnicode vaut true, sa valeur par défaut (propriétés de connexion). Il faut donc, mais ce n’est pas nouveau, déclarer le paramètre dans le type de la colonne.
• Passer une colonne de varchar à une collation UTF-8 retire le résumé à ses statistiques. Les LIKE qui commencent par un joker sont estimés à 9 %, les préfixes passent par l’histogramme ('QA1%' : 2 lignes estimées pour 1 000). Sur une copie du jeu de test en UTF-8, '%QC3' passait de 100 852 (pour 100 000) à 90 000, et '%QB2%' de 9 233 (pour 10 000, sur une autre construction de la statistique) à 90 000.
• Une statistique sur plusieurs colonnes n’a de résumé que pour la première, comme son histogramme.

Ces estimations sans résumé diffèrent selon l’estimateur. L’estimateur actuel applique 9 % à tout LIKE à joker initial qu’il ne sait pas estimer (CSelCalcFixedFilter (0.09)), quelle que soit la longueur du motif ; un préfixe sans résumé, ou avec ESCAPE, est estimé par l’histogramme ('QA1%' ESCAPE '\' : 2 lignes pour 1 000). L’estimateur hérité dépend de la longueur : sur ce jeu d’un million de lignes, sans résumé, '%Q%' donne 612 216, '%QB%' 306 108, '%QB2%' 204 072, un motif de onze caractères 55 656 : une proportion divisée par le nombre de caractères, pour un motif littéral encadré de %. Un suffixe '%QC3' en reçoit la moitié, 102 036. La proportion dépend de la colonne : 61,2 % ici, de 41 % à 74 % sur d’autres jeux, de chaînes de 10 à 60 caractères. Les valeurs de la colonne CE 70 du tableau sont donc propres à ce jeu, alors que les 90 000 de l’estimateur actuel se retrouvent partout. Les jokers internes donnent d’autres valeurs, non mesurées ici.

Lire le résumé

Le résumé est stocké dans le blob de la statistique, avec l’histogramme. DBCC SHOW_STATISTICS ... WITH STATS_STREAM rend ce blob en entier, précédé d’un en-tête de 64 octets, et on le récupère en T-SQL par INSERT ... EXEC dans une colonne varbinary(max). L’exemple de la petite table, plus bas, le fait.

Le format n’est pas documenté. J’ai utilisé Claude pour le déduire, et il l’a fait en construisant des tables de quelques lignes dont il connaissait chaque octet, en ne changeant qu’une chose d’une table à l’autre, puis en comparant les blobs. Le résumé suit l’histogramme, après un marqueur fixe. Son en-tête donne le nombre de NULL rencontrés par l’échantillonnage, le nombre de valeurs échantillonnées, NULL compris, le nombre de valeurs distinctes de l’échantillon, où NULL compte pour une, deux fois 40, les longueurs de la troncature, huit octets nuls, et le nombre de caractères qui suivent. Viennent ensuite les caractères de l’échantillon, mis bout à bout, puis les nœuds du trie.

Le plus simple est de le voir sur une petite table. Celle-ci compte huit noms, dont Martin deux fois ; sous onze lignes, l’échantillon les garde toutes :

USE [PachaDataFormation];
GO
CREATE TABLE dbo.DemoTrie (Nom varchar(50) COLLATE French_CI_AS);
INSERT dbo.DemoTrie (Nom)
VALUES ('Martin'), ('Martinez'), ('Marty'), ('Martin'),
       ('Dupont'), ('Durand'), ('Dubois'), ('Dupuis');
CREATE STATISTICS st_Nom ON dbo.DemoTrie (Nom) WITH FULLSCAN;
GO
-- Le blob de la statistique, en hexadécimal
DECLARE @flux TABLE (stats_stream varbinary(max), [rows] bigint, data_pages bigint);
INSERT @flux EXEC ('DBCC SHOW_STATISTICS (''dbo.DemoTrie'', st_Nom) WITH STATS_STREAM');
SELECT CONVERT(varchar(max), stats_stream, 2) AS blob FROM @flux;
GO
DROP TABLE dbo.DemoTrie;

L’en-tête du résumé annonce 0 NULL, 8 valeurs échantillonnées, 7 distinctes, puis 26 caractères, qui sont les morceaux de tous les nœuds mis bout à bout : DuboispontuisrandMartinezy. Suivent onze nœuds de cinq octets, en ordre préfixe :

Le premier octet contient les drapeaux : 0x80 quand le nœud a un frère après lui, 0x40 quand le nœud suivant est son premier enfant. Ses quatre bits bas stockent le compteur quand il ne dépasse pas 15 : 2 pour Martin, 1 pour les autres chaînes, 0 pour les nœuds où aucune chaîne ne se termine, comme Du ou Mart. Un compteur plus grand ajoute après le nœud un octet, signalé par le drapeau 0x10, ou quatre, signalés par 0x20 (249 est le plus grand compteur sur un octet que j’aie vu, 295 le plus petit sur quatre). Le deuxième octet donne la longueur du morceau, les trois suivants sa position dans la suite de caractères. La chaîne d’un nœud est la suite des morceaux de ses ancêtres, puis le sien : on lit Du, puis p, puis ont, et on obtient Dupont.

flowchart TD
    R(("racine")) --> DU["Du · 0"]
    R --> MART["Mart · 0"]
    DU --> BOIS["bois · 1 : Dubois"]
    DU --> P["p · 0"]
    DU --> RAND["rand · 1 : Durand"]
    P --> ONT["ont · 1 : Dupont"]
    P --> UIS["uis · 1 : Dupuis"]
    MART --> IN["in · 2 : Martin"]
    MART --> Y["y · 1 : Marty"]
    IN --> EZ["ez · 1 : Martinez"]

Le résumé ne stocke aucune sous-chaîne : ce sont les chaînes entières, en varchar dans le code page de la colonne, en nvarchar en UTF-16. En collation insensible à la casse, MiXeD, mixed et Mixed font une seule entrée, de compteur 3.

Il n’y a donc qu’un trie par statistique, et il reste petit : au plus 2 800 chaînes environ, de 80 caractères au plus, soit quelque 224 Ko avant le partage des débuts communs, et c’est autour de 200 Ko (194 Ko en varchar, 212 Ko en nvarchar dans mes essais) que SQL Server coupe l’échantillon en deux (voir « L’échantillon »). Le trie ne sert pas non plus de moteur de recherche. Pour LIKE '%.org', l’estimation vaut exactement le nombre de chaînes de l’échantillon qui satisfont le motif, comme si l’optimiseur les reconstituait une à une pour leur appliquer le LIKE ; je n’ai pas vu comment il parcourt l’arbre pour y arriver, seulement le résultat. Un trie n’accélère d’ailleurs que la recherche par le début d’une chaîne, ce qui ne sert à rien pour un motif qui commence par %. Il sert à stocker l’échantillon de façon compacte et à compter les doublons ; quelques milliers de comparaisons à la compilation coûtent peu.

Le script string-summary.sql décode le résumé d’une statistique, liste les chaînes échantillonnées et calcule l’estimation que le résumé donne pour un motif, à condition que le prédicat l’utilise (motif du même type que la colonne, sans fonction autour de la colonne). Lancé tel quel, sur la statistique de Contact.ProspectUS.Email, il trouve 2 825 valeurs échantillonnées, dont 29 NULL, et 241 chaînes qui satisfont '%.org' : 1 000 000 × 241 / 2 825 = 85 309,7, l’estimation du plan.

L’échantillon

Une table de 10 000 lignes de valeurs 0000001 à 0010000 donne un résumé de 510 chaînes, espacées de 19 ou 20 valeurs dans l’ordre de tri. Les mêmes valeurs insérées dans l’ordre inverse, ou dans un ordre aléatoire, donnent les mêmes 510 chaînes : l’échantillon est pris à pas fixe dans le flux trié de la construction, quel que soit l’ordre physique des lignes. Une valeur présente dans 30 % des lignes occupe 153 places sur 510, soit 30 %.

Sa taille vaut 5 % des lignes lues par la statistique plus 10, sans dépasser le nombre de lignes (une table de quatre lignes les garde toutes) : 510 chaînes pour 10 000 lignes, 1 010 pour 20 000, 2 510 pour 50 000. Avec un échantillonnage, ce sont 5 % des lignes échantillonnées : sur une table de 40 000 lignes larges, SAMPLE 2 PERCENT lit 984 lignes, et le résumé garde 59 chaînes, contre 2 018 en FULLSCAN. Elle plafonne ensuite vers 2 820 : le plafond est atteint vers 56 000 lignes, et il tient jusqu’à 3 000 000, la plus grande table mesurée (2 814 à 2 830 selon les données et le parallélisme). Le plafond est aussi une limite de place, et pas seulement un nombre de chaînes : quand l’échantillon ne tient pas dans le résumé, SQL Server en garde une chaîne sur deux. Sur 200 000 chaînes distinctes et dissemblables, avec MAXDOP = 1, l’échantillon garde 2 824 chaînes de 65 caractères, et tombe d’un coup à 1 412 chaînes de 66 caractères ; la statistique stockée pesait alors 211 Ko. C’est la place occupée dans le trie qui compte, et non la longueur : des chaînes de 200 caractères qui partagent leur début gardent les 2 824. En nvarchar, le plafond de départ est plus bas, 2 409 chaînes, et il passe à 1 205 entre 43 et 44 caractères (86 et 88 octets), pour un résumé d’environ 212 Ko contre 194 Ko en varchar au même moment. Ce plafond de départ ne dépend que de la largeur des caractères : 2 824 en char, varchar et varchar(max), 2 409 en nchar, nvarchar et nvarchar(max), quelle que soit la longueur déclarée de la colonne, sa collation (BIN2, collation SQL, japonaise ou UTF-8) ou la longueur des chaînes sous le seuil. La règle qui le fixe reste à trouver. L’échantillon des e-mails de la base de démonstration en compte 2 410 en nvarchar, contre 2 825 en varchar.

L’estimation d’un LIKE à joker se calcule alors exactement : le nombre de lignes de la table, multiplié par le nombre de chaînes de l’échantillon qui satisfont le motif, divisé par la taille de l’échantillon. Sans aucune chaîne qui le satisfait, le compte vaut 0,1. Sur dix motifs ('%x%', 'x%', '%x', _, [bc], deux % internes), le calcul fait sur l’échantillon décodé a donné l’estimation du plan à la décimale. Une égalité sans joker passe par l’histogramme.

Les estimations avancent donc par paliers d’une chaîne échantillonnée, 354 lignes sur le million de prospects (1 000 000 / 2 825), avec un plancher de 35,4 :

USE [PachaDataFormation];
GO
-- Estimation contre nombre réel, pour des noms de fréquences différentes
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Aguila';
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Baldwin';
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Wilson';

Le même plancher se lit sur des tables de tailles différentes :

Le rapport vaut dix fois la taille de l’échantillon : 5 100 pour 510 chaînes, 15 100 pour 1 510, 28 140 pour 2 814. Sur la table de trois millions de lignes, une sous-chaîne présente 1, 10 ou 100 fois est estimée à 106,5, comme une sous-chaîne absente ; à 999 occurrences, elle est estimée à 1 065, une chaîne de l’échantillon ; à 10 000, à 11 719, onze chaînes d’un échantillon de 2 816, construit une autre fois. Pour des chaînes de 200 caractères toutes différentes, l’échantillon tombe à environ 1 410 chaînes en varchar (1 200 en nvarchar), et le plancher à environ le nombre de lignes divisé par 14 000.

Un échantillon aussi petit estime pourtant bien les motifs fréquents, parce que sa précision dépend du nombre de chaînes qui satisfont le motif, et non de la fraction de la table qu’il représente. C’est le principe du sondage : un millier de personnes interrogées donne la même marge d’erreur sur une petite ville que sur un grand pays. Pour une proportion p mesurée sur n chaînes, l’erreur relative typique vaut environ √((1 − p) / (n × p)). Avec '%.org', 241 chaînes de l’échantillon satisfont le motif, et l’erreur attendue est d’environ 6 % : l’estimation de 85 310 pour 85 060 lignes réelles est donc en partie de la chance, un écart de 10 % aurait été aussi normal.

Le pas fixe dans l’ordre de tri favorise en plus les préfixes. Les lignes qui satisfont 'Mc%' forment un bloc contigu dans cet ordre, et un pas de 354 lignes y tombe toujours 49 ou 50 fois : l’erreur ne dépasse pas une chaîne échantillonnée, soit 354 lignes, et on obtient 17 699 lignes estimées pour 17 620. Un suffixe ou une sous-chaîne, dispersés dans l’ordre de tri, n’ont pas cet avantage, et l’échantillon se comporte pour eux à peu près comme un tirage au hasard.

Pour un motif rare, la précision est celle d’un échantillon de quelques dizaines de chaînes. Une sous-chaîne présente dans 1 % d’un million de lignes, soit 28 chaînes attendues dans l’échantillon, y en avait 27, 32, 28 puis 27 sur quatre UPDATE STATISTICS ... WITH FULLSCAN successifs, sans changement de données : estimations de 9 585, 11 356, 9 947 et 9 581 pour 10 000. En parallèle, la taille de l’échantillon variait aussi, de 2 815 à 2 818 chaînes. Avec MAXDOP = 1, les reconstructions donnent toutes le même échantillon, de 2 824 chaînes, qui contenait ici 22 fois la sous-chaîne : 7 790 lignes estimées. Sur trois reconstructions d’une autre table, le même effet avait donné 5 329, 10 653 et 6 392 pour 10 000.

La documentation de SQL Server 2005 (Index Statistics) prévenait que le résumé n’est pas conservé quand il dépasse ce que le moteur peut maintenir, avec l’exemple de 85 000 valeurs varchar(80) uniques et dissemblables, en FULLSCAN. L’exemple ne se reproduit plus : avec 85 000 valeurs uniques de 80 caractères, String Index vaut YES, et l’échantillon est réduit à 1 413 chaînes.

Au-delà de 80 caractères

La règle des livres blancs tient toujours. Table de 100 000 chaînes de 200 caractères, une sous-chaîne de trois caractères placée en position 5, 60, 100 ou 190, un quart des lignes chacun :

Les positions 60 et 100 tombent hors des 40 premiers et des 40 derniers caractères : l’échantillon ne les contient pas, et elles reçoivent le plancher. Avec des chaînes de 79 à 82 caractères et une sous-chaîne à cheval sur le 40e et le 41e caractère, l’estimation est juste à 79 et 80 caractères (25 710 et 25 994), et tombe à 1 634 puis 1 136 à 81 et 82, en varchar Latin1 comme en nvarchar ; ces deux valeurs viennent d’occurrences fortuites ailleurs dans mes chaînes hexadécimales, et une sous-chaîne qui n’apparaît nulle part ailleurs tombe au plancher.

Le résumé stocke les 40 premiers et les 40 derniers caractères mis bout à bout, et un motif peut donc correspondre à la jonction. Sur 100 000 chaînes de 200 caractères avec un Q en position 40 et un W en position 161, '%QW%', qui ne figure dans aucune ligne, est estimé à 100 000 ; '%Qm%' et '%mW%', présents dans toutes les lignes, sont estimés à 3,5.

En varchar, le seuil se compte en octets. Sur une colonne varchar en Japanese_CI_AS dont les dix premiers caractères occupent deux octets chacun, une sous-chaîne placée aux caractères 39 à 41 reste visible dans une chaîne de 76 caractères (86 octets), et disparaît dans une chaîne de 79 caractères (89 octets) : 3,6 lignes estimées pour 25 000. La même valeur en nvarchar reste estimée à 24 230 : là, le seuil est de 80 caractères.

Sur des colonnes varchar(max) de 100 à 20 000 caractères, un préfixe et un suffixe sont bien estimés, avec l’imprécision d’un échantillon d’environ 1 400 chaînes ; tout ce qui se trouve entre les deux est invisible. Pour une colonne de commentaires ou de descriptions, un LIKE '%mot%' dont les occurrences ne se trouvent qu’au milieu des textes peut donc recevoir l’estimation d’un motif absent, comme dans ces essais. Pour chercher des mots dans un long texte, la recherche en texte intégral (CONTAINS) est l’outil prévu ; elle trouve des mots et des préfixes de mots, et un fragment pris au milieu d’un mot lui échappe.

Ce qu’il faut retenir

• Un LIKE qui compare la colonne, sans fonction autour, à un littéral est souvent mieux estimé qu’on ne le croit, y compris '%abc%'. L’écrire tel quel plutôt qu’avec LEFT, RIGHT, CHARINDEX ou LOWER.
• Échapper un joker par crochets, pas par ESCAPE.
• Un motif dans une variable locale reçoit une estimation fixe ; OPTION (RECOMPILE) rend l’estimation au résumé, un paramètre du type de la colonne la donne pour sa valeur de compilation.
• Un varchar en collation UTF-8 n’a pas de résumé de chaîne ; un nvarchar dans la même collation en a un.
• Passer le motif dans le type de la colonne : un littéral ou un paramètre nvarchar face à une colonne varchar perd le résumé (9 % pour un motif qui commence par un joker, l’histogramme pour un préfixe).
• Le résumé est un échantillon de 5 % des lignes lues plus 10, plafonné vers 2 800 chaînes dès 56 000 lignes environ (2 400 en nvarchar, moitié moins pour des chaînes longues et dissemblables). Un motif présent dans moins d’une ligne sur 2 800 environ peut être estimé comme absent, et un motif rare l’est avec l’imprécision d’un petit échantillon.
• D’une longue chaîne, le résumé ne garde que les 40 premiers et les 40 derniers caractères (octets en varchar), mis bout à bout.

Améliorations possibles

Maintenant que le format est lisible, on peut se demander comment il pourrait évoluer. Les pistes suivantes sont un avis de lecteur, sans mesure du coût de chaque changement : Microsoft a des contraintes que l’on ne voit pas d’ici, comme le temps de compilation, la taille du blob ou la compatibilité du format entre versions.

Quatre cas perdent le résumé ou le trompent, alors que la correction semble à portée de main. Sur une table de 100 000 lignes dont 2 000 se terminent par .org, le motif varchar est estimé à 1 954 lignes, et chacun des trois premiers cas à 9 000 :

• un motif nvarchar face à une colonne varchar, littéral N'...' ou paramètre, perd le résumé, et un motif qui commence par un joker reçoit l’estimation de 9 %. Le convertir dans le type de la colonne, quand la conversion ne perd rien, suffirait. Les pilotes .NET envoient les chaînes en nvarchar par défaut, ce qui rend ce cas courant ;
• ESCAPE fait aussi perdre le résumé, alors que l’estimation consiste déjà à appliquer un LIKE aux chaînes de l’échantillon ;
• LOWER(colonne) ne change rien au résultat sur une collation insensible à la casse, et pourrait être ignoré pour l’estimation ;
• la troncature à 40 + 40 caractères met bout à bout le début et la fin de la chaîne. Sur des chaînes de 100 caractères où un Q finit les 40 premiers et un W commence les 40 derniers, '%QW%', qui ne correspond à aucune ligne, est estimé à 100 000. Un marqueur de jonction, que le motif ne pourrait pas traverser, éviterait ces fausses correspondances. L’effet inverse, une sous-chaîne prise dans la partie supprimée et estimée au plancher, est le prix de la troncature elle-même.

D’autres pistes touchent le fond du mécanisme, et leur intérêt dépend des données :

• le trie compte déjà les doublons, mais seulement dans l’échantillon. Pour une colonne de quelques valeurs distinctes sur un million de lignes, les valeurs et leur nombre exact de lignes tiendraient en quelques octets, et l’estimation deviendrait exacte ;
• tous les motifs absents de l’échantillon reçoivent le même plancher, un dixième de chaîne, alors qu’un motif de deux caractères absent est bien plus probable qu’un motif de douze. La littérature sur l’estimation des sous-chaînes, comme les arbres des suffixes élagués (Krishnan, Vitter et Iyer, 1996) ou les travaux de Chaudhuri, Ganti et Gravano (2004) sur la sous-estimation, propose de décomposer le motif absent en morceaux présents ;
• la taille de l’échantillon ne suit pas celle de la table : sur cent millions de lignes, si le plafond tient, le calcul donne un plancher de 3 500 lignes. Un échantillon qui grandirait un peu avec la table, dans la limite de place, réduirait ce saut ;
• en parallèle, deux UPDATE STATISTICS ... WITH FULLSCAN successifs, sans changement des données, donnent des échantillons différents, donc des estimations différentes. Un prélèvement au même pas, quel que soit le découpage entre threads, rendrait les plans reproductibles.

Le compromis actuel se défend malgré tout : un échantillon de 2 800 chaînes dans un trie compressé tient dans 200 Ko environ, s’applique vite à la compilation, estime bien les motifs fréquents, et ses erreurs sur les motifs rares changent rarement le plan.