1 Introduction
WHERE
clauses (see also the right-hand column of Table 1 for a formal definition of Allen’s relations and extensions). The evaluation of these predicates using the implementation present in contemporary relational database management systems (RDBMSs) would be very inefficient, though, as a lot of inequality predicates are involved [26]. We also note that the predicates in the aforementioned overlap interval joins ( [8, 14, 36]) only check for any form of overlap between intervals. Basically, they do not distinguish between many of the relationships defined by Allen and do not cover the before and meets relations at all. Additionally, many of the approaches so far lack parameterized versions, in which further range-based constraints can be formulated directly in the join predicate.
-
We develop a family of plane-sweeping interval join algorithms that can evaluate a wide range of interval relationship predicates going even beyond Allen’s relations.
-
At the core of this framework sits one base algorithm, called interval-time stamp join, that can be parameterized using a set of iterators traversing a Timeline Index. This offers an elegant way of configuring and adapting the base algorithm for processing different interval join predicates, improving code maintainability.
-
Additionally, our algorithm utilizes the CPU cache efficiently, relying on a compact hash map data structure for managing data during the processing of the join operation. Together with the index, in many cases we can achieve linear run time.
-
In an experimental evaluation, we show that our approach is faster than state-of-the-art methods: an order of magnitude faster than a direct competitor and several orders of magnitude faster than an inequality join.
2 Related work
2.1 Allen’s interval relations joins
2.2 Overlap interval joins
2.3 Generic inequality joins
3 Background
SELECT * FROM
\(\varvec{r}\), \(\varvec{s}\) WHERE
P(r, s)’. For example, we define the ISEQL left overlap join as ‘SELECT * FROM
\(\varvec{r}\), \(\varvec{s}\) WHERE
r LEFT OVERLAP
s’. If the predicate is parameterized, the join operator will also be parameterized.4 Formalizing our approach
4.1 Non-parameterized joins
4.2 Parameterized joins
5 Our framework
5.1 The endpoint index
5.2 Endpoint iterators
-
getEndpoint
: returns the endpoint, which the iterator is currently pointing to (initially returns the first endpoint in the list); -
moveToNextEndpoint
: advances the cursor to the next endpoint; -
isFinished
: returntrue
if the cursor is pointing beyond the last endpoint of the list,false
otherwise.
5.3 The core algorithm JoinByS
6 Assembling the parts
6.1 Expressions without map operators
6.2 Expressions with map operators
6.3 Correctness of algorithms
7 Implementation considerations
7.1 Managing the active tuple set
insert
key-value pairs, remove
them, and quickly enumerate (scan) one by one all the values contained in the data structure via the operation getnext
. In our case, the keys are tuple identifiers and the values are the tuples themselves. The data structure of choice here is a map or associative array.insert
and remove
operations is a hash table (with O(1) time complexities for these operations). However, hash tables are not well suited for scanning. The std::unordered_map class in the C++ Standard Template Library and the java.util.HashMap in the Java Class Library, for instance, scan through all the buckets of a hash table, making the performance of a scan operation linear with respect to the capacity of the hash table and not to the actual amount of elements in it.getnext
, the elements in the hash table can be connected via a doubly linked list (see Fig. 5). The hash table stores pointers to elements, which in turn contain a key, a value, two pointers for the doubly linked list (list prev and list next) and a pointer for chaining elements of the same bucket for collision resolution (pointer bucket next). This approach is employed in the java.util.LinkedHashMap in the Java Class Library.
getnext
, the execution times of different calls of getnext
can vary widely in practice, depending on the memory footprint of the map. After a series of insertions and deletions the elements of the linked list become randomly scattered in memory, which has an impact on caching: sometimes the next list element is still in the cache (resulting in fast retrieval), sometimes it is not (resulting in slow random memory accesses). Additionally, the pointer structure make it hard for a prefetcher to determine where the next elements are located. However, for our approach it is crucial that getnext
can be executed very efficiently, as it is typically called much more often than insert
and remove
. We will see in Sect. 7.4 how to implement a hash map more efficiently.7.2 Lazy joining of the active tuple set
getnext
operations are actually those that are not executed. We modify our algorithm to boost its performance by significantly reducing the number of getnext
operations needed to generate the output.7.3 Features of contemporary hardware
7.4 Implementation of the active tuple set
insert
operation this means that we always append a new element at the end of the storage area. Removing the last element from the storage area is straightforward. If the element to be removed is not the last in the storage area, we swap it with the last element and then remove it. When doing so, we have to update all the references to the swapped elements. Scanning involves stepping through the contiguous storage area sequentially. We call our data structure a gapless hash map (see Fig. 7).
7.5 Overhead for abstractions
std::less
or std::less_equals
. The consumers were defined as C++11 lambda-functions, also passed as a template parameter. This time both compilers were able to inline all method calls and generate very optimized code with all variables (including iterator fields) kept in CPU registers.7.6 Parallel execution
8 Theoretical analysis
9 Experimental evaluation
9.1 Setup
-O3
optimization flag. We executed the code on a machine with two Intel Xeon E5-2667 v3 processors under Linux. All experiments used 12-byte tuples containing two 32-bit time stamp attributes (\(T_s\) and \(T_e\)) and a 32-bit integer payload. All experiments were repeated (also with bigger tuple sizes) on a seven-year-old Intel Xeon X5550 processor and on a notebook processor i5-4258U, showing a similar behavior.std::vector
containers. The Endpoint Index was implemented analogously, using structures for the endpoints and a vector for the index.dataset | n | |r.T| | \(r.T_s\) and \(r.T_e\) | |||
---|---|---|---|---|---|---|
Min | Avg | Max | Domain | #Distinct (k) | ||
Flight | 58 k | 61 | 8 k | 86 k | 812 k | 10 |
Inc | 84 k | 2 | 184 | 574 | 9 k | 2.7 |
Web | 1.2 M | 1 | 60 M | 352 M | 352 M | 110 |
Feed | 3.7 M | 1 | 432 | 8.5 k | 8.6 k | 5.6 |
Basf | 5.3 M | 1 | 127 k | 16 M | 16 M | 760 |
9.2 Experiments and results
9.2.1 Cache efficiency
getnext
operation, which is crucial for generating the result tuples. We compare a linked hash map (Sect. 7.1), a gapless hash map (Sect. 7.4), and a tree structure (mentioned in Sect. 8). The tree was implemented using a red-black tree (std::map) from the C++ Standard Library.getnext
operation depending on the number of tuples (note the double-logarithmic scale).
getnext
operation is not constant but grows depending on the memory footprint of the tuples. In order to find the cause of this, we used the Performance Application Programming Interface (PAPI) library to read out the CPU performance counters [34]. When looking at the average number of stalled CPU cycles (PAPI-RES-STL) per getnext
operation, we get a very similar picture (see Fig. 10). Therefore, the latency is clearly caused by the CPU memory subsystem.
getnext
operation for the gapless hash map plateaus at around 2.7 ns, while the latency for the linked hash map and the tree reaches 100 ns.getnext
operation is lower for the gapless hash map, the factor between the data structures in terms of stalled CPU cycles is disproportionately higher (please note the double-logarithmic scale in Fig. 10). Also, the cache misses do not explain the leftmost part of Fig. 10, in which there are no cache misses at all. The additional performance boost stems from out-of-order execution. Examining the different (slightly simplified) versions of the machine code generated for getnext
makes this clear. For the gapless hash map, the code looks like this:
9.2.2 Lazy joining
getnext
operations than JoinByS in such a scenario. The actual reduction depends not only on the clusteredness of the events, but also on the size of the corresponding active tuple set and the buffer capacity reserved in LazyJoinByS. We define a getnext
operation reduction factor (\( GNORF \)), changing the cost for scanning through active tuple sets for the LazyJoinByS to
, where k is the cardinality of the result set.