Elmasri R., Navathe S.B. Fundamentals of Database Systems

Подождите немного. Документ загружается.

672 Chapter 18 Indexing Structures for Files

Exercises

18.18. Consider a disk with block size B = 512 bytes. A block pointer is P = 6 bytes

long, and a record pointer is P

= 7 bytes long. A file has r = 30,000

EMPLOYEE records of fixed length. Each record has the following fields: Name

(30 bytes), Ssn (9 bytes), Department_code (9 bytes), Address (40 bytes),

Phone (10 bytes), Birth_date (8 bytes), Sex (1 byte), Job_code (4 bytes), and

Salary (4 bytes, real number). An additional byte is used as a deletion marker.

a. Calculate the record size R in bytes.

b. Calculate the blocking factor bfr and the number of file blocks b, assum-

ing an unspanned organization.

c. Suppose that the file is ordered by the key field Ssn and we want to con-

struct a primary index on

Ssn. Calculate (i) the index blocking factor bfr

(which is also the index fan-out fo); (ii) the number of first-level index

entries and the number of first-level index blocks; (iii) the number of lev-

els needed if we make it into a multilevel index; (iv) the total number of

blocks required by the multilevel index; and (v) the number of block

accesses needed to search for and retrieve a record from the file—given its

Ssn value—using the primary index.

d. Suppose that the file is not ordered by the key field Ssn and we want to

construct a secondary index on

Ssn. Repeat the previous exercise (part c)

for the secondary index and compare with the primary index.

e. Suppose that the file is not ordered by the nonkey field Department_code

and we want to construct a secondary index on Department_code, using

option 3 of Section 18.1.3, with an extra level of indirection that stores

record pointers. Assume there are 1,000 distinct values of

Department_code and that the EMPLOYEE records are evenly distributed

among these values. Calculate (i) the index blocking factor bfr

(which is

also the index fan-out fo); (ii) the number of blocks needed by the level of

indirection that stores record pointers; (iii) the number of first-level

index entries and the number of first-level index blocks; (iv) the number

of levels needed if we make it into a multilevel index; (v) the total number

of blocks required by the multilevel index and the blocks used in the extra

level of indirection; and (vi) the approximate number of block accesses

needed to search for and retrieve all records in the file that have a specific

Department_code value, using the index.

f. Suppose that the file is ordered by the nonkey field Department_code and

we want to construct a clustering index on

Department_code that uses

block anchors (every new value of

Department_code starts at the beginning

of a new block). Assume there are 1,000 distinct values of

Department_code and that the EMPLOYEE records are evenly distributed

among these values. Calculate (i) the index blocking factor bfr

(which is

also the index fan-out fo); (ii) the number of first-level index entries and

the number of first-level index blocks; (iii) the number of levels needed if

we make it into a multilevel index; (iv) the total number of blocks

Exercises 673

required by the multilevel index; and (v) the number of block accesses

needed to search for and retrieve all records in the file that have a specific

Department_code value, using the clustering index (assume that multiple

blocks in a cluster are contiguous).

g. Suppose that the file is not ordered by the key field Ssn and we want to

construct a B

-tree access structure (index) on Ssn. Calculate (i) the

orders p and p

leaf

of the B

-tree; (ii) the number of leaf-level blocks

needed if blocks are approximately 69 percent full (rounded up for con-

venience); (iii) the number of levels needed if internal nodes are also 69

percent full (rounded up for convenience); (iv) the total number of blocks

required by the B

-tree; and (v) the number of block accesses needed to

search for and retrieve a record from the file—given its

Ssn value—using

the B

-tree.

h. Repeat part g, but for a B-tree rather than for a B

-tree. Compare your

results for the B-tree and for the B

-tree.

18.19. A PARTS file with Part# as the key field includes records with the following

Part# values: 23, 65, 37, 60, 46, 92, 48, 71, 56, 59, 18, 21, 10, 74, 78, 15, 16, 20,

24, 28, 39, 43, 47, 50, 69, 75, 8, 49, 33, 38. Suppose that the search field values

are inserted in the given order in a B

-tree of order p = 4 and p

leaf

= 3; show

how the tree will expand and what the final tree will look like.

18.20. Repeat Exercise 18.19, but use a B-tree of order p = 4 instead of a B

-tree.

18.21. Suppose that the following search field values are deleted, in the given order,

from the B

-tree of Exercise 18.19; show how the tree will shrink and show

the final tree. The deleted values are 65, 75, 43, 18, 20, 92, 59, 37.

18.22. Repeat Exercise 18.21, but for the B-tree of Exercise 18.20.

18.23. Algorithm 18.1 outlines the procedure for searching a nondense multilevel

primary index to retrieve a file record. Adapt the algorithm for each of the

following cases:

a. A multilevel secondary index on a nonkey nonordering field of a file.

