• Logical query plan
• Alegebraic representation of query
• Operators taken from relational algebra
• Is abstract
• Physical query plan
• Algorithms selected for each operator in plan
• Execution order for specific operators

Algorithm that implements one of the basic relational operations that are used in query plans

e.g. Relational algebra has join operator. How the join is carried out depends on >Structure of relations, > Size of relations, > Presence of indexes and hashes, etc

What is the computational model for Pyhsical plan operators?

Need to choose good physical plan operators:

• Estimate "cost" of each operator
• Key measure of cost is the number of disk accesses (far more costly than main memory accesses)

Assumption: arguments of operator are on disk, result is in main memory

M: Main memory available for buffers

S(R): Size of a tuple of relation R

B(R): Blocks used to store relation R

T(R): Number of tuples in relation R (Cardinality of R)

V(R,a): Number of distinct values for attribute a in relation R

1. Tuples from different relations that can be joined (on particular attribute values) stored in blocks together.
• [R1 R2 S1 S2] [R3 R4 S3 S4]
2. Tuples from relation are stored together in blocks, but not necessarily sorted
• [R1 R2 R3 R4] [R5 R6 R7 R8]
3. Index allows tuples to be read in an order that corresponde to physical order

• e.g. Read all tuples of relation R (that satisfy some predicate)
• Two variants
• Table Scan 
• Index Scan

• Tuples arranged in blocks
• All blocks known to the system
• Possible to get blocks one at a time
• I/O Cost
• B(R) disk accesses, if R is clustered
• T(R) disk accesses, if R is not clustered

• An index exists on some attribute of R
• Use index to find all blocks holding R
• Retreive blocks for R
• I/O Cost
• B(R) + B(I_R) disk accesses if clustered
• B(R) >> B(I_R), so treat as only B(R)
• T(R) disk accesses if not clustered

• Read data from disk only once
• Typically require that at least one argument fits in main memory
• Three broad categories:
• Unary, tuple at a time (i.e. select, project)
• Unary, full relation (i.e. duplicate elimination, grouping)
• Binary, full relation

• Algorithm:
• Foreach block of R:
• Copy block to input buffer
• Perform operation (select, project) on each tuple in block
• Move selected/projected tuples to output buffer
• Cost:
• In general, B(R) or T(R) disk accesses depending on clustering
• If operator is a select that compares an attribute to a constant and index exists for attributes used in select, <<B(R) disk accesses

• Algorithm (Normal):
• foreach block of R
• Copy block to input buffer
• update accumulator
• move tuples to output buffer
• Algorithm (Duplicate Elimination)
• foreach block of R:
• copy block to input buffer
• foreach tuple in block
• If tuple is not in accumulator
• copy to output buffer
• else copy to accumulator
• Requires M >= B(d(R))+1 block of main memory
• 1 block for input buffer
• M-1 blocks for accumulator (records each tuple seen so far)
• Accumulator implemented as in-memory data structure (tree, hash)
• If fewer than B(d(R)) blocks available, thrashing likely
• Cost is B(R) disk accesses

Grouping operators: min, max, sum, count, avg

• Accumulator contains per-group values
• Output contains per-group values
• Cost is B(R) disk accesses

Union, intersection, difference, product, join

In general, cost is B(R) + B(S). (R, S are operand relations)

Requirement for one pass operation:

min(B(R), B(S)) < M-1

• Two relations, R(X,Y) and S(Y,Z), B(S)<B(R)
• Uses main memory search structure keyed on Y

• foreach block of S:
• read block
• add tuples to search structure
• foreach block of R:
• copy block to input buffer
• foreach tuple in block:
• Find matching tuples in search structure
• Construct new tuples and copy to output

• Also known as iteration join
• Assumming that we're joining the relations R,S on attribute C, the algorithm is as follows:
• foreach tuple r in R
• foreach tuple s in S
• if r.C = s.C then output r,s pair

• Tuples of a relation stored physically together (clustered)
• Relations sorted by join attribute
• Indexes exist?

• Solve a join between relations R1, R2 on attribute C through a tuple-based nested loop join with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

• Relations not contiguous
• One disk access per tuple
• Cost for each tuple in R1=cost to read tuple + cost to read R2
• Total Cost = 
• T(R1)*(1+T(R2)) =
• 10,000 * (1+5,000) = 
• 50,010,000 disk accesses

It is possible to do better by using all available main memory (M=101), read outer relation R1 in chunks of 100 blocks, and read all inner relation2 (using 1 block) + join

• Solve a join between relations R1, R2 on attribute C through a block-based nested loop join with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

• Cost to read one 100-block chunk of R1 = 100*1/S(R1) = 1,000 disk accesses
• Cost to process each chunk = 1000 + T(R2) = 6,000
• Total cost = T(R1)/ 1000 * 6000 = 60,000 disk accesses

It's possible to do better by reversing the join order ( i.e. R1 becomes the inner relation, R2 becomes the outer relation).

• Solve a join between relations R1, R2 on attribute C through a join reordering with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

• Cost to read one 100-block chunk of R2=100*1/S(R2)=1,000 disk accesses
• Cost to process each chunk = 1000+T(R1) = 11,000
• Total cost = T(R1)/1000*11,000 = 55,000 disk accesses

It's possible to do better if the tuples in each relation are contiugous (i.e. clustered)

• Solve a join between relations R1, R2 on attribute C through Contiguous Relations with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

• B(R1)=1000, B(R2)=500
• Cost to read one 100-block chunk of R2=100 disk accesses
• Cost to process each chunk = 100+B(R1)=1100
• Total cost=B(R2)/100*1,100=5,500 disk accesses

We can do better if both relations are contiguous and sorted by C, the join attribute

• Solve a join between relations R1, R2 on attribute C through a merge join with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

Both relations are contiguous and sorted by C, the join attribute

Total cost = B(R1)+B(R2)=1000+500

= 1,500 disk accesses

Problem is if R1 and R2 aren't sorted by C, as it is needed to sort them.

• Solve a join between relations R1, R2 on attribute C through a Two Pass Algorithm with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

If R1 and R2 are not sorted by C, we need to sort them - this can be done with mergesort:

1. Foreach 100 block chunk of R
1. Read chunk 
2. sort in memory
3. Write to disk
2. Read all chunks + merge + write out

Each tuple is read, written, read, written... so:

• Sort cost R1: 4x1000 = 4,000 disk accesses
• Sort cost R2: 4x500 = 2,000 disk accesses

• Solve a join between relations R1, R2 on attribute C through a Merge Join with sort with the following elements:
• T(R1) = 10,000
• T(R2) = 5,000
• S(R1) = S(R2) = 1/10 block
• M = 101 blocks

• R1,R2 contiguous but usorted:
• Total Cost = sort cost + join cost
• = 6,000 + 1,500
• = 7,500 disk accesses

• Nested loop cost = 5,500 disk accesses
• Merge join does not necessarily pay off

If R1=10,000blocks contiugous

and

R2=5,000blocks not ordered

Nested loop cost = 505,000 disk accesses

Merge join cost = 75,000 disk accesses

In this case merge join with sort is better

Are trees that represent queries visually by breaking them down into components:

SELECT PNUMBER,DNUM,LNAME,ADDRESS,DATE FROM PROJECT,DEPARTMENT, EMPLOYEE WHERE DNUM=DNUMBER AND MGRSSN=SSN AND PLOCATION='Stafford'

[image]

Heuristic approach

1. Start with canonical form
2. Move o operators down the tree
3. Reorder subtrees to put most restrictive o first
4. Combine x and o to form |><|
5. Move pi operators down the tree