Query processing: list the steps in order.
Parsing and translation; query optimization; evaluation.
What does the parser do in the first step?
It checks syntax and semantic, verifies relations, and translates the query into its relational algebra form.
What is query optimization?
The process of choosing a suitable execution strategy for processing a query: amongst all equivalent evaluation plans, choose the one with lowest cost.
What is an evaluation-plan?
An annotated relational algebra expression that specifies a detailed evaluation strategy.
How is query cost measured, and why?
By the number of block transfers from disk — disk access is typically the predominant cost and is relatively easy to estimate.
What is a query block?
The basic unit that can be translated into algebraic operators and optimized: a single SELECT-FROM-WHERE expression, plus GROUP BY and HAVING if part of the block. Nested queries are separate query blocks.
What is external sorting, and which algorithm suits it?
Sorting large files stored on disk that do not fit entirely in main memory; merge sort is a good choice.
Merge sort sorting phase: how many initial runs, and at what cost?
nR = ⌈b/nB⌉ runs (b = file blocks, nB = buffer pages); cost = read b + write b = 2b.
What is the degree of merging dM, and why nB − 1?
dM = min(nB − 1, nR): one buffer block holds a block from each run being merged, and one block is needed for the merged result.
Number of merge passes and total merge-sort cost.
nP = ⌈log_dM(nR)⌉; Cost = 2b + 2b × nP = 2b (⌈log_dM(nR)⌉ + 1).
External merge sort: b = 10,000, nB = 3. Runs, passes and total I/O?
nR = 3334; dM = 2; nP = 12 passes; total I/O = 2 × 10000 × 13 = 260,000.
What do r, R, b and bfr mean in catalog information?
r = # of records in the file; R = record size; b = # of blocks in the file; bfr = blocking factor.
Define selectivity (sl) and selection cardinality (s).
sl = the ratio of the # of records satisfying the condition to the total # of records; s = sl × r = average # of records that satisfy an equality condition on the attribute.
sl and s for a key attribute vs a nonkey attribute.
Key: d = r, sl = 1/r, s = 1. Nonkey (uniform): sl = 1/d, s = r/d.
File scan vs index scan.
File scan: search algorithms that locate and retrieve records fulfilling a selection condition. Index scan: search algorithms that use an index (the condition must be on the index search-key). Cost C = # of disk blocks scanned.
S1 linear search cost: nonkey attribute vs equality on a key.
Nonkey: C = b. Key equality: C = b/2 on average if found, else C = b.
When can S2 binary search be used, and what does it cost?
For an equality comparison on the attribute on which the file is ordered (blocks stored contiguously); C = ⌈log2 b⌉.
S3 cost with a primary index vs a hash index.
Primary index: C = x + 1 (one more block than the # of index levels). Hash index: C = 1 for static or linear hashing, C = 2 for extendable hashing.
S4 and S5 costs.
S4 (primary index on a key, range): average C = x + b/2. S5 (clustered index on nonkey, equality): C = x + ⌈s/bfr⌉.
S9 vs S10.
S9 (conjunctive): intersection of the record-pointer sets from each condition's index. S10 (disjunctive): union of the pointer sets — only if all conditions have indices, otherwise linear scan.
How does S7 handle a conjunctive selection with one index?
Choose the condition and algorithm (S1–S6) with the least cost for σ θi (r), then test the other conditions on each tuple after fetching it into the memory buffer.
What is materialized evaluation?
Evaluating one operation at a time, starting at the lowest level, and storing intermediate results in temporary relations used for the next-level operations.
What is pipelined evaluation, and why is it cheaper?
Several operations are evaluated simultaneously, each passing its results to the next without waiting (stream-based processing). It is much cheaper because no temporary relation is stored to disk.
Give two operations for which pipelining may not be possible.
Sort and hash-join.
Which factors affect join performance?
Available buffer space and the choice of inner vs outer relation.
Nested-loop join: advantages and disadvantage.
Requires no indices and can be used with any kind of join condition; but it is expensive since it examines every pair of tuples in the two relations.
Nested-loop join: worst-case cost, and which relation should be inner if one fits in memory?
Worst case: C = bR + (rR × bS) + bRS. If the smaller relation fits entirely in memory, use it as the inner relation: bR + bS + bRS.
Block nested-loop join: how does it work and what is its worst-case cost?
Every block of the inner relation is paired with every block of the outer relation. Worst case: C = bR + (bR × bS) + bRS. If neither fits in memory, choose the smaller relation for the outer loop.
When can an indexed nested-loop join be used, and which relation is outer if both have indices?
When an index is available on the inner relation's join attribute (or one is built for the join). If both have indices, use the relation with fewer tuples as the outer.
depositor (5,000 records, 100 blocks) ⋈ customer (400 blocks; primary B+-tree index on the join attribute, 4 levels): block nested loops vs indexed nested loops cost?
Block nested loops: 100 + 100 × 400 = 40,100. Indexed (primary B+-tree, 4 levels + 1 data access = 5): 100 + 5000 × 5 = 25,100 (each + bRS).
Sort-merge join: steps and restriction.
Sort both relations on the join attribute (if not sorted), then merge them, matching every pair with the same join value. Can be used only for equi-joins and natural joins.
How many block accesses does a merge-join need?
bR + bS + sorting cost (if not sorted) + bRS — each block needs to be read only once.