Localisez le plus petit élément manquant en fonction d'une formule spécifique

J'ai besoin de pouvoir localiser un élément manquant dans une table avec des dizaines de millions de lignes, et possède une clé primaire d'une BINARY(64)colonne (qui est la valeur d'entrée à partir de laquelle calculer). Ces valeurs sont principalement insérées dans l'ordre, mais à l'occasion, je souhaite réutiliser une valeur précédente qui a été supprimée. Il est impossible de modifier les enregistrements supprimés avec une IsDeletedcolonne, car parfois une ligne est insérée qui est plusieurs millions de valeurs en avance sur les lignes existantes. Cela signifie que les données d'exemple devraient ressembler à ceci:

KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF

Ainsi, l'insertion de toutes les valeurs manquantes entre 0x000000000002et 0xFFFFFFFFFFFFest impossible, la quantité de temps et d'espace utilisé serait indésirable. Essentiellement, lorsque j'exécute l'algorithme, je m'attends à ce qu'il revienne 0x000000000003, ce qui est la première ouverture.

J'ai trouvé un algorithme de recherche binaire en C #, qui interrogerait la base de données pour chaque valeur à la position iet tester si cette valeur était attendue. Pour le contexte, mon terrible algorithme: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Cet algorithme exécuterait, par exemple, 26-27 requêtes SQL sur une table avec 100 000 000 éléments. (Cela ne semble pas beaucoup, mais cela se produira très fréquemment.) Actuellement, ce tableau contient environ 50 000 000 de lignes et les performances deviennent perceptibles .

Ma première pensée alternative est de traduire cela en une procédure stockée, mais qui a ses propres obstacles. (Je dois écrire un BINARY(64) + BINARY(64)algorithme, ainsi qu'un tas d'autres choses.) Ce serait douloureux, mais pas irréalisable. J'ai également envisagé de mettre en œuvre l' algorithme de traduction basé sur ROW_NUMBER, mais j'ai un très mauvais pressentiment à ce sujet. (A BIGINTn'est pas assez grand pour ces valeurs.)

Je suis prêt pour d' autres suggestions, car j'ai vraiment besoin que cela soit aussi rapide que possible. Pour ce que ça vaut la seule colonne sélectionnée par la requête C # est la KeyCol, les autres ne sont pas pertinentes pour cette partie.

En outre, pour ce que cela vaut, la requête actuelle qui récupère l'enregistrement approprié va dans le sens de:

SELECT [KeyCol]
  FROM [Table]
  ORDER BY [KeyCol] ASC
  OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY

Où <VALUE>est l'index fourni par l'algorithme. Je n'ai pas encore eu de BIGINTproblème avec OFFSET, mais je le ferai. (Avoir seulement 50 000 000 lignes en ce moment signifie qu'il ne demande jamais d'index au-dessus de cette valeur, mais à un moment donné, il dépassera la BIGINTplage.)

Quelques données supplémentaires:

• Des suppressions, le gap:sequentialrapport est d'environ 1:20;
• Les 35 000 dernières lignes du tableau ont des valeurs> BIGINTmaximum;

Joe a déjà touché la plupart des points que je viens de passer une heure à taper, en résumé:

• il est très douteux que vous manquiez de KeyColvaleurs < bigintmax (9.2e18), donc les conversions (si nécessaire) vers / depuis bigintne devraient pas être un problème tant que vous limitez les recherches àKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• Je ne peux pas penser à une requête qui va trouver «efficacement» un écart tout le temps; vous pourriez avoir de la chance et trouver un écart vers le début de votre recherche, ou vous pourriez payer cher pour trouver l'écart assez loin dans votre recherche
• alors que je réfléchissais brièvement à la façon de paralléliser la requête, j'ai rapidement rejeté cette idée (en tant qu'administrateur de base de données, je ne voudrais pas découvrir que votre processus embourbe régulièrement mon serveur de données avec une utilisation à 100% du processeur ... surtout si vous pouvez en avoir plusieurs copies de ce fonctionnement en même temps); noooo ... la parallélisation va être hors de question

Alors que faire?

Mettons en suspens pendant une minute l'idée de recherche (répétée, intensive en CPU, force brute) et regardons la situation dans son ensemble.

