DOC PREVIEW
UW CSE 444 - Query Processing Overview

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UW CSE 444 - Query Processing Overview

Documents in this Course
XML

XML

48 pages

SQL

SQL

25 pages

SQL

SQL

42 pages

Recovery

Recovery

30 pages

SQL

SQL

36 pages

Indexes

Indexes

35 pages

Security

Security

36 pages

Wrap-up

Wrap-up

6 pages

SQL

SQL

37 pages

More SQL

More SQL

48 pages

SQL

SQL

35 pages

XML

XML

46 pages

Triggers

Triggers

26 pages

Load more
Download Query Processing Overview
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Query Processing Overview and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Query Processing Overview 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?