Advanced interval queries with the Static Relational Interval Tree

In my previous article “A Static Relational Interval Tree”, I described a new powerful structure, the Static Relational Interval Tree (or Static RI-Tree), efficiently handling interval intersection queries in SQL. The power of Static RI-Trees resides in their ability to efficiently partition a set of intervals so that queries can focus on just a subset of the intervals. In this article, I present other kinds of queries that are also nicely handled by a Static RI-Tree.

Remember the large car rental company that I mentioned in the introduction to the previous article? What if, instead of requesting the contracts effective between two dates, we wish to find those which started and ended between the two dates? Or those that started before a first date and ended after a second date? The Static Relational Interval Tree, with just a few additional tweaks, can handle these other interval relationships nicely.

Refining the intersection query

Let’s begin with two improvements to the intersection query from the previous article. As a reminder, a sample binary tree for 5-bit positive integers is presented in Figure 1 below. This binary tree is also the virtual backbone of a Static RI-Tree.

Figure 1. The virtual backbone of a Static RI-Tree. Node values are shown both in decimal and binary representations.

Figure 1. The virtual backbone of a Static RI-Tree. Node values are shown both in decimal and binary representations.

Filtering out useless values from the BitMasks table

Cast your mind back to the queries used to fill the leftNodes and rightNodes tables (shown in Listing 1), and to the BitMasks table, a sample of which is shown in Table 1 for 5-bit integers. Filling leftNodes and rightNodes is a preliminary step in the execution of an intersection query. If you examine these queries, you may notice that they return some unnecessary values. Fortunately, these extra values don’t change the result of an intersection query. They do, however, cause additional I/O.

Table 1: Sample BitMasks table for 5-bit integers

Table 1: Sample BitMasks table for 5-bit integers

 

The query filling the leftNodes table may return the useless value 0. For instance, suppose the bound variable x has the binary value 00110, which is 6 in decimal. The query to fill the leftNodes table, because of its WHERE clause “:x & b2 <> 0”, only retains the b1 values 11100 and 11000. For the b1 value 11100, the query selects 00110 & 11100 = 00100, which is a valid value for leftNodes. For the b1 value 11000, the query selects 00110 & 11000 = 00000, or 0 in decimal, which is useless for leftNodes.

The query filling the rightNodes table may return values from x’s right subtree, which are useless. For instance, say variable x has the binary value 01100, which is 12 in decimal. The query to fill the rightNodes table, because of its WHERE clause “:x & b3 = 0”, only retains the (b1, b3) pairs (11110, 00010) and (10000, 10000). For these pairs, the select expression “(:x & b1) | b3” yields (01100 & 11110) | 00010 = 01110 and (01100 & 10000) | 10000 = 10000 respectively. The former, 01110 (14 decimal), is part of x’s right subtree, as you can see in Figure 1 above, so it’s useless. In fact, all values of x to be collected into rightNodes should be found in the following way:

  1. Looking at x’s binary value, find the rightmost 0 bit having at least one 1 bit to its right.
  2. If none is found, exit.
  3. Set that rightmost 0 bit.
  4. Clear all 1 bits to its right.
  5. Retain the new value obtained and set x to this value.
  6. Go to step 1.

Let’s apply the algorithm above to our example, with x having the value 01100 (12 decimal). Step 1 tells us to find the rightmost 0 bit having at least one 1 bit to its right. Only the leftmost 0 bit of 01100 qualifies. Following steps 3 and 4, the resulting value is 10000. Applying step 1 again to 10000 yields no qualifying 0 bit, so we exit the algorithm. Thus, the only value produced for rightNodes is 10000, or 16 decimal.

The original queries to fill the leftNodes and rightNodes tables can easily be fixed to exclude all spurious values; you can find the corrected queries in Listing 2 below.

Listing 2: Corrected SQL code to populate the leftNodes and rightNodes tables without spurious values

Filtering out nodes outside the actual value range