• en moyenne, une instance de cette recherche va devoir analyser des millions de clés d'index (et nécessiter un bon peu de processeur, un débordement de cache db et un utilisateur regardant un sablier tournant) juste pour localiser une seule valeur
• multiplier l'utilisation du processeur / cache-thrashing / spin-hour-glass par ... combien de recherches attendez-vous en une journée?
• gardez à l'esprit que, d'une manière générale, chaque instance de cette recherche devra analyser le même ensemble de (millions de) clés d'index; c'est beaucoup d'activités répétées pour un bénéfice aussi minime

J'aimerais proposer quelques ajouts au modèle de données ...

• une nouvelle table qui garde la trace d'un ensemble de KeyColvaleurs «disponibles à utiliser» , par exemple:available_for_use(KeyCol binary(64) not null primary key)
• combien d'enregistrements vous maintenez dans ce tableau est à vous de décider, par exemple, peut-être assez pour l'équivalent d'un mois d'activité?
• la table peut être périodiquement (hebdomadairement?) complétée par un nouveau lot de KeyColvaleurs (peut-être créer un proc stocké 'top off'?) [par exemple, mettre à jour la select/top/row_number()requête de Joe pour faire un top 100000]
• vous pouvez configurer un processus de surveillance pour garder une trace du nombre d'entrées disponibles available_for_use au cas où vous commenceriez à manquer de valeurs
• un nouveau déclencheur (ou modifié) DELETE sur la table principale qui place les KeyColvaleurs supprimées dans notre nouvelle table available_for_usechaque fois qu'une ligne est supprimée de la table principale
• si vous autorisez les mises à jour de la KeyColcolonne, alors un déclencheur UPDATE nouveau / modifié sur la table principale pour garder également notre nouvelle table à available_for_usejour
• quand vient le temps de `` rechercher '' une nouvelle KeyColvaleur, vous select min(KeyCol) from available_for_use(évidemment il y a un peu plus car a) vous devrez coder pour les problèmes de concurrence - ne voulez pas que 2 copies de votre processus saisissent la même chose min(KeyCol)et b) vous 'll faudra supprimer min(KeyCol)du tableau; cela devrait être relativement facile à coder, peut-être en tant que proc stocké, et peut être traité dans une autre Q&R si nécessaire)
• dans le pire des cas, si votre select min(KeyCol)processus ne trouve aucune ligne disponible, vous pouvez lancer votre proc `` top off '' pour générer un nouveau lot de lignes

Avec ces modifications proposées au modèle de données:

• vous éliminez BEAUCOUP de cycles de processeur excessifs [votre DBA vous remerciera]
• vous éliminez TOUS ces scans d'index répétitifs et le thrashing du cache [votre DBA vous remerciera]
• vos utilisateurs n'ont plus à regarder le sablier en rotation (même s'ils peuvent ne pas aimer la perte d'une excuse pour s'éloigner de leur bureau)
• il existe de nombreuses façons de surveiller la taille de la available_for_usetable pour vous assurer de ne jamais manquer de nouvelles valeurs

Oui, le available_for_usetableau proposé n'est qu'un tableau de valeurs de «clé suivante» pré-générées; et oui, il y a un potentiel de contention lors de la saisie de la valeur `` suivante '', mais tout conflit a) est facilement résolu par une conception de table / d'index / de requête appropriée et b) va être mineur / de courte durée par rapport à la surcharge / retards avec l'idée actuelle de recherches répétées et forcées d'index.

Il y a quelques défis avec cette question. Les index dans SQL Server peuvent effectuer les opérations suivantes de manière très efficace avec seulement quelques lectures logiques chacun:

• vérifier qu'une ligne existe
• vérifier qu'il n'y a pas de ligne
• trouver la ligne suivante commençant à un moment donné
• trouver la ligne précédente commençant à un moment donné

Cependant, ils ne peuvent pas être utilisés pour rechercher la Nème ligne dans un index. Pour ce faire, vous devez rouler votre propre index stocké sous forme de table ou analyser les N premières lignes de l'index. Votre code C # repose fortement sur le fait que vous pouvez trouver efficacement le Nème élément du tableau, mais vous ne pouvez pas le faire ici. Je pense que cet algorithme n'est pas utilisable pour T-SQL sans changement de modèle de données.

