Index Scan et Allocation Order Scans : Quesaco ?

Les opérations d’analyses d’un index (opérations logiques) peuvent engendrer 2 types d’opérations physiques appelés : Index Scans ou les Allocation Order Scans pour reprendre les termes anglophones. Chaque type d’opération est exécuté dans un contexte bien précis. C’est le moteur de stockage SQL Server qui décide de la stratégie à employer. Nous verrons cela dans un exemple très simple.

Je reprendrais l’exemple donné par zinzineti à l’occasion de la discussion d’un post sur developpez.com :

SET STATISTICS IO ON;

DECLARE @id INT = 1000

IF EXISTS (SELECT * FROM T_TEST2 WHERE id = @id)
PRINT ‘——— seek’

IF EXISTS (SELECT * FROM T_TEST2 WHERE id LIKE @id)
PRINT ‘——— index scan’

IF EXISTS (SELECT * FROM T_TEST2 WITH (NOLOCK) WHERE id LIKE @id)
PRINT ‘——— allocation order scan’

Nous venons de créer une table T_TEST2 qui contient un million de lignes avec un index non cluster sur la colonne id (colonne auto incrémenté). Le script suivant (extrait du post sur le forum developpez.com) va nous permettre de voir deux stratégies empruntées par le moteur de stockage. Nous utiliserons également SET STATISTICS IO pour visualiser l’activité IO généré par les 3 requêtes composants le script.

SET STATISTICS IO ON;

DECLARE @id INT = 1000

IF EXISTS (SELECT * FROM T_TEST2 WHERE id = @id)
PRINT ‘——— seek’

IF EXISTS (SELECT * FROM T_TEST2 WHERE id LIKE @id)
PRINT ‘——— index scan’

IF EXISTS (SELECT * FROM T_TEST2 WITH (NOLOCK) WHERE id LIKE @id)
PRINT ‘——— allocation order scan’

Voici tout d’abord un comparatif du plan d’exécution des 3 requêtes :

image

? et l’activité IO engendrée :

Table ‘T_TEST2′. Scan count 1, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
——— seek
Table ‘T_TEST2′. Scan count 1, logical reads 4, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
——— index scan
Table ‘T_TEST2′. Scan count 1, logical reads 66, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
——— allocation order scan

La première requête effectue une recherche d’index classique car le prédicat est sargable. (WHERE id = @id). La seconde requête effectuera un scan d’index car l’opérateur LIKE rend le prédicat non sargable. Enfin la 3ème requête effectue également un scan d’index mais en employant une autre stratégie d’extraction des données qui correspond à allocation order scan. Dans cette 3ème requête il faut noter que nous avons utilisé un niveau d’isolation des transactions différent avec le hint (NOLOCK) qui permet une lecture sale des données (dirty reads).

icon_arrow[7] Stratégies employées par le moteur de stockage :

Globalement, les plans d’exécution ne différent pas vraiment. On voit cependant que la recherche d’index est légèrement plus performante. Ce qui nous intéresse ici c’est l’activité IO : 4 lecteurs logiques pour le 2ème script contre 65 lectures logiques pour le 3ème script. Pourquoi cette différence ? Pour répondre à cela nous devons remonter aux stratégies employées par le moteur de stockage de SQL Server pour les analyses d’index :

Dans le cas présent aucun ordre n’est imposé pour retourné les données depuis l’index. On peut le remarquer en visualisant le détail concernant l’opérateur Index Scan de chaque plan d’exécution et le paramètre Ordered = False.

image

Ce paramètre est important car il laisse la possibilité au moteur de stockage de SQL Server d’employer la stratégie qui lui semble la plus performante selon le contexte d’exécution. Attention ordered = false ne signifie pas que l’index ne soit pas ordonné mais simplement que l’ordre des données à ramener n’a aucune importance. 2 stratégies peuvent être utilisés par le moteur de requête mais pour le moment rien ne nous indique de façon concrète la stratégie qu’emploiera le moteur de stockage. Nous pouvons essayer de la déduire en corrélant les résultats de SET STATISTICS IO et les données fournis par DCC IND et DBCC PAGE.

icon_arrow  Stratégie 1 : Index Scan :

Un index scan fait une analyse des pages situées au niveau feuille de l’index comme le montre le schéma ci-dessous. (Les pages de niveaux feuilles sont liées entre elles).

image

Dans mon cas l’index NC_IX_id correspond à l’index ayant une valeur d’id égale à 2.

