DOC PREVIEW
UW CSE 444 - Query Optimization

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 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 26 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 26 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 26 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 26 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 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Query OptimizationVery Big PictureMore Detail, but Still Big PictureQuery Rewrite SummaryTodayCost EstimationStatistics and CatalogsSize Estimation and Reduction FactorsHistogramsHistogramsSlide 11Slide 12Plans for Single-Relation Queries (Prep for Join ordering)ExampleDetermining Join OrderingTypes of Join TreesSlide 17Slide 18ProblemDynamic ProgrammingSlide 21Slide 22Slide 23Slide 24Slide 25Key Lessons in OptimizationQuery OptimizationMarch 10th, 2003Very Big Picture•A query execution plan is a program.•There are many of them.•The optimizer is trying to chose a good one.•Hence, the optimizer is reasoning about programs.•Key: cost model, search space.•Compilers don’t have cost models. Why?More Detail, but Still Big Picture•Parse the SQL query into a logical tree:–identify distinct blocks (corresponding to nested sub-queries or views). •Query rewrite phase: SQL-to-SQL transforms–apply algebraic transformations to yield a cheaper plan.–Merge blocks and move predicates between blocks. •Optimize each block: join ordering.•Complete the optimization: select scheduling (pipelining strategy).Query Rewrite Summary•The optimizer can use any semantically correct rule to transform one query to another.•Rules try to:–move constraints between blocks (because each will be optimized separately)–Unnest blocks•Especially important in decision support applications where queries are very complex.•Rules can be very tricky!Today•Cost and size estimation–Need for comparing between plans.–Not always used in algebraic transformation phase.•Join ordering–Very crucial!Cost Estimation•For each plan considered, must estimate cost:–Must estimate cost of each operation in plan tree.•Depends on input cardinalities.–Must estimate size of result for each operation in tree!•Use information about the input relations.•For selections and joins, assume independence of predicates.•We’ll discuss the System R cost estimation approach.–Very inexact, but works ok in practice.–More sophisticated techniques known now.Statistics and Catalogs•Need information about the relations and indexes involved. Catalogs typically contain at least:–# tuples (NTuples) and # pages (NPages) for each relation.–# distinct key values (NKeys) and NPages for each index.–Index height, low/high key values (Low/High) for each tree index.•Catalogs updated periodically.–Updating whenever data changes is too expensive; lots of approximation anyway, so slight inconsistency ok.•More detailed information (e.g., histograms of the values in some field) are sometimes stored.Size Estimation and Reduction Factors•Consider a query block:•Maximum # tuples in result is the product of the cardinalities of relations in the FROM clause.•Reduction factor (RF) associated with each term reflects the impact of the term in reducing result size. Result cardinality = Max # tuples * product of all RF’s.–Implicit assumption that terms are independent!–Term col=value has RF 1/NKeys(I), given index I on col–Term col1=col2 has RF 1/MAX(NKeys(I1), NKeys(I2))–Term col>value has RF (High(I)-value)/(High(I)-Low(I))SELECT attribute listFROM relation listWHERE term1 AND ... AND termkHistograms•Key to obtaining good cost and size estimates.•Come in several flavors:–Equi-depth–Equi-width•Which is better?•Compressed histograms: special treatment of frequent values.HistogramsEmployee(ssn, name, salary, phone)•Maintain a histogram on salary:•T(Employee) = 25000, but now we know the distributionSalary: 0..20k 20k..40k 40k..60k 60k..80k 80k..100k > 100kTuples 200 800 5000 12000 6500 500HistogramsRanks(rankName, salary)•Estimate the size of Employee RanksEmployee 0..20k 20k..40k 40k..60k 60k..80k 80k..100k > 100k200 800 5000 12000 6500 500Ranks 0..20k 20k..40k 40k..60k 60k..80k 80k..100k > 100k8 20 40 80 100 2SalaryHistograms•Assume:–V(Employee, Salary) = 200–V(Ranks, Salary) = 250•Then T(Employee Ranks) == i=1,6 Ti Ti’ / 250= (200x8 + 800x20 + 5000x40 + 12000x80 + 6500x100 + 500x2)/250= ….SalaryPlans for Single-Relation Queries(Prep for Join ordering)•Task: create a query execution plan for a single Select-project-group-by block.•Key idea: consider each possible access path to the relevant tuples of the relation. Choose the cheapest one. •The different operations are essentially carried out together (e.g., if an index is used for a selection, projection is done for each retrieved tuple, and the resulting tuples are pipelined into the aggregate computation).Example•If we have an Index on rating:–(1/NKeys(I)) * NTuples(R) = (1/10) * 40000 tuples retrieved.–Clustered index: (1/NKeys(I)) * (NPages(I)+NPages(R)) = (1/10) * (50+500) pages are retrieved (= 55). –Unclustered index: (1/NKeys(I)) * (NPages(I)+NTuples(R)) = (1/10) * (50+40000) 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.•Doing a file scan: we retrieve all file pages (500).SELECT S.sidFROM Sailors SWHERE S.rating=8Determining Join Ordering•R1 R2 …. Rn•Join tree:•A join tree represents a plan for a block. An optimizer needs to inspect many (all ?) join treesR3 R1 R2 R4Types of Join Trees•Left deep:R3R1R5R2R4Types of Join Trees•Bushy:R3R1R2 R4R5Types of Join Trees•Right deep:R3R1R5R2 R4Problem•Given: a query R1 R2 … Rn•Assume we have a function cost() that gives us the cost of every join tree•Find the best join tree for the queryDynamic Programming•Idea: for each subset of {R1, …, Rn}, compute the best plan for that subset•In increasing order of set cardinality:–Step 1: for {R1}, {R2}, …, {Rn}–Step 2: for {R1,R2}, {R1,R3}, …, {Rn-1, Rn}–…–Step n: for {R1, …, Rn}•A subset of {R1, …, Rn} is also called a subqueryDynamic Programming•For each subquery Q ⊆ {R1, …, Rn} compute the following:–Size(Q)–A best plan for Q: Plan(Q)–The cost of that plan: Cost(Q)Dynamic Programming•Step 1: For each {Ri} do:–Size({Ri}) = B(Ri)–Plan({Ri}) = Ri–Cost({Ri}) = (cost of scanning Ri)Dynamic Programming•Step i: For each Q ⊆ {R1, …, Rn} of cardinality i do:–Compute Size(Q) –For every pair of subqueries Q’, Q’’ s.t. Q = Q’ U Q’’compute cost(Plan(Q’) Plan(Q’’))–Cost(Q) = the smallest such cost–Plan(Q) = the corresponding planDynamic


View Full Document

UW CSE 444 - Query Optimization

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 Optimization
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 Optimization 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 Optimization 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?