3. Query Processing Flashcards
Disk cost can be estimated as:
- Number of ___ * average-___
- Number of ___ * average-___
- – Number of ___ * average-___
- Seeks / seek-cost
- Blocks Read / block-read-cost
- Blocks Written / block-write-cost
In the File Scan Selection Operation we scan each ___ and test all records to see whether ___
File block
They satisfy the selection condition
The cost estimate for the File Scap operation (A1 - ___ search) = number of ___ + 1 ___
Linear search
Block transfers
Seek
In the Index Scan we use a ___ on the index ___
Condition
Search-Key
A2 (clustered index, equality on key) Retrieves ___ that satisfies the corresponding equality condition
A single record
A3 (clustered index, equality on non-key) Retrieves ___
Multiple records
A4 (non-clustered index, equality on key/non-key) Retrieves ___ if the search-key is a ___ key
OR Retrieves ___ if it is not
A single Record
Candidate
Multiple records
Selections Involving Comparisons can use both ___ Scans and ___ Scans
File
Index
A5 (clustered index, comparison)
1. For sigma A >= V (r) use __ to find ___ tuple >= v and scan relation
___ from there
2. For sigma A <= V (r) just scan relation ___ till ___ tuple > v; do not use
___
- Index / First / Sequentially
2. Sequentially / First / Index
A6 (non-clustered index, comparison)
1. For sigma A >= V (r) use __ to find ___ index entry >= v and scan relation
2. For sigma A <= V (r) 2. For sigma A <= V (r) just scan ___ pages ___ till ___ index entry > v; do not use
___
- Index / First / Sequentially
2. Leaf / Sequentially / First / Index
A7 (conjunctive selection using one index) uses a combination of ___ to ___ that results in the least ___ possible
A1
A6
Cost
A8 (conjunctive selection using composite index) uses appropriate ___ (___) index if available
Composite (multi-key)
A9 (conjunctive selection by intersection of identifiers) Requires indices with ___
Use corresponding index for each condition, and take ___ of all the obtained sets of ___
Record pointers
Intersection
Record pointers
A10 (disjunctive selection by union of identifiers) Requires ___
Use corresponding index for each condition and take ___ of all the obtained set of ___
Indexes
Union
Record pointers
The External Sort merge algorithm works by:
- ___ into ___ of N blocks
- Sort ___ and then merge them ___ at a time until obtaining ___ output
- Divide / Groups
2. Groups / Two / Sorted
Nested-Loop Join cost is ___ since it examines every ___ in the two
___
Expensive
Pair of tuples
Relations
Block Nested-Loop Join reads each ___ in the ___ relation s once for each ___ in the ___ relation
Block
Inner
Block
Outer
Indexed Nested-Loop Join
For each __ tr in the outer relation r, use the ___ to look up ___ in s that satisfy the ___ with tuple tr
Tuple
Index
Tuples
Join
Merge-Join
Each ___ needs to be read only once (assuming all ___ for any given ___ of the join attributes fit in memory)
Block
Tuples
Value
Hash-Join
Read and write every ___ and compare the ___ in the ___ by reading them once more
Block
Tuples
Partitions
Materialized evaluation: evaluate one ___ at a time, starting at the ___-___. Use intermediate results
materialized into ___ to evaluate next-level
operations.
Operation
Lowest-level
Temporary Relations
Pipelined evaluation: evaluate several operations
___, passing the results of ___ to the ___.
Simultaneously
One operation
Next
Pipelined is much ___ than materialization as there is ___ to store a ___ to disk. But sometimes it may not be possible to use it, Ex: ___ and ___
Cheaper
No need
temporary relation
Sort and Hash-Join