Assume that option 3 of Section 18.1.3 is used, where an extra level of

indirection stores pointers to the individual records with the corres-

ponding index field value.

b. A multilevel secondary index on a nonordering key field of a file.

c. A multilevel clustering index on a nonkey ordering field of a file.

18.24. Suppose that several secondary indexes exist on nonkey fields of a file,

implemented using option 3 of Section 18.1.3; for example, we could have

secondary indexes on the fields

Department_code, Job_code, and Salary of the

EMPLOYEE file of Exercise 18.18. Describe an efficient way to search for and

retrieve records satisfying a complex selection condition on these fields, such

as (

Department_code = 5 AND Job_code = 12 AND Salary = 50,000), using the

record pointers in the indirection level.

674 Chapter 18 Indexing Structures for Files

18.25.

Adapt Algorithms 18.2 and 18.3, which outline search and insertion proce-

dures for a B

-tree, to a B-tree.

18.26. It is possible to modify the B

-tree insertion algorithm to delay the case

where a new level is produced by checking for a possible redistribution of val-

ues among the leaf nodes. Figure 18.17 (next page) illustrates how this could

be done for our example in Figure 18.12; rather than splitting the leftmost

leaf node when 12 is inserted, we do a left redistribution by moving 7 to the

leaf node to its left (if there is space in this node). Figure 18.17 shows how

the tree would look when redistribution is considered. It is also possible to

consider right redistribution. Try to modify the B

-tree insertion algorithm

to take redistribution into account.

18.27. Outline an algorithm for deletion from a B

-tree.

18.28. Repeat Exercise 18.27 for a B-tree.

Selected Bibliography

Bayer and McCreight (1972) introduced B-trees and associated algorithms. Comer

(1979) provides an excellent survey of B-trees and their history, and variations of B-

trees. Knuth (1998) provides detailed analysis of many search techniques, including

B-trees and some of their variations. Nievergelt (1974) discusses the use of binary

search trees for file organization. Textbooks on file structures including Claybrook

(1992), Smith and Barnes (1987), and Salzberg (1988), the algorithms and data

structures textbook by Wirth (1985), as well as the database textbook by

Ramakrihnan and Gehrke (2003) discuss indexing in detail and may be consulted

for search, insertion, and deletion algorithms for B-trees and B

-trees. Larson

(1981) analyzes index-sequential files, and Held and Stonebraker (1978) compare

static multilevel indexes with B-tree dynamic indexes. Lehman and Yao (1981) and

Srinivasan and Carey (1991) did further analysis of concurrent access to B-trees.

The books by Wiederhold (1987), Smith and Barnes (1987), and Salzberg (1988),

among others, discuss many of the search techniques described in this chapter. Grid

files are introduced in Nievergelt et al. (1984). Partial-match retrieval, which uses

partitioned hashing, is discussed in Burkhard (1976, 1979).

New techniques and applications of indexes and B

-trees are discussed in Lanka

and Mays (1991), Zobel et al. (1992), and Faloutsos and Jagadish (1992). Mohan

and Narang (1992) discuss index creation. The performance of various B–tree and

-tree algorithms is assessed in Baeza-Yates and Larson (1989) and Johnson and

Shasha (1993). Buffer management for indexes is discussed in Chan et al. (1992).

Column-based storage of databases was proposed by Stonebraker et al. (2005) in the

C-Store database system; MonetDB/X100 by Boncz et al. (2008) is another imple-

mentation of the idea. Abadi et al. (2008) discuss the advantages of column stores

over row-stored databases for read-only database applications.

Selected Bibliography 675

10 30 50 70 80

Insert 12: overflow (left

redistribution)

Insert 9: overflow (new level)

Insert 6: overflow (split)

10 30 50 70 80 12 0

10 30 50 70 80 90 12 0

12 0

3 9

10 30 50 60 70 80 90

36 9

Figure 18.17

-tree insertion with left redistribution.

This page intentionally left blank

Query Processing and

Optimization, and

Database Tuning

part 8

This page intentionally left blank

679

Algorithms for Query

Processing and Optimization

n this chapter we discuss the techniques used inter-

nally by a DBMS to process, optimize, and execute

high-level queries. A query expressed in a high-level query language such as SQL

must first be scanned, parsed, and validated.

The scanner identifies the query

tokens—such as SQL keywords, attribute names, and relation names—that appear

in the text of the query, whereas the parser checks the query syntax to determine

whether it is formulated according to the syntax rules (rules of grammar) of the

query language. The query must also be validated by checking that all attribute and

relation names are valid and semantically meaningful names in the schema of the

particular database being queried. An internal representation of the query is then

created, usually as a tree data structure called a query tree. It is also possible to rep-

resent the query using a graph data structure called a query graph. The DBMS must

then devise an execution strategy or query plan for retrieving the results of the

query from the database files. A query typically has many possible execution strate-

