Optimieren der Suche nach numerischen Bereichen (Intervallen) in SQL Server

Diese Frage ähnelt der Optimierung der IP-Bereichssuche? dieser ist jedoch auf SQL Server 2000 beschränkt.

Angenommen, ich habe 10 Millionen Bereiche vorläufig in einer Tabelle gespeichert, die wie folgt strukturiert und ausgefüllt ist.

CREATE TABLE MyTable
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX IX1 (RangeFrom,RangeTo),
INDEX IX2 (RangeTo,RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO MyTable
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(1)
FROM   RandomNumbers 

Ich muss alle Bereiche kennen, die den Wert enthalten 50,000,000. Ich versuche die folgende Abfrage

SELECT *
FROM MyTable
WHERE 50000000 BETWEEN RangeFrom AND RangeTo

SQL Server zeigt, dass es 10.951 logische Lesevorgänge gab und fast 5 Millionen Zeilen gelesen wurden, um die 12 übereinstimmenden zurückzugeben.

Kann ich diese Leistung verbessern? Eine Umstrukturierung der Tabelle oder zusätzlicher Indizes ist in Ordnung.

Columnstore ist hier sehr hilfreich im Vergleich zu einem nicht gruppierten Index, der die Hälfte der Tabelle durchsucht. Ein nicht gruppierter Columnstore-Index bietet den größten Vorteil, aber das Einfügen geordneter Daten in einen gruppierten Columnstore-Index ist noch besser.

DROP TABLE IF EXISTS dbo.MyTableCCI;

CREATE TABLE dbo.MyTableCCI
(
Id        INT PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX CCI CLUSTERED COLUMNSTORE
);

INSERT INTO dbo.MyTableCCI
SELECT TOP (987654321) *
FROM dbo.MyTable
ORDER BY RangeFrom ASC
OPTION (MAXDOP 1);

Durch das Design kann ich Zeilengruppen in der RangeFromSpalte entfernen, wodurch die Hälfte meiner Zeilengruppen entfernt wird. Aufgrund der Art der Daten erhalte ich aber auch eine Zeilengruppen-Eliminierung für die RangeToSpalte:

Table 'MyTableCCI'. Segment reads 1, segment skipped 9.

Für größere Tabellen mit mehr variablen Daten gibt es verschiedene Möglichkeiten, die Daten zu laden, um die bestmögliche Eliminierung von Zeilengruppen in beiden Spalten zu gewährleisten. Insbesondere für Ihre Daten dauert die Abfrage 1 ms.

Paul White wies auf eine Antwort auf eine ähnliche Frage hin, die einen Link zu einem interessanten Artikel von Itzik Ben Gan enthielt . Dies beschreibt das Modell "Static Relational Interval Tree", mit dem dies effizient durchgeführt werden kann.

Zusammenfassend beinhaltet dieser Ansatz das Speichern eines berechneten ("forknode") Wertes basierend auf den Intervallwerten in der Zeile. Wenn Sie nach Bereichen suchen, die einen anderen Bereich überschneiden, können Sie die möglichen forknode-Werte vorberechnen, die für übereinstimmende Zeilen erforderlich sind, und auf diese Weise die Ergebnisse mit maximal 31 Suchoperationen ermitteln (im Folgenden werden Ganzzahlen im Bereich von 0 bis maximal vorzeichenbehafteten 32 unterstützt) bit int)

Auf dieser Grundlage habe ich die Tabelle wie folgt umstrukturiert.

CREATE TABLE dbo.MyTable3
(
  Id        INT IDENTITY PRIMARY KEY,
  RangeFrom INT NOT NULL,
  RangeTo   INT NOT NULL,   
  node  AS RangeTo - RangeTo % POWER(2, FLOOR(LOG((RangeFrom - 1) ^ RangeTo, 2))) PERSISTED NOT NULL,
  CHECK (RangeTo > RangeFrom)
);

