Query Evaluation & Query Optimization
Ed Knorr, Fall 2020
Chapters 12 & 14 Combined (Part 1 of 2)
Based on:
Ramakrishnan & Gehrke (textbook):
(a) Introduction to Chapter 12 and Sections 12.1 & 12.2 on pages 393-400; (b) Introduction to Chapter 14 and Section 14.1 on pages 439-444; and (c) Sections 14.4-14.4.1 on pages 452-458.
Other Acknowledgements: UBC Database Faculty Members,
Jim Unger’s Herman Treasuries (circa 1980), Database Tuning by Dennis Shasha & Philippe Bonnet (2003)
1
Some Learning Goals
Explain the purpose of a plan in an RDBMS. Explain why many plans are often possible when evaluating a query. Differentiate between good and bad plans.
Justify the use of metadata in estimating the cost of computing relational queries. Explain why the System R model has stood the test of time for query evaluation.
Provide examples of—and explain—how out-of-date catalog statistics can provide horrendous query performance.
Provide examples of when it is faster to read the whole data table in response to a query, rather than use an index.
Explain how access paths relate to query plans.
Given an SQL query, determine the indexes that may apply when evaluating the query, and justify your choice.
2
Some Learning Goals (cont.)
Given an SQL query and a list of indexes, determine an efficient plan for evaluating the query, and justify your choice. List any assumptions behind your reasoning.
Compute the difference that clustering makes when evaluating certain types of queries.
Describe the kinds of queries that utilize a clustering index.
Compute the cost of evaluating a given query using: PNL, BNL, and INL joins.
3
Schemas for Our Examples
(You may wish to bookmark this page.)
Sailors (sid: integer, sname: string, rating: integer, age: real) Reserves (sid: integer, bid: integer, day: date, rname: string)
Sailors has 4+38+4+4 = 50 bytes; Reserves has 4+4+10+22 = 40 bytes
The above schema is similar to our old schema; but, rname (the person who made the reservation) is added.
Sailors: NTuplesS = 40,000; NPagesS = 500 Each tuple is 50 bytes long, 80 tuples per page
Reserves: NTuplesR = 100,000; NPagesR = 1,000 Each tuple is 40 bytes long, 100 tuples per page
4
Relational Algebra, Sample Instances
R1sid bid day 22 101 10/10/96
Flashback to CPSC 304 … Sailors and Reserves
S1
sid sname rating age
Relations
Basic Operations:
22 dustin
7 45.0
Projection Selection Join
Union
31 lubber 58 rusty
8 55.5 10 35.0
Intersection
Set Difference
28 yuppy 31 lubber 44 guppy 58 rusty
9 35.0 8 55.5 5 35.0 10 35.0
S2
sid sname rating age
58 103 11/12/96
5
Projection, Selection, & Join (Review)
sid sname rating age 28 yuppy 9 35.0
sname rating yuppy 9
58
rusty 10 35.0
(S2) rating 8
rusty 10
sid sname rating age bid day
22 dustin 7 45.0 101 10/10/96 58 rusty 10 35.0 103 11/12/96
S1sid R1
( (S2)) sname,rating rating 8
6
Example:
Overview of Query Evaluation
Plan = A tree of relational algebra (RA) operations, with a pre-determined choice of algorithms for the operations.
7
The I/O Cost Model
Two main issues in query optimization:
For a given query, what plans are considered?
• We want an algorithm to search the plan space for the cheapest plan.
How is the cost of a plan estimated?
• Ideally: We want to find the best (cheapest) plan.
• In the I/O cost model, “best” or “cheapest” is the plan that minimizes the number of I/Os.
• Practically: Let’s make sure we avoid the worst plans! • … because often, there are too many plans to consider.
We will study the System R approach (IBM, 1970s), which has stood the test of time.
8
The I/O Cost Model (cont.)
We want the “cheapest” plan.
We want to avoid bad plans.
9
What Access Path Should Be Used to Find the Cheapest Plan for a Query?
Algorithms to evaluate relational operators use some simple ideas extensively:
Indexing: We’ve already seen the benefits of indexing in this course. We can use WHERE-clause conditions to retrieve a single record—or a small set of records—that satisfy conditions in the selection or join (and we’ll informally call this an “index probe”).
• A point query returns at most one record (or part of a record) using an equality selection.
• A multipoint query returns several records based on an equality selection.
• A range query returns a set of records that lie in an interval.
10
Access Paths and Plans (cont.)
Iteration: Sometimes, it’s faster to read the whole data table (“table scan”) even if there is an index!
• But, sometimes we can simply scan all—or some of—the data entries in an index ( “index scan” ) instead of the table to get the answer to our query more quickly.
• Contrast an “index probe” (a few) to an “index scan” (a lot).
Partitioning: By using sorting or hashing, we can partition the input tuples and replace an expensive operation by similar operations on smaller inputs.
• Commonly used for group-by, elimination of duplicates, etc.
• More later
11
SELECT * FROM Sailors;
SELECT sid FROM Sailors;
SELECT count(*) FROM Sailors;
Access Path Examples
(A few of these ideas are a review of our earlier work.)
Suppose we have an Alt. 2 B+ tree index on sid (the PK for table Sailors) and there are 40,000 sailors in the table. What access path (index, table scan, or both) would you use to answer these queries?
12
Access Path Examples (cont.)
Suppose we had an Alt. 2 B+ tree index on sid and there were 40,000 sailors with sid’s (Sailor IDs) in the range 1 to 40,000. What access path would you use for these queries?
SELECT *
FROM Sailors WHERE sid > 39800;
SELECT sid FROM Sailors WHERE sid > 50;
Would your answer to any of the previous questions on these two pages change if you knew: (a) there were 100,000 sailors (and not
40,000), or (b) there were only 2 pages in the data table?
13
Access Path Examples (cont.)
How about these queries?
B+ tree index on: • Rating
SELECT count(*)
• Age
FROM Sailors
WHERE rating = 10 AND • Rating and Age (separately)
age > 30;
SELECT *
B+ tree index on: • Rating
FROM Sailors
WHERE rating = 10 AND age > 30;
• Age
• Rating and Age (separately) • Rating and Age (composite)
• Rating and Age (composite)
14
Access Paths – Tree Indexes
A tree index matches (a conjunction of) terms that involve attributes in a prefix of the search key.
e.g., tree index on
matchesselectiona=5ANDb=3 matchesselectiona=5ANDb>6 but doesn’t match prefix b = 3
a b c rid
However, under what circumstances could you still use the index for b = 3?
120 128 129 141 179 191 3 15 6 535 5 10 0
…………
15
Access Paths – Tree Indexes (cont.)
If we had separate B+ tree indexes for
We can use no indexes, or just one of the indexes (in which case, we’d verify the remaining conditions by fetching the record), or both indexes (in which case, we’d intersect the rid sets).
We could use indexes to handle some disjunctions (OR), too, when it will save I/Os.
16
Access Paths – Hash Indexes
A hash index can be used if it matches the term attribute = value for every attribute in the search key of the index.
e.g., Hash index on
b=3
a = 5 AND b = 3
a > 5 AND b = 3 AND c = 5
17
Access Paths – Hash Indexes (cont.)
If we had separate hash indexes for
18
Statistics and Catalogs (Review)
Metadata about tables, indexes, and other DB objects will be critical for making query optimization decisions.
For each relation (table) or index:
• Cardinality = # tuples (NTuples)
• Size = # pages (NPages)
• Index cardinality = # distinct keys (NKeys)
• Index size = # index pages (i.e., leaves) (NPages)
• Index range = min, max key values (Low, High)
• Index height for tree indexes
• More detailed information is sometimes stored (e.g., histograms of values for some fields may be kept)
Remember: The catalog is updated periodically for most things.
Updating whenever the data changes is often too expensive.
There is a lot of approximation anyway, so minor inconsistency is OK.
19
One Approach to Selections; Selectivity Estimation
Selectivity refers to the number of pages retrieved. Most of the time, we prefer the access path that accesses the fewest pages.
Find the most selective access path, retrieve tuples using it, and apply any remaining terms that don’t match the index:
Most selective access path: an index or table scan that we estimate will require the fewest page I/Os
Terms that match this index reduce: the number of tuples retrieved, and the number of pages retrieved.
Other terms are used to discard some retrieved tuples.
20
One Approach to Selections (cont.)
Example: day < 2009-08-19 AND bid = 5 AND sid = 3
A B+ tree index on day can be used, if it exists; then, bid=5 and sid=3 must be checked for each retrieved tuple (either by simply retrieving and examining the tuple, or we could use an index, if available).
Similarly, a hash index on
Can optimize by dropping unwanted information while sorting
Hashing (or Partitioning) Approach: Hash on
Load partitions into memory one at a time, build in-memory hash structure, and eliminate duplicates.
If there is an index with both R.sid and R.bid in the search key, then a lot of the work is done for us!
If there is a clustered index on
25
FROM Reserves R
Page Nested Loop (PNL) Join
// PNL = It’s Block Nested Loop Join with exactly 3 buffer pages:
// 1 for R, 1 for S, and 1 for result For each page PR in R do
For each page PS in S do For each tuple r in PR do
For each tuple s in PS do If rkey = skey then
Add
26
SELECT FROM WHERE
S.sid, S.sname Sailors S, Reserves R R.sid = S.sid;
PNL Join (cont.)
Estimate the # of page I/Os for this query using PNL, where R is the outer table.
27
Block Nested Loop (BNL) Join
// For B ≥ 3 buffer pages (same as PNL when B = 3): // Use B-2 for R, 1 for S, and 1 for result
For each block of B-2 pages in relation R do:
For each page PS in relation S do: For each tuple s in PS do:
For each tuple r in the outer block do: If rkey = skey then:
Add
28
SELECT FROM WHERE
S.sid, S.sname Sailors S, Reserves R R.sid = S.sid;
BNL Join (cont.)
Estimate the # of page I/Os for the query below using BNL with B=12, where R is the outer table.
What about the case where S is the outer table?
29
Index Nested Loop (INL) Join
For each page PR in relation R do: For each tuple r in PR do:
Probe the index, and then, for each tuple s in S where rkey = skey do:
Add
If there is an index on the join column(s) of only one relation (say S), we can make it the inner table, and then exploit the index.
30
INL Join (cont.)
For each R tuple, cost of probing S index is about 1.2 page I/Os for a hash index, and about 3 for a B+ tree
Cost of then finding S tuples (assuming Alternative (2) or (3) for data entries) depends on clustering
Clustered index: one I/O (typically)
Unclustered: may be one I/O per matching S tuple
31
INL (cont.)
B+ Tree example, cost of joining records:
Let M=#pages of R, and let pR=# R tuples per page Cost: M + (M*pR)*cost of finding matching S tuples
32
Examples of INL Joins: Hash Indexes
Case (1): Larger table (Reserves) is outer table
SELECT FROM WHERE
S.sid, S.sname Sailors S, Reserves R R.sid = S.sid;
(a) Hash-index (Alt. 2) on sid of Sailors (as inner)
• Scan Reserves: 1000 page I/Os, 100*1000 tuples
• For each Reserves tuple: 1.2 I/Os to get data entry in index, plus 1 I/O to get (the exactly one) matching Sailors tuple. Total = 221,000 page I/Os
33
Examples of INL Joins (cont.)
(b) Hash-index (Alt. 2) on sid of Reserves (as inner):
• Scan Sailors: 500 page I/Os, 80*500 tuples
• ForeachSailorstuple:
• 1.2 I/Os to find index page with data entries, plus cost of retrieving matching Reserves tuples
• Assuming uniform distribution, 2.5 reservations per sailor (i.e., |R| / |S| = 100,000 / 40,000)
• Cost of retrieving them is 1 or 2.5 I/Os, depending on whether the index is clustered
• Unclustered case: Cost = • Clustered case: Cost =
34
Summary
There are several alternative evaluation algorithms for each relational operator.
Two parts to optimizing a query:
Consider a set of alternative plans containing different access
paths.
Estimate the cost of each plan that is considered.
• Key issues: Statistics, indexes, operator implementations
• Type of index, and clustered vs. unclustered, are important
We’ve started by looking at some basic kinds of joins: Page Nested Loop (PNL) Join – BNL with B = 3
Block Nested Loop (BNL) Join – general case
Index Nested Loop (INL) Join – must have index on inner table
More to come in Part 2 …
35