Untitled

Page 1

Intro

Each node in a Logical Query Plan may be executed in several ways

there is no single implementation that is always better than the others

so we need to compare alternatives based on their costs (in I/O Model of Computation it's # of I/O operations)

Statistics

To estimate a cost we use the following statistics from Database System Catalog:

B(R) - # of blocks that relation R holds

T(R) - # of tuples in R

typically can be used to calculate B(R) when we know how many bytes we have per block

V(R,A1,...,An)=|δπA1,...,An(R)| - # of distinct values

Parameters

And also we use

M - number of available main memory buffers

To simplify we suppose that the situation is ideal

all buffers of Buffer Manager are available

there are no other operations that concurrently claim the space

Bag Union

no need to remove duplicates

for this operation just need to use one buffer block

load elements to the block and then just output

Cost

B(R)+B(S)

we don't count output

Must have some available buffers: M⩾1

Set Union

this time we care about duplicates

assume that R is smaller than S

One-Pass Set Union

R fits into memory:

We assume that we have B(R)+1 available buffers

i.e. R can fit into memory and after that there's at least one remaining available buffer

Idea:

load all elements of R

using 1 extra buffer go through all blocks of S

output element if only it's not in R

Algorithm

load R to N1,...,NB(R) buffers

for each tuple tR∈∪iNi

output tR

for each block BS∈S

load BS to N0

for each tuple tS∈N0

if tS∉∪iNi, output tS

Cost

B(R)+B(S)

pass once through R and once through S

we ignore the cost of searching in memory - interested only in I/O cost

Problem:

We can do it only when one of the relations fin into memory

usually they don't fit!

Page 2

Sort-Based Set Union

what if there's no enough memory available?

Algorithm:

Sort R with External Merge Sort

Sort S with External Merge Sort

Iterate Synchronously over R and S

like in External Merge Sort, but don't output repeating values

i.e.: increase both pointers when see a duplicate

Synchronous Iteration:

load block of R to NR, block of S to NS

iterate over tuples tR∈NR and tS∈NS synchronously

if tR<tS

output tR

move tR pointer to the next tuple in R (load next block if needed)

if tR>tS

output tS

move tS pointer to the next tuple in S (load next block if needed)

if tR=tS

output tS

move both tR and tS

Cost:

2B(R)⌈logMB(R)⌉: cost of sorting R

2B(S)⌈logMB(S)⌉: cost of sorting S

B(R)+B(S) to iterate synchronously to output the results