Sstrhsrtj

This question is similar to Optimizing IP Range Search? but that one is restricted to SQL Server 2000.

Suppose I have 10 million ranges provisionally stored in a table structured and populated as below.

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 

I need to know all ranges containing the value 50,000,000. I try the following query

SELECT *

FROM MyTable

WHERE 50000000 BETWEEN RangeFrom AND RangeTo

SQL Server shows that there were 10,951 logical reads and nearly 5 million rows were read to return the 12 matching ones.

Can I improve on this performance? Any restructuring of the table or additional indexes is fine.

One alternative way of representing a range would be as points on a line.

The below migrates all the data into a new table with the range represented as a geometry datatype.

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); 

The equivalent query to find ranges containing the value 50,000,000 is below.

SELECT Id,

       RangeFrom,

       RangeTo

FROM   MyTable2

WHERE  Range.STContains(geometry::STPointFromText ('POINT (50000000 0)', 0)) = 1 

The reads for this show an improvement on the 10,951 from the original query.

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.

However there is no significant improvement over the original in terms of time elapsed. Typical execution results are 250 ms vs 252 ms.

The execution plan is more complex as below

The only case where the rewrite reliably performs better for me is with a cold cache.

So disappointing in this case and difficult to recommend this rewrite but publication of negative results can also be useful.

Not sure if you want other answers, but you can get significantly better results with a columnstore index. A nonclustered columnstore index provides most of the benefit but inserting ordered data into a clustered columnstore index is even better.

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);

By design I can get rowgroup elimination on the RangeFrom column which will eliminate half of my rowgroups. But due to the nature of the data I also get rowgroup elimination on the RangeTo column as well:

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

For what it's worth, for larger tables with more variable data there are different ways to load the data to guarantee the best possible rowgroup elimination on both columns. For your data in particular, the query takes 1 ms.

I'll look for other algorithms but I don't think I'll be able to beat that.