CREATE INDEX ix1 ON dbo.MyTable3 (node, RangeFrom) INCLUDE (RangeTo);
CREATE INDEX ix2 ON dbo.MyTable3 (node, RangeTo) INCLUDE (RangeFrom);

SET IDENTITY_INSERT MyTable3 ON

INSERT INTO MyTable3
            (Id,
             RangeFrom,
             RangeTo)
SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable

SET IDENTITY_INSERT MyTable3 OFF 

Und dann die folgende Abfrage verwendet (der Artikel sucht nach sich überschneidenden Intervallen, so dass das Finden eines Intervalls, das einen Punkt enthält, ein entarteter Fall ist)

DECLARE @value INT = 50000000;

;WITH N AS
(
SELECT 30 AS Level, 
       CASE WHEN @value > POWER(2,30) THEN POWER(2,30) END AS selected_left_node, 
       CASE WHEN @value < POWER(2,30) THEN POWER(2,30) END AS selected_right_node, 
       (SIGN(@value - POWER(2,30)) * POWER(2,29)) + POWER(2,30)  AS node
UNION ALL
SELECT N.Level-1,   
       CASE WHEN @value > node THEN node END AS selected_left_node,  
       CASE WHEN @value < node THEN node END AS selected_right_node,
       (SIGN(@value - node) * POWER(2,N.Level-2)) + node  AS node
FROM N 
WHERE N.Level > 0
)
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS L
    ON I.node = L.selected_left_node
    AND I.RangeTo >= @value
    AND L.selected_left_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS R
    ON I.node = R.selected_right_node
    AND I.RangeFrom <= @value
    AND R.selected_right_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
WHERE node = @value;

Dies wird normalerweise 1msauf meinem Computer ausgeführt, wenn sich alle Seiten im Cache befinden - mit E / A-Statistiken.

Table 'MyTable3'. Scan count 24, logical reads 72, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 4, logical reads 374, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

und planen

NB: Die Quelle verwendet Multistatement-TVFs anstelle eines rekursiven CTE, um die Knoten zum Beitritt zu bewegen, aber um meine Antwort in sich geschlossen zu halten, habe ich mich für Letzteres entschieden. Für die Produktion würde ich wahrscheinlich die TVFs verwenden.

Ich konnte einen Zeilenmodus-Ansatz finden, der mit dem N / CCI-Ansatz konkurriert, aber Sie müssen etwas über Ihre Daten wissen. Angenommen, Sie hatten eine Spalte, die den Unterschied von RangeFromund enthielt, RangeTound Sie indizierten sie zusammen mit RangeFrom:

ALTER TABLE dbo.MyTableWithDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableWithDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

Wenn Sie alle unterschiedlichen Werte von kennen, können DiffOfColumnsSie DiffOfColumnsmit einem Bereichsfilter nach jedem Wert von suchen RangeTo, um alle relevanten Daten abzurufen. Wenn wir zum Beispiel wissen, dass DiffOfColumns= 2 ist, sind die einzigen zulässigen Werte für RangeFrom49999998, 49999999 und 50000000. Mit der Rekursion können alle eindeutigen Werte von ermittelt werden, DiffOfColumnsund dies funktioniert gut für Ihren Datensatz, da es nur 256 davon gibt. Die folgende Abfrage dauert auf meinem Computer ca. 6 ms:

WITH RecursiveCTE
AS
(
    -- Anchor
    SELECT TOP (1)
        DiffOfColumns
    FROM dbo.MyTableWithDiff AS T
    ORDER BY
        T.DiffOfColumns

    UNION ALL

    -- Recursive
    SELECT R.DiffOfColumns
    FROM
    (
        -- Number the rows
        SELECT 
            T.DiffOfColumns,
            rn = ROW_NUMBER() OVER (
                ORDER BY T.DiffOfColumns)
        FROM dbo.MyTableWithDiff AS T
        JOIN RecursiveCTE AS R
            ON R.DiffOfColumns < T.DiffOfColumns
    ) AS R
    WHERE
        -- Only the row that sorts lowest
        R.rn = 1
)
SELECT ca.*
FROM RecursiveCTE rcte
CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableWithDiff mt
    WHERE mt.DiffOfColumns = rcte.DiffOfColumns
    AND mt.RangeFrom >= 50000000 - rcte.DiffOfColumns AND mt.RangeFrom <= 50000000
) ca
OPTION (MAXRECURSION 0);

