C H A P T E R 1 2
Q
u
e
r
y
P
r
o
c
e
ss
i
n
g
and
Q
u
e
r
y
O
p
t
i
m
i
z
a
t
i
o
n
(
C
h
a
p
t
e
r
s
12 and
13
)
This section contains questions related to Chapters 12 and 13.
E
x
e
r
c
i
s
e
s
12.1 Consider external sorting using replacement selection. What is the minimum,
average, and maximum length of the runs generated? Explain when the mini-
12.2 Suppose you want to compute the join of relations A and B, where A fits in
memory with plenty of space to spare, and B is much larger than memory.
What join technique would you use?
. .
.2
12.3 Very briefly outline how to extend merge-join to compute the full outer natural
join.
. .
.3
12.4 Describe how to compute full outer join by using an extension of the hash join
algorithm.
. .
.4
12.6 Pipelining is used to avoid writing intermediate results to disk. Suppose you
12.7 Explain how to implement A
✶
B using hashing, where A is used as the build
relation.
. .
.6
12.8 Explain how to implement the division operator, using sort-merge. (Recall that
division of
r(A,
B) by s(B) finds values a for which (a, x) is in
r
for every
32 Chapter 12 Query Processing and Query Optimization (Chapters 12 and 13)
12.10 When using the block nested loops join algorithm to join relations A and
B
,
suppose memory has M blocks. How many blocks should be given to A and
how many to B? What is the cost of the algorithm assuming A has
b
a
blocks
b
12.11 Given a materialized view A
✶
B, how would you update it if some tuples are
added to A; let
i
A
denote the tuples added to A.
. .
.3
be
0.8
∗
M blocks.
. .
.2
12.13 What is the cost of finding the best left-deep join order and the cost of finding
the best right-deep join order?
. .
.1
12.14 Suppose you have a query that only wants the first ten results in sorted order
12.15 What is the motivation behind the
optimization
heuristic ”Push selects through
joins”.
. .
.3
12.16 Let
r
and s be relations with the number of blocks in the two being
b
r
and
b
s
respectively.
Assume that there are no indices on the two relations and they are
12.17 For each of the following pairs of queries, indicate under what conditions are
they equivalent (i.e. they return exactly the same answers),
12.18 Give examples to show non-equivalence of the following pairs of
expressions.
Assume the relation schemas are A(X,
Y
), B(X,
Z
) and C(X,
W
)
.
a. A
✶
(B
✶
C) and (A
✶
B)
✶
C?
. . .3
b. A
✶
(B
✶
C) and (A
✶
B)
✶
C?
. . .3
c. A
✶
(B
✶
C) and (A
✶
B)
✶
C? (Hint: consider values common to
A
12.19 Why are the following equivalences incorrect; describe the reason either in
Exercises
33
a.
Π
A
(R − S)
↔
Π
A
(R) −
Π
A
(S).
. . .4
12.20 Consider
select r.A, r.B, r.C from r
12.21 Suppose you have to compute
A
G
s
um
(
C
)
(r)
as well as
A
,
B
G
s
um
(
C
)
(r).
Describe
how to compute these together using a single sorting of
r.
. . .4
12.22 Consider a relation
r(A,
B, C), with an index on attribute A. Give an example
of a query that can
answered
using the index only, without looking at the tuples
in the relation.
. .
.2
12.23 Suppose you want to get answers to
r
✶
s sorted on an attribute of
r,
and
want only the top n answers for some relatively small n. Give a good way of
12.24 Given two SQL queries of the form
select A1,
. . . ,
A
n
from R1,
. . . ,
R
n
where P1
34 Chapter 12 Query Processing and Query Optimization (Chapters 12 and 13)
12.25 Suppose you want to compute the results of all the following queries:
12.26 Suppose you want to compute a groupby on a relation, where you believe the
number of groups is likely to be much smaller than memory, but aren’t 100%
12.27 Suppose you have a huge relation and want to do a groupby and find groups
whose count is greater than 1 percent of the size of the relation. The total num-
12.28 Consider a block nested loop join, where memory has M
+
1 pages. Let the
relations
r
and s have
b
r
and
b
s
pages. Suppose we divide memory as follows:
one page for output,
i
pages for
r
and M −
i
pages for s.
a. What is the cost of block nested loop join of
r
and s, with
r
as the outer
relation.
b. Based on your cost formula, what value of
i
gives the lowest cost.
c. If you could choose which of
r
and s is the outer relation, how would
you
choose it?
. . .8
12.29 Consider a join
r
✶
s, where both
r
and s are pipelined in (that is, they are gen-
erated by other operations, and are piped in a tuple at a time). Let the schemas
12.30 Consider the issue of interesting orders in
optimization.
Given a set of relations
S to be joined, and a subset
S1
of S, what are the interesting orders of
S1? . .
.4
12.31 a. Suppose the number of interesting orders for a query (and each of its inter-
mediate relations) is “d”. Suppose also that there is only one join method
available. Consider a join of 2n relations.
i. What is the number of different left-deep join trees.
. . .2
ii. How many different plans does the System R optimizer actually
exam-
Exercises
35
12.32 a. Suppose the view v
= r
1
✶
r
2
has been materialized (computed and stored),
and now a set of tuples
i
1 is inserted into
r
1
, and
i
2 into
r
2
. As- sume you have
the sets
i
1 and
i
2
,
as well as the contents of relations
r
1 and
r
2
a
f
t
e
r
the insertion.
Give an expression to compute the new tuples to be inserted into the view result
computed earlier, in order to keep the materialized view up to date.
12.33 Suppose you want to build a query optimizer can make use of materialized views.
Disregard selections and projections, and assume queries as well as materialized
12.34 Suppose you are given a relation
e
m
p
(
e
m
p
i
d,
d
e
p
t
,
s
a
l
a
r
y)
and wish to maintain a
materialized view
d
e
p
t
s
a
l
a
r
y(
d
e
p
t
,
t
o
t
a
l
s
a
l
a
r
y)
which stores the total salary for all
employees of each department. Suppose the system does not support mate- rialized
views but supports triggers.
a. Give triggers on insert and delete on
e
m
p
to record changes into
i
n
s
e
r
t
–
d
e
l
t
a
and
d
e
l
e
t
e
–
d
e
l
t
a
relations. Don’t worry about updates.
. .
.6
b. Write a JDBC program to use the tuples in the delta relations to
update