Final

Question 1

Linear Search (A1) Cost

Answer 1

b_r + t_S
One initial seek
b_r block transfers, where b_r is the number of blocks in a file

Question 2

Linear Search (A1) Cost, Equality on Key Average Case.

Answer 2

t_s+ (b_r/2). Average case, scan can be terminated as soon as a record is found.

Question 3

Primary B+-tree Index search, Equality on Key (A2)

Answer 3

(h_i + 1) * t_T
h_i - tree height.
Index traverses tree height and 1 I/O to fetch the record.

Question 4

Primary B+-tree Index, Equality on Nonkey (A3)

Answer 4

h_i * t_T + b * t_T
Height of the tree and then however many blocks we get

Question 5

SQL Query Processor Steps

Answer 5

Parser -> Translator -> Optimizer -> Evaluator -> Query Output

Question 6

Predominant Cost in Evaluation

Answer 6

Disk Access

Question 7

t_T

Answer 7

Time to transfer one block

Question 8

t_S

Answer 8

Time for one seek

Question 9

Generic Cost Algorithm

Answer 9

bt_T + St_S

Question 10

b_r

Answer 10

Number of blocks containing records from relation r

Question 11

Secondary Index, Equality on Key (A4)

Answer 11

(h_i+1)*t_t

Question 12

TF: Index Scans are Search Algorithms

Answer 12

True

Question 13

b

Answer 13

Blocks with records with the specified search key

Question 14

Secondary Index, Equality on Nonkey (A4)

Answer 14

(h_i + n) * t_T

Question 15

Primary Index Comparison (A5)

Answer 15

h_i*t_T + b * t_T
Less than: Start at first tuple and scan until end
Greater than: Use index to find first tuple and scan onwards

Question 16

Secondary Index Comparison (A6)

Answer 16

(h_i+n) * t_T
Same as A5 but you’re finding pointers to records
Linear file scan might be cheaper

Question 17

Conjunctive Selection with One Index (A7)

Answer 17

Select algos in A1-7 for lowest cost

Question 18

Composite Index Matching with Tree Indexes

Answer 18

Involves attributes in prefix of search key. Ex, given a,b,c.
a=1, b=2 is good
a=1, c=3 is bad

Question 19

Composite Index Matching with Hash Indexes

Answer 19

every term must have a value, order does not matter

Question 20

Disjunctive Selection (A10)

Answer 20

Can use if all conditions have indices, else use Linear Scan

Question 21

Negation

Answer 21

Use linear scan

Question 22

Nested Loop Algorithm

Answer 22

for t in t_r
for u in t_s
if cond(t,u); then add to result

Question 23

Nested Loop Cost

Answer 23

n_r * b_s + b_r

Question 24

Nested Loop Cost if inner relation fits in memory

Answer 24

b_r + b_s

Question 25

Block Nested Loop Cost

Answer 25

b_r * b_s + b_r

Question 26

Improved Block Nested Loop Cost

Answer 26

[b_r / (M-2)] * b_s + b_r
3 partitions of M needed for outer, inner, and output

Question 27

TF: In a block nested-loop join, if equi-join attribute forms a key on the inner relation, stop the inner loop on the first match

Answer 27

True

Question 28

Index Nested-Loop Join Conditions

Answer 28

Join is equi or natural join
Index is available on inner relation’s join attribute

Question 29

Index Nested-Loop Join Process

Answer 29

For each tuple in t_r, use the index to look up tuples in s that satisfy the outer join condition

Question 30

Index Nested-Loop Join Process Worst Case

Answer 30

Buffer has space for one page of r and for each tuple in r, we do an index lookup on s
b_r + n_r * c
c = cost of fetching all matching s tuples for r. Cost of a single selection on s using the join condition.

Question 31

TF: If indices are available on join attributes on r and s, use the relation with fewer tuples as the inner relation

Answer 31

False, as the outer

Question 32

Merge-Join Conditions

Answer 32

Join is equi or natural join. If R and S are sorted, then join can be computed in a similar manner as the merge-sort algo

Question 33

Merge-Join Cost

Answer 33

b_r + b_s + sort cost
Worst Case Sort: M log M + N log N

Question 34

Hybrid Merge Join Process

Answer 34

One relation is sorted, and the other is unsorted but has a secondary index on the join attribute. Merge sorted relation with leaf entries of the secondary index

Question 35

Hash Join Process

Answer 35

Partition s using hash function h, reserving 1 block of memory as the output buffer for each partition
Do the same with r
for each i:
- load s_i into memory
- build an in-memory hash index on s_i using the join attribute and a different h
- Read tuples from r_i one by one
- Find the matching s_i using the hash index

Question 36

Hash Join Build Input

Answer 36

Used to build in-memory hash index (s)

Question 37

Hash Join Probe Input

Answer 37

Used to find matches of in-built index (r)

Question 38

When is recursive partitioning needed in the hash join?

Answer 38

When n_h + 1 >= M
Also sqrt(b_s) >= M

Question 39

When does hash table overflow occur?

Answer 39

If hash index on s_i is larger than main memory

Question 40

When is hash table overflow common?

Answer 40

• Many tuples in s with same join value. This can be subverted with block nested loop join
• Bad hash function

Question 41

Hash Join Cost

Answer 41

3(b_r + b_s). Just b_r + b_s if build input can be kept in memory.

Question 42

Hybrid Hash Join

Answer 42

Keeps first partition of build relation in memory. Most useful when M is much greater than sqrt(b_s)

Question 43

Joins with a conjunctive / disjunctive condition

Answer 43

Nested block joins

Question 44

Duplicate elimination

Answer 44

Sorting - next to each other
Hashing - in same bucket

Question 45

TF: Secondary indices must always be dense

Answer 45

True

Question 46

Difference between primary and secondary indices

Answer 46

Primary stored in sequential order, secondary are not

Question 47

TF: The Result of an SQL statement is always a relation

Answer 47

True

Question 48

Cost of External File Sort

Answer 48

2N*passes, where N is the number of pages

Question 49

Runs in first pas of external file sort

Answer 49

N/B, where N is the number of pages, and B is the number of available buffer pages

Question 50

Number of passes needed to sort a file completely

Answer 50

1+ceil(log(N/B,B-1))