Query Processing

Kamal Karlapalem
Query Processing Steps
• Input: SQL query Output: Result
• SQL query is scanned, parsed, and validated
• The scanner identifies language tokens in the text of the query, while the parser
checks the correctness of the query syntax
• The query is validated (by accessing the system catalog) whether the attribute names
and relation names are valid
• An internal representation (tree or graph) of the query is created
• The DBMS selects an execution strategy (from more than one) for executing the
query by accessing internal database files
Steps in Query Processing
SQL Query or any high language query

Scanning, Parsing and Validating

SQL Operators
• Select
Intermediate form of Query • Join
• Project
Query Optimizer
• Set
Execution Plan • Aggregate
• Group by
Query Code Generator/Function Calls • Having
Execution Code/Functions
• Order by
• Limit
Runtime Database Processor

Result of Query
Heuristic Optimization of Query Trees
• A query tree corresponds to a relational algebra expression
• Leaf nodes are relations/tables
• Non-leaf nodes are relational algebra operations
• The execution of query tree consists of executing non-leaf nodes
whenever the data in immediate descendants of the node are
available
• It can be done in a pipeline mode (if possible) or step by step manner
 Example
• Find last names of Employees born after 1957 who work on a project
named ‘Aquarius’
SELECT LNAME FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME=‘Aquarius’ AND PNUMBER=PNO AND ESSN=SSN AND
BDATE>’DEC-31-1957’;

⌅LNAME
Canonical
Query Tree 𝝈 PNAME=‘Aquarius’ and Pnumber=PNO and ESSN=SSN and Bdate>’Dec-31-1957’
All queries
X
start like
this X

PROJECT
EMPLOYEE WORKS_ON
 Example
⌅LNAME

• Move selects on attributes of relation

closer to the relation
𝝈 Pnumber=PNO
• Move Join selections closer to the
cartesian products X

𝝈 ESSN=SSN

X 𝝈 PNAME=‘Aquarius’

𝝈 Bdate>’Dec-31-1957’
PROJECT
EMPLOYEE WORKS_ON
 Example
⌅LNAME

• Replace cartesian product followed

by selection with join condition with
⨝ Pnumber=PNO
join

⨝ ESSN=SSN

𝝈 PNAME=‘Aquarius’

𝝈 Bdate>’Dec-31-1957’
PROJECT
EMPLOYEE WORKS_ON
 Example
⌅LNAME

• Change the join order – perform ⨝ ESSN=SSN

Project join with works_on first and ⨝ Pnumber=PNO
then with employee
𝝈
⨝ Pnumber=PNO

𝝈 Bdate>’Dec-31-1957’

𝝈 PNAME=‘Aquarius’
EMPLOYEE
PROJECT WORKS_ON
 Example
⌅LNAME
• Puh the Projects to as far below as
possible so that only the required ⨝ ESSN=SSN
columns will come to the next
operation
⌅ESSN
⌅SSN,NAME
⨝ Pnumber=PNO

⌅PNO 𝝈 Bdate>’Dec-31-1957’
⌅ESSN,PNO
𝝈 PNAME=‘Aquarius’
EMPLOYEE
PROJECT WORKS_ON
 Example Final Result ⌅LNAME

Final Execution
• Temp Result ←
⨝ ESSN=SSN
Execution of Tree 2
Tree 1 ⌅ESSN
• Final Result ←
execution of ⌅SSN,NAME
Tree 2
Temp Result ⨝ Pnumber=PNO
Tree 1 ⌅PNO 𝝈 Bdate>’Dec-31-1957’
⌅ESSN,PNO
𝝈 PNAME=‘Aquarius’ EMPLOYEE

PROJECT WORKS_ON
 Example ⌅LNAME Final Result

TempResult ⨝ Pnumber=PNO ⨝ ESSN=SSN

Tree 2

Tree 1 ⌅Pnumber
⌅ESSN,PNO ⌅SSN,NAME
TempResult
𝝈 PNAME=‘Aquarius’
𝝈 Bdate>’Dec-31-1957’
PROJECT WORKS_ON

EMPLOYEE

TempResult ← SPJ(PROJECT, PNumber, PNAME=‘Aquarius’, WORKS_ON, ESSN, PNo, NULL, 1,Pnumber, Pno)
Result ← SPJ(TempResult, NULL, NULL,Employee, SSN, NAME, Bdate>’DEC-31-1957’, 1, ESSN,SSN)
Transformation Rules – Set Theory
1. Select operation
• σc1 AND c2 AND … AND cn(R) ≡ σc1 (σc2 (…(σcn(R))…))
• σc1 (σc2(R)) ≡ σc2(σc1(R))
2. Project
• πList1(πList2 (…(πListn(R))…)) ≡ πList1(R)
• πA1, A2, … , An(σc (R)) ≡ σc (πA1, A2, … , An(R))
3. Joins
• R ⨝c S ≡ S ⨝c R
• RXS≡SXR
4. Select distribution over join
• σc (R ⨝ S) ≡ (σc (R)) ⨝ S
• σc (R ⨝ S) ≡ (σc1(R)) ⨝ (σc2(S))
Transformation Rules – Set Theory
1. Project distribution over join
• πL (R ⨝c S) ≡ (πA1, … , An(R)) ⨝c (πB1, … , Bm (S))
• πL (R ⨝c S) ≡
πL((πA1, … , An, An+1, … , An+k(R)) ⨝c (πB1, … , Bm, Bm+1, … , Bm+p (S)))
2. Set operations (θ can be ⋃, ⋂, ⨝, X)
• RθS≡SθR
• R θ (S θ T) ≡ (R θ S) θ T
3. Select and Set operations
• σc (R θ S) ≡ (σc (R)) θ (σc (S))
4. Project and Set Operations
• πL (R ∪ S) ≡ (πL (R)) ∪ (πL (S))
Transformation Rules – Set Theory
1. Select over X to join
• (σc (R × S)) ≡ (R ⨝c S)
2. Select over set difference
• σc(R − S) = σc (R) – σc ( S) = σc (R) - S
3. Slect over intersection
• σc (R ∩ S) = σc (R) ∩ S
4. Trivial transformations
• If S is empty R U S = R
Heuristic Algebraic Optimization Algorithm
1. Break up select statements to individual select operations
2. Move selects as much down the tree as possible. Join Selections stop at
Cartesian product condition
3. Use commutivity and associativity to rearrange tree to get smaller intermediate
results first
4. Combine Cartesian product with select to form joins
5. Apply cascading of project to as far down the tree as possible.
6. Identify subtrees that represent groups of operations that can be executed by a
single algorithm