Another interesting optimization, which we’ll refer to as the range optimization, can further reduce the I/O of intersection queries when the actual values of the Interval table’s node column don’t spread over the full range of possible values for the integer data type, i.e., the minimum and/or maximum values are far beyond the integer type’s minimum and maximum values. In order to implement this optimization, when computing node values to fill the leftNodes and rightNodes tables, we should only consider values within the minimum and maximum node values range.

Fortunately, thanks to the lowerIndex and upperIndex indexes, computing the minimum and maximum value of the node column is very cheap and costs only 2 B-tree lookups. Each value filtered out with this idea saves one B-tree lookup. Listing 3 shows the final optimized queries to fill the leftNodes and rightNodes tables. Of course, if the range of actual values in use starts at, or close to, the minimum value, you can omit the minimum value test and save 1 B-tree lookup.

Listing 3: Optimized SQL code to populate the leftNodes and rightNodes tables without spurious or out-of-range values.

Introducing other kinds of interval queries

Up to now, we’ve been focusing on intersection queries only. Other kinds of interval queries can also be useful, and the Static RI-Tree can handle them pretty well, even if it is not always as efficient as an intersection query. Let’s examine these other kinds of queries.

A paper entitled “Object-Relational Indexing for GeneralInterval Relationships”, published in 2001 by Hans-Peter Kriegel, Marco Pötke and Thomas Seidl, from the University of Munich, in Germany, studies how the RI-Tree can be extended to handle the 13 general interval relationships defined by Allen (Allen J.F.: “Maintaining Knowledge about Temporal Intervals”. Communications of the ACM 26(11): 832-843, 1983). The paper refines the partitioning of RI-Tree nodes in the neighborhood of the lower and upper bounds of the query interval: instead of merely relying on the leftNodes and rightNodes tables, it defines 12 classes of nodes, combined into 13 sets to support the 13 queries implementing Allen’s interval relationships. The classes of nodes are named topLeft, bottomLeft, innerLeft, topRight, bottomRight, innerRight, lower, fork, upper, allLeft, allInner and allRight.

Computing the new node classes

Among the node classes listed above, some need to be computed, while others will not.
The allLeft, allInner and allRight classes don’t need to be computed, because they can be represented by simple predicates. In addition, their computation could be too costly because of the potentially large number of nodes they could contain.

The lower, upper and fork classes don’t need to be computed because they are singleton classes: each of them contains exactly one node.

Since bottomLeft is always used with topLeft and bottomRight with topRight, we don’t need to compute bottomLeft nor bottomRight. Since bottomLeft and topLeft together form leftNodes and bottomRight and topRight together form rightNodes, we need to compute leftNodes and rightNodes instead, but we already know how to do it.

Consequently, we only need to compute the 6 classes topLeft, leftNodes, innerLeft, innerRight, topRight and rightNodes. Note that all of these classes never contain more nodes than the height of the RI-Tree.

Kriegel, Pötke and Seidl’s paper uses integer arithmetic, applied in an iterative fashion, to compute these node classes. However, as explained in my previous article, while database engines are extremely efficient with set-based queries, they often perform poorly performance with language-based iterative and conditional logic. I therefore found it useful to turn this iterative logic into set-based queries. Later in this article, we’ll examine the benefit of this approach in specific tests developed with Microsoft SQL Server 2008 R2.

topLeft

As the nodes in topLeft are all left ancestors of the fork node, topLeft can be easily computed by applying the leftNodes query to fork:

topRight

As the nodes in topRight are all right ancestors of the fork node, topRight can be computed by applying the rightNodes query to fork:

bottomLeft and bottomRight

Just to satisfy our curiosity, bottomLeft can be computed by adding a predicate to the leftNodes query, excluding nodes from topLeft:

Similarly, bottomRight can be computed by adding a simple predicate to the rightNodes query, which excludes nodes from topRight:

innerLeft

To compute innerLeft, we can apply the query to fill rightNodes to lower and set fork as an upper bound:

innerRight

To compute innerRight, we can apply the query to fill leftNodes to upper and set fork as a lower bound:

Writing the queries for Allen’s 13 interval relationships

