Suchen Sie das kleinste fehlende Element anhand einer bestimmten Formel

Ich muss in der Lage sein, ein fehlendes Element aus einer Tabelle mit mehreren zehn Millionen Zeilen zu finden und habe einen Primärschlüssel einer BINARY(64)Spalte (der Eingabewert, aus dem berechnet werden soll). Diese Werte werden meistens der Reihe nach eingefügt, aber gelegentlich möchte ich einen vorherigen Wert wiederverwenden, der gelöscht wurde. Es ist nicht möglich, die gelöschten Datensätze mit einer IsDeletedSpalte zu ändern , da manchmal eine Zeile eingefügt wird, die viele Millionen Werte vor den derzeit vorhandenen Zeilen liegt. Dies bedeutet, dass die Beispieldaten ungefähr so ​​aussehen würden:

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

Das Einfügen aller fehlenden Werte zwischen 0x000000000002und 0xFFFFFFFFFFFFist nicht möglich. Der Zeit- und Raumaufwand wäre unerwünscht. Wenn ich den Algorithmus ausführe, erwarte ich im Wesentlichen, dass er zurückkehrt 0x000000000003. Dies ist die erste Öffnung.

Ich habe einen binären Suchalgorithmus in C # entwickelt, der die Datenbank nach jedem Wert an der Position iabfragt und testet, ob dieser Wert erwartet wird. Für den Kontext mein schrecklicher Algorithmus: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Dieser Algorithmus würde beispielsweise 26-27 SQL-Abfragen für eine Tabelle mit 100.000.000 Elementen ausführen. (Das scheint nicht viel zu sein, aber es wird sehr häufig vorkommen .) Derzeit enthält diese Tabelle ungefähr 50.000.000 Zeilen, und die Leistung macht sich bemerkbar .

Mein erster alternativer Gedanke ist, dies in eine gespeicherte Prozedur zu übersetzen, aber das hat seine eigenen Hürden. (Ich muss einen BINARY(64) + BINARY(64)Algorithmus sowie eine Reihe anderer Dinge schreiben .) Dies wäre schmerzhaft, aber nicht unmöglich. Ich habe auch überlegt, den Übersetzungsalgorithmus basierend auf zu implementieren ROW_NUMBER, aber ich habe ein wirklich schlechtes Bauchgefühl. (A BIGINTist für diese Werte bei weitem nicht groß genug.)

Ich bin bereit für andere Vorschläge, da ich dies wirklich brauche, um so schnell wie möglich zu sein. Für das, was es wert ist, ist die einzige Spalte, die von der C # -Abfrage ausgewählt wird, die KeyCol, die anderen sind für diesen Teil irrelevant.

Für das, was es wert ist, lautet die aktuelle Abfrage, die den entsprechenden Datensatz abruft, wie folgt:

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

Wo <VALUE>ist der vom Algorithmus gelieferte Index? Ich hatte auch noch kein BIGINTProblem damit OFFSET, aber ich werde es tun. (Nur 50.000.000 Zeilen im Moment bedeuten, dass nie nach einem Index über diesem Wert gefragt wird, aber irgendwann wird er über den BIGINTBereich hinausgehen .)

Einige zusätzliche Daten:

• Bei Löschungen gap:sequentialbeträgt das Verhältnis ungefähr 1:20;
• Die letzten 35.000 Zeilen in der Tabelle haben Werte> BIGINTmaximal;

Joe hat bereits die meisten Punkte erreicht, die ich gerade eine Stunde lang getippt habe. Zusammenfassend:

