Optimale Leistung für Joining auf Wertebereich

Question

Ich habe eine wirklich große Tabelle, die ganzzahlige Darstellungen von IP-Adressen und eine zweite Tabelle enthält, die Anfangs- und Endbereiche von Ganzzahlen Darstellungen von IP-Adressen hat. Die zweite Tabelle dient zur Rückgabe des Landes gemäß several stackoverflow articles. Obwohl dies die erforderlichen Ergebnisse liefert, ist die Leistung ziemlich schlecht. Gibt es eine bessere Alternative zum Beitritt zu einer Reihe? Im Folgenden finden Sie einen Beispielsatz von Code, der zeigt, wie der Join derzeit funktioniert:

CREATE TABLE #BaseTable 
    (SomeIntegerValue INT PRIMARY KEY); 

INSERT INTO #BaseTable (SomeIntegerValue) 
SELECT SomeIntegerValue 
FROM (VALUES 
    (123), (456), (789)) Data (SomeIntegerValue); 

CREATE TABLE #RangeLookupTable 
    (RangeStartValue INT PRIMARY KEY 
    , RangeEndValue INT NOT NULL); 

INSERT INTO #RangeLookupTable (RangeStartValue, RangeEndValue) 
SELECT RangeStartValue, RangeEndValue 
FROM (VALUES 
     (0, 100), (101, 200), (201, 300) 
    , (301, 400), (401, 500), (501, 600) 
    , (701, 800), (901, 1000)) Data (RangeStartValue, RangeEndValue); 

SELECT * 
FROM #BaseTable bt 
JOIN #RangeLookupTable rlt 
    ON bt.SomeIntegerValue BETWEEN rlt.RangeStartValue AND rlt.RangeEndValue 

Answer 1

Dies ist fast sicher ein Indizierungsproblem. Sie haben derzeit einen Index für die RangeStartValue (Primärschlüssel), aber nicht für die RangeEndValue, so dass es wahrscheinlich einen vollständigen Scan in der zweiten Spalte nach dem Eingrenzen der ersten durchführen muss. Versuchen Sie, die RangeEndValue zu indizieren und sehen Sie, wie sich dies auf das System auswirkt.

Ich bin nicht gut in den Leistungseigenschaften der BETWEEN-Klausel, aber Sie können garantieren, dass kein Problem sein, indem Sie beide Seiten des Vergleichs mit Ungleichheitsprüfungen schreiben.

---

Auch in diesem Testskript Sie jede Zeile in der Basistabelle auswählen, die ich Sie nehme an, in Ihrer Produktion db tun nicht?

Answer 2

Das Problem ist, dass Ihre Nachschlagetabelle nicht überlappende Kacheln (Bereiche) von Adressen hat. Das erkennt SQL Server jedoch wahrscheinlich nicht. Also, wenn Sie ipaddress between A and B haben, muss es den gesamten Index beginnend am Anfang und endend mit A scannen.

Ich weiß nicht, ob es eine Möglichkeit gibt zu erklären, was die Tabelle wirklich macht, in einer Weise, dass die Der Optimierer springt zum ersten passenden Datensatz im Index. Es ist möglich, dass so etwas wie dies funktionieren würde:

select bt.*, 
     (select top 1 RangeEndValue 
     from #RangeLookupTable rlt 
     where rlt.RangeStartValue <= bt.SomeIntegerValue 
     order by RangeStartValue desc) 
FROM #BaseTable bt 

Dies könnte „Trick“ der Optimierer in Blick auf nur einen Datensatz im Index. Die Daten in Ihrem Beispiel sind zu klein, um festzustellen, ob sich dies auf die Leistung auswirkt.

Ein anderer Ansatz besteht darin, einen Equi-Join zu verwenden, um die Suche zu stoppen. Fügen Sie in jeder Tabelle den TypeA-Teil der Adresse (das erste Byte) hinzu. Dies kann entweder redundant sein, wobei das zweite Feld die volle Adresse hat, oder Sie können die anderen drei Bytes in das nächste Feld setzen. Jede IP-Liste, die mehrere TypeA-Adressen umfasst, müsste in separate Einträge aufgeteilt werden.

Machen Sie dieses Feld zur ersten Spalte im Index mit der Adresse (oder dem Rest der Adresse) als zweiten Teil des Primärschlüssels. Sie können Constraints verwenden, um einen Primärschlüssel mit mehreren Spalten zu erstellen.