gies, and the process of choosing a suitable one for processing a query is known as

query optimization.

Figure 19.1 shows the different steps of processing a high-level query. The query

optimizer module has the task of producing a good execution plan, and the code

generator generates the code to execute that plan. The runtime database processor

has the task of running (executing) the query code, whether in compiled or inter-

preted mode, to produce the query result. If a runtime error results, an error mes-

sage is generated by the runtime database processor.

chapter 19

We will not discuss the parsing and syntax-checking phase of query processing here; this material is

discussed in compiler textbooks.

680 Chapter 19 Algorithms for Query Processing and Optimization

The term optimization is actually a misnomer because in some cases the chosen exe-

cution plan is not the optimal (or absolute best) strategy—it is just a reasonably effi-

cient strategy for executing the query. Finding the optimal strategy is usually too

time-consuming—except for the simplest of queries. In addition, trying to find the

optimal query execution strategy may require detailed information on how the files

are implemented and even on the contents of the files—information that may not

be fully available in the DBMS catalog. Hence, planning of a good execution strategy

may be a more accurate description than query optimization.

For lower-level navigational database languages in legacy systems—such as the net-

work DML or the hierarchical DL/1 (see Section 2.6)—the programmer must

choose the query execution strategy while writing a database program. If a DBMS

provides only a navigational language, there is limited need or opportunity for exten-

sive query optimization by the DBMS; instead, the programmer is given the capabil-

ity to choose the query execution strategy. On the other hand, a high-level query

language—such as SQL for relational DBMSs (RDBMSs) or OQL (see Chapter 11)

for object DBMSs (ODBMSs)—is more declarative in nature because it specifies

what the intended results of the query are, rather than identifying the details of how

the result should be obtained. Query optimization is thus necessary for queries that

are specified in a high-level query language.

We will concentrate on describing query optimization in the context of an RDBMS

because many of the techniques we describe have also been adapted for other types

Query in a high-level language

Scanning, parsing, and validating

Immediate form of query

Query optimizer

Execution plan

Query code generator

Code to execute the query

Runtime database processor

Code can be:

Executed directly (interpreted mode)

Stored and executed later whenever

needed (compiled mode)

Result of query

Figure 19.1

Typical steps when

processing a high-level

query.

19.1 Translating SQL Queries into Relational Algebra 681

There are some query optimization problems and techniques that are pertinent only to ODBMSs.

However, we do not discuss them here because we give only an introduction to query optimization.

of database management systems, such as ODBMSs.

A relational DBMS must sys-

tematically evaluate alternative query execution strategies and choose a reasonably

efficient or near-optimal strategy. Each DBMS typically has a number of general

database access algorithms that implement relational algebra operations such as

SELECT or JOIN (see Chapter 6) or combinations of these operations. Only execu-

tion strategies that can be implemented by the DBMS access algorithms and that

apply to the particular query, as well as to the particular physical database design, can

be considered by the query optimization module.

This chapter starts with a general discussion of how SQL queries are typically trans-

lated into relational algebra queries and then optimized in Section 19.1. Then we

discuss algorithms for implementing relational algebra operations in Sections 19.2

through 19.6. Following this, we give an overview of query optimization strategies.

There are two main techniques that are employed during query optimization. The

first technique is based on heuristic rules for ordering the operations in a query

execution strategy. A heuristic is a rule that works well in most cases but is not guar-

anteed to work well in every case. The rules typically reorder the operations in a

query tree. The second technique involves systematically estimating the cost of dif-

ferent execution strategies and choosing the execution plan with the lowest cost esti-

mate. These techniques are usually combined in a query optimizer. We discuss

heuristic optimization in Section 19.7 and cost estimation in Section 19.8. Then we

provide a brief overview of the factors considered during query optimization in the

Oracle commercial RDBMS in Section 19.9. Section 19.10 introduces the topic of

semantic query optimization, in which known constraints are used as an aid to

devising efficient query execution strategies.

The topics covered in this chapter require that the reader be familiar with the mate-

rial presented in several earlier chapters. In particular, the chapters on SQL

(Chapters 4 and 5), relational algebra (Chapter 6), and file structures and indexing

(Chapters 17 and 18) are a prerequisite to this chapter. Also, it is important to note

that the topic of query processing and optimization is vast, and we can only give an

introduction to the basic principles and techniques in this chapter.

19.1 Translating SQL Queries into Relational

Algebra

In practice, SQL is the query language that is used in most commercial RDBMSs. An

SQL query is first translated into an equivalent extended relational algebra expres-

sion—represented as a query tree data structure—that is then optimized. Typically,

SQL queries are decomposed into query blocks, which form the basic units that can

be translated into the algebraic operators and optimized. A query block contains a

single

SELECT-FROM-WHERE expression, as well as GROUP BY and HAVING clauses

if these are part of the block. Hence, nested queries within a query are identified as