DOC PREVIEW
UT Dallas CS 6360 - CS-6360_ch19-QueryProcessing(1)

This preview shows page 1-2-3-4-5-6-40-41-42-43-44-82-83-84-85-86-87 out of 87 pages.

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

Unformatted text preview:

!" #Chris Irwin Davis, Ph.D. !Email: [email protected] Phone: (972) 883-3574 Office: ECSS 4.705Chapter 19: Query Processing and OptimizationCS-6360 Database Design!" #Introduction to Query Processing■Query optimization:!■The process of choosing a suitable execution strategy for processing a query.!■Two internal representations of a query:!■Query Tree!■Query Graph319.1 – Translating SQL Queries into Relational Algebra!" #Translating SQL Queries into Relational Algebra■In practice, SQL is the query language that is used in most commercial RDBMSs. !■An SQL query is first translated into an equivalent extended relational algebra expression—represented as a query tree data structure—that is then optimized.5!" #Translating SQL Queries into Relational Algebra■Query block: !■The basic unit that can be translated into the algebraic operators and optimized.!■A query block contains a single SELECT-FROM-WHERE expression, as well as GROUP BY and HAVING clause if these are part of the block.!■Nested queries within a query are identified as separate query blocks.!■Aggregate operators in SQL must be included in the extended algebra.6!" #Translating SQL Queries into Relational AlgebraSELECT!!Lname,!Fname!FROM!! EMPLOYEE!WHERE!! Salary!>!(! SELECT!!MAX!(Salary)!!!!FROM!EMPLOYEE!!!!WHERE!! Dno!=!5);7Nested query without correlation with the outer query!" #Translating SQL Queries into Relational AlgebraSELECT!!LNAME,!FNAME!FROM!! EMPLOYEE!WHERE!! SALARY!>!(! SELECT!!MAX!(SALARY)!!!!FROM!EMPLOYEE!!!!WHERE!! DNO!=!5);SELECT!MAX!(SALARY)!FROM!EMPLOYEE!WHERE!! DNO!=!5SELECT!!LNAME,!FNAME!FROM!! EMPLOYEE!WHERE!! SALARY!>!C8Must be a single value, i.e. exactly one column and one row!" #Translating SQL Queries into Relational AlgebraSELECT!!LNAME,!FNAME!FROM!! EMPLOYEE!WHERE!! SALARY!>!(! SELECT!!MAX!(SALARY)!!!!FROM!EMPLOYEE!!!!WHERE!! DNO!=!5);SELECT!MAX!(SALARY)!FROM!EMPLOYEE!WHERE!! DNO!=!5SELECT!!LNAME,!FNAME!FROM!! EMPLOYEE!WHERE!! SALARY!>!Cπ Lname, Fname (σSalary>C (EMPLOYEE))MAX Salary (σDno=5 (EMPLOYEE))919.2 – Algorithms for External Sorting!" #External Access (Files)■Data access occurs in main memory!■It is necessary to copy from data stored in files into main memory!■Available memory is (usually) less than the size of data files!■How to access data in files?!■nB –"buffer size in disk blocks (int)!■b –"file size in disk blocks (int)!■nR –"number of “runs” to access the entire file (int)11!" #Algorithms for External Sorting■How to sort records in a file?!■Sort + Merge!■Sort the records in each block!■Recursively merge the blocks12!" #Algorithms for External Sorting■Sorting Phase!■The size of each run and the available buffer space (nB).!■For example, if the number of available main memory buffers nB = 5 disk blocks and the size of the file b = 1024 disk blocks, then nR = !(b/nB)" or 205 initial runs each of size 5 blocks (except the last run which will have only 4 blocks).!■Hence, after the sorting phase, 205 sorted runs (or 205 sorted subfiles of the original file) are stored as temporary subfiles on disk.13!" #Algorithms for External Sorting■Merging Phase!■The sorted runs are merged during one or more merge passes.!■Each merge pass can have one or more merge steps.!■The degree of merging (dM) is the number of sorted subfiles that can be merged in each merge step.!■Performance!■The performance of the sort-merge algorithm can be measured in the number of disk block reads and writes (between the disk and main memory) before the sorting of the whole file is completed. The following formula approximates this cost:1419.3 –!Algorithms for SELECT and JOIN!" #Algorithms for SELECT and JOIN Operations ■Implementing the SELECT Operation!■SELECT Examples:!■(OP1): σ SSN='123456789' (EMPLOYEE)#■(OP2): σ DNUMBER>5 (DEPARTMENT)#■(OP3): σ DNO=5 (EMPLOYEE)#■(OP4): σ DNO=5 AND SALARY>30000 AND SEX=F (EMPLOYEE)#■(OP5): σ ESSN=123456789 AND PNO=10(WORKS_ON)16!" #Algorithms for SELECT and JOIN Operations ■Implementing the SELECT Operation (contd.):!■Search Methods for Simple Selection:!■S1 Linear search (brute force):!□Retrieve every record in the file, and test whether its attribute values satisfy the selection condition.!■S2 Binary search:!□If the selection condition involves an equality comparison on a key attribute on which the file is ordered, binary search (which is more efficient than linear search) can be used. (See OP1).!■S3 Using a primary index or hash key to retrieve a single record:!□If the selection condition involves an equality comparison on a key attribute with a primary index (or a hash key), use the primary index (or the hash key) to retrieve the record. 17!" #Algorithms for SELECT and JOIN Operations ■Implementing the SELECT Operation (cont’d.):!■Search Methods for Simple Selection:!■S4 Using a primary index to retrieve multiple records:!□If the comparison condition is >, ≥, <, or ≤ on a key field with a primary index, use the index to find the record satisfying the corresponding equality condition, then retrieve all subsequent records in the (ordered) file. !■S5 Using a clustering index to retrieve multiple records:!□If the selection condition involves an equality comparison on a non-key attribute with a clustering index, use the clustering index to retrieve all the records satisfying the selection condition.!■S6 Using a secondary (B+-tree) index:!□On an equality comparison, this search method can be used to retrieve a single record if the indexing field has unique values (is a key) or to retrieve multiple records if the indexing field is not a key.!□In addition, it can be used to retrieve records on conditions involving >,>=, <, or <=. (FOR RANGE QUERIES) 18!" #Algorithms for SELECT and JOIN Operations ■Implementing the SELECT Operation (cont’d.):!■Search Methods for Simple Selection:!■S7 Conjunctive selection:!□If an attribute involved in any single simple condition in the conjunctive condition has an access path that permits the use of one of the methods S2 to S6, use that condition to retrieve the records and then check whether each retrieved record satisfies the remaining simple conditions in the conjunctive condition.!■S8 Conjunctive selection using a composite index!□If two or more attributes are involved in equality conditions in the conjunctive condition and a composite index (or hash structure) exists on the


View Full Document

UT Dallas CS 6360 - CS-6360_ch19-QueryProcessing(1)

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 CS-6360_ch19-QueryProcessing(1)
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 CS-6360_ch19-QueryProcessing(1) 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 CS-6360_ch19-QueryProcessing(1) 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?