DOC PREVIEW
UT Dallas CS 6360 - query processing example

This preview shows page 1-2-3-26-27-28 out of 28 pages.

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

Unformatted text preview:

ECS-165A WQ’11 1368. Query ProcessingGoals: Understand the basic concepts underlying the steps inquery processing and optimization and estimating query processingcost; apply query optimization techniques;Contents:• Overview• Catalog Information for Cost Estimation• Measures of Query Cost• Selection• Join Operations• Other Operations• Evaluation and Transformation of ExpressionsQuery Processing & OptimizationTask: Find an efficient physical query plan (aka execution plan)for an SQL queryGoal: Minimize the evaluation time for the query, i.e., computequery result as fast as possibleCost Factors: Disk accesses, read/write operations, [I/O, pagetransfer] (CPU time is typically ignored)Dept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 137Basic Steps in Processing an SQL Query(System Catalogs)SQL QueryRelational AlgebraExpressionOptimizerStatisticsExecution PlanEvaluation EngineQuery ResultData FilesParser &Translator• Parsing and Translating– Translate the query into its internal form (parse tree).This is then translated into an expression of the relationalalgebra.– Parser checks syntax, validates relations, attributes andaccess permissions• Evaluation– The query execution engine takes a physical query plan(aka execution plan), executes the plan, and returns theresult.• Optimization: Find the “cheapest” execution plan for a queryDept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 138• A relational algebra expression may have many equivalentexpressions, e.g.,πCName(σPrice>5000((CUSTOMERS 1 ORDERS) 1 OFFERS))πCName((CUSTOMERS 1 ORDERS) 1 (σPrice>5000(OFFERS)))Representation as logical query plan (a tree):ooCNamePrice > 5000CNamePrice > 5000CUSTOMERS ORDERS OFFERSORDERSOFFERSCUSTOMERSNon-leaf nodes ≡ operations of relational algebra (withparameters); Leaf nodes ≡ relations• A relational algebra expression can be evaluated in manyways. An annotated expression specifying detailed evaluationstrategy is called the execution plan (includes, e.g., whetherindex is used, join algorithms, . . . )• Among all semantically equivalent expressions, the one withthe least costly evaluation plan is chosen. Cost estimate of aplan is based on statistical information in the system catalogs.Dept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 139Catalog Information for Cost EstimationInformation about relations and attributes:• NR: number of tuples in the relation R.• BR: number of blocks that contain tuples of the relation R.• SR: size of a tuple of R.• FR: blocking factor; number of tuples from R that fit into oneblock (FR= dNR/BRe)• V(A, R): number of distinct values for attribute A in R.• SC(A, R): selectivity of attribute A≡ average number of tuples of R that satisfy anequality condition on A.SC(A, R) = NR/V(A, R).Information about indexes:• HTI: number of levels in index I (B+-tree).• LBI: number of blocks occupied by leaf nodes in index I(first-level blocks).• ValI: number of distinct values for the search key.Some relevant tables in the Oracle system catalogs:USER TABLES USER TAB COLUMNS USER INDEXESNUM ROWS NUM DISTINCT BLEVELBLOCKS LOW VALUE LEAF BLOCKSEMPTY BLOCKS HIGH VALUE DISTINCT KEYSAVG SPACE DENSITY AVG LEAF BLOCKS PER KEYCHAIN CNT NUM BUCKETSAVG ROW LEN LAST ANALYZEDDept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 140Measures of Query Cost• There are many possible ways to estimate cost, e.g., based ondisk accesses, CPU time, or communication overhead.• Disk access is the predominant cost (in terms of time);relatively easy to estimate; therefore, number of block transfersfrom/to disk is typically used as measure.– Simplifying assumption: each block transfer has the samecost.• Cost of algorithm (e.g., for join or selection) depends ondatabase buffer size; more memory for DB buffer reduces diskaccesses. Thus DB buffer size is a parameter for estimatingcost.• We refer to the cost estimate of algorithm S as cost(S). Wedo not consider cost of writing output to disk.Selection OperationσA=a(R) where a is a constant value, A an attribute of R• File Scan – search algorithms that locate and retrieve recordsthat satisfy a selection condition• S1 – Linear searchcost(S1)= BRDept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 141Selection Operation (cont.)• S2 – Binary search, i.e., the file ordered based on attribute A(primary index)cost(S2) = dlog2(BR)e +‰SC(A, R)FRı− 1– dlog2(BR)e ≡ cost to locate the first tuple using binarysearch– Second term ≡ blocks that contain records satisfying theselection.– If A is primary key, then SC(A, R) = 1, hencecost(S2) = dlog2(BR)e.Dept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 142• Example (for Employee DB)– FEmployee= 10;V(Deptno, Employee) = 50 (different departments)– NEmployee= 10, 000 (Relation Employee has 10,000 tuples)– Assume selection σDeptno=20(Employee) and Employee issorted on search key Deptno :=⇒ 10,000/50 = 200 tuples in Employee belong toDeptno 20;(assuming an equal distribution)200/10 = 20 blocks for these tuples=⇒ A binary search finding the first block would requiredlog2(1, 000)e = 10 block accessesTotal cost of binary search is 10+20 block accesses (versus1,000 for linear search and Employee not sorted by Deptno).Dept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 143• Index scan – search algorithms that use an index (here, aB+-tree); selection condition is on search key of index• S3 – Primary index I for A, A primary key, equality A = acost(S3) = HTI+ 1 (only 1 tuple satisfies condition)• S4 – Primary index I on non-key A equality A = acost(S4) = HTI+‰SC(A, R)FRı• S5 – Non-primary (non-clustered) index on non-key A,equality A = acost(S5) = HTI+ SC(A, R)Worst case: each matching record resides in a different block.• Example (Cont.):– Assume primary (B+-tree) index for attribute Deptno– 200/10=20 blocks accesses are required to read Employeetuples– If B+-tree index stores 20 pointers per (inner) node, thenthe B+-tree index must have between 3 and 5 leaf nodesand the entire tree has a depth of 2=⇒ a total of 22 blocks must be read.Dept. of Computer Science UC Davis 8. Query Processing and OptimizationECS-165A WQ’11 144Selections Involving


View Full Document

UT Dallas CS 6360 - query processing example

Documents in this Course
Ch22(1)

Ch22(1)

44 pages

Ch21

Ch21

38 pages

Ch19

Ch19

46 pages

Ch18

Ch18

25 pages

Ch17

Ch17

21 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch05

Ch05

34 pages

Ch22

Ch22

45 pages

Ch21

Ch21

38 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch16

Ch16

17 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

34 pages

Ch06

Ch06

43 pages

Ch05

Ch05

34 pages

Ch04

Ch04

39 pages

Ch03(2)

Ch03(2)

36 pages

Ch02

Ch02

33 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

lab-manual

lab-manual

215 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch17

Ch17

25 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch04(1)

Ch04(1)

43 pages

Ch07

Ch07

40 pages

Ch03

Ch03

42 pages

Ch01

Ch01

36 pages

Ch02

Ch02

38 pages

Ch05

Ch05

41 pages

Ch06

Ch06

47 pages

Ch08

Ch08

39 pages

Ch17

Ch17

25 pages

Ch18

Ch18

24 pages

Ch09

Ch09

42 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04(1)

Ch04(1)

43 pages

Ch03

Ch03

42 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Load more
Download query processing example
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 example 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 example 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?