Kriegel, Pötke and Seidl’s paper summarized the SQL queries for Allen’s 13 interval relationships. These queries use the pre-computed node classes. In this section, let’s examine how to adapt these queries to use our set-based computation of the node classes. We’ll refer to those rewritten queries as the Static RI-Tree queries for interval relationships, or Static RI-Tree queries for short.

The range optimization can be applied to all Static RI-Tree queries, using pre-computed node classes. Note that, in the following queries, we’ll leave it out in the interest of clarity. However, this optimization should be considered in production queries, because it can reduce I/O.

In the following, lower and upper are the integers representing the bounds of the interval, and the interval table is defined as:

before

The original query is:

This query does not make use of the node classes, so there’s nothing to rewrite; we’ll therefore use the query as it is.

Meets

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. Since topLeft and bottomLeft together form leftNodes, the query is:

Overlaps

The original query is:

Let’s replace the joined table by a table expression, using our precomputed node class queries. Notice that topLeft and bottomLeft together form leftNodes. The query is:

FinishedBty

he original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. The query is:

Starts

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. The query is:

Contains

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. The query is:

Equals

The original query is:

This query does not make use of the node classes, so there’s nothing to rewrite; we’ll therefore use the query as it is.

During

The original query is:

This query does not make use of the node classes, so there’s nothing to rewrite; we’ll therefore use the query as it is.

StartedBy

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. The query is:

Finishes

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. The query is:

OverlappedBy

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. Note that topRight and bottomRight together form rightNodes. The query is:

MetBy

The original query is:

Let’s replace the joined table by a table expression using our precomputed node class queries. Since topRight and bottomRight together form rightNodes, the query is:

After

The original query is:

This query does not make use of the node classes, so there’s nothing to rewrite; we’ll therefore use the query as it is.

About query performance

The performance of the Static RI-Tree queries, although generally very good, is not excellent for all query types.

Some queries exhibit excellent performance, similar to that of the intersection query, because they only scan useful portions of lowerIndex or upperIndex (the indexes we had created for the intersection query). Kriegel, Pötke and Seidl call this behavior blocked index scan and they call the opposite behavior, where useless portions of the index are being traversed, non-blocked index scan.
Other queries can achieve blocked index scans, provided lowerIndex and upperIndex are turned into the richer indexes upperLowerIndex and lowerUpperIndex, as described in Kriegel, Pötke and Seidl’s paper.

Other queries expose non-blocked index scans, whatever index you create.
Let’s create the richer indexes upperLowerIndex and lowerUpperIndex, as shown in listing 4, in order to optimize as many of the Static RI-Tree queries as we can.

Listing 4: Creating the richer indexes upperLowerIndex and lowerUpperIndex

The well-optimized queries are: meets, finishedBy, starts, equals, startedBy, finishes and metBy. Among these, some don’t need the rich indexes: meets only needs upperIndex and metBy only needs lowerIndex. But it’s unlikely that your application only uses the meets and metBy relationship, so you’re better off sticking with the rich indexes.

The other queries only partly benefit from the indexes, with non-blocked index scans. However, this partial use, combined with node class selectivity, should generally provide good performance.

In the next section, we discuss the implementation of the Static RI-Tree queries for Microsoft SQL Server 2005 and above. The significant performance gains obtained with our set-based approach versus the iterative approach are illustrated by a performance comparison test script.

Note that the number of iterations in the original RI-Tree can be reduced by the mechanism of dynamic expansion, but we’re really moving away from the iterative approach because we don’t want to manage the RI-Tree’s four parameters – offset, leftRoot, rightRoot and minstep – for the reasons explained in my previous article, and we don’t want an iterative approach with loops. Fortunately, the range optimization presented above is a good alternative to dynamic expansion.

Writing the Static RI-Tree queries for Microsoft SQL Server

In this section, let’s write the Static RI-Tree queries for Microsoft SQL Server.

We’ll assume that the actual intervals do not cover the full range of values. Therefore, we’ll use the full range optimizatio.
Note that, once created and filled, the BitMasks table is always accessed in a read-only fashion, so we can safely use a NOLOCK table hint.

