We present an algorithm for efficient processing of set-containment joins in main memory. Our algorithm uses an index structure based on inverted files. We focus on improving performance of the algorithm in a main-memory environment by utilizing the L2 CPU cache more efficiently. To achieve this, we employ some optimizations including partitioning the inverted lists and compressing the intermediate results.
Set-valued attributes have become more important in recent years with growing distribution of object-relational database systems (ORDBMS) and rapid development of such application areas as information retrieval and data mining. In practice it is often required to evaluate join queries on set-valued attributes. In such cases the join predicate is a set predicate, such as set containment or intersection. Many real-world queries can be naturally expressed as set containment and intersection joins. For example, a query that finds appropriate candidates among job seekers includes a condition that the set of candidate’s skills contains the set of skills required for the job as a subset. If we are interested in retrieving all documents containing the specified set of terms from the collection, this again can be considered a set containment query. A relation People that includes a set-valued attribute Hobbies leads us to the problem of finding all pairs of people sharing common hobbies that can be formulated as a set intersection self-join.
Set-valued attributes are not directly supported in a
traditional relational DBMS, since already the first
normal form explicitly requires an attribute to be atomic, i.e.
forbids the value of an attribute to be a set. However,
setvalued attributes in a relational DBMS can be simulated
using unnested external representation [3] that creates an
auxiliary relation connected to the original relation by a
foreign key, thus representing one-to-many relationship
between a record of the original relation and the elements
of the value of its set-valued attribute. It can be easily
noticed [
Given the growing practical importance of joins with set predicates, efficient algorithms for performing such joins are required. Nested-loops algorithm is the most common way to handle joins with complex predicates. However, in case of joins with set predicates nested loops algorithm falls short, because its poor performance makes it inappropriate [2]. The reason is that testing predicates on sets is a very expensive operation. Its cost in large extent depends on how the sets in question are represented, but in general this cost is much higher than the cost of simple join predicates on atomic attributes traditionally used in relational database systems.
Main-memory DBMS (MMDBMS) have attracted
much attention during recent decade. A MMDBMS
stores all the data and support structures (such as
indexes) in RAM of the database server. Constantly
growing amount of memory in modern database servers
already enables to store small and medium-size databases
directly in main memory. It has been shown that
MMDBMS provide huge performance gain over
traditional, disk-based DBMS, since retrieving the necessary
data in MMDBMS usually does not involve disk access
at all. Slow disk device is used only for logging and
recovery. Many researchers [
In this paper we present an efficient algorithm based on inverted files for set-containment joins in main memory. Inverted files are well-known and widely used tool for indexing text documents. Our algorithm takes two relations R and S sharing a set-valued attribute A as parameters, scans the common inverted file IFRAS built on the set-valued attribute A for R and S and processes the inverted lists in such a way that the resulting structure appears to be the answer to the set-containment query. The idea of the algorithm is fairly simple, and we focus our study on tailoring the algorithm for MMDBMS by improving CPU cache utilization. We achieve this by partitioning the inverted lists being processed. This enables to fit the working set of the algorithm into the L2 CPU cache and reduce the number of L2 cache misses. We also study the effect of compressing the intermediate results which provides significant memory savings and allows to join larger relations at the cost of more intensive CPU usage and some loss in response time. We present experimental results showing that our optimizations give significant effect as compared with a straightforward implementation. We also demonstrate that the algorithm is superior to some other algorithms for set-containment joins.
The structure of the paper is as follows. The section 2 presents a survey of related work in the area of algorithms for joins with set predicates. In the section 3 we first describe the basic algorithm for set-containment joins using inverted files, and then discuss various optimizations aiming to improve its performance. The section 4 summarizes the results of experimental evaluation of the algorithm. The section 5 concludes the paper and outlines directions for future work. 2
Helmer and Moerkotte [2] seem to be the first researchers who addressed specifically set containment joins. They evaluated several algorithms for set containment join in main memory. The first group of algorithms includes variations of nested-loops join which differ in how the set comparison is implemented. Three implementations of set comparison were considered: the naive algorithm, an implementation based on sorting the sets and an approach that uses signatures. The latter turned out to be the best among nested-loops joins. The second algorithm employs signature-based approach by hashing all the signatures of the relation R (assuming that the join condition is tR.A ⊆ tS .A, tR, tS are tuples of R and S, respectively, tR.A is a set that is the value of A in tR), enumerating subsets of each set of the relation S, and matching each subset with hashed signatures of R.
Melnik and Garcia-Molina [
Mamoulis [
During the last decade, many algorithms commonly
used in DBMS in the course of many years were
reconsidered from the viewpoint of their suitability and
optimality for main-memory DBMS. [
Inverted files are a well-known technique for
indexing text documents. Essentially, an inverted file
provides a mapping of a term T into the list of documents
D1, ..., Dk where this term occurs (Dj is an ID of the
document in the collection). [
We apply inverted files in a different context but the idea remains the same. Instead of collection of documents, we consider relations R and S and the common set-valued attribute A. We denote Domain(A) the domain from which elements of values of A in tuples of R and S are drawn. Tuples of relations are identified by record ID (RID). Inverted file RIF then maps an element of the Domain(A) into the list of RIDs of tuples whose value of A contains this element.
We design our algorithm under assumption that all the
data and indexes are kept in main memory. This
assumption greatly affects the algorithm design, since main
focus now shifts from minimizing the number of disk
accesses (which we assume do not happen at all) to
minimizing the number of cache misses. While both these
aims require good reference locality, the methods for
achieving them are somewhat different [
Our algorithm employs the idea of join indexes [
We present the basic version of the algorithm for setcontainment joins based on inverted files. We assume that the join predicate is r ⊆ s where r, s are values of the set-valued attribute A in relations R and S, respectively. We denote tR, tS tuples of relations R and S, tR.rid, tS .rid RIDs of tuples, and tR.A, tS .A their values of the attribute A. Let also |Result| be the cardinality of the result relation that consists of pairs (tR.rid, tS .rid) qualifying the containment predicate tR.A ⊆ tS .A. The algorithm traverses the combined inverted file RSIF , and on each step processes inverted lists lRv, lSv , where v is an element of the Domain(A) (both lists may be empty). It maintains a mapping W orkmap that maps tR.rid into a reference to the list of Lr = tS1 .rid, ..., tSn .rid such that each of tSk .A contains all the elements of tR.A encountered so far. These lists shrink as the algorithm proceeds. After the final iteration W orkmap is exactly a mapping of tR.rid into the list of tS1 .rid, ..., tSm .rid where tR.A ⊆ tSk .A, k = 1, ..., m. The average length of the Lr in the final result can be estimated as Workmap : map : RID -> ref to list of RID; foreach (Value v in RSIF ) { lRv, lSv : ref to list of RID; Initialize lRv and lSv; foreach (tR.rid in ↑lRv) {
Lr = W orkmap.Get(tR.rid); (!) if (Lr = NULL)
v result = lS; else
result = Intersect(↑Lr, ↑lSv); (!)
W orkmap.P ut(tR.rid, result); }
} L(R, S) = |Result| . The basic algorithm is presented in |R| the Figure 1.
For clarity, our notation uses ↑ to mark dereferences which cause cache misses. This facilitates identifying sources of the cache misses in the algorithm.
The function Intersect computes intersection of two inverted lists. Given that lists are kept in ascending order of RIDs, this function can be efficiently implemented by synchronously traversing both inverted lists. For the sake of simplicity, in our analysis we will ignore the fact that lists shrink during processing. Then the cost of computing the intersection in terms of elementary operations (such that index increment and integer comparison) does not exceed C(|Lr| + |lS |), where |Lr| is the average length of the Lr and |lS | is the average length of inverted list for S, and C is a constant. Let |V| be the number of different values in the inverted file RSIF , |R| and |S| - cardinality of relations R and S, and |r| and |s| - average cardinalities of values of the set-valued attribute A in relations R and S, respectively. Assuming that the values are uniformly distributed across tuples, the probability for a tuple tS to have a value v among the elements of the set tS .A is equal to 1 )|s|. Hence we have |lS | = |S|Pv∈s, Pv∈s = 1 − (1 − |V | and the cost of the algorithm can be estimated as |r||R| C |Re|Rsu| lt| + |S|Pv∈s + CW orkmap where CW orkmap is the cost of lookup into the W orkmap.
Our algorithm and cost estimation, however, do not take into account that the memory access is not uniform on modern architectures. Random memory access such that access to the W orkmap becomes very expensive in presence of several memory hierarchies like L1 and L2 caches, unless the W orkmap entirely fits into one of the caches. Let us then take a closer look on the memory reference behavior of the algorithm. Let Cmiss be the cost of a L2 cache miss. The main sources of cache misses in the basic algorithm are (in the Figure 1 the corresponding lines are marked (!)): • The W orkmap is accessed in a random fashion, and if the size of the W orkmap exceeds the size of the L2 cache, we may consider that every access to the W orkmap incurs at least one cache miss (The exact number of cache misses depends on the implementation of the W orkmap. In case if W orkmap is implemented as a hash table, we expect the access to this hash table to be as efficient as access to an array, since the number of collisions in our situation is small). The total cost of these cache misses is therefore |r||R|Cmiss. • Dereferencing a reference to Lr that happens in the line result = Intersect(↑Lr, ↑lSv ) incurs another cache miss. The cost of these cache misses is (|r| − 1)|R|Cmiss, since the first access to the W orkmap for the given tR.rid does not cause a cache miss. • Computing the intersection of two lists of lengths l1 (|l1|+|l2|) and l2 sorted in ascending order incurs |CacheLine| cache misses, where |CacheLine| is the size of the L2 cache line.
Of course, there are other sources of cache misses in the algorithm, for instance, dereferencing references to the lists lRv and lSv may also incur a cache miss. However, provided that the |V| is small as compared with |R| and |S| (we expect this to be true in practical cases), the cost of those cache misses is negligible. 3.2
Our method reduces amount of cache misses of all the
aforementioned kinds. In order to eliminate misses of the
first kind, we partition the processing to fit W orkmap
into the L2 cache. This can be done in an obvious way
- we modify the algorithm so that only a part of the
tuples of R are considered at a moment, and other tuples
of R are ignored. This also reduces the number of cache
misses of the second kind, since the fewer inverted lists
are processed at a moment, the more likely they reside in
the L2 cache. The cache misses of the third kind are dealt
with by compressing the Lr using one of many
compression techniques for ascending sequences of positive
integer numbers [
The function Select selects the range of RIDs relevant to the current partition p from the (possibly compressed) inverted list lRv. This function can be implemented in various ways: using sequential scan of the lv , the biR nary search in lRv or even the specialized index on lRv that would enable to determine the first RID residing within the interval [p.F irstID, p.LastID].
Let us now estimate the cost of the partitioned version of the algorithm. We can proceed by analogy with the case of the basic algorithm. For the partitioned version of the algorithm we also need to take into account the cost of the Select function. Generalizing possible implementations of Select, we denote this cost Cselect. Thus we have an additional term Np|V |Cselect (where Np is the number of partitions), and the overall cost in terms of elementary operations can be estimated as: P artBounds : array of (FirstID:RID,LastID:RID);
Fill P artBounds by partition R into |P artBounds| partitions; foreach (PartBound p in P artBounds) { RID;
W orkmapp = map : RID -> ref to list of foreach (Value v in RSIF ) { lRv, lSv, lRvp : ref to list of RID; Ivnitialize lRv and lSv; lRp = Select(↑lRv, p); foreach (tR.rid in ↑lRvp ) {
Lr = W orkmapp.Get(tR.rid); if (Lr == NULL)
v result = lS; else
result = Intersect(↑Lr, ↑lSv);
W orkmapp.P ut(tR.rid, result); } }
} where C0 is a constant accounting for synchronous traversal of (possibly compressed) lists, and CW orkmapp is the cost of lookup into the W orkmapp. Comparison with the basic algorithm shows that the CW orkmapp ≤ CW orkmap, and, in presence of a compression, C0 > C. So in terms of elementary operations we do not get clear benefits. Let us now turn to the cost of memory references. Since W orkmapp now fits into the L2 cache, we do not get misses of the first kind at all. Since the number of inverted lists processed in a partition is fewer than that in the basic algorithm, we expect the cache misses of the second kind to happen more rarely. The number of misses of the third kind is also significantly reduced, since compressed lists occupy much less space and utilize cache lines more efficiently.
The question is therefore whether the better locality of memory references of the partitioned algorithm outweighs the cost of some additional CPU-intensive processing. As our experimental study reveals, under the condition that the number of partitions is properly chosen according to characteristics of the system, the partitioned version provides a significant performance improvement over the basic one.
The optimal number of partitions can be estimated as follows. Since it is desirable that all Lr fit into the cache, the number of tuples to be processed in each partition should not exceed |Csaiczhe(eLSriz)e| , and hence the number of partitions should be the minimal number that is greater than |CRa|scihzeeS(Lizre) . |Lr| decreases as the algorithm proceeds, but its average value remains in the bounds [L(R, S), |lS |], where L(R, S) and |lS |, as before, are the average number of qualifying tuples of S for a tuple of R, and average length of inverted lists lSv in RSIF , respectively. This observation enables to get an upper and a lower bounds for the number of partitions, but the interval between them can be quite large. So in practice, the number of partitions needs to be carefully tuned. 4
We have implemented both basic and partitioned version
of the algorithm in our research prototype MMDBMS
kernel Memphis. A short description of Memphis can be
found in [
All experiments were conducted on a laptop with
Intel P4 2.8 GHz CPU and 1 Gb RAM running under
Windows XP. This machine features Intel Pentium
Mobile processor with 2-level on-chip cache. The size of
the L2 cache is 512 Kb, and the size of the L2 cache
line is 128 bytes (these parameters were measured
using Stefan Manegold’s Calibrator tool [
In the most of experiments, synthetic datasets are used. These datasets were generated by a program that takes desired characteristics of the dataset (relations cardinalities, average set cardinality, distributions of set cardinalities and set elements, size of the element domain etc.) as parameters and produces the resulting dataset in the form of a text file. Each experiment starts with bulkloading the relevant relations from text files into memory. We used VTune’s ResumeSampling / SuspendSampling API to profile only cache misses that happen during the join execution and exclude other stages of the process. 4.1
In this case study, we use a dataset containing two relations, each of which consists of two attributes - the first is used as a primary key, and the second is a set-valued attribute. The characteristics of relations are given in the Table 1, the join selectivity is 5007 = 1.2 ∗ 10−7. |R||S| Running times corresponding to different values of the Np, i.e. to different numbers of partitions, are presented in the Table 2. Note that the basic version of the algorithm is essentially the case Np = 1. Looking at the Table 2, it becomes obvious that 5 partitions (which correspond to 150000/5 = 30000 RIDs in a partition) give the best results, providing the balance between the number of L2 cache misses and the amount of extra processing caused by partitioning. As the number of partitions grows further, the number of L2 cache misses reduces only marginally. The observed dependency between running time and number of partitions is depicted in the Figure 3. This experiment shows the impact of |V | on the running time of the algorithm. In this case study we only consider the partitioned version of the algorithm, the number of partition is chosen so that W orkmapp fits into the L2 cache, and the cardinalities of relations R and S are selected to keep all the processing in the main memory and avoid trashing as long as possible. We keep |R| = 100000, |S| = 250000 and |r| = |s| = 5 fixed, and vary |V |. The less |V |, the greater the expected length of inverted lists |S|Pv∈s. On the other hand, the weight of the term Np|V |Cselect decreases with the decrease of |V |. The results of the experiment given in the The compression of inverted lists in the intermediate results (W orkmapp) helps to reduce number of L2 cache misses while intersecting inverted lists, at the cost of increasing the constant C0 in the formula (1). We vary length of the inverted lists by changing average set cardinalities and the size of the domain |V |. The cardinalities of relations are kept fixed: |R| = 100000, |S| = 250000. The dependency among running time, total memory used by the program (to retrieve this value, the code was instrumented by a call to the GC.GetT otalM emory function from the .NET standard library. This function performs garbage collection before calculating the size of the heap), the average lengths of inverted lists and the cardinality of the result |Result| is illustrated in the Table 4. The table shows results for both versions of the algorithm, with and without compression. The one cell ‘-’ is missed because the algorithm was not able to finish due to exhaustion of all the available memory.
From these results it becomes clear that more compact inverted lists in the ‘compressed’ version, though reducing the number of L2 cache misses, do not pay off the increase in the cost of intersection operation. So the most important goal for using compression is smaller memory footprint. As the third and the fourth rows of the table demonstrate this effect is achieved only when all lR, lS and |Result| are large enough. This fact quite matches the intuitive expectations, since the less the cardinality of the result (in the extreme case of the third row the result is empty), the shorter inverted lists in the intermediate results, and the less benefits we give compressing them. A more sophisticated algorithm could use compression adaptively, predicting the cardinality of the join and keeping track of the size of intermediate results. More detailed development of such an algorithm is left for future work. 4.4
To demonstrate the efficiency of the proposed
algorithmm, we have compared its performance with some
other algorithms for set-containment joins. Those
algorithms include signature nested-loops join (SNL),
partitioned set join (PSJ) and the algorithm Index-SCJ based
on computing the intersection index of the relations
which we discussed in [
We have proposed an efficient algorithm for setcontainment joins in main memory. Our algorithm exploits inverted files which are combined into single join index allowing very efficient traversal of the set elements and the corresponding RIDs. The algorithm maintains a mapping of RIDs of the first relation to the list of RIDs of the second relation each of which contains all the elements of the set of the first relation encountered so far. After the final iteration, this mapping is exactly the join result. We have focused on the cache efficiency and discussed a partitioning method that improves memory references locality of the algorithm. As our experimental evaluation shows, the partitioning reduces the number of L2 cache misses by 10−15%. We have also applied compression to inverted lists in the intermediate results. The compression may decrease space requirements of the algorithm 4 times at the cost of performance deterioration. Its effectiveness in large extend depends on such parameters of the input relations as average lengths of the inverted lists in the index and join selectivity.
Future research on this algorithm should focus on applying compression adaptively. An adaptive version may keep inverted lists compressed or not depending on the length of the list, predicted join selectivity and current memory usage. Another possible direction for future work is a parallel algorithm for set-containment joins. The partitioned version of the algorithm can be easily parallelized, since there is no any data dependency between processing of different partitions. Running the algorithm in a multi-processor environment opens new possibilities for improving its response time. A more accurate cost model should be developed, since the current one does not take into account the fact that the inverted lists shrink during processing. We are now working on these problems and hope to present detailed results in the next paper.
Uncompressed Time, sec Mem. Usage, Mb 1.5 110 1.8 113 73 144 - 300
Compressed
Mem. Usage, Mb 113 90 146 91 [2] Sven Helmer and Guido Moerkotte. Evaluation of main memory join algorithms for joins with set comparison join predicates. In Proceedings of the 23rd VLDB Conference, pages 386–395, 1997. [3] Sven Helmer and Guido Moerkotte. Compiling away set containment and intersection joins (technical report), 2002.