Improving 2D Range Query Performance in SQL Server

When using the BETWEEN operator on multiple
columns, you are likely using a 2D range query.  Such queries perform very
poorly in SQL Server.   This article will tell you how you can often use
additional information to rewrite such queries for much better performance. 
We’ll conclude by rewriting an actual BETWEEN query in a manner that increases
performance to more than 100 times faster. (!)

What is a 2D range query?

A 2D range query is one where two
independent columns are being tested against a range of values.  For instance,
the query:

SELECT*FROM MyTable WHERE @constant_date BETWEEN
DateStart AND DateEnd

Has two degrees of freedom: both DateStart
and DateEnd are being range tested.  DateStart  must lie between {min_date} and
@constant_date, and DateEnd between @constant_date and {max_date}.  This is a
2D range query.

Note: the very similar-looking query:

@constant_date1 AND @constant_date2

Is not a 2D range query.  It
is one-dimensional– only one column is being queried.

You can have 2D range queries without using
the BETWEEN operator.  For instance, the query:

Column1 > @SomeValue AND Column2 > @SomeOtherValue

Is also a 2D range query, and one that
cannot be easily handled by a B-Tree Index.

There can be higher dimensional queries as
well. For instance, 3D range queries are common for geospatial data.

The Problem

SQL Server uses B-Tree indexes for
everything but spatial data.  A B-Tree is single-dimensional and cannot be
properly utilized in 2D range queries.  Taking a closer look at our sample

…WHERE @date BETWEEN DateStartANDDateEnd

You can create an index onDateStart or
DateEnd, or the composite index (DateStart, DateEnd).  An index onDateStart
alone allows the QO (Query Optimizer) to narrow the range of values only to the
range {min_date} to @date.   The rows must then be scanned to find those that
satisfy DateEnds’s portion of the query.  Statistically, this averages out to
only eliminating half the rows.   Unless @date happens to be very close to what
the index stats says is the highest value, the engine is therefore better off
doing a full table scan.  The same problem applies to an index on DateEnd.

What about the composite index?  That
doesn’t help either—values for DateEnd are sorted only within each specific
value of DateStart.  Every time the index moves to a new value of DtStart, an
entire new B-Tree is built for DateEnd values that correspond to that specific
start date.  The composite index gains you a small amount because it’s coveringthe
query– it contains both search arguments and therefore saves you some RIDs
(row ID) lookups.  But, on average, you still have to scan half the entire
index to answer the query.  If you have other columns in the query, the QO mayfind
its cheaper to do a full table scan anyway.

Note: quadtree indexes solve this problem
for the 2D case, just as octrees work well for 3D.   In the second half of this
article, I will tell you how you can utilize such indexes in SQL Server for
non-spatial data types, but this article will focus on improving the
performance of higher-dimension range queries with a standard B-Tree index.


Pages: 1 2


No comments yet... Be the first to leave a reply!