Le deuxième défi concerne les restrictions sur les BINARYtypes de données. Autant que je sache, vous ne pouvez pas effectuer d'addition, de soustraction ou de division de la manière habituelle. Vous pouvez convertir votre BINARY(64)en un BIGINTet il ne générera pas d'erreurs de conversion, mais le comportement n'est pas défini :

Les conversions entre n'importe quel type de données et les types de données binaires ne sont pas garanties d'être identiques entre les versions de SQL Server.

De plus, l'absence d'erreurs de conversion est en quelque sorte un problème ici. Vous pouvez convertir quelque chose de plus grand que la plus grande BIGINTvaleur possible , mais cela vous donnera les mauvais résultats.

Il est vrai que vous avez actuellement des valeurs supérieures à 9223372036854775807. Cependant, si vous commencez toujours à 1 et recherchez la plus petite valeur minimale, ces grandes valeurs ne peuvent être pertinentes que si votre table contient plus de 9223372036854775807 lignes. Cela semble peu probable car votre table à ce moment-là serait d'environ 2000 exaoctets, donc pour répondre à votre question, je vais supposer que les très grandes valeurs n'ont pas besoin d'être recherchées. Je vais également faire une conversion de type de données car elles semblent inévitables.

Pour les données de test, j'ai inséré l'équivalent de 50 millions d'entiers séquentiels dans un tableau avec 50 millions d'entiers supplémentaires avec un écart de valeur unique toutes les 20 valeurs. J'ai également inséré une valeur unique qui ne rentre pas correctement dans une signature BIGINT:

CREATE TABLE dbo.BINARY_PROBLEMS (
    KeyCol BINARY(64) NOT NULL
);

