3. Query Processing

Question 1

Disk cost can be estimated as:

1. Number of ___ * average-___
2. Number of ___ * average-___
3. – Number of ___ * average-___

Answer 1

1. Seeks / seek-cost
2. Blocks Read / block-read-cost
3. Blocks Written / block-write-cost

Question 2

In the File Scan Selection Operation we scan each ___ and test all records to see whether ___

Answer 2

File block

They satisfy the selection condition

Question 3

The cost estimate for the File Scap operation (A1 - ___ search) = number of ___ + 1 ___

Answer 3

Linear search
Block transfers
Seek

Question 4

In the Index Scan we use a ___ on the index ___

Answer 4

Condition

Search-Key

Question 5

A2 (clustered index, equality on key) Retrieves ___ that satisfies the corresponding equality condition

Answer 5

A single record

Question 6

A3 (clustered index, equality on non-key) Retrieves ___

Answer 6

Multiple records

Question 7

A4 (non-clustered index, equality on key/non-key) Retrieves ___ if the search-key is a ___ key
OR Retrieves ___ if it is not

Answer 7

A single Record
Candidate
Multiple records

Question 8

Selections Involving Comparisons can use both ___ Scans and ___ Scans

Answer 8

File

Index

Question 9

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
___

Answer 9

1. Index / First / Sequentially

2. Sequentially / First / Index

Question 10

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
___

Answer 10

1. Index / First / Sequentially

2. Leaf / Sequentially / First / Index

Question 11

A7 (conjunctive selection using one index) uses a combination of ___ to ___ that results in the least ___ possible

Answer 11

A1
A6
Cost

Question 12

A8 (conjunctive selection using composite index) uses appropriate ___ (___) index if available

Answer 12

Composite (multi-key)

Question 13

A9 (conjunctive selection by intersection of identifiers) Requires indices with ___
Use corresponding index for each condition, and take ___ of all the obtained sets of ___

Answer 13

Record pointers
Intersection
Record pointers

Question 14

A10 (disjunctive selection by union of identifiers) Requires ___
Use corresponding index for each condition and take ___ of all the obtained set of ___

Answer 14

Indexes
Union
Record pointers

Question 15

The External Sort merge algorithm works by:

1. ___ into ___ of N blocks
2. Sort ___ and then merge them ___ at a time until obtaining ___ output

Answer 15

1. Divide / Groups

2. Groups / Two / Sorted

Question 16

Nested-Loop Join cost is ___ since it examines every ___ in the two
___

Answer 16

Expensive
Pair of tuples
Relations

Question 17

Block Nested-Loop Join reads each ___ in the ___ relation s once for each ___ in the ___ relation

Answer 17

Block
Inner
Block
Outer

Question 18

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

Answer 18

Tuple
Index
Tuples
Join

Question 19

Merge-Join

Each ___ needs to be read only once (assuming all ___ for any given ___ of the join attributes fit in memory)

Answer 19

Block
Tuples
Value

Question 20

Hash-Join

Read and write every ___ and compare the ___ in the ___ by reading them once more

Answer 20

Block
Tuples
Partitions

Question 21

Materialized evaluation: evaluate one ___ at a time, starting at the ___-___. Use intermediate results
materialized into ___ to evaluate next-level
operations.

Answer 21

Operation
Lowest-level
Temporary Relations

Question 22

Pipelined evaluation: evaluate several operations

___, passing the results of ___ to the ___.

Answer 22

Simultaneously
One operation
Next

Question 23

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 ___

Answer 23

Cheaper
No need
temporary relation
Sort and Hash-Join