CoqBlog

SQL Server : extraction d’informations sur la fragmentation des valeurs d’une colonne à valeurs séquentielles

Il arrive, surtout lors de phases d’exploration de données existantes, de se demander quel est l’état de “fragmentation” des valeurs d’une colonne dont la valeur est séquentielle.
Vous aurez probablement déjà vu des solutions à ce problème sous le terme “gaps and islands”.

Je parle ici en gros des colonnes dont les définitions les rendent éligibles pour une utilisation de la propriété IDENTITY (mais pas forcément de colonnes sur lesquelles cette propriété est réellement définie) : la fragmentation de valeurs n’a aucun sens sur une colonne de type uniqueidentifier.
Je me base ici sur des incréments de 1 : c’est le cas le plus courant (de mon point de vue en tout cas) et ajouter la gestion d’un incrément différent alourdirai les requêtes.
En plus de cela je tiendrais quand même ici compte des valeurs négatives des types de données éligibles, même si la propriété IDENTITY ne peut être utilisée avec ces valeurs.

Les problèmes éventuels

Pour recevoir la propriété IDENTITY, une colonne doit être définie avec un des types suivants :

• tinyint
• smallint
• int
• bigint
• decimal / numeric (avec scale à 0)

Autant le dire de suite : la solution proposée ici ne permettra pas, en terme de taille du jeu de données en entrée, de couvrir l’intégralité des plages de ces types : la plage du type int (et donc de tinyint et smallint aussi) le sera, bigint ne le sera pas complètement, et je ne parle donc même pas de numeric…
La solution va ici reposer sur ROW_NUMBER, dont le type de retour est bigint et dont la numérotation commence à 1. Je n’ai pas trouvé d’information précise à ce sujet mais j’imagine qu’une fois la valeur maximale du type bigint atteinte, une erreur est levée.
En clair : nous sommes “limités” à un volume d’un maximum de 9223372036854775807 enregistrements dans la table/vue testée.
Je me vois de toute façon assez mal exécuter ce type de requête sur un tel volume, mais libre à vous de le faire si vous disposez d’un tel jouet (sur un serveur de développement ou test, bien entendu) et de nous faire par du résultat.

Soyez donc vigilant sur l’état de vos paramètres “SET ARITHABORT” et “SET ANSI_WARNINGS” lors de l’exécution de cette requête.

A propos des données

Pour l’exemple les requêtes seront ici basées sur une table contenant les données du fichier principal (allCountries.txt) des dumps GeoNames au 26/10/2008 : 6 674 082 enregistrements, avec une colonne de clé de type int.
Dans un contexte d’exploration, mon but principal est d’obtenir les informations le plus rapidement possible sans trop tenir compte des ressources consommées tant côté mémoire  que CPU et accès disque. Si la machine est assez bonne (dans mon cas il s’agissait d’un portable), les résultats devraient arriver plutôt rapidement.
Je pars aussi du principe que les indexes qui vont bien sont définis sur les colonnes impactées, donc ici un index nonclustered sur la colonne testée.

La requête

Voici la requête permettant de lister les gaps en donnant un jeu de résultat de la forme suivante :

Il serait assez difficile de la rendre lisible ici tout en la laissant lisible une fois placée dans un éditeur, je vous la donne donc de façon un peu brute en vous laissant la coller dans votre éditeur favori pour la lire.
Je me contente de mettre en avant les parties à personnaliser pour votre jeu de données.

USE [GeoNamesData];
GO

DECLARE @Seed bigint;
SET @Seed = 1;

-- Liste des gaps : [FreeIDsInGap] / [From] / [To]
-- Trié sur "From"
WITH StatsCTE AS
(
  SELECT
    ROW_NUMBER() OVER (ORDER BY Diff ASC ) AS RowNumber,
    MIN(ID) AS IDMin,
    MAX(ID) AS IDMax
  FROM (
        SELECT [ID],
          RowNumber,
          [ID] - RowNumber AS Diff
        FROM ( SELECT [GeonameId] AS ID,
                 ROW_NUMBER() OVER (ORDER BY [GeonameId] ASC ) - 1 AS RowNumber
               FROM [GeoNames].[MainData]
          ) AS [Values]
    ) AS [Stats]
  GROUP BY Diff
)
SELECT (MainData.IDMin - 1) - (ISNULL(PrecedingData.IDMax + 1, @Seed)) + 1 AS [FreeIDsInGap],
  ISNULL(PrecedingData.IDMax + 1, @Seed) AS [From],
  MainData.IDMin - 1 AS [To]
FROM StatsCTE AS MainData
  LEFT OUTER JOIN StatsCTE AS PrecedingData ON PrecedingData.RowNumber = MainData.RowNumber - 1
WHERE MainData.IDMin > @Seed
  AND (MainData.IDMin - 1) - (ISNULL(PrecedingData.IDMax + 1, @Seed)) + 1 > 0
ORDER BY [From] ASC;

