Query Processing Declarative SQL Query → Query Plan NOTE: You will not be tested on how well you know SQL. Understanding the SQL introduced in class will be sufficient (a primer follows). SQL is described in Chapter 6, GMUW. Focus: Relational System (i.e., data is organized as tables, or relations)
SQL Primer We will focus on SPJ, or Select-Project-Join Queries Select <attribute list> From <relation list> Where <condition list> Example Filter Query over R(A,B,C): Select B From R Where R.A = “c” R.C > 10
SQL Primer (contd.) We will focus on SPJ, or Select-Project-Join-Queries Select <attribute list> From <relation list> Where <condition list> Example Join Query over R(A,B,C) and S(C,D,E): Select B, D From R, S Where R.A = “c” S.E = 2 R.C = S.C
R A B C S C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 Select B,D Answer B D From R,S Where R.A = “c” 2 x S.E = 2 R.C=S.C
• How do we execute this query? Select B,D From R,S Where R.A = “c” S.E = 2 R.C=S.C - Do Cartesian product One idea - Select tuples - Do projection
R X S R.A R.B R.C S.C S.D S.E Select B,D a 1 10 10 x 2 From R,S a 1 10 20 y 2 Where R.A = “c” S.E = 2 . R.C=S.C . Bingo! c 2 10 10 x 2 Got one... . .
Relational Algebra - can be used to describe plans Ex: Plan I B,D s =“c” R.A S.E=2 R.C=S.C X R S
Relational Algebra Primer (Chapter 5, GMUW) Select: s =“c” R.A R.C=10 Project: B,D Cartesian Product: R X S Natural Join: R S
Relational Algebra - can be used to describe plans Ex: Plan I B,D s =“c” R.A S.E=2 R.C=S.C X R S OR: [ s (RXS)] B,D R.A=“c” S.E=2 R.C = S.C
Another idea: Plan II B,D natural join s s R.A = “c” S.E = 2 R(A,B,C) S(C,D,E) Select B,D From R,S Where R.A = “c” S.E = 2 R.C=S.C
R S A B C s (R) s(S) C D E a 1 10 A B C C D E 10 x 2 b 1 20 c 2 10 10 x 2 20 y 2 c 2 10 20 y 2 30 z 2 d 2 35 30 z 2 40 x 1 e 3 45 50 y 3 Select B,D From R,S Where R.A = “c” S.E = 2 R.C=S.C
Plan III Use R.A and S.C Indexes (1) Use R.A index to select R tuples with R.A = “c” (2) For each R.C value found, use S.C index to find matching tuples (3) Eliminate S tuples S.E 2 (4) Join matching R,S tuples, project B,D attributes, and place in result
R S A=“c” C A B C I1 I2 C D E a 1 10 10 x 2 <c,2,10> <10,x,2> b 1 20 20 y 2 c 2 10 check=2? 30 z 2 d 2 35 output: <2,x> 40 x 1 e 3 45 50 y 3 c 7 15 next tuple: <c,7,15>
Overview of SQL query Query Processing parse parse tree Query rewriting Query statistics logical query plan Optimization Physical plan generation physical query plan execute Query result Execution
Example: Parse Tree <Query> <SFW> SELECT <SelList> FROM <FromList> WHERE <Cond> <Attribute> <SelList> <RelName> <FromList> <Cond> AND <Cond> B <Attribute> R <RelName> <Attr> <Op> <Const> D S R.A = “c” Select B,D From R,S <Attr> <Op> <Attr> Where R.A = “c” R.C=S.C R.C = S.C
Along with Parsing … • Semantic checks – Do the projected attributes exist in the relations in the From clause? – Ambiguous attributes? – Type checking, ex: R.A > 17.5 • Expand views
SQL query Initial logical plan parse parse tree Rewrite rules Query rewriting Logical plan statistics logical query plan Physical plan generation “Best” logical plan physical query plan execute result
Initial Logical Plan B,D Select B,D s From R,S R.A = “c” Λ R.C = S.C Where R.A = “c” R.C=S.C X R S Relational Algebra: [ s (RXS)] B,D R.A=“c” R.C = S.C
앞 20페이지만 표시됩니다. 전체를 보려면 자료를 다운로드하세요.
댓글이 없습니다. 첫 댓글을 남겨보세요!
댓글 (0)
댓글이 없습니다. 첫 댓글을 남겨보세요!