数据库课件lec9QueryOptimization幻灯片.pptVIP

17 18 5 2 2 7 3 7 7 10 11 8 8 9 9 12 13 14 15 16 16 17 12 13 14 16 Enumeration of Alternative Plans There are two main cases: Single-relation plans (base case) Multiple-relation plans (induction) Single-table queries include selects, projects, and grouping/aggregate operations: Consider each available access path (file scan / index) Choose the one with the least estimated cost Selection/Projection done on the fly Result pipelined into grouping/aggregation Cost Estimates for Single-Relation Plans Index I on primary key matches selection: Cost is Height(I)+1 for a B+ tree. Clustered index I matching one or more selects: (NPages(I)+NPages(R)) * product of RF’s of matching selects. Non-clustered index I matching one or more selects: (NPages(I)+NTuples(R)) * product of RF’s of matching selects. Sequential scan of file: NPages(R). Recall: Must also charge for duplicate elimination if required Example If we have an index on rating: Cardinality = (1/NKeys(I)) * NTuples(R) = (1/10) * 40000 tuples Clustered index: (1/NKeys(I)) * (NPages(I)+NPages(R))  = (1/10) * (50+500) = 55 pages are retrieved. (This is the cost.) Unclustered index: (1/NKeys(I)) * (NPages(I)+NTuples(R))  = (1/10) * (50+40000) = 4005 pages are retrieved. If we have an index on sid: Would have to retrieve all tuples/pages. With a clustered index, the cost is 50+500, with unclustered index, 50+40000. Doing a file scan: We retrieve all file pages (500). SELECT S.sid FROM Sailors S WHERE S.rating=8 Queries Over Multiple Relations A System R heuristic:only left-deep join trees considered. Restricts the search space Left-deep trees allow us to generate all fully pipelined plans. Intermediate results not written to temporary files. Not all left-deep trees are fully pipelined (e.g., SM join). B A C D B A C D C D B A Enumeration of Left-Deep Plans Left-deep plans differ in the order of relations the access method for each relation the join method for each join. Enumerated using N