Query Optimization and Plan Selection - Physical Database Design - page 36

Finally, we use sequential block accesses (SBA) and random block accesses (RBA) as
estimators for I/O time since there is a linear relationship between SBA or RBA and I/O
time, and I/O time is a generally accepted form of cost comparison in database operations.

Option 1A Cost Estimation: Brute-force Method
of Doing All Joins First, with No Indexes

We summarize the basic sizes of records, counts of records, and counts of blocks
accessed sequentially in the following table. The tables TEMPA, TEMPB, and so on.
are temporary tables formed as the result of intermediate operations during the course
of the query.

Scan Table
(no. Blocks) Ta b l e R o w S i z e No . R o w s B F

supplier (S) 37 bytes 200 405 1

part (P) 23 bytes 100 652 1

shipment (SH) 26 bytes 100K 576 174

TEMPA (S join SH) 58 bytes 100K 258 388

TEMPB (TEMPA join P) 73 bytes 100K 205 488

TEMPC (select TEMPB) 73 bytes 10K 205 49

BF is the blocking factor or rows per block (estimated with average row size).

This approach is detailed below and summarized in Figure 3.1 using the query exe-
cution plan notation of Roussopoulos [1982]. The query execution plan dictates that
the joins are executed first, then the selections. We use merge joins, so no indexes are
used in this option. For each step we first estimate the number of records accessed, then
sequential blocks accesses, then take a sum of SBAs. We assume each table is stored on
disk after each operation and then must be read from disk to do the next operation.

Step 1. Join S and SH over the common column snum forming TEMPA (snum, sname,
city, status, pnum, qty, shipdate) at 58 bytes per row (record). If a sort of a table is
required before executing a merge join, the estimated cost of an M -way sort is
approximately 2

log M nb [O'Neil 2001, Silberschatz 2006] where nb is the
number of blocks (pages) in the table to be sorted. In these examples, M = 3. How-
ever, in this case we don't need to sort SH since table S is very small, less than one
block, so we only need to scan SH and compare in fast memory with one block of S.

×

nb

×

Number of block accesses (step 1)
= read S + read SH + write TEMPA
= ceiling(200/405) + ceiling(100K/576) + ceiling(100K/258)