Creating the sample Intervals table

The Intervals table can be created, along with its indexes, as shown in Listing 5. It can be filled with sample data as was demonstrated in my previous article.

Listing 5. Creating the Intervals table

Creating the BitMasks table

To create and populate the BitMasks table, you can reuse the code from the previous article.

Creating functions for the node classes

Let’s create functions to wrap the node classes. This will promote code reuse and simplify the final queries. The best choice for these functions is to implement them as inline table-valued, because SQL Server inlines their code upon execution, and thus we avoid the cost of invoking a function

topLeft

The topLeft node class can be implemented by the following function:

topRight

The topRight node class can be implemented by the following function:

innerLeft

The innerLeft node class can be implemented by the following function:

innerRight

The innerRight node class can be implemented by the following function:

leftNodes

The leftNodes node class represents the union of the topLeft and bottomLeft node classes. It can be implemented by the following function:

rightNodes

The rightNodes node class represents the union of the topRight and bottomRight node classes. It can be implemented by the following function:

fork

The fork node class can be implemented by the following function:

Notice that this is a scalar function and not a table-valued function, as are the other functions. As I explained in my previous article, the Fork function should not be called from the definition of the computed node column in the Intervals table, because this would significantly impact performance. In this particular situation, we prefer an inline formula. However, it’s perfectly OK to invoke the function once during the execution of one of the Static RI-Tree queries.

Writing the Static RI-Tree queries

Notes:
– In the following queries, you can add a MAXDOP query hint to help save some precious CPU cycles when a parallel plan is unnecessary. Just append “OPTION (MAXDOP 1)” to the query.
– Full range optimizations are used when appropriate, via the @min and @max variables.
– The intersection query, although not strictly part of Allen’s 13 interval relationships, is one of the most useful.

In order to compare the performance of queries written with iterative node class logic with those written with set-based node class logic, let’s write iterative versions of the node class functions.

topLeft

The topLeft node class can be inmplemented by the following function:

topRight

The topRight node class can be inmplemented by the following function:

innerLeft

The innerLeft node class can be inmplemented by the following function:

innerRight

The innerRight node class can be inmplemented by the following function:

rightNodes

The leftNodes node class represents the union of the topRight and bottomRight node classes. It can be inmplemented by the following function:

leftNodes

The leftNodes node class represents the union of the topLeft and bottomLeft node classes. It can be inmplemented by the following function:

fork

The fork node class can be inmplemented by the following function:

Test Results

The test script executes each Static RI-Tree query involving the node class functions in both the iterative and set-based versions. To magnify the measures, it runs each query 1,000 times in a loop. Also, instead of returning the results, it just counts the rows, in order to avoid overloading the query editor window with result sets.
Below is an excerpt of the script involving the StartedBy query:

Note that for some queries, I had to add a MAXDOP 1 query option, in order to prevent SQL Server from using a parallel query plan when it turned out to be more costly in CPU time.

I ran this test script on my laptop, which is equipped with an Intel® Core™ 2 Duo P7450 / 2.13 GHz processor and 4GB of RAM. The SQL Server version is 2008 R2 SP1 Developer Edition 64-bit, running on Windows 7 Family Edition Premium SP1 64-bit. The results are shown in Table 2. As you can see, using the set-based approach is significantly more efficient.

Table 2: Results of the performance comparison test script between iterative and set-based interval queries

Table 2: Results of the performance comparison test script
between iterative and set-based interval queries

lmartin

Software Architect at StatPro
Laurent Martin is a software architect working in Paris, France, for StatPro, a leading portfolio analysis and asset valuation provider. Laurent has been working in the software industry for over 20 years, specializing in Microsoft technologies.

Trackbacks/Pingbacks

  1. Using the Static Relational Interval Tree with time intervals | SolidQ - […] my previous articles, “A Static Relational Interval Tree” and “Advanced interval queries with the Static Relational Interval Tree”, I …

Submit a Comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">