SELECT
OBJECT_NAME(object_id) AS [object_name],
name AS index_name,
type_desc,
index_id
FROM sys.indexes
WHERE object_id = OBJECT_ID(‘T_TEST2′);

qui donne le résultat :

image

Pour le second script, il faut retrouver la 1ère page de l’index au niveau feuille et connaitre la page qui contient la valeur de clé égale à 1000. Le niveau feuille correspond toujours à une valeur de colonne IndexLevel égale à 0. La table temporaire me permet ici de retrouver rapidement l’information que nous cherchons.

CREATE TABLE #DBCCIND
(
PageFID INT,
PagePID INT,
IAMFID INT,
IAMPID INT,
ObjectID INT,
IndexID INT,
PartitionNumberID INT,
PartitionID BIGINT,
iam_chain_page VARCHAR(100),
PageType INT,
IndexLevel INT,
NextPageFID INT,
NextPagePID INT,
PrevPageFID INT,
PrevPagePID INT
);

INSERT INTO #DBCCIND
EXEC(‘DBCC IND( »TEST »,  »T_TEST2 », 2)’);

On récupère la première page du niveau feuille :

SELECT
PagePID,
PageType,
IndexLevel
FROM #DBCCIND
WHERE IndexLevel = 0
AND PrevPagePID = 0

image

DBCC TRACEON(3604);
DBCC PAGE(‘TEST’, 1, 579736, 3);

On peut voir que cette page contient les valeurs de clé de 1 à 539. L’index étant monotone pour le moment (sur une colonne de type IDENTITY) on peut admettre que les pages soient contigües. On peut d’ailleurs le vérifier avec DBCC PAGE dans l’entête ou DBCC IND avec la valeur de colonne NextPagePID pour la ligne correspond à la page 579736. On peut facilement voir que la page 579737 contient la valeur de clé égale à 1000 (valeur imposée dans notre script).

DBCC PAGE(‘TEST’, 1, 579737, 3);

image

Le moteur doit donc lire 2 pages dans cette première stratégie pour satisfaire à la requête du script. Une fois cette valeur trouvée la recherche s’arrête et on affiche le caractère 1 à l’écran. (IF EXISTS … PRINT ‘1’). Le moteur de stockage n’a pas besoin d’aller plus loin car la condition est satisfaite. Le nombre de pages lues correspond à celui trouvé pour la 2ème requête avec SET STATISTICS IO. (Des pages supplémentaires peuvent apparaitre. Celles-ci sont probablement celles qui hébergent les méta données. J’avoue qu’à ce stade je suis encore incapable de le dire Sourire ).

icon_arrow[3] Stratégie 2 : Allocation order scan :

Cette stratégie est différente de la première car elle utilise la page IAM affectée à la table et scanne les pages dans l’ordre physique du fichier conteneur comme le montre le schéma ci-dessous :

image

Cette fois il suffit d’utiliser la commande DBCC IND qui permet de compter le nombre de pages allouées à la table T_TEST2 dans l’ordre du fichier jusqu’à la page 579737 :

SELECT
COUNT(*) AS nb_pages
FROM #DBCCIND
WHERE PagePID <= 579737
AND PageType = 2

image

Le résultat correspond bien au nombre de pages lues pour la 3ème requête avec SET STATISTICS IO.

 

icon_arrow[9] Choix d’une stratégie par le moteur de stockage :

Alors comment SQL Server choisit de favoriser une stratégie par rapport à une autre dans notre exemple ? La réponse est la suivante :

Les allocation order scans sont favorisés lorsqu’aucune modification de données ne peut se produire pendant l’intervalle de lecture (avec TABLOCK, mode lecture seule par exemple …) , ou bien lorsque l’on stipule explicitement qu’une lecture sale est autorisée (NOLOCK, SET ISOLATION LEVEL READUNCOMMITED …).

 

icon_arrow[9] Pourquoi privilégier ce mode dans certains cas ?

L’intérêt des allocation order scans est qu’ils ne sont pas sujet à la fragmentation logique qui peut exister au niveau feuille contrairement aux index scan car le moteur de stockage lit les pages dans l’ordre physique du fichier, c’est à dire l’ordre dans lequel les pages ont été écrites. Ceci favorise généralement (en fonction du sous système disque ceci peut être faussé) les lectures séquentielles depuis le disque et rend l’analyse de l’index concernée plus rapide !!!

David BARBARIN (Mikedavem) 
MVP SQL Server

Laisser un commentaire