Sie können den üblichen rekursiven Teil zusammen mit der Indexsuche für jeden einzelnen Wert sehen:

Der Fehler bei diesem Ansatz ist, dass es langsam wird, wenn es zu viele unterschiedliche Werte für gibt DiffOfColumns. Lass uns den gleichen Test machen, aber CRYPT_GEN_RANDOM(2)stattdessen verwenden CRYPT_GEN_RANDOM(1).

DROP TABLE IF EXISTS dbo.MyTableBigDiff;

CREATE TABLE dbo.MyTableBigDiff
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO dbo.MyTableBigDiff
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(2) -- note the 2
FROM   RandomNumbers;


ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableBigDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

Dieselbe Abfrage findet jetzt 65536 Zeilen aus dem rekursiven Teil und beansprucht 823 ms CPU auf meinem Computer. Es gibt PAGELATCH_SH Wartezeiten und andere schlimme Dinge. Ich kann die Leistung verbessern, indem ich die Diff - Werte sammle, um die Anzahl der eindeutigen Werte unter Kontrolle zu halten, und das Sammeln in anpasse CROSS APPLY. Für diesen Datensatz versuche ich 256 Eimer:

ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns_bucket256 AS CAST(CEILING((RangeTo-RangeFrom) / 256.) AS INT);

CREATE INDEX [IXDIFF😎] ON dbo.MyTableBigDiff (DiffOfColumns_bucket256, RangeFrom) INCLUDE (RangeTo);

Eine Möglichkeit, zusätzliche Zeilen zu vermeiden (jetzt vergleiche ich mit einem gerundeten Wert anstelle des wahren Werts), besteht darin, Folgendes zu filtern RangeTo:

CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableBigDiff mt
    WHERE mt.DiffOfColumns_bucket256 = rcte.DiffOfColumns_bucket256
    AND mt.RangeFrom >= 50000000 - (256 * rcte.DiffOfColumns_bucket256)
    AND mt.RangeFrom <= 50000000
    AND mt.RangeTo >= 50000000
) ca

Die vollständige Abfrage auf meinem Computer dauert jetzt 6 ms.

Eine alternative Möglichkeit, einen Bereich darzustellen, wären Punkte auf einer Linie.

Das Folgende migriert alle Daten in eine neue Tabelle, wobei der Bereich als geometryDatentyp dargestellt wird.

CREATE TABLE MyTable2
(
Id INT IDENTITY PRIMARY KEY,
Range GEOMETRY NOT NULL,
RangeFrom AS Range.STPointN(1).STX,
RangeTo   AS Range.STPointN(2).STX,
CHECK (Range.STNumPoints() = 2 AND Range.STPointN(1).STY = 0 AND Range.STPointN(2).STY = 0)
);

SET IDENTITY_INSERT MyTable2 ON

INSERT INTO MyTable2
            (Id,
             Range)
SELECT ID,
       geometry::STLineFromText(CONCAT('LINESTRING(', RangeFrom, ' 0, ', RangeTo, ' 0)'), 0)
FROM   MyTable

SET IDENTITY_INSERT MyTable2 OFF 


CREATE SPATIAL INDEX index_name   
ON MyTable2 ( Range )  
USING GEOMETRY_GRID  
WITH (  
BOUNDING_BOX = ( xmin=0, ymin=0, xmax=110000000, ymax=1 ),  
GRIDS = (HIGH, HIGH, HIGH, HIGH),  
CELLS_PER_OBJECT = 16); 

Die entsprechende Abfrage zum Suchen von Bereichen, die den Wert enthalten, finden Sie 50,000,000unten.

SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable2
WHERE  Range.STContains(geometry::STPointFromText ('POINT (50000000 0)', 0)) = 1 

