程序代写代做代考 algorithm database CS W4111.001 Introduction to Databases Fall 2020

CS W4111.001 Introduction to Databases Fall 2020
Computer Science Department Columbia University
1

Overview of Query Optimization
• Goal: Choose an efficient execution plan for a query (hence avoiding the really inefficient plans)
• Given a SQL query, define and analyze cost of many different execution plans that produce the correct answer for the query, but with potentially very different run times
• First, we will focus on how to evaluate individual relational algebra operators efficiently
• Afterwards, we will discuss how to evaluate full-fledged SQL queries efficiently
3

Processing a Selection Condition
• Consider all access paths that could be used for the relation and selection condition: scan plus any indexes that match condition
• Find the most selective access path (i.e., requiring fewest I/Os), retrieve tuples using it, and apply any remaining conditions that don’t match the index
7

other conditions (i.e., name=‘Jane’ and did=214)
Processing a Selection Condition: Example
Employees(ssn, name, sal, did), with
B+ tree on name, hash table on did, B+ tree on sal
𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
Alternative access paths and corresponding execution plans:
1. Scan relation and check full selection condition for each retrieved tuple
2. Use B+ tree index on name to find the set N of rids of all tuples with name=‘Jane’; retrieve those tuples and filter with other conditions (i.e., did=214 and sal>50K)
3. Use hash table on did to find the set D of rids of all tuples with did=214; retrieve those tuples and filter with other conditions (i.e., name=‘Jane’ and sal>50K)
4. UseB+ treeindexonsaltofindthesetSofridsofall tuples with sal>50K; retrieve those tuples and filter with
12

Employees(ssn, name, sal, did), with
B+ tree on name, hash table on did, B+ tree on sal
𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
Yet another possible plan uses all three indexes:
5. Retrieve three sets of rids using the three indexes that match the selection condition:
• Use B+ tree index on name to find the set N of rids of all tuples with name=‘Jane’
• Use hash table on did to find the set D of rids of all tuples with did=214
• Use B+ tree index on sal to find the set S of rids of all tuples with sal>50K
• Retrieve and return only the tuples in N ∩ D ∩ S (i.e., the tuples whose rid is in the intersection of the three sets of rids and hence satisfy all three conditions)
Sometimes “index-only” query execution plans are possible
Processing a Selection Condition: Example
14

Factors Influencing Choice of Plan
• # of tuples matching index condition
• index characteristics
For our example, we know (from database catalogs) that Employees has:
• 100,000 tuples in 1,000 blocks (i.e., 100 tuples/block)
• 1,000 distinct name values
• 500 distinct did values
• values of sal between 20K and 250K
Cost of plan (1), Scan? 1,000 I/Os
15

Cost of Plan (4), B+ Tree on Sal 𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
25

Cost of Plan (4), B+ Tree on Sal 𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
• 2 or 3 I/Os to navigate from root of B+ tree to leaf node for sal=50K
26

Cost of Plan (4), B+ Tree on Sal 𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
• 2 or 3 I/Os to navigate from root of B+ tree to leaf node for sal=50K
• Costofretrievingallleafnodeswithdataentrieswith sal>50K:
• “fraction”ofsalspacecoveredbysal>50Kcondition: (250K-50K)/(250K-20K)=0.87, based on range of values of sal
• onaverage,wethenneed100,000*0.87=87,000suchdataentries
• Costofretrievingtheactualtuplesassociatedwiththe matching rids, to filter with other conditions
• mostlikelyretrievingtheactualtuplesforthe87,000dataentrieswill require retrieving all 1,000 blocks of the relation
• sowearebetteroffjustretrievingallblocksoftherelationwithout using the B+ tree index on sal
28

sal condition not selective enough to merit use of sal B+ tree
Cost of Plan (4), B+ Tree on Sal 𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
• 2 or 3 I/Os to navigate from root of B+ tree to leaf node for sal=50K
• Costofretrievingallleafnodeswithdataentrieswith sal>50K:
• “fraction”ofsalspacecoveredbysal>50Kcondition: (250K-50K)/(250K-20K)=0.87, based on range of values of sal
• onaverage,wethenneed100,000*0.87=87,000suchdataentries
• Costofretrievingtheactualtuplesassociatedwiththe matching rids, to filter with other conditions
• mostlikelyretrievingtheactualtuplesforthe87,000dataentrieswill require retrieving all 1,000 blocks of the relation
• sowearebetteroffjustretrievingallblocksoftherelationwithout using the B+ tree index on sal
Plan (4), B+ tree on sal: dominated by other plans

Cost of Plan (5), Using 3 Indexes
𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
30

