Introduction to Database Systems CSE 444 Lecture 19: Query Processing OverviewWhere We Are 2! We#are#learning#how#a#DBMS#executes#a#query# How#come#a#DBMS#can#execute#a#query#so#fast?# Lectures#16?17:#Data#storage,#indexing,#physical#tuning# Lecture#18:#RelaGonal #algebra# Lecture#19:#Overview#of#query#processing#steps# Includes#a#descripGon#of#how#queries#are#executed# Lecture#20:#Operator#algorithms# Lectures#21?23:#Overview#of#query#opGmizaGon#Outline for Today 3! Steps&involved&in&processing&a&query& Logical#query#plan# Physical#query#plan# Query#execuGon#overview# Readings:#SecGon#15.1#of#the#book# Query#processing#steps# Query#execuGon#using#the#iterator#model# An#introducGon#to#next#lecture#on#operator#algos#Query Evaluation Steps 4!Parse#&#Rewrite#Query#Select#Logical#Plan#Select#Physical#Plan#Query#ExecuGon #Disk#SQL#query#Query#opGmizaGon#Logical#plan#Physical#plan#Example Database Schema 5!Supplier(sno,sname,scity,sstate) Part(pno,pname,psize,pcolor) Supplies(sno,pno,price) View:#Suppliers#in#SeaZle#CREATE VIEW NearbySupp AS SELECT sno, sname FROM Supplier WHERE scity='Seattle' AND sstate='WA' xExample Query 6!Find#the#names#of#all#suppliers#in#SeaZle##who#supply#part#number#2#SELECT sname FROM NearbySupp WHERE sno IN ( SELECT sno FROM Supplies WHERE pno = 2 )Steps in Query Evaluation 7! Step&0:&Admission&control& User#connects#to#the#db#with#username,#password# User#sends#query#in#tex t# format# Step&1:&Query&parsing& Parses#query#into#an#internal#format# Performs#various#checks#using#catalog# Correctness,#authorizaGon,#integrity#constraints# Step&2:&Query&rewrite& View#rewriGng,#flaZening,#etc.#Rewritten Version of Our Query 8!Original#query: SELECT sname FROM NearbySupp WHERE sno IN ( SELECT sno FROM Supplies WHERE pno = 2 ) RewriZen#query: SELECT S.sname FROM Supplier S, Supplies U WHERE S.scity='Seattle' AND S.sstate='WA’ AND S.sno = U.sno AND U.pno = 2;#Continue with Query Evaluation 9! Step&3:&Query&op>miza>on& Find#an#efficient#query#plan#for#execuGng#the#query# We#will#spend#three#lectures#on#thi s#topic# A&query&plan&is& Logical#query#plan:#an#extended#relaGonal#algebra#tree## Physical#query#plan:#with#addiGonal#annotaGons#at#each#node# Access#method#to#use#for#each#relaGon# ImplementaGon#to#use#for#each#relaGonal#operator#Extended Algebra Operators 10! Union#∪,#intersecGon#∩,#difference#–## SelecGon##σ$ ProjecGon#π$ Join### Duplicate#eliminaGon#δ$ Grouping#and#aggregaGon#γ$ SorGng#τ$ Rename#ρ$Logical Query Plan 11!Suppliers#Supplies#sno#=#sno#σ sscity=‘SeaZle’#∧sstate=‘WA’#∧#pno=2#π sname#Query Block 12! Most#opGmizers#operate#on#individual#quer y#blocks# A#query#block#is#an#SQL#query#with#no#nesGng# Exactly#one# SELECT#clause# FROM#clause# At#most#one# WHERE#clause# GROUP#BY#clause# HAVING#clause#Typical Plan for Block (1/2) 13!R#S#join#condiGon#σ selecGon#condiGon#π fields#join#condiGon#…#SELECT?PROJECT?JOIN#Query#...#Typical Plan For Block (2/2) 14!π fields!γ fields, sum/count/min/max(fields)!havingcondition!σ selection condition!join condition!…! …!How about Subqueries? 15!SELECT Q.name FROM Person Q WHERE Q.age > 25 AND NOT EXISTS (SELECT * FROM Purchase P WHERE P.buyer = Q.name AND P.price > 100)How about Subqueries? 16!Purchase!Person!buyer=name!Person!σPrice > 100!πname!−!SELECT Q.name FROM Person Q WHERE Q.age > 25 AND NOT EXISTS (SELECT * FROM Purchase P WHERE P.buyer = Q.name AND P.price > 100) πname!σage > 25!Physical Query Plan 17! Logical#query#plan#with#extra#annotaGons# Access&path&selec>on#for#each#relaGon# Use#a#file#scan#or#use#an#index# Implementa>on&choice#for#each#operator# Scheduling&decisions#for#operators#Physical Query Plan 18!Suppliers Supplies sno = sno!σ sscity=‘Seattle’ ∧sstate=‘WA’ ∧ pno=2!π sname!(File scan) (File scan) (Nested loop) (On the fly) (On the fly)Final Step in Query Processing 19! Step&4:&Query&execu>on& How#to#synchronize#operators?# How#to#pass#data#between#operators?# Approach:# Iterator#interface#with# Pipelined#execuGon#or# Intermediate#result#materializaGon#Iterator Interface 20! Each&operator&implements&iterator&interface& Interface#has#only#three#methods# open()# IniGalizes#operator#state# Sets#parameters#such#as#selecGon#condiGon# get_next()# Operator#invokes#get_next()#recursively#on#its#inputs# Performs#processing#and#produces#an#output#tuple# close():#cleans?up#state#Pipelined Execution 21! Applies#parent#operator#to#tuples#directly#as#th ey#are#produced#by#child#operators# Benefits# No#operator#synchronizaGon#issues# Saves#cost#of#wriGng#intermediate#data#to#disk# Saves#cost#of#reading#intermediate#d ata#from#disk# Good#resource#uGlizaGons#on#single#processor# This#approach#is#used#whenever#possible#Pipelined Execution 22!Suppliers Supplies sno = sno!σ sscity=‘Seattle’ ∧sstate=‘WA’ ∧ pno=2!π sname!(File scan) (File scan) (Nested loop) (On the fly) (On the fly)Intermediate Tuple Materialization 23! Writes#the#resul ts#of #an#o perator#to#an#intermediate#table#on#disk# No#direct#benefit#but# Necessary#for#some#operator#i mplementaGons# When#operator#needs#to#examine#the#same#tuples#mulGple#Gmes#Intermediate Tuple Materialization 24!Suppliers Supplies sno = sno!σ sscity=‘Seattle’ ∧sstate=‘WA’!π sname!(File scan) (File scan) (Sort-merge join) (Scan: write to T2) (On the fly) σ pno=2!(Scan: write to T1)Next Time 25! Algorithms#for#physical#op.#implementaGons#
View Full Document