Join Algorithms
Let's first understand why we would use join. We will normalize tables in relational databases to avoid the unnecessary repetition of information. We use the JOIN clause to reconstruct tuples without any information loss.
We want to focus on combining 2 tables at a time. In general, we want the smaller table to always be the left table in the outer plan. We will also focus on equijoin, and we want to check to see if there are equality match for tuples in tables. We want the smaller table to be the left, or the "outer table", in the query plan.
Before we discuss the algorithm, we make design decisions to talk about how these algorithm would work. The 2 design decisions is
1. What is the output of our join operator?
2. How do we decide whether one join implication is better than another.
Remember, epsilon here represents "in the relation". ∈
In general, we're trying to say for a tuple r ∈ R and a tuple s ∈ S, we want to produce some output that satisfy the joint predicate to send up to the next operator in the tree.
The benefit of this approach means that above in the tree we never will have to go back and ask for data from our underlying tables.
Only copy the joins keys along with the record ids of matching tuples. This is ideal for column stores because DBMS does not cope data that is not needed for query. This is called late materialization, which is only copying data that is needed.
The other thing to consider how we are going to determine whether one joint algorithm is better than the other.
We're considering the cost to compute the join and not the cost to compute the final metric in itself.
The join (R ⋈ S) is the most common operation and thus must be carefully optimized, and R x S followed by a selection is inefficient because the cross product is large. There are many algorithms reducing join cost, but no algorithm optimizes or works well for every since possible scenario.
Nested loop join is a for loop inside of another for loop and we check the predicate in the join clause in the SQL query, see whether they match, and then buffer for the output every time. Remember by this theory, for every single tuple in R, it scans S once. This is a stupid idea.
foreach tuple r ∈ R:
foreach tuple s ∈ S:
emit, if r and s match
Why is it a stupid idea? Because we fetch the page in the tuple every time, and it's super dumb because it's super expensive and repetitive and you can easily simplify this process. For M pages and nn tuples for R and N pages and n tuples for S, the cost is M + (m x N).
One optimization to speed this thing up with the smaller table as the outer table.
A way to improe this "stupid" method is to have locks or pages. For each block and tuple, we can pack in multiple tuples in our pages, allocating one block for the outer table and one block for the inner table. We don't go to the block in the inner table until we evaluate every tuple in the outer block. For every single PAGE in the inner table, we're seeking out the page in the outer table. Now, getting multiple tuples, and sequential I/O can cut things down to nearly a second.
The algorithm uses B-2 for scanning R. Cost is M + ([M / (B - 2)] * N.
Why do nested loop joins suck? We know nothing about the locality of the data, we knew about matches. For each tuple in the outer table, we must check a sequential scan to check for a match in the inner table. We can avoid these scans by using an index to find inner table matches.
We can avoid sequential scans by using the index to find inner table matches. We can build an ephemeral index to do query and then throw it away afterwards. But again, if it's a hash table best case scenario O(1) vs. just a B+ table.
All you need to know about nested loop joins is that it's a brute force approach that is the easiest to implement. ALWAYS pick the smaller table as the outer iteration.
There is a sort-merge join algorithm.
Phase 1: Sort
Sort both tables on the JOIN keys. Use the external merge sort algorithm talked about in the last lecture.
Phase 2: Merge
Step through the two sorted tables with cursors and emit matching tuples
May need to backtrack depending on join type.
After sorting we're going to have 2 cursors (one on the inner table and one on the outer table). At each iteration, if the outer relation cursor points at a tuple greater than the inner, then we increment the inner. If the inner is greater than the outer then increment the outer. If equal, set as a match then increment the inner.
Here's the code:
sort R, S on join keys
cursorR <= Rsorted, cursorS <- Ssorted
while cursorR and cursorS:
if cursorR > cursorS:
increment cursorS
if cursorR < cursorS:
increment cursorR
elif cursorR and cursorS match:
emit
increment cursorS
Reading code like this is difficult, let's do a visual example. we first sort by ID as first, and we then have a cursor walk through these 2 tables.
Here we first match when id = 100.
Go through ids and increment everything based on the smaller id and maybe get a match. We may have to backtrack on the inner relation, but not on the outer relation. When you backtrack, then if you see there is a 200 on one table and you are on 400 in the inner relation, this is where you need to backtrack.
The merge cost is M + N (read every page of the outer table and inner table once they are sorted). Let's attempt a sort-merge join on 2 tables, R and S.
Let's say M = 100, m = 100,000 with 100 buffer pages for table R.
Let's also say N = 500 and n = 50,000 for table S.
Sort Cost (R) = 2000 x (log 1000 / log 100) = 3000 IOs.
Sort Cost (S) = 1000 x (log 500 / log 100) = 1350 IOs.
Merge Cost = (1000 + 500) = 1500 IOs.
Total cost = 3000 + 1350 + 1500 = 5850 I/Os which at 0.1ms/IO time is 0.59 seconds.
Sort-merge join is useful when 2 tables are already created on the join key. The input relations may be sorted by either an explicit sort operator or by scanning the relation using an index on the join key.
For enormous data sets, we use a Hash Join. The basis of hash function is based on hash aggregation, and this hash joining is deterministic. So if 2 tuples satisfy the join condition, then they have the same value for join attributes.
If that value is hashed to some partition i, the R tuple must be in ri and S tuple in si, thus R tuples in ri need only to be compared with S table in Si, only comparing the tuples in our particular partition.
build hash table HTR for R
foreach tuple s ∈ S
output, if h1(s) ∈ HTR
There are 2 approaches:
Approach 1 is Full tuple, avoid having to retrieve the outer relation's tuple contents on a match. However, this takes up more space in the memory.
Approach 2 is a tuple identifier, which is ideal for column stores because the DBMS does not feth data it doesn't need, and better if the join selectivity is very low.
We can use a bloom filter for probe phas optimization during the build phase when the key is not likely to exist in the hash table. Threads check the filter before probing the table and this will be faster since filter will fit in CPU caches, sometimes called sideways information passing.
Bloom filters is a probabilitstic data structure, or a bitmap that answers set membership queries. False negatives will never occur, but false positives will sometimes occur. There are 2 methods in the Bloom filter: Insert and Lookup.
Insert(x) use k hash functions to set bits in the filter to 1.
Lookup(x) checks whether the bits are 1 in each hash function.
We hash something and mod this by the number of bits in the bloom filter and that gives us the corresponding location inside of the bitmap.
What if we have hash join that doesn't fit entire hash table. We don't want the buffer pool manager to be swapping out hash tables at random! We want to convert the random access pattern in the hash table into something that's more sequential. This is the grace hash join or technique. This is Hash join when tables do not fit in the memory.
The Build Phase is when you hash both tables on the join attribution on partitions. The probe phase compares tuples in corresponding partitions for each table.
This is based on the Grace data machine in Tokyo.
In Grace Hash Join, we want ot hash R into (0, 1, max) buckets and hash S into the same number of buckets with the same function. In the probe phase, we're just going to take all the buckets within the partition and just do a nested for loop now to see if the buckets match as a result.
If the buckets do not fit in memory, then use recursive partitioning to split the tables into chunks that will fit, build another hash table with an alternative hash. Then at the end I can run both hash functions in each of these partitions and keep doing this over and over again until I can get things to fit in memory.
Assuming we have enough buffers to fit all the hashes, the cost is 3(M + N). The reduced cost is why the hash join is preferable. If the DBMS knows the side of the outer table, then it can try to size the buffer/hash table accordingly by using a static hash table. If we do not know the side, we can either use a dynamic hash table with overflow pages.
Here's a summary of all of the different costs:
If I have 3 tables to join A, B, and C, I first join A and B and then the corresponding output that I want to join is in B and C. The more joins you have, the worse your estimations get.
The main takeaway is that Hash is almost always better than sorting than non-uniform data or the data is already sorted. This is what separates open-source database systems to the very expensive ones. If the data is not skewed, it should be uniformly distributed.
Comments
Post a Comment