INSERT INTO dbo.BINARY_PROBLEMS WITH (TABLOCK)
SELECT CAST(SUM(OFFSET) OVER (ORDER BY (SELECT NULL) ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS BINARY(64))
FROM
(
    SELECT 1 + CASE WHEN t.RN > 50000000 THEN
        CASE WHEN ABS(CHECKSUM(NewId()) % 20)  = 10 THEN 1 ELSE 0 END
    ELSE 0 END OFFSET
    FROM
    (
        SELECT TOP (100000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
        CROSS JOIN master..spt_values t3
    ) t
) tt
OPTION (MAXDOP 1);

CREATE UNIQUE CLUSTERED INDEX CI_BINARY_PROBLEMS ON dbo.BINARY_PROBLEMS (KeyCol);

-- add a value too large for BIGINT
INSERT INTO dbo.BINARY_PROBLEMS
SELECT CAST(0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000 AS BINARY(64));

Ce code a mis quelques minutes à s'exécuter sur ma machine. J'ai fait en sorte que la première moitié du tableau ne présente aucun écart pour représenter une sorte de pire cas de performance. Le code que j'ai utilisé pour résoudre le problème scanne l'index dans l'ordre afin qu'il se termine très rapidement si le premier écart est au début du tableau. Avant d'en arriver là, vérifions que les données sont telles qu'elles devraient être:

SELECT TOP (2) KeyColBigInt
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    FROM dbo.BINARY_PROBLEMS
) t
ORDER By KeyCol DESC;

Les résultats suggèrent que la valeur maximale à laquelle nous convertissons BIGINTest 102500672:

╔══════════════════════╗
║     KeyColBigInt     ║
╠══════════════════════╣
║ -9223372036854775808 ║
║            102500672 ║
╚══════════════════════╝

Il y a 100 millions de lignes avec des valeurs qui correspondent à BIGINT comme prévu:

SELECT COUNT(*) 
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF;

Une approche à ce problème consiste à analyser l'index dans l'ordre et à quitter dès que la valeur d'une ligne ne correspond pas à la ROW_NUMBER()valeur attendue . La table entière n'a pas besoin d'être scannée pour obtenir la première ligne: uniquement les lignes jusqu'au premier écart. Voici une façon d'écrire du code susceptible d'obtenir ce plan de requête:

SELECT TOP (1) KeyCol
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    , ROW_NUMBER() OVER (ORDER BY KeyCol) RN
    FROM dbo.BINARY_PROBLEMS
    WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt <> RN
ORDER BY KeyCol;

Pour des raisons qui ne rentrent pas dans cette réponse, cette requête sera souvent exécutée en série par SQL Server et SQL Server sous-estimera souvent le nombre de lignes à analyser avant de trouver la première correspondance. Sur ma machine, SQL Server analyse 50000022 lignes à partir de l'index avant de trouver la première correspondance. L'exécution de la requête prend 11 secondes. Notez que cela renvoie la première valeur après l'écart. On ne sait pas exactement quelle ligne vous voulez exactement, mais vous devriez pouvoir modifier la requête en fonction de vos besoins sans trop de problèmes. Voici à quoi ressemble le plan :

Ma seule autre idée était d'intimider SQL Server pour qu'il utilise le parallélisme pour la requête. J'ai quatre processeurs, donc je vais diviser les données en quatre plages et faire des recherches sur ces plages. Chaque CPU se verra attribuer une plage. Pour calculer les plages, j'ai simplement saisi la valeur maximale et j'ai supposé que les données étaient uniformément réparties. Si vous voulez être plus intelligent à ce sujet, vous pouvez consulter un histogramme de statistiques échantillonné pour les valeurs de colonne et créer vos plages de cette façon. Le code ci-dessous repose sur de nombreuses astuces non documentées qui ne sont pas sûres pour la production, y compris l' indicateur de trace 8649 :

SELECT TOP 1 ca.KeyCol
FROM (
    SELECT 1 bucket_min_value, 25625168 bucket_max_value
    UNION ALL
    SELECT 25625169, 51250336
    UNION ALL
    SELECT 51250337, 76875504
    UNION ALL
    SELECT 76875505, 102500672
) buckets
CROSS APPLY (
    SELECT TOP 1 t.KeyCol
    FROM
    (
        SELECT KeyCol
        , CAST(KeyCol AS BIGINT) KeyColBigInt
        , buckets.bucket_min_value - 1 + ROW_NUMBER() OVER (ORDER BY KeyCol) RN
        FROM dbo.BINARY_PROBLEMS
        WHERE KeyCol >= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol <=  CAST(buckets.bucket_max_value AS BINARY(64))
    ) t
    WHERE t.KeyColBigInt <> t.RN
    ORDER BY t.KeyCol
) ca
ORDER BY ca.KeyCol
OPTION (QUERYTRACEON 8649);

Voici à quoi ressemble le modèle de boucle imbriquée parallèle:

Dans l'ensemble, la requête fait plus de travail qu'auparavant, car elle analysera plus de lignes dans le tableau. Cependant, il fonctionne maintenant en 7 secondes sur mon bureau. Il pourrait mieux se paralléliser sur un vrai serveur. Voici un lien vers le plan réel .

Je ne peux vraiment pas penser à un bon moyen de résoudre ce problème. Faire le calcul en dehors de SQL ou modifier le modèle de données peut être votre meilleur choix.

Voici une réponse qui ne fonctionnera probablement pas pour vous, mais je l'ajouterai quand même.

Même si BINARY (64) est dénombrable, il existe un faible soutien pour déterminer le successeur d'un élément. Étant donné que BIGINT semble être trop petit pour votre domaine, vous pouvez envisager d'utiliser un DECIMAL (38,0), qui semble être le plus grand type NUMBER dans SQL-server.

CREATE TABLE SearchTestTableProper
( keycol decimal(38,0) not null primary key );

INSERT INTO SearchTestTableProper (keycol)
VALUES (1),(2),(3),(12);

Trouver le premier écart est facile puisque nous pouvons construire le nombre que nous recherchons:

select top 1 t1.keycol+1 
from SearchTestTableProper t1 
where not exists (
    select 1 
    from SearchTestTableProper t2 
    where t2.keycol = t1.keycol + 1
)
order by t1.keycol;

Une jointure de boucle imbriquée sur l'index pk devrait être suffisante pour trouver le premier élément disponible.