• Es ist höchst zweifelhaft, dass Ihnen die KeyColWerte < bigintmax (9.2e18) ausgehen. Daher sollten Konvertierungen (falls erforderlich) von / nach bigintkein Problem darstellen, solange Sie die Suche auf beschränkenKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• Ich kann mir keine Abfrage vorstellen, die die ganze Zeit "effizient" eine Lücke findet. Möglicherweise haben Sie Glück und finden zu Beginn Ihrer Suche eine Lücke, oder Sie zahlen teuer, um die Lücke in Ihrer Suche zu finden
• Während ich kurz darüber nachdachte, wie die Abfrage parallelisiert werden kann, verwarf ich diese Idee schnell (als DBA möchte ich nicht herausfinden, dass Ihr Prozess meinen Datenserver routinemäßig mit 100% CPU-Auslastung blockiert ... insbesondere, wenn Sie mehrere haben könnten Kopien davon laufen gleichzeitig); noooo ... Parallelisierung kommt nicht in Frage

Also, was tun?

Lassen Sie uns die Suchidee (wiederholt, CPU-intensiv, Brute Force) für eine Minute auf Eis legen und das Gesamtbild betrachten.

• Im Durchschnitt muss eine Instanz dieser Suche Millionen von Indexschlüsseln scannen (und ein gutes Stück CPU, das Übertragen des Datenbankcaches und einen Benutzer, der sich eine sich drehende Sanduhr ansieht), um nur einen einzigen Wert zu finden
• Multiplizieren Sie die CPU-Auslastung / Cache-Thrashing / Spinning-Hour-Glass mit ... wie viele Suchvorgänge erwarten Sie an einem Tag?
• Beachten Sie, dass im Allgemeinen jede Instanz dieser Suche denselben Satz (Millionen) Indexschlüssel scannen muss . Das ist eine Menge wiederholter Aktivitäten für solch einen minimalen Nutzen

Was ich vorschlagen möchte, sind einige Ergänzungen zum Datenmodell ...

• Eine neue Tabelle, die eine Reihe von "zur Verwendung verfügbaren" KeyColWerten protokolliert, z.available_for_use(KeyCol binary(64) not null primary key)
• Wie viele Datensätze, die Sie in dieser Tabelle führen, können Sie selbst entscheiden, z. B. vielleicht genug für einen Monat Aktivität?
• Die Tabelle kann regelmäßig (wöchentlich?) mit einem neuen Wertestapel "aufgefüllt" KeyColwerden (möglicherweise wird ein gespeicherter "Top-off" -Prozess erstellt?) [z. B. Joes select/top/row_number()Abfrage aktualisieren , um eine top 100000] auszuführen
• Sie können einen Überwachungsprozess einrichten, um die Anzahl der verfügbaren Einträge zu verfolgen, für den available_for_use Fall, dass Ihnen jemals die Werte ausgehen
• Ein neuer (oder geänderter) DELETE-Trigger in der> main_table <, der gelöschte KeyColWerte in unsere neue Tabelle einfügt, available_for_usewenn eine Zeile aus der Haupttabelle gelöscht wird
• wenn Sie Aktualisierungen der erlauben KeyColSpalte dann eine neue / geänderte UPDATE - Trigger auf der> main_table <auch unsere neue Tabelle halten available_for_useaktualisiert
• Wenn es an der Zeit ist, nach einem neuen KeyColWert zu suchen, den Sie select min(KeyCol) from available_for_use(offensichtlich gibt es ein bisschen mehr, da a) Sie für Parallelitätsprobleme codieren müssen - möchten Sie nicht, dass 2 Kopien Ihres Prozesses denselben min(KeyCol)und b) Sie greifen muss min(KeyCol)aus der Tabelle löschen ; Dies sollte relativ einfach zu codieren sein, möglicherweise als gespeicherter Prozess, und kann bei Bedarf in einem anderen Q & A behandelt werden.
• Im schlimmsten Fall, wenn Ihr select min(KeyCol)Prozess keine verfügbaren Zeilen findet, können Sie Ihren Top-Off-Prozess starten, um einen neuen Stapel von Zeilen zu generieren

Mit diesen vorgeschlagenen Änderungen am Datenmodell:

