Data-Intensive Computing Systems Introduction to Query Processing Shivnath Babu 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 From R,S Answer Where R.A = “c”  S.E = 2  R.C=S.C B 2 D x How do we execute this query? Select B,D From R,S Where R.A = “c”  S.E = 2  R.C=S.C One idea Do Cartesian product Select tuples Do projection RXS Select B,D R.A R.B R.C S.C S.D S.E a 1 10 10 x 2 a . . 1 10 20 y 2 c . . 2 10 10 x 2 From R,S Where R.A = “c”  S.E = 2  R.C=S.C Bingo! Got one... Relational Algebra - can be used to describe plans Ex: Plan I B,D sR.A=“c” S.E=2  R.C=S.C X R S Relational Algebra Primer (Chapter 5, GMUW) Select: sR.A=“c” 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 sR.A=“c” S.E=2  R.C=S.C X R S OR: B,D [ sR.A=“c” S.E=2  R.C = S.C (RXS)] Another idea: Plan II B,D sR.A = “c” Select B,D R(A,B,C) From R,S Where R.A = “c”  S.E = 2  R.C=S.C sS.E = 2 S(C,D,E) natural join 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