=Paper=
{{Paper
|id=Vol-154/paper-7
|storemode=property
|title=Partitioning Inverted Lists for Efficient Evaluation of Set-Containment Joins in Main Memory
|pdfUrl=https://ceur-ws.org/Vol-154/shaporenkov.pdf
|volume=Vol-154
}}
==Partitioning Inverted Lists for Efficient Evaluation of Set-Containment Joins in Main Memory==
https://ceur-ws.org/Vol-154/shaporenkov.pdf
Partitioning Inverted Lists for Efficient Evaluation of
Set-Containment Joins in Main Memory
c Dmitry Shaporenkov
University of Saint-Petersburg, Russia
dsha@acm.org
Abstract However, as study [3] shows, relational query optimizers
are generally unable to deal with such queries in an effi-
We present an algorithm for efficient process- cient manner, since set predicates are unknown for them.
ing of set-containment joins in main memory. Given the growing practical importance of joins with
Our algorithm uses an index structure based on set predicates, efficient algorithms for performing such
inverted files. We focus on improving perfor- joins are required. Nested-loops algorithm is the most
mance of the algorithm in a main-memory envi- common way to handle joins with complex predicates.
ronment by utilizing the L2 CPU cache more ef- However, in case of joins with set predicates nested
ficiently. To achieve this, we employ some op- loops algorithm falls short, because its poor performance
timizations including partitioning the inverted makes it inappropriate [2]. The reason is that testing
lists and compressing the intermediate results. predicates on sets is a very expensive operation. Its cost
in large extent depends on how the sets in question are
1 Introduction represented, but in general this cost is much higher than
Set-valued attributes have become more important in re- the cost of simple join predicates on atomic attributes tra-
cent years with growing distribution of object-relational ditionally used in relational database systems.
database systems (ORDBMS) and rapid development of Main-memory DBMS (MMDBMS) have attracted
such application areas as information retrieval and data much attention during recent decade. A MMDBMS
mining. In practice it is often required to evaluate join stores all the data and support structures (such as in-
queries on set-valued attributes. In such cases the join dexes) in RAM of the database server. Constantly grow-
predicate is a set predicate, such as set containment or in- ing amount of memory in modern database servers al-
tersection. Many real-world queries can be naturally ex- ready enables to store small and medium-size databases
pressed as set containment and intersection joins. For ex- directly in main memory. It has been shown that
ample, a query that finds appropriate candidates among MMDBMS provide huge performance gain over tradi-
job seekers includes a condition that the set of candi- tional, disk-based DBMS, since retrieving the necessary
date’s skills contains the set of skills required for the job data in MMDBMS usually does not involve disk access
as a subset. If we are interested in retrieving all docu- at all. Slow disk device is used only for logging and re-
ments containing the specified set of terms from the col- covery. Many researchers [11, 1] have recognized that
lection, this again can be considered a set containment the crucial factor for performance of a MMDBMS is
query. A relation People that includes a set-valued at- CPU cache utilization, that is, how many cache misses
tribute Hobbies leads us to the problem of finding all database operations incur. If the number of cache misses
pairs of people sharing common hobbies that can be for- is high, CPU will spend most of time waiting the data to
mulated as a set intersection self-join. be fetched from RAM (so-called CPU stall).
Set-valued attributes are not directly supported in a
In this paper we present an efficient algorithm based
traditional relational DBMS, since already the first nor-
on inverted files for set-containment joins in main mem-
mal form explicitly requires an attribute to be atomic, i.e.
ory. Inverted files are well-known and widely used tool
forbids the value of an attribute to be a set. However, set-
for indexing text documents. Our algorithm takes two
valued attributes in a relational DBMS can be simulated
relations R and S sharing a set-valued attribute A as pa-
using unnested external representation [3] that creates an A
rameters, scans the common inverted file IFRS built on
auxiliary relation connected to the original relation by a
the set-valued attribute A for R and S and processes the
foreign key, thus representing one-to-many relationship
inverted lists in such a way that the resulting structure ap-
between a record of the original relation and the elements
pears to be the answer to the set-containment query. The
of the value of its set-valued attribute. It can be easily
idea of the algorithm is fairly simple, and we focus our
noticed [7] that many complex joins on atomic attributes
study on tailoring the algorithm for MMDBMS by im-
that arise in relational DBMS in fact hide set predicates
proving CPU cache utilization. We achieve this by par-
behind sophisticated expressions involving aggregation.
titioning the inverted lists being processed. This enables
Proceedings of the Spring Young Researcher’s Colloquium
to fit the working set of the algorithm into the L2 CPU
on Database and Information Systems SYRCoDIS, St.-Petersburg, cache and reduce the number of L2 cache misses. We
Russia, 2005 also study the effect of compressing the intermediate re-
sults which provides significant memory savings and al- and s2 are said to k-overlap if they have at least k el-
lows to join larger relations at the cost of more intensive ements in common). He proposes Block Nested-Loops
CPU usage and some loss in response time. We present algorithm (BNL) that uses inverted file SIF built on the
experimental results showing that our optimizations give relation S. The SIF is partitioned into blocks each of
significant effect as compared with a straightforward im- which can fit into the main memory. The BNL algo-
plementation. We also demonstrate that the algorithm rithm proceeds by reading each block of SIF and scan-
is superior to some other algorithms for set-containment ning the relation R to find qualifing tuples. Different
joins. strategies for handling the intermediate results are eval-
The structure of the paper is as follows. The section uated. Mamoulis also discusses the algorithm IFJ (IFJ
2 presents a survey of related work in the area of al- - Inverted File Join) that joins two inverted files RIF
gorithms for joins with set predicates. In the section 3 and SIF , but rejects this algorithm as inefficient. While
we first describe the basic algorithm for set-containment IFJ and our algorithm are based on essentially the same
joins using inverted files, and then discuss various opti- idea, our algorithm targets specifically MMDBMS and
mizations aiming to improve its performance. The sec- exploits some important optimizations improving cache
tion 4 summarizes the results of experimental evaluation performance like partitioning the processing to fit the in-
of the algorithm. The section 5 concludes the paper and termediate results into the L2 CPU cache. Our partition-
outlines directions for future work. ing method differs from that of Mamoulis, as he simply
reads the inverted files block by block, while our method
rather operates on the individual inverted lists and pro-
2 Related work cesses only the part of each list relevant to the current
Helmer and Moerkotte [2] seem to be the first researchers partition. The reason is that Mamoulis designed and
who addressed specifically set containment joins. They evaluated his algorithms in the context of a disk-based
evaluated several algorithms for set containment join in DBMS where efficiency criteria differ significantly from
main memory. The first group of algorithms includes those in a MMDBMS.
variations of nested-loops join which differ in how the During the last decade, many algorithms commonly
set comparison is implemented. Three implementations used in DBMS in the course of many years were recon-
of set comparison were considered: the naive algorithm, sidered from the viewpoint of their suitability and op-
an implementation based on sorting the sets and an ap- timality for main-memory DBMS. [11] was one of the
proach that uses signatures. The latter turned out to be first works concerning this problem. It suggests cache-
the best among nested-loops joins. The second algo- conscious versions of several well-known database al-
rithm employs signature-based approach by hashing all gorithms such as hash-join, and also demonstrates some
the signatures of the relation R (assuming that the join fundamental techniques that can be used for improving
condition is tR .A ⊆ tS .A, tR , tS are tuples of R and S, performance of main-memory algorithms. One of the re-
respectively, tR .A is a set that is the value of A in tR ), cent works in the field, [6], discusses cache-conscious
enumerating subsets of each set of the relation S, and hash-join algorithms including projections on different
matching each subset with hashed signatures of R. storage models. These and other works have made great
Melnik and Garcia-Molina [7] describe two algo- contribution by increasing researchers’ and developers’
rithms for set containment joins. Both algorithms ex- awareness of cache performance issues. However, to
ploit essentially the same idea, namely, partitioning the the best of our knowledge, more complex database al-
relations being joined in such a way that the join result gorithms like one discussed in this paper have not been
can be computed by joining sets from each pair of cor- reviewed from the viewpoint of their optimality on mod-
responding partitions and then merging intermediate re- ern hardware yet.
sults. The main problem with this approach is that in the
case of set containment joins the partitions inevitably in- 3 Set-containment join algorithm using in-
tersect. The first method, Adaptive Pick-and-Sweep Join, verted files
extends the Pick-and-Sweep algorithm proposed in [8].
The algorithm is parameterized by a set of {h1 , ..., hk } Inverted files are a well-known technique for index-
boolean hash functions that take sets as input. For each ing text documents. Essentially, an inverted file pro-
tuple tR ∈ R the function hi is randomly chosen such vides a mapping of a term T into the list of documents
that hi (tR .A) = true, and tR is assigned to the parti- D1 , ..., Dk where this term occurs (Dj is an ID of the
tion Ri . For each tuple tS ∈ S all the functions hj such document in the collection). [13] discusses in depth var-
that hj (tS .A) = true are chosen, and tS is assigned to ious methods for constructing inverted files. To reduce
each of the partitions Sj . The second method, Adaptive storage cost, inverted files can be efficiently compressed
Divide-and-Conquer Join, progressively refines the par- at almost no loss in search speed: the list of documents
tition assignment. It starts with the single partition pair, D1 , ..., Dk is ordered, and instead of storing document
and on each step doubles the number of partitions by ap- IDs, the differences Di − Di−1 are kept in an encoded
plying a hash function to either set tR .A or tS .A. On form. Given that the access to inverted list is mostly se-
each step the partition assignment is modified to make quential, document IDs can be easily decoded ‘on the
the condition that each set of Ri can be contained only in fly’.
sets of the corresponding Si true (details can be found in We apply inverted files in a different context but the
[7]). idea remains the same. Instead of collection of docu-
Mamoulis [4] considers several algorithms for set ments, we consider relations R and S and the common
containment, intersection and overlap join (two sets s1 set-valued attribute A. We denote Domain(A) the do-
Workmap : map : RID -> ref to list of RID;
main from which elements of values of A in tuples of R
foreach (Value v in RSIF )
and S are drawn. Tuples of relations are identified by {
record ID (RID). Inverted file RIF then maps an element v
lR , lSv : ref to list of RID;
of the Domain(A) into the list of RIDs of tuples whose Initialize lR v
and lSv ;
value of A contains this element. foreach (tR .rid in ↑lR v
)
We design our algorithm under assumption that all the {
data and indexes are kept in main memory. This assump- Lr , result : ref to list of RID;
tion greatly affects the algorithm design, since main fo- Lr = W orkmap.Get(tR .rid); (!)
cus now shifts from minimizing the number of disk ac- if (Lr = NULL)
cesses (which we assume do not happen at all) to min- result = lSv ;
else
imizing the number of cache misses. While both these
result = Intersect(↑Lr , ↑lSv ); (!)
aims require good reference locality, the methods for W orkmap.P ut(tR .rid, result);
achieving them are somewhat different [6]. The first im- }
portant difference between the CPU cache and file cache }
in RAM is that the former is normally much smaller. The
second difference is that generally speaking CPU cache Figure 1: Basic algorithm for computing set-containment
cannot be directly controlled by the program. joins
Our algorithm employs the idea of join indexes [12, 9]
to speed-up the join. Instead of building two separate L(R, S) = |Result|
|R| . The basic algorithm is presented in
inverted files RIF and SIF , we build one inverted file the Figure 1.
(we denote it RSIF ) that maps an element v of the For clarity, our notation uses ↑ to mark dereferences
v
Domain(A) into two lists of the RIDs, lR and lSv , where which cause cache misses. This facilitates identifying
v v sources of the cache misses in the algorithm.
lR and lS consist of all RIDs of tuples from R and S, re-
spectively, each of which contains the element v among The function Intersect computes intersection of two
the values of the set-valued attribute. In an actual im- inverted lists. Given that lists are kept in ascending order
v
plementation, lR and lSv can be merged into one list, but of RIDs, this function can be efficiently implemented
there should be an efficient way to separate them. This by synchronously traversing both inverted lists. For the
enables us to find all tuples from R and S containing the sake of simplicity, in our analysis we will ignore the
given element using only single lookup in the inverted fact that lists shrink during processing. Then the cost
file. As noticed in [9], this property comes at the cost of of computing the intersection in terms of elementary
some loss in efficiency in case if RSIF is used in role operations (such that index increment and integer
of either RIF or SIF (that is, if RSIF is used for finding comparison) does not exceed C(|Lr | + |lS |), where |Lr |
all tuples from either R or S containing an element). The is the average length of the Lr and |lS | is the average
exact value of the decrease in search efficiency depends length of inverted list for S, and C is a constant. Let
on the implementation of the inverted file. In our im- |V| be the number of different values in the inverted
plementation it is quite affordable. On the positive side, file RSIF , |R| and |S| - cardinality of relations R and
combining two inverted files into one gives us a very effi- S, and |r| and |s| - average cardinalities of values of the
cient way for traversing all elements of the Domain(A) set-valued attribute A in relations R and S, respectively.
and their corresponding inverted lists in both relations Assuming that the values are uniformly distributed
without using index lookup. across tuples, the probability for a tuple tS to have a
value v among the elements of the set tS .A is equal to
Pv∈s = 1 − (1 − |V1 | )|s| . Hence we have |lS | = |S|Pv∈s ,
3.1 Basic set-containment join algorithm
and the cost
of the algorithm can be estimated
as
We present the basic version of the algorithm for set- |r||R| C |Result|
|R| + |S|P v∈s + CW orkmap where
containment joins based on inverted files. We assume CW orkmap is the cost of lookup into the W orkmap.
that the join predicate is r ⊆ s where r, s are values of the Our algorithm and cost estimation, however, do not
set-valued attribute A in relations R and S, respectively. take into account that the memory access is not uniform
We denote tR , tS tuples of relations R and S, tR .rid, on modern architectures. Random memory access such
tS .rid RIDs of tuples, and tR .A, tS .A their values of that access to the W orkmap becomes very expensive in
the attribute A. Let also |Result| be the cardinality of presence of several memory hierarchies like L1 and L2
the result relation that consists of pairs (tR .rid, tS .rid) caches, unless the W orkmap entirely fits into one of the
qualifying the containment predicate tR .A ⊆ tS .A. The caches. Let us then take a closer look on the memory ref-
algorithm traverses the combined inverted file RSIF , and erence behavior of the algorithm. Let Cmiss be the cost
v v
on each step processes inverted lists lR , lS , where v is an of a L2 cache miss. The main sources of cache misses in
element of the Domain(A) (both lists may be empty). the basic algorithm are (in the Figure 1 the corresponding
It maintains a mapping W orkmap that maps tR .rid into lines are marked (!)):
a reference to the list of Lr = tS1 .rid, ..., tSn .rid such
that each of tSk .A contains all the elements of tR .A en- • The W orkmap is accessed in a random fashion,
countered so far. These lists shrink as the algorithm pro- and if the size of the W orkmap exceeds the size of
ceeds. After the final iteration W orkmap is exactly a the L2 cache, we may consider that every access to
mapping of tR .rid into the list of tS1 .rid, ..., tSm .rid the W orkmap incurs at least one cache miss (The
where tR .A ⊆ tSk .A, k = 1, ..., m. The average exact number of cache misses depends on the imple-
length of the Lr in the final result can be estimated as mentation of the W orkmap. In case if W orkmap
is implemented as a hash table, we expect the ac- P artBounds : array of
(FirstID:RID,LastID:RID);
cess to this hash table to be as efficient as access to
Fill P artBounds by partition R into
an array, since the number of collisions in our situ- |P artBounds| partitions;
ation is small). The total cost of these cache misses foreach (PartBound p in P artBounds)
is therefore |r||R|Cmiss . {
W orkmapp = map : RID -> ref to list of
• Dereferencing a reference to Lr that happens in the RID;
line result = Intersect(↑Lr , ↑lSv ) incurs another foreach (Value v in RSIF )
cache miss. The cost of these cache misses is (|r| − {
v
1)|R|Cmiss , since the first access to the W orkmap lR , lSv , lR
v
p
: ref to list of RID;
v
for the given tR .rid does not cause a cache miss. Initialize lR and lSv ;
v v
lRp = Select(↑lR , p);
v
• Computing the intersection of two lists of lengths l1 foreach (tR .rid in ↑lR p
)
(|l1 |+|l2 |) {
and l2 sorted in ascending order incurs |CacheLine| Lr , result : ref to list of RID
cache misses, where |CacheLine| is the size of the Lr = W orkmapp .Get(tR .rid);
L2 cache line. if (Lr == NULL)
result = lSv ;
Of course, there are other sources of cache misses in else
result = Intersect(↑Lr , ↑lSv );
the algorithm, for instance, dereferencing references to
v W orkmapp .P ut(tR .rid, result);
the lists lR 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.
Figure 2: Partitioned algorithm for computing set-
3.2 Partitioned version of the algorithm containment joins
Our method reduces amount of cache misses of all the
aforementioned kinds. In order to eliminate misses of the |Result|
first kind, we partition the processing to fit W orkmap |r||R| C 0 + |S|Pv∈s +
into the L2 cache. This can be done in an obvious way |R|
- we modify the algorithm so that only a part of the tu-
CW orkmapp + Np |V |Cselect (1)
ples 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 where C 0 is a constant accounting for synchronous
are processed at a moment, the more likely they reside in traversal of (possibly compressed) lists, and CW orkmapp
the L2 cache. The cache misses of the third kind are dealt is the cost of lookup into the W orkmapp . Comparison
with by compressing the Lr using one of many compres- with the basic algorithm shows that the CW orkmapp ≤
sion techniques for ascending sequences of positive in- CW orkmap , and, in presence of a compression, C 0 > C.
teger numbers [13]. The modified version of the algo- So in terms of elementary operations we do not get clear
rithm is presented in the Figure 2. To make presentation benefits. Let us now turn to the cost of memory refer-
clearer, we omit compression. In reality, if inverted lists ences. Since W orkmapp now fits into the L2 cache, we
are already kept compressed in the inverted files, the al- do not get misses of the first kind at all. Since the num-
gorithm can be unaware of compression at all. The rea- ber of inverted lists processed in a partition is fewer than
son is that the computation of intersection of inverted that in the basic algorithm, we expect the cache misses
lists is done by the same code regardless of whether the of the second kind to happen more rarely. The number
arguments are compressed are not, since this computa- of misses of the third kind is also significantly reduced,
tion accesses elements of lists in a sequential fashion. since compressed lists occupy much less space and uti-
The function Select selects the range of RIDs relevant lize cache lines more efficiently.
to the current partition p from the (possibly compressed) The question is therefore whether the better locality
v
inverted list lR . This function can be implemented in of memory references of the partitioned algorithm out-
various ways: using sequential scan of the lR v
, the bi- weighs the cost of some additional CPU-intensive pro-
v
nary search in lR or even the specialized index on lR v
that cessing. As our experimental study reveals, under the
would enable to determine the first RID residing within condition that the number of partitions is properly chosen
the interval [p.F irstID, p.LastID]. according to characteristics of the system, the partitioned
version provides a significant performance improvement
Let us now estimate the cost of the partitioned ver-
over the basic one.
sion of the algorithm. We can proceed by analogy with
The optimal number of partitions can be estimated
the case of the basic algorithm. For the partitioned ver-
as follows. Since it is desirable that all Lr fit into the
sion of the algorithm we also need to take into account
cache, the number of tuples to be processed in each par-
the cost of the Select function. Generalizing possible
implementations of Select, we denote this cost Cselect . tition should not exceed |CacheSize|
size(Lr ) , and hence the num-
Thus we have an additional term Np |V |Cselect (where ber of partitions should be the minimal number that is
Np is the number of partitions), and the overall cost in greater than |R|size(L r)
CacheSize . |Lr | decreases as the algorithm
terms of elementary operations can be estimated as: 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 Table 1: Relations characteristics for Case Study 1
of R, and average length of inverted lists lSv in RSIF , re- Rel. Rel. Card. Avg. Set Card. |Domain(A)|
spectively. This observation enables to get an upper and R 150000 5 5000
a lower bounds for the number of partitions, but the in- S 300000 5 5000
terval between them can be quite large. So in practice,
the number of partitions needs to be carefully tuned. Partitions Time, sec L2 Cache Misses, * 106
1 3.9 42
3 3.66 36
4 Experimental study
5 3.52 33
We have implemented both basic and partitioned version 8 3.72 33
of the algorithm in our research prototype MMDBMS 11 3.84 33
kernel Memphis. A short description of Memphis can be 16 4.04 32
found in [10]. The implementation is written in the C#
programming language [14] and runs on the .NET frame- Table 2: Tuning the number of partitions
work. Inverted files are implemented using the standard
Hashtable class. We considered two variants of the Running times corresponding to different values of the
algorithm: the first does not use compression, and the Np , i.e. to different numbers of partitions, are presented
second compresses inverted lists by encoding differences in the Table 2. Note that the basic version of the algo-
between subsequent elements in γ-code [13]. Unless ex- rithm is essentially the case Np = 1. Looking at the
plicitly mentioned, we assume that the version without Table 2, it becomes obvious that 5 partitions (which cor-
compression is used. Our implementation of the Select respond to 150000/5 = 30000 RIDs in a partition) give
function uses sequential scan of lR v
, since in the case of the best results, providing the balance between the num-
compressed inverted lists binary search would be impos- ber of L2 cache misses and the amount of extra process-
sible. Trying implementation of the Select function in ing caused by partitioning. As the number of partitions
the form of index on long inverted lists is left for future grows further, the number of L2 cache misses reduces
research. only marginally. The observed dependency between run-
All experiments were conducted on a laptop with In- ning time and number of partitions is depicted in the Fig-
tel P4 2.8 GHz CPU and 1 Gb RAM running under ure 3.
Windows XP. This machine features Intel Pentium Mo-
bile processor with 2-level on-chip cache. The size of 4.2 Case Study 2: Varying element domain’s cardi-
the L2 cache is 512 Kb, and the size of the L2 cache nality
line is 128 bytes (these parameters were measured us- This experiment shows the impact of |V | on the running
ing Stefan Manegold’s Calibrator tool [5]). For mea- time of the algorithm. In this case study we only con-
suring the number of L2 cache misses we used the Intel sider the partitioned version of the algorithm, the num-
VTune Performance Analyser [15] that provides a graph- ber of partition is chosen so that W orkmapp fits into
ical user interface to various CPU counters. All reported the L2 cache, and the cardinalities of relations R and S
times were estimated using QueryPerformanceCounter / are selected to keep all the processing in the main mem-
QueryPerformanceFrequency Windows API that gives ory and avoid trashing as long as possible. We keep
a programmatic access to the high-resolution hardware |R| = 100000, |S| = 250000 and |r| = |s| = 5 fixed,
performance counter. To reduce noise, we present aver- and vary |V |. The less |V |, the greater the expected
age times based on results of several runs. We do not length of inverted lists |S|Pv∈s . On the other hand, the
include in the results the time necessary for constructing weight of the term Np |V |Cselect decreases with the de-
the inverted file (join index), since it is assumed to exist crease of |V |. The results of the experiment given in the
in a practical situation.
In the most of experiments, synthetic datasets are
used. These datasets were generated by a program that
takes desired characteristics of the dataset (relations car-
dinalities, average set cardinality, distributions of set car-
dinalities 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 bulk-
loading 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 Case Study 1: Tuning number of partitions
In this case study, we use a dataset containing two rela-
tions, 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 Figure 3: Dependency of running time on number of par-
5007
the Table 1, the join selectivity is |R||S| = 1.2 ∗ 10−7 . titions
|V | Time, sec Algorithm Time, sec
500 15 SNL 545
250 29 PSJ 146
200 37 Index-SCJ 12
100 213 IFJ 0.3
Table 3: Impact of element domain cardinality Table 5: Comparison with other algorithms
Table 3 show that the cost of merging the inverted lists results are depicted in the Table 5, where the proposed al-
dominates in the cost formula (1), and long inverted lists gorithm is denoted IFJ (Inverted File Join). Though this
dramatically reduce the performance of the algorithm. measurement is not quite representative, it nevertheless
This is where compression comes into play and enables shows that the IFJ outperforms competitors on the or-
to process much larger relations by effectively reducing ders of magnitude. For fair comparison we should note,
memory space consumed by inverted lists. however, that such a performance is achieved at the cost
of significant extra space needed for intermediate results.
4.3 Case Study 3: Effect of compression Among other algorithms, SNL and PSJ have very mod-
The compression of inverted lists in the intermediate re- erate space requirements, while Index-SCJ also needs
sults (W orkmapp ) helps to reduce number of L2 cache much memory for the intersection index.
misses while intersecting inverted lists, at the cost of in-
creasing the constant C 0 in the formula (1). We vary 5 Conclusion
length of the inverted lists by changing average set cardi-
We have proposed an efficient algorithm for set-
nalities and the size of the domain |V |. The cardinalities
containment joins in main memory. Our algorithm ex-
of relations are kept fixed: |R| = 100000, |S| = 250000.
ploits inverted files which are combined into single join
The dependency among running time, total memory used
index allowing very efficient traversal of the set elements
by the program (to retrieve this value, the code was in-
and the corresponding RIDs. The algorithm maintains a
strumented by a call to the GC.GetT otalM emory func-
mapping of RIDs of the first relation to the list of RIDs
tion from the .NET standard library. This function per-
of the second relation each of which contains all the el-
forms garbage collection before calculating the size of
ements of the set of the first relation encountered so far.
the heap), the average lengths of inverted lists and the
After the final iteration, this mapping is exactly the join
cardinality of the result |Result| is illustrated in the Ta-
result. We have focused on the cache efficiency and dis-
ble 4. The table shows results for both versions of the
cussed a partitioning method that improves memory ref-
algorithm, with and without compression. The one cell
erences locality of the algorithm. As our experimental
‘-’ is missed because the algorithm was not able to finish
evaluation shows, the partitioning reduces the number of
due to exhaustion of all the available memory.
L2 cache misses by 10−15%. We have also applied com-
From these results it becomes clear that more compact
pression to inverted lists in the intermediate results. The
inverted lists in the ‘compressed’ version, though reduc-
compression may decrease space requirements of the al-
ing the number of L2 cache misses, do not pay off the in-
gorithm 4 times at the cost of performance deterioration.
crease in the cost of intersection operation. So the most
Its effectiveness in large extend depends on such param-
important goal for using compression is smaller mem-
eters of the input relations as average lengths of the in-
ory footprint. As the third and the fourth rows of the
verted lists in the index and join selectivity.
table demonstrate this effect is achieved only when all
Future research on this algorithm should focus on ap-
lR , lS and |Result| are large enough. This fact quite
plying compression adaptively. An adaptive version may
matches the intuitive expectations, since the less the car-
keep inverted lists compressed or not depending on the
dinality of the result (in the extreme case of the third
length of the list, predicted join selectivity and current
row the result is empty), the shorter inverted lists in the
memory usage. Another possible direction for future
intermediate results, and the less benefits we give com-
work is a parallel algorithm for set-containment joins.
pressing them. A more sophisticated algorithm could use
The partitioned version of the algorithm can be easily
compression adaptively, predicting the cardinality of the
parallelized, since there is no any data dependency be-
join and keeping track of the size of intermediate results.
tween processing of different partitions. Running the
More detailed development of such an algorithm is left
algorithm in a multi-processor environment opens new
for future work.
possibilities for improving its response time. A more ac-
4.4 Case Study 4: Comparison with other algo- curate cost model should be developed, since the current
rithms one does not take into account the fact that the inverted
lists shrink during processing. We are now working on
To demonstrate the efficiency of the proposed algo- these problems and hope to present detailed results in the
rithmm, we have compared its performance with some next paper.
other algorithms for set-containment joins. Those algo-
rithms include signature nested-loops join (SNL), parti-
References
tioned set join (PSJ) and the algorithm Index-SCJ based
on computing the intersection index of the relations [1] P. A. Boncz, S. Manegold, and M. L. Kersten.
which we discussed in [10]. To keep running times rea- Database Architecture Optimized for the New Bot-
sonable we considered small relations: |R| = 15000, |S| tleneck: Memory Access. In Proceedings of the
= 25000, |V | = 1000, |r| = |s| = 5, |Result| = 1147. The 25th VLDB Conference, pages 54–65, 1999.
Uncompressed Compressed
|lR | |lS | |Result| Time, sec Mem. Usage, Mb Time, sec Mem. Usage, Mb
20 50 137 1.5 110 3.2 113
75 188 1759 1.8 113 3.9 90
3000 7500 0 73 144 115 146
500 2250 50 ∗ 106 - 300 151 91
Table 4: Effect of compression
[2] Sven Helmer and Guido Moerkotte. Evaluation [15] Intel VTune Performance Analyzer.
of main memory join algorithms for joins with set http://www.intel.com/software/products/vtune/.
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 (tech-
nical report), 2002.
[4] Nikos Mamoulis. Efficient processing of joins on
set-valued attributes. In Proceedings of the SIG-
MOD 2003 Conference, pages 157–168, 2003.
[5] Stefan Manegold. The Calibrator, a
Cache-Memory and TLB Calibration Tool.
http://homepages.cwi.nl/˜manegold/Calibrator/.
[6] Stefan Manegold, Peter Boncz, Niels Nes, and Mar-
tin Kersten. Cache-conscious radix-decluster pro-
jections. In Proceeding of the SIGMOD 2004 Con-
ference, 2004.
[7] Sergey Melnik and Hector Garcia-Molina. Adap-
tive Algorithms for Set Containment Joins. ACM
Transactions on Database Systems, 28:56–99,
2003.
[8] Karthikeyan Ramasamy et al. Set containment
joins: The good, the bad and the ugly. In Proceed-
ings of the 26th VLDB Conference, pages 351–362,
2000.
[9] Dmitry Shaporenkov. Multi-indices - a tool for
optimizing join processing in main memory. In
Proceedings of the Baltic DBIS 2004 Conference,
pages 105–114, 2004.
[10] Dmitry Shaporenkov. Performance comparison of
main-memory algorithms for set containment joins.
In Proceedings of the SYRCoDIS’04, pages 17–21,
2004.
[11] Ambuj Shatdal, Chander Kant, and Jeffrey F.
Naughton. Cache Conscious Algorithms for Re-
lational Query Processing. In Proceedings of the
20th VLDB Conference, pages 510–521, 1994.
[12] Patrick Valduriez. Join Indices. ACM Transactions
on Database Systems, 12:218–246, 1987.
[13] Ian Witten, Alistair Moffat, and Timothy Bell.
Managing Gigabytes : Compressing and Indexing
Documents and Images. Morgan Kaufmann pub-
lishers, second edition, 1999.
[14] C# Language Specification. ECMA-334 Interna-
tional Standard, 2001.