• Sie eliminieren eine Menge übermäßiger CPU-Zyklen [Ihr DBA wird es Ihnen danken]
• Sie eliminieren ALLE diese sich wiederholenden Index-Scans und Cache-Thrashing [Ihr DBA wird es Ihnen danken]
• Ihre Benutzer müssen nicht mehr auf die sich drehende Sanduhr achten (obwohl sie den Verlust einer Ausrede, sich von ihrem Schreibtisch zu entfernen, möglicherweise nicht mögen).
• Es gibt viele Möglichkeiten, die Größe der available_for_useTabelle zu überwachen , um sicherzustellen, dass Ihnen nie die neuen Werte ausgehen

Ja, die vorgeschlagene available_for_useTabelle ist nur eine Tabelle mit vorgenerierten Werten für den nächsten Schlüssel. und ja, es besteht die Möglichkeit von Konflikten, wenn der 'nächste' Wert ermittelt wird, aber jeder Konflikt a) kann leicht durch ein geeignetes Tabellen- / Index- / Abfragedesign behoben werden und b) wird im Vergleich zum Overhead / geringfügig / kurzlebig sein. Verzögerungen mit der aktuellen Idee wiederholter Brute-Force-Indexsuchen.

Bei dieser Frage gibt es einige Herausforderungen. Indizes in SQL Server können Folgendes mit jeweils nur wenigen logischen Lesevorgängen sehr effizient ausführen:

• Überprüfen Sie, ob eine Zeile vorhanden ist
• Überprüfen Sie, ob keine Zeile vorhanden ist
• Finde die nächste Reihe, die irgendwann beginnt
• Finden Sie die vorherige Zeile ab einem bestimmten Punkt

Sie können jedoch nicht verwendet werden, um die N-te Zeile in einem Index zu finden. Dazu müssen Sie Ihren eigenen Index rollen, der als Tabelle gespeichert ist, oder die ersten N Zeilen im Index scannen. Ihr C # -Code hängt stark von der Tatsache ab, dass Sie das N-te Element des Arrays effizient finden können, aber das können Sie hier nicht tun. Ich denke, dass der Algorithmus für T-SQL ohne eine Änderung des Datenmodells nicht verwendbar ist.

Die zweite Herausforderung betrifft die Einschränkungen der BINARYDatentypen. Soweit ich das beurteilen kann, können Sie Addition, Subtraktion oder Division nicht auf die übliche Weise durchführen. Sie können Ihre BINARY(64)in a konvertieren BIGINTund es werden keine Konvertierungsfehler ausgegeben, aber das Verhalten ist nicht definiert :

Es wird nicht garantiert, dass die Konvertierungen zwischen einem Datentyp und den binären Datentypen zwischen den Versionen von SQL Server identisch sind.

Darüber hinaus ist das Fehlen von Konvertierungsfehlern hier ein Problem. Sie können alles konvertieren, was größer als der größtmögliche BIGINTWert ist, aber Sie erhalten die falschen Ergebnisse.

Es stimmt, dass Sie derzeit Werte haben, die größer als 9223372036854775807 sind. Wenn Sie jedoch immer bei 1 beginnen und nach dem kleinsten Mindestwert suchen, können diese großen Werte nur relevant sein, wenn Ihre Tabelle mehr als 9223372036854775807 Zeilen enthält. Dies scheint unwahrscheinlich, da Ihre Tabelle zu diesem Zeitpunkt etwa 2000 Exabyte groß sein würde. Um Ihre Frage zu beantworten, gehe ich davon aus, dass die sehr großen Werte nicht durchsucht werden müssen. Ich werde auch eine Datentypkonvertierung durchführen, da diese unvermeidlich zu sein scheinen.

Für die Testdaten habe ich das Äquivalent von 50 Millionen aufeinanderfolgenden Ganzzahlen in eine Tabelle eingefügt, zusammen mit 50 Millionen weiteren Ganzzahlen mit einer einzelnen Wertelücke etwa alle 20 Werte. Ich habe auch einen einzelnen Wert eingefügt, der nicht richtig in ein signiertes passt 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));