Cost of Plan (5), Using 3 Indexes
𝜎name=‘Jane’ AND did=214 AND sal>50K(Employees)
• Costofusingeachofthethreeindexes:
• 2or3I/OsforB+ treeonname
• 1I/Oforhashtableondid
• 2or3I/Osplus87%ofallleafnodesforB+ treeonsal
• B+ tree on sal not competitive, so use just B+ tree on name to get set of rids N and hash table on did to get set of rids D, at a cost of 3 or 4 I/Os
• CostofretrievingtheactualtupleswithridsinN∩D:
• crudeanalysis:assumingthatconditiononnameisindependentof condition on did, then we expect 100,000*(1/1000)*(1/500)<1 rids in intersection, so at most 1 more I/O expected Cost of plan (5), using 2 (of 3) indexes: 4 or 5 I/Os Best plan, but analysis depended on crude independence assumption 32 Processing a Selection Condition With ORs Employees(ssn, name, sal, did), with B+ tree on name, hash table on did, B+ tree on sal 𝜎name=‘Jane’ OR did=214 OR sal>50K(Employees)
33

Processing a Selection Condition With ORs
Employees(ssn, name, sal, did), with
B+ tree on name, hash table on did, B+ tree on sal
𝜎name=‘Jane’ OR did=214 OR sal>50K(Employees)
Alternative access paths and corresponding execution plans:
1. Scan relation and check full selection condition for each retrieved tuple
2. Retrieve three sets of rids using the three indexes that match the
selection condition:
• Use B+ tree index on name to find the set N of rids of all tuples with
name=‘Jane’
• UsehashtableondidtofindthesetDofridsofalltupleswithdid=214
• Use B+ tree index on sal to find the set S of rids of all tuples with sal>50K
• RetrieveandreturnonlythetuplesinN∪D∪S(i.e.,thetupleswhoseridis
in the union of the three sets of rids)
Scan is likely to prevail given the low selectivity of the condition on sal
34

SELECT DISTINCT R.sid, R.bid FROM Reserves R
Processing a Projection
35

SELECT DISTINCT R.sid, R.bid FROM Reserves R
Processing a Projection
• Without DISTINCT: No duplicate elimination, so just use scan
36

SELECT DISTINCT R.sid, R.bid FROM Reserves R
Processing a Projection
• Without DISTINCT: No duplicate elimination, so just use scan
• With DISTINCT: Need duplicate elimination; two main options:
• Sorting: Sort on and remove duplicates; drop unneeded attributes while sorting, for efficiency
• Hashing: Hash on to create buckets; then load buckets into memory one at a time, build in-memory hash table for bucket (with a different hash function), and eliminate duplicates
37

Processing Joins
• Joins are a highly optimized operation in DBMSs
• Several well studied algorithms available: • “Nested loops” join family of algorithms
• “Sort-merge” join • “Hash” join
•…
• Best choice for a query depends on characteristics of the query and the relations, as well as on available indexes
38

Processing Joins: Example
Reserves: pR=100 tuples/page; 100K tuples; M=1,000 pages Sailors: pS=80 tuples/page; 40K tuples; N=500 pages
SELECT * FROM Reserves R, Sailors S WHERE R.sid=S.sid;
39

•…
Processing Joins: Example
Reserves: pR=100 tuples/page; 100K tuples; M=1,000 pages Sailors: pS=80 tuples/page; 40K tuples; N=500 pages
SELECT * FROM Reserves R, Sailors S WHERE R.sid=S.sid;
• We will describe different join execution algorithms and estimate their cost in number of I/Os
• Our analysis will ignore the cost of writing the output, which is equal across execution algorithms
Options:
• Naïve nested loops join
• Page-oriented nested loops join
• Block nested loops join
• (Index nested loops join)
• (Sort-merge join)
• (Hash join)
40

Naïve Nested Loops Join
For each tuple r in R do: For each tuple s in S do:
if r.sid = s.sid then add r ⨝ s to result
• R is the “outer” relation; S is the “inner” relation
• cost = M + pR*M*N I/Os = 1,000 + 100K*500 I/Os ≅ 5*107 I/Os • @10ms/I/O:about140hours(!)
41

Page-Oriented Nested Loops Join
Improvement: Read inner relation only as many times as there are pages of the outer relation, not once per outer tuple
For each page BR of R do: For each page BS of S do:
For each tuple r in BR and tuple s in BS: if r.sid = s.sid then add r ⨝ s to result
• R is the “outer” relation; S is the “inner” relation
• cost=M+M*NI/Os=1,000+1,000*500I/Os=501KI/Os • @10ms/I/O:about1.4hours
42

Block Nested Loops Join
Improvement: Exploit main-memory buffer pool as much as possible to reduce number of I/Os
Assumption: B pages of main memory available for processing join
43

Block Nested Loops Join
Improvement: Exploit main-memory buffer pool as much as possible to reduce number of I/Os
Assumption: B pages of main memory available for processing join
For each “chunk” CR of B-2 pages of R do: For each page BS of S do:
For each tuple r in CR and tuple s in BS: if r.sid = s.sid then add r ⨝ s to result
• cost,forB=102=M+ceiling(M/(B-2))*NI/Os= 1,000 + ceiling(1,000/100)*500 I/Os = 6K I/Os
44

Overview of Query Optimization
• So far, we studied choices—and their costs—for plans for individual relational operators (selections, projections, joins, …)
• We will now cover more complex queries
45

Related Posts