数据库课件lec8QueryProcessing幻灯片.ppt

Summary A virtue of relational DBMSs: queries are composed of a few basic operators The implementation of these operators can be carefully tuned Many alternative implementation techniques for each operator No universally superior technique for most operators. Must consider available alternatives Called “Query optimization” -- we will study this topic soon! * * * * * * * 11 * * * * 13 * 14 * * 15 * 16 * * 18 * * * * * * * * * * * * 22 Implementation of Relational Operations Jianlin Feng School of Software SUN YAT-SEN UNIVERSITY Introduction Next topic: QUERY PROCESSING Some database operations are EXPENSIVE Huge performance gained by being “smart” We’ll see 1,000,000x over na?ve approach Main weapons are: clever implementation techniques for operators exploiting relational algebra “equivalences” using statistics and cost models to choose Simple SQL Refresher SELECT list-of-fields  FROM list-of-tables WHERE condition SELECT S.name, E.cid FROM Students S, Enrolled E WHERE S.sid=E.sid AND E.grade=A A Really Bad Query Optimizer For each Select-From-Where query block Create a plan that: Forms the cross product of the FROM clause Applies the WHERE clause (Then, as needed: Apply the GROUP BY clause Apply the HAVING clause Apply any projections and output expressions Apply duplicate elimination and/or ORDER BY) ? spredicates tables … Cost-based Query Sub-System Query Parser Query Optimizer Plan Generator Plan Cost Estimator Query Plan Evaluator Catalog Manager Schema Statistics Select * From Blah B Where B.blah = blah Queries The Query Optimization Game Goal is to pick a “good” plan Good = low expected cost, under cost model Degrees of freedom: access methods physical operators operator orders Roadmap for this topic: First: implementing individual operators Then: optimizing multiple operators Relational Operations We will consider how to implement: Selection ( ? ) Select a subset of rows. Projection ( ? ) Remove u