Introduction to Database SystemsCSE 444Lecture 18: Query Processing OverviewCSE 444 - Summer 2010 1Where We Are• We are learning how a DBMS executes a query– How come a DBMS can execute a query so fast?• Lecture 15-16: Data storage, indexing, physical tuning•Lecture 17: Relational algebraLecture 17: Relational algebra• Lecture 18: Overview of query processing steps– Includes a description of how queries are executed• Lecture 19: Operator algorithms• Lecture 20: Overview of query optimizationCSE 444 - Summer 2010 2Outline for Today• Steps involved in processing a query– Logical query plan– Physical query plan– Query execution overview• Readings: Section 15.1 of the bookQit–Query processing steps– Query execution using the iterator modelAn intro to next lecture on operator algorithmsCSE 444 - Summer 2010–An intro to next lecture on operator algorithms3Query Evaluation StepsQuery Evaluation StepsSQL queryParse & Rewrite QuerySelect Logical PlanQueryoptimizationLogicalplanSelect Physical PlanoptimizationPhysicalplanQuery ExecutionplanDisk4Example Database SchemaSupplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno pno price)Supply(sno,pno,price)View: Suppliers inSeattleView: Suppliers in SeattleCREATE VIEW NearbySupp ASSELECT sno, snameFROM SupplierWHERE scity='Seattle' AND sstate='WA'CSE 444 - Summer 2010y5Example QueryFind the names of all suppliers in Seattlewho supply part number 2pp ypSELECT sname FROM NearbySuppWHERE sno IN ( SELECT snoFROM SuppliesWHERE pno = 2 )pCSE 444 - Summer 2010 6Steps in Query Evaluation• Step 0: Admission control– User connects to the db with username, passwordUd ittft–User sends query in text format• Step 1: Query parsingParses query into an internal format–Parses query into an internal format– Performs various checks using catalog• Correctness, authorization, integrity constraints,,gy• Step 2: Query rewrite–View rewriting, flattening, etc.CSE 444 - Summer 2010gg7Rewritten Version of Our QueryOriginal query:gqySELECT snameFROM NearbySuppWHERE sno IN ( SELECT sno(FROM SuppliesWHERE pno = 2 )Rewritten query:SELECT S.snameFROM Supplier S Supplies UFROM Supplier S, Supplies UWHERE S.scity='Seattle' AND S.sstate='WA’AND S.sno = U.snoANDU pno=2;CSE 444 - Summer 2010AND U.pno= 2;8Continue with Query Evaluation• Step 3: Query optimization– Find an efficient query plan for executing the query•A query plan is– Logical query plan: an extended relational algebra tree – Physical query plan: with additional annotations at each dnode• Access method to use for each relation•Implementation to use for each relational operatorCSE 444 - Summer 2010pp9Extended Algebra Operators• Union ∪, intersection ∩, difference –• Selection σ• Projection π• Join • Duplicate elimination δ•Grouping and aggregationγGrouping and aggregation γ• Sorting τ•RenameρCSE 444 - Summer 2010•Rename ρ10Logical Query Planπ π snameσ sscity=‘Seattle’ ∧ sstate=‘WA’ ∧ pno=2sno = snoSuppliersSuppliesCSE 444 - Summer 2010 11Query Block• Most optimizers operate on individual query blocks• A query block is an SQL query with no nesting– Exactly one• SELECT clause• FROM clause–At most oneAt most one• WHERE clause• GROUP BY clauseHAVING lCSE 444 - Summer 2010•HAVING clause12Typical Plan for Block (1/2)...π fieldsσ selection conditionSELECTPROJECTJOINjoin conditionSELECT-PROJECT-JOINQueryjoin condition…CSE 444 - Summer 2010RS13Typical Plan For Block (2/2)σ having conditionγ fields, sum/count/min/max(fields)σ selection conditionjoin condition……CSE 444 - Summer 2010 14Supplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno,pno,price)How about Subqueries?SELECT Q.snoFROM Supplier QWHEREQsstate=‘WA’WHEREQ.sstate WA and not existsSELECT *FROMS ppl PFROMSupply PWHERE P.sno = Q.snoand P.price > 100CSE 444 - Summer 2010 15Supplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno,pno,price)How about Subqueries?SELECT Q.snoFROM Supplier QWHEREQ sstate=‘WA’Correlation !WHEREQ.sstate WA and not existsSELECT *FROMS ppl PCorrelation !FROMSupply PWHERE P.sno = Q.snoand P.price > 100CSE 444 - Summer 2010 16Supplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno,pno,price)How about Subqueries?SELECT Q.snoFROM Supplier QWHEREQ sstate=‘WA’De-CorrelationWHEREQ.sstate WA and not existsSELECT *FROMS ppl PSELECTQsnoFROMSupply PWHERE P.sno = Q.snoand P.price > 100SELECTQ.snoFROM Supplier QWHERE Q.sstate = ‘WA’dQtiandQ.sno notinSELECT P.snoFROM Supply P17pp yWHERE P.price > 100Supplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno,pno,price)How about Subqueries?Un-nestingUnnestingSELECTQsno(SELECT Q.snoFROM Supplier QWHEREQsstate=‘WA’)SELECTQ.snoFROM Supplier QWHERE Q.sstate = ‘WA’dQtiWHEREQ.sstate WA )EXCEPT(SELECT P.snoFROMSlPand Q.sno notinSELECT P.snoFROM Supply PFROMSupply PWHERE P.price > 100)18pp yWHERE P.price > 100Supplier(sno,sname,scity,sstate)Part(pno,pname,psize,pcolor)Supply(sno,pno,price)How about Subqueries?−Finally…(SELECT Q.snoFROM Supplier QWHEREQ sstate=‘WA’)Finally…σsstate=‘WA’σPrice > 100WHEREQ.sstate WA )EXCEPT(SELECT P.snoFROMSlPSupplySupplierFROMSupply PWHERE P.price > 100)CSE 444 - Summer 2010 19Physical Query Plan• Logical query plan with extra annotations• Access path selection for each relation– Use a file scan or use an index• Implementation choice for each operatorpp•Scheduling decisionsfor operatorsCSE 444 - Summer 2010Scheduling decisionsfor operators20Physical Query Planπ (On the fly)π sname(On the fly)σ sscity=‘Seattle’ ∧ sstate=‘WA’ ∧ pno=2(On the fly)sno = sno(Nested loop)SuppliersSuppliesCSE 444 - Summer 2010(File scan)(File scan)21Final Step in Query Processing•Step 4: Query execution•Step 4: Query execution–How to synchronize operators?–How topass data between operators?How to pass data between operators?•Approach:pp– One thread per query– Iterator interface– Pipelined execution, or– Intermediate result materializationCSE 444 - Summer 2010 22Iterator Interface•Eachoperator implementsiteratorinterface•Each operator implementsiteratorinterface• Interface has only three methods•open()•open()– Initializes operator state–Sets parameters such as selection conditionSets parameters such as selection condition• get_next()–Operator invokesget next()recursively on its
View Full Document
Unlocking...