würde die Abfrage dann wie folgt aussehen:

SELECT * 
FROM #BaseTable bt join 
    #RangeLookupTable rlt 
    ON bt.typeA = rlt.typeA and 
     bt.SomeIntegerValue BETWEEN rlt.RangeStartValue AND rlt.RangeEndValue 

Die Scan-Index dann nur mit demselben ersten Byte auf die Werte begrenzt werden würde. Natürlich könnten Sie dies auch auf TypeAB erweitern, indem Sie die ersten zwei Bytes verwenden.

Answer 3

Wenn die spezifische Situation es erlaubt, Daten in einer Tabelle zu de-normalisieren, und dann Abfragen von dieser Tabelle anstelle der normalisierten Basistabelle, konnte eine sehr schnelle Retrieval-Zeit erreicht werden. Der Abfrage-Ausführungsplan zeigt 2x Verstärkung in SELECT, selbst bei diesen Beispieldaten von 3 Zeilen.

Ein solcher Ansatz wäre in einem Szenario mit relativ wenig Schreib- und Leseoperationen möglich.Der JOIN muss nur ausgeführt werden, wenn die Daten aktualisiert werden; Das Testen mit tatsächlichen Daten zeigt, wie viel (oder überhaupt!) eine Verbesserung tatsächlich im Gesamtbild (UPDATE + SELECT) erreicht wird.

Beispielcode, zusammen mit den resultierenden Ausführungsplan Screenshots für die SELECT-Anweisungen, ist unten angegeben.

CREATE TABLE #BaseTable 
    (SomeIntegerValue INT PRIMARY KEY); 

INSERT INTO #BaseTable (SomeIntegerValue) 
SELECT SomeIntegerValue 
FROM (VALUES 
    (123), (456), (789)) Data (SomeIntegerValue); 

CREATE TABLE #RangeLookupTable 
    (RangeStartValue INT PRIMARY KEY 
    , RangeEndValue INT NOT NULL); 

INSERT INTO #RangeLookupTable (RangeStartValue, RangeEndValue) 
SELECT RangeStartValue, RangeEndValue 
FROM (VALUES 
     (0, 100), (101, 200), (201, 300) 
    , (301, 400), (401, 500), (501, 600) 
    , (701, 800), (901, 1000)) Data (RangeStartValue, RangeEndValue); 

-- Alternative approach: Denormalized base table 
CREATE TABLE #BaseTable2 
    (SomeIntegerValue INT PRIMARY KEY, 
     RangeStartValue INT null, 
     RangeEndValue INT NULL); 

INSERT INTO #BaseTable2 (SomeIntegerValue) 
SELECT SomeIntegerValue 
FROM (VALUES 
    (123), (456), (789)) Data (SomeIntegerValue); 

UPDATE #BaseTable2 
SET RangeStartValue = rlt.RangeStartValue, 
    RangeEndValue = rlt.RangeEndValue 
FROM #BaseTable2 bt2 
JOIN #RangeLookupTable rlt 
    ON bt2.SomeIntegerValue BETWEEN rlt.RangeStartValue AND rlt.RangeEndValue 

-- The original: SELECT with a JOIN 
SELECT * 
FROM #BaseTable bt 
JOIN #RangeLookupTable rlt 
    ON bt.SomeIntegerValue BETWEEN rlt.RangeStartValue AND rlt.RangeEndValue 

-- The alternative: SELECT from the denormalized base table 
SELECT * from #BaseTable2; 

GO 

Abfrageausführungspläne für die zusammengefügten vs. denormalized SELECTs:

Answer 4

ich 15 verschiedene Ansätze getestet, dass ich dachte funktionieren würde, und diese Lösung war bei weitem das beste:

SELECT bt.* 
    , RangeStartValue = 
     (SELECT TOP 1 RangeStartValue 
     FROM #RangeLookupTable rlt 
     WHERE bt.SomeIntegerValue >= rlt.RangeStartValue 
     ORDER BY rlt.RangeStartValue) 
FROM #BaseTable bt; 

Dies erstellt eine Clustered-Index-Suche in der Nachschlagetabelle und ist in der Lage, Millionen von Datensätzen in Sekunden zu verarbeiten. Bitte beachten Sie, dass ich diese Lösung von Code in this blog angepasst habe.