Un intérêt de cette forme de requête, outre le gain de lisibilité apporté par la CTE, est la possibilité de manipuler facilement la sortie de cette dernière. Et cette sortie n’est autre que la fameuse liste d’islands, autrement dit la définition des îlots de valeurs contigües existants.

Vous pouvez ainsi sortir quelques statistiques :

-- Stats : nombre de gaps, taille de gap min, taille de gap max, taille moyenne, somme des IDs libres
WITH StatsCTE AS
( 
  ...
)
SELECT COUNT(*) AS GapCount,
  MIN([FreeIDsInGap]) AS GapSizeMin,
  MAX([FreeIDsInGap]) AS GapSizeMax,
  AVG([FreeIDsInGap]) AS GapSizeAvg,
  SUM([FreeIDsInGap]) AS FreeIDsSum
FROM (
        SELECT (MainData.IDMin - 1) - (ISNULL(PrecedingData.IDMax + 1, @Seed)) + 1 AS [FreeIDsInGap]
        FROM StatsCTE AS MainData
          LEFT OUTER JOIN StatsCTE AS PrecedingData ON PrecedingData.RowNumber = MainData.RowNumber - 1
        WHERE MainData.IDMin > @Seed
          AND (MainData.IDMin - 1) - (ISNULL(PrecedingData.IDMax + 1, @Seed)) + 1 > 0
    ) AS GapsData ;

Comment fonctionne la requête

Détaillons un peu plus le fonctionnement de cette requête listant les gaps.
Arriver à nos fins nécessite de connaitre pour un enregistrement n la valeur située à l’enregistrement n-1.
Un reflexe dans ce genre de cas pourrait être d’utiliser un curseur, chose que j’évite autant que possible, et qui serait à mon avis loin d’être viable sur un jeu de données important.
Faire une jointure du jeu de données complet sur lui même est aussi exclu pour les mêmes raisons.

La requête repose ici sur une supposition optimise (une fois n’est pas coutume) : le jeu de données en entrée n’est pas un vrai gruyère.
Comme dit plus haut, la CTE se contente de créer la liste d’îlots, et c’est sur cette liste que nous allons effectuer la jointure pour identifier les gaps : le gain est certains en cas de faible fragmentation car le jeu de données en sortie de la CTE sera faible (dans notre exemple la jointure sera faite sur 9584 enregistrements au lieu de 6674082) alors qu’en cas de gruyère complet nous nous approcherons du pire cas, sans pour autant le dépasser.

Cette phase se déroule en 3 étapes, différenciées par des couleurs (rouge pour la première, bleu pour la seconde et noir pour la dernière) :

Première étape :

Nous attribuons un numéro séquentiel (via ROW_NUMBER) à chaque enregistrement du jeu de données en entrée, trié sur la colonne ciblée.
Nous en profitons aussi pour effectuer une abstraction des noms du jeu de données d’entrée afin de ne pas avoir à modifier trop de choses au changement de celui-ci.

SELECT [GeonameId] AS ID,
ROW_NUMBER() OVER (ORDER BY [GeonameId] ASC ) - 1 AS RowNumber
FROM [GeoNames].[MainData]

Seconde étape :

A partir de ce jeu, nous bâtissons des statistiques composées de :

• l’ID
• le numéro séquentiel généré par ROW_NUMBER
• la différence entre la valeur de la colonne ciblée et le numéro séquentiel généré

SELECT [ID],
  RowNumber,
  [ID] - RowNumber AS Diff
FROM ( <<première étape>> 
  ) AS [Values]

Comme vous le constatez sur la portion choisie ci-dessus, cette différence va progressivement augmenter au fur et à mesure que nous rencontrons un nouvel îlot, tout en restant identique pour toutes les valeurs de l’îlot (l’ID et le numéro séquentiel évoluant du même incrément).

Troisième étape :

Vous l’aurez deviné, cette définition de “Diff” n’est pas choisie au hasard : elle va nous permettre de grouper les enregistrements des îlots pour en sortir les données qui nous intéressent !

• un numéro séquentiel d’îlot (généré via ROW_NUMBER, en triant sur Diff)
• la borne minimum de l’îlot
• la borne maximum de l’îlot

SELECT
  ROW_NUMBER() OVER (ORDER BY Diff ASC ) AS RowNumber,
  MIN(ID) AS IDMin,
  MAX(ID) AS IDMax
FROM ( 
      <<Seconde étape>>
  ) AS [Stats]
GROUP BY Diff

Nous avons notre liste d’îlots, nous n’avons plus qu’à en déduire nos gaps :-)

Pour cela nous effectuons une jointure de la sortie de notre CTE (MainData) sur elle même en décalant la valeur de RowNumber de 1 (PrecedingData), afin d’obtenir pour un enregistrement à la fois la valeur courante et la valeur précédente :

Que nous allons donc filtrer et manipuler pour obtenir les données qui nous intéressent :

Et voilà. Si vous connaissez mieux je prends, car personnellement je suis à court d’idées :-)

PS : les exemples sont ici donnés avec le type bigint pour @Seed, si vous devez cibler des données numeric faites les remplacements de type.