Databases Reference
In-Depth Information
3.2.5 Optimization Depth
Different database products have different search depth, the simplest being greedy
search, but there are usually more advanced dynamic programming-based approaches as
well. Often the search depth is a configurable parameter.
3.3
Query Cost Evaluation—An Example
The example in this section assumes that we have a basic query execution plan to work
with, and focuses on query cost evaluation to minimize I/O time to execute the query
whose plan we are given. It illustrates the benefit of applying well-known query optimi-
zation strategies to a simple real-life problem. Although the problem is elementary, sig-
nificant benefits in query time can still be reached using heuristic rules, and the defini-
tion of those rules can be clearly illustrated.
Let us assume a simple three-table database [Date 2003] with the following materi-
alization of tables: part, supplier, and the intersection table shipment.
Part (P)
Supplier (S)
Shipment (SH)
pnum
pname
wt
snum
sname
city
status
snum
pnum
qty
shipdate
p1
bolt
3
s1
brown
NY
3
s1
p2
50
1-4-90
p2
nail
6
s2
garcia
LA
2
s1
p3
45
2-17-90
p3
nut
2
s3
kinsey
NY
3
s2
p1
100
11-5-89
s2
p3
60
6-30-91
s3
p3
50
8-12-91
Attribute name and size (bytes), and table name and size:
•
supplier: snum(5), sname(20), city(10), status(2) => 37 bytes in one record in
supplier
•
part: pnum(8), pname(10), wt(5) => 23 bytes in one record in part
•
shipment: snum(5), pnum(8), qty(5), shipdate(8) => 26 bytes in one record in
shipment
Note
: Assumed block size (bks) = 15,000 bytes.
3.3.1 Example Query 3.1
“What are the names of parts supplied by suppliers in New York City?” If we translate
the query to SQL we have
SELECT p.pname
FROM P, SH, S
WHERE P.pnum = SH.pnum
