Query

Query Execution

The cost of query execution is dominated by the cost to do Disk I/Os. Therefore, when calculating the cost of executing a physical query plan, we usually count the size of blocks being written to or read from the disk. There are three main types of algorithms:

1. Sorting based
2. Hash based
3. Index based

Nested Loop Join and Fundamental Operations

This is the most native and intuitive way to join. To join R and S, we simply iterate through tuples inside each relation. (i.e. For each tuple in S, iterate tuples in R). This result of this is \(O(n^{2})\). There are however, some optimizations which can make it more efficient either by repeating less in each iteration or leverage Disk I/O's bulk I/O chracteristics.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Tuple:
    pass

class Relation:
    pass

for s: Tuple in S: Relation:
    for r: Tuple in S: Relation:
        if condition(r, s):
            return t = r join s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# if B(S) <= B(R) and B(S) > M

class Block:
    pass

class Tuple:
    pass

class Relation:
    pass


for chunk: List[Block] in S: Relation:

    read_chunk_into_main_memory_buffer()
    organize_tuples_in_chunk_into_datastructure_with_searchkey_as_common_attributed_for_R_and_S

    for b: Block in R: Relation:

        read_b_into_main_memory_buffer()

        for r: Tuple in b:

            result = find_tuples_in_chunk_that_joins_with_r()

            return result

Sorting Algorithms

One Pass

This is pretty trivial, if your memory can fit all tuples of both Relations, you can simply use any sorting alrogithm we've learned in the past.

Two Pass

|

Hashing Algorithms

Two Pass

One Pass Algorithms

Unary Tuple at a Time Operation

• Operation(s): \(\sigma\) and \(\pi\)
• Spatial Cost: 1
• Disk I/O Cost: \(B(R)\)

Unary Full Relation Operation

• Operation(s): \(\delta\) and \(\gamma\)
• Sptial Cost: M - 1
• Sptial Requirement: \(B(\delta(R)) \le M\)
• Disk I/O Cost: \(B(R)\)

Binary Full Relation Operation

• Operation(s): \(\cup, \cap, -, \times, \Join\)
• Spatial Cost:

Relational Algebra

Fundamentals

Commutativity and Associativity

Selection Pushdown

Selection can significantly reduce the size of necessary Disk I/O, and hence improves the performance of a database query. Pushing selection down the tree means that we can reduce the number of tuples in our relation before executing other operators. Therefore, it is almost always right to push selection (\(\sigma\)) down the tree as far as possible. There are, however, some scenarios where first bringing the selection up the tree, then pushing it down the tree can improve query performance.

Projection Pushdown

As described in the textbook, projection does not reduce the number of tuples, but rather the length of tuples. In fact, extended project actually increase the length of a tuple.

Duplicate Elimination Pushdown

• \(\delta(R \times S) = \delta(R) \times \delta(S)\)
• \(\delta(R \Join S) = \delta(R) \Join \delta(S)\)
• \(\delta(R \Join_{C} S) = \delta(R) \Join_{C} \delta(S)\)
• \(\delta(\sigma_{C}(R)) = \sigma_{C}(\delta(R))\)
• 🇧\(\delta(R \cap S) = \delta(R) \cap S = R \cap \delta(S) = \delta(R) \cap \delta(S)\)

Join → Cartesian Product

• \(R \Join S = \pi_{L}(\sigma_{C}(R \times S))\)
• \(R \Join_{C} S = \sigma_{C}(R \times S)\)

Grouping & Aggregation

Grouping is not affected by duplicate elimination if the given aggregation function is \(min() or max()\). Group is however, affected by by duplicate elimination if the given aggregation function is \(avg(), count(), sum(), etc...\)

Operational Cost

The goal is to estimate the cost of execution a query plan as accurately as possible without actually executing it.

The value of V(A, R) is being preserved as we traverse the logical query planning tree in a bottom-up fashion.

Selection

Join

\(T(R \Join S) = \frac{T(R)T(S)}{max(V(R,A), V(S,A))}\)

The intuition behind this is that we take the cost of a cartesian product then multiple it by the probability that R and S share a common value in attribute A.

Other Operations

Pipelining and Materialization

Physical query planning tree can be generated by following steps:

1. Break the tree into subtress at each edge that represents materialization which will be executed one at a time.
2. Order the execution of the subtrees in a buttom-up, left-to-right manner.
3. Execute all nodes of each subtree using a network of iterators. All nodes should be executed simultaneously.