Die Reads dafür zeigen eine Verbesserung 10,951gegenüber der ursprünglichen Abfrage.

Table 'MyTable2'. Scan count 0, logical reads 505, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'extended_index_1797581442_384000'. Scan count 4, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Es gibt jedoch keine signifikante Verbesserung gegenüber dem Original in Bezug auf die verstrichene Zeit . Typische Ausführungsergebnisse sind 250 ms gegenüber 252 ms.

Der Ausführungsplan ist komplexer als unten

Der einzige Fall, in dem das Neuschreiben für mich verlässlich besser funktioniert, ist ein kalter Cache.

Daher ist es in diesem Fall enttäuschend und schwierig, dieses Umschreiben zu empfehlen, aber die Veröffentlichung negativer Ergebnisse kann ebenfalls nützlich sein.

Als Hommage an unsere neuen Roboter-Overlords habe ich mich entschieden, ob uns eine der neuen R- und Python-Funktionen hier weiterhelfen kann. Die Antwort ist nein, zumindest für die Skripte, mit denen ich arbeiten konnte und die korrekte Ergebnisse liefern. Wenn jemand mit besseren Kenntnissen vorbeikommt, zögern Sie nicht, mich zu verprügeln. Meine Preise sind angemessen.

Zu diesem Zweck habe ich eine VM mit 4 Kernen und 16 GB RAM eingerichtet, da ich dachte, dies würde ausreichen, um mit einem Datensatz von ~ 200 MB fertig zu werden.

Beginnen wir mit der Sprache, die es in Boston nicht gibt!

R

EXEC sp_execute_external_script 
@language = N'R', 
@script = N'
tweener = 50000000
MO = data.frame(MartinIn)
MartinOut <- subset(MO, RangeFrom <= tweener & RangeTo >= tweener, select = c("Id","RangeFrom","RangeTo"))
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

Das war eine schlechte Zeit.

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3219 ms,  elapsed time = 5349 ms.

Der Ausführungsplan ist ziemlich uninteressant, obwohl ich nicht weiß, warum der mittlere Operator uns Namen nennen muss.

Als nächstes wird mit Buntstiften codiert!

Python

EXEC sp_execute_external_script 
@language = N'Python', 
@script = N'
import pandas as pd
MO = pd.DataFrame(MartinIn)
tweener = 50000000
MartinOut = MO[(MO.RangeFrom <= tweener) & (MO.RangeTo >= tweener)]
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

Gerade als Sie dachten, es könnte nicht schlimmer werden als R:

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3797 ms,  elapsed time = 10146 ms.

Ein weiterer Exekutionsplan mit schlechtem Mund :

Hmm und Hmmer

Bisher bin ich nicht beeindruckt. Ich kann es kaum erwarten, diese VM zu löschen.

Ich habe eine ziemlich gute Lösung mit einer berechneten Spalte gefunden, die jedoch nur für einen einzelnen Wert geeignet ist. Davon abgesehen, wenn Sie einen magischen Wert haben, ist es vielleicht genug.

Beginnen Sie mit Ihrem vorgegebenen Beispiel und ändern Sie dann die Tabelle:

ALTER TABLE dbo.MyTable
    ADD curtis_jackson 
        AS CONVERT(BIT, CASE 
                            WHEN RangeTo >= 50000000
                            AND RangeFrom < 50000000
                            THEN 1 
                            ELSE 0 
                        END);

CREATE INDEX IX1_redo 
    ON dbo.MyTable (curtis_jackson) 
        INCLUDE (RangeFrom, RangeTo);

Die Abfrage wird einfach zu:

SELECT *
FROM MyTable
WHERE curtis_jackson = 1;

Welches die gleichen Ergebnisse wie Ihre Startabfrage zurückgibt. Mit deaktivierten Ausführungsplänen sind hier die Statistiken (der Kürze halber abgeschnitten):

Table 'MyTable'. Scan count 1, logical reads 3...

SQL Server Execution Times:
  CPU time = 0 ms,  elapsed time = 0 ms.