Es dauerte einige Minuten, bis dieser Code auf meinem Computer ausgeführt wurde. Ich habe dafür gesorgt, dass die erste Tabellenhälfte keine Lücken aufweist, die einen schlechteren Fall für die Leistung darstellen. Der Code, mit dem ich das Problem gelöst habe, durchsucht den Index der Reihe nach, sodass er sehr schnell beendet wird, wenn die erste Lücke früh in der Tabelle liegt. Bevor wir dazu kommen, überprüfen wir, ob die Daten so sind, wie sie sein sollten:

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

Die Ergebnisse legen nahe, dass der maximale Wert, in den wir konvertieren, BIGINT102500672 beträgt:

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

Es gibt 100 Millionen Zeilen mit Werten, die wie erwartet in BIGINT passen:

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

Ein Ansatz für dieses Problem besteht darin, den Index der Reihe nach zu scannen und zu beenden, sobald der Wert einer Zeile nicht mit dem erwarteten ROW_NUMBER()Wert übereinstimmt. Die gesamte Tabelle muss nicht gescannt werden, um die erste Zeile zu erhalten: nur die Zeilen bis zur ersten Lücke. Hier ist eine Möglichkeit, Code zu schreiben, der wahrscheinlich diesen Abfrageplan erhält:

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;

Aus Gründen, die nicht in diese Antwort passen, wird diese Abfrage häufig seriell von SQL Server ausgeführt, und SQL Server unterschätzt häufig die Anzahl der Zeilen, die gescannt werden müssen, bevor die erste Übereinstimmung gefunden wird. Auf meinem Computer durchsucht SQL Server 50000022 Zeilen aus dem Index, bevor die erste Übereinstimmung gefunden wird. Die Abfrage dauert 11 Sekunden. Beachten Sie, dass dies den ersten Wert nach der Lücke zurückgibt. Es ist nicht klar, welche Zeile Sie genau möchten, aber Sie sollten in der Lage sein, die Abfrage ohne große Probleme an Ihre Anforderungen anzupassen. So sieht der Plan aus:

Meine einzige andere Idee war, SQL Server dazu zu bringen, Parallelität für die Abfrage zu verwenden. Ich habe vier CPUs, also werde ich die Daten in vier Bereiche aufteilen und nach diesen Bereichen suchen. Jeder CPU wird ein Bereich zugewiesen. Um die Bereiche zu berechnen, habe ich einfach den Maximalwert ermittelt und angenommen, dass die Daten gleichmäßig verteilt sind. Wenn Sie klüger sein möchten, können Sie sich ein Stichprobenhistogramm für die Spaltenwerte ansehen und Ihre Bereiche auf diese Weise erstellen. Der folgende Code basiert auf vielen undokumentierten Tricks, die für die Produktion nicht sicher sind, einschließlich des Ablaufverfolgungsflags 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);

So sieht das parallele verschachtelte Schleifenmuster aus:

Insgesamt erledigt die Abfrage mehr Arbeit als zuvor, da mehr Zeilen in der Tabelle gescannt werden. Es läuft jetzt jedoch in 7 Sekunden auf meinem Desktop. Auf einem echten Server kann es möglicherweise besser parallelisiert werden. Hier ist ein Link zum aktuellen Plan .

Ich kann mir wirklich keinen guten Weg vorstellen, um dieses Problem zu lösen. Die Berechnung außerhalb von SQL durchzuführen oder das Datenmodell zu ändern, ist möglicherweise die beste Wahl.

Hier ist eine Antwort, die wahrscheinlich nicht für Sie funktioniert, aber ich werde sie trotzdem hinzufügen.

Obwohl BINARY (64) aufzählbar ist, gibt es eine schlechte Unterstützung, um den Nachfolger eines Elements zu bestimmen. Da BIGINT für Ihre Domain zu klein zu sein scheint, können Sie ein DECIMAL (38,0) verwenden, das der größte NUMBER-Typ in SQL Server zu sein scheint.

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

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

Die erste Lücke zu finden ist einfach, da wir die gesuchte Zahl konstruieren können:

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;

Ein verschachtelter Loop-Join über dem pk-Index sollte ausreichen, um das erste verfügbare Element zu finden.