Und hier ist der Abfrageplan :

Meine Lösung basiert auf der Beobachtung, dass das Intervall eine bekannte maximale Breite W hat . Für die Beispieldaten ist dies ein Byte oder 256 Ganzzahlen. Daher wissen wir für einen gegebenen Suchparameterwert P , dass der kleinste RangeFrom, der in der Ergebnismenge enthalten sein kann, P - W ist . Wenn Sie dies zum Prädikat hinzufügen, erhalten Sie

declare @P int = 50000000;
declare @W int = 256;

select
    *
from MyTable
where @P between RangeFrom and RangeTo
and RangeFrom >= (@P - @W);

Bei der ursprünglichen Einrichtung und Abfrage gibt mein Computer (64-Bit-Windows 10, 4-Core-Hyperthread-i7, 2,8 GHz, 16 GB RAM) 13 Zeilen zurück. Diese Abfrage verwendet eine parallele Indexsuche des Index (RangeFrom, RangeTo). Die überarbeitete Abfrage führt auch eine parallele Indexsuche für denselben Index durch.

Die Maße für die ursprünglichen und überarbeiteten Abfragen sind

                          Original  Revised
                          --------  -------
Stats IO Scan count              9        6
Stats IO logical reads       11547        6

Estimated number of rows   1643170  1216080
Number of rows read        5109666       29
QueryTimeStats CPU             344        2
QueryTimeStats Elapsed          53        0

Bei der ursprünglichen Abfrage entspricht die Anzahl der gelesenen Zeilen der Anzahl der Zeilen, die kleiner oder gleich @P sind. Der Abfrageoptimierer (QO) hat keine Alternative, sondern liest sie alle, da er nicht im Voraus bestimmen kann, welche Zeilen das Prädikat erfüllen sollen. Der mehrspaltige Index für (RangeFrom, RangeTo) ist nicht nützlich, um Zeilen zu entfernen, die nicht mit RangeTo übereinstimmen, da keine Korrelation zwischen dem ersten Indexschlüssel und dem zweiten Indexschlüssel besteht, der angewendet werden kann. Beispielsweise kann die erste Reihe ein kleines Intervall haben und beseitigt werden, während die zweite Reihe ein großes Intervall hat und zurückgegeben wird, oder umgekehrt.

In einem fehlgeschlagenen Versuch habe ich versucht, diese Sicherheit durch eine Prüfbedingung zu gewährleisten:

alter table MyTable with check
add constraint CK_MyTable_Interval
check
(
    RangeTo <= RangeFrom + 256
);

Es machte keinen Unterschied.

Indem ich mein externes Wissen über die Datenverteilung in das Prädikat einbeziehe, kann ich bewirken, dass die QO niedrigwertige RangeFrom-Zeilen, die niemals Teil der Ergebnismenge sein dürfen, überspringt und die führende Spalte des Index zu den zulässigen Zeilen durchläuft. Dies wird in dem unterschiedlichen Suchprädikat für jede Abfrage angezeigt.

In einem Spiegel - Argumente ist die obere Grenze der RangeTo P + W . Dies ist jedoch nicht sinnvoll, da es keine Korrelation zwischen RangeFrom und RangeTo gibt, die es der nachfolgenden Spalte eines mehrspaltigen Index ermöglicht, Zeilen zu entfernen. Daher ist es nicht vorteilhaft, diese Klausel zur Abfrage hinzuzufügen.

Dieser Ansatz profitiert vor allem von der geringen Intervallgröße. Wenn die mögliche Intervallgröße zunimmt, nimmt die Anzahl der übersprungenen Zeilen mit niedrigem Wert ab, obwohl einige weiterhin übersprungen werden. Im Grenzfall ist dieser Ansatz bei einem Intervall, das so groß ist wie der Datenbereich, nicht schlechter als die ursprüngliche Abfrage (die ich zugeben muss, ist ein kalter Trost).

Ich entschuldige mich für etwaige Fehler in dieser Antwort.