#Practical Session 8 - Algorithms for Query Processing & Optimisation ###By Dr Edmund Sadgrove ### University of New England --- ## Reading * Chapter 18 from ***Fundamentals of Database Systems*** by Elmazri and Navathe --- ## Summary * Introduction * Query Tree Notation * Query Tree Optimisation * Query Transformation Rules * An Algebraic Query Optimisation Algorithm ## Introduction * Recall query tree notation can be used for the conceputal optimisation of relational queries. We will recap some of this weeks lectures and look at a few examples. ## Query Tree Notation * A **Query Tree** is a data structure that corresponds to a relational algebra expression. * The inputs to the relation are the leaf nodes. * The RA operations are represented by the internal nodes of the tree. * **Example**: $$ \pi_{pnumber, dnum, lname, address, bdate} ((\sigma_{plocation = 'Stafford'} (PROJECT)) $$ $$ \bowtie_{dnum = dnumber} (DEPARTMENT) $$ $$ \bowtie_{mgrssn = ssn} (EMPLOYEE) $$ * **Example (a)** - *Query Tree*: * The **leaves** represent the **relations**. * **Operations** are represented by **nodes**. * The **query tree** also represents an order of operations of the RA expression. * Bottom up, the order can be derived. * SQL: ```sql SELECT P.pnumber, P.dnum, E.lname, E.address, E.bdate FROM PROJECT as P, DEPARTMENT as D, EMPLOYEE as E WHERE P.dnum = D.dnum AND D.mgrssn = E.ssn AND P.plocation = 'Stafford' ``` * **Example (c)** - *Query Graph*: * The **query graph** does not indicate the order of the operations. * **Selection** and **Join** conditions are represented by edges. * **Nodes** represent the **relations** involved. * Constant nodes (**double ovals**/circles): * Represent **constant values** (a result of selection). * **Query trees** are the preferred representation as the optimiser needs to show the order of operations for query executions. ## Query Tree Optimisation * Multiple different **RA** expressions (and there **query trees**) can be equivalent. * Yielding the same results, but some will be more efficient than others. * The query **parser** will generate an initial tree: * This is depicted in Figure 19.4 (b). * The 'X' symbols represent **cartesian product**. * This is very inefficient. * This is a standard form that can be generated from the SQL query. * Initial canonical query tree (a): * **Optimisation** process involves moving the operations down the query tree. 1. Move the `SELECT` operations down the tree (b). 2. Re-organise the tree: the most selective operations appear first (c). 3. **Cartesian product** operations are replaced with **joins** (d). 4. Then the **projections** are moved down the tree (e). * A motivating Example: ```sql SELECT lname FROM EMPLOYEE, WORKS_ON, PROJECT WHERE pname = 'Aquarius' AND pnumber=pno AND essn=ssn AND bdate > '1957-12-31' ``` * Steps 2, 3 and 4 of optimizing the query tree: * The query optimiser must know which transformations can be performed while still preserving equivalence. * Transformation rules can be used to perform optimisations of RA expressions, these include: * **Commutativity**: * Operations who's order can be changed, in and outside parathesis. $$ \(\sigma_{c_1} (\sigma_{c_2}(R)) ≡ \sigma_{c_2} (\sigma_{c_1}(R))\) $$ * **Associativity**: * Where the emphasis on individual operations in an expression can be changed. $$ \((R\ \theta\ S)\ \theta\ T \equiv R\ \theta\ (S\ \theta\ T)\) $$ * **Cascades**: * Conditions that can be broken up into individual operations. $$ \(\sigma_{c_1\ AND\ c_2\ AND ..\ AND\ c_n}(R) ≡ \sigma_{c_1}(\sigma_{c_2}(...(\sigma_{c_n}(R))...)) \) $$ ## Query Transformation Rules * **Cascade** of **σ** A **conjunctive** selection conditions: * Can be broken up into a cascade of individual **σ** operations: $$ \(\sigma_{c_1\ AND\ c_2\ AND ..\ AND\ c_n} (R) ≡ \sigma_{c_1}(\sigma_{c_2}(...(\sigma_{c_n}(R))...)) \) $$ * **Commutativity** of σ. The σ operation is commutative: * Same result regardless of order: $$ \( \sigma \_{c_1}(\sigma \_{c_2}(R)) ≡ \sigma_{c_2}(\sigma_{c_1}(R)) \) $$ * **Cascade** of **π**: * In a cascade (sequence) of π operations, all but the last one can be ignored: $$ \( \pi_{List_1} (\pi_{List_2}(...(\pi_{List_n} (R))...)) ≡ \pi_{List_1} (R)\) $$ * **Commuting σ with π**: * If the selection condition inolves Attributes `\(A_1, . . . , A_n\)` in the projection list, * The two operations can be commuted: $$ \( \pi _{A_1, A_2, ..., A_n} (\sigma_c (R)) ≡ \sigma_c (\pi \_{A_1, A_2, ..., A_n}(R))\) $$ * **Commutativity** of `\(\bowtie\)` (and ×). * The **join** operation is commutative, as is the **×** operation: $$ \(R \bowtie_c S ≡ S \bowtie_c R\) $$ $$ \(R × S ≡ S × R\) $$ * Note: the order of the attributes may be different in the result * **Commuting σ** with **⋈** (or **×**): * Conditions on the attributes of one relation can be commuted. $$ \(\sigma_c (R \bowtie S) ≡ (σ_c (R)) \bowtie S\) $$ * Conditions on individual relations can also be communted. $$ \(\sigma_c (R \bowtie S) ≡ (\sigma_{c_1} (R)) \bowtie (\sigma_{c_2} (S))\) $$ * The same rules apply if the is replaced by a **×** operation. * **Commuting π** with **⋈** (or **×**): * Projections on attributes of individual relations can be communited. $$ \(\pi_L (R \bowtie_c S) ≡ (\pi_{A_1, ..., A_n} (R)) \bowtie_c (\pi{B_1, ...,B_m}(S))\) $$ * If the join condition (**c**) includes additional attributes not in *L*: * These must be added to the projection list. * **Set operations** (excluding MINUS) are **commutative**. * JOIN, CARTESIAN PRODUCT, UNION and INTERSECTION are all individually **associative**: $$ \((R\ \theta\ S)\ \theta\ T \equiv R\ \theta\ (S\ \theta\ T)\) $$ * Theta represents any of these operations. * **Commuting σ** with set **operations**. * The σ operation commutes with ∪, ∩ and −: $$ \( \sigma_c (R\ θ\ S) ≡ (\sigma_c (R))\ θ\ (\sigma_c (S)) \) $$ * The **π operation commutes** with **∪**: $$ \(\pi_L (R ∪ S) ≡ (\pi_L (R)) ∪ (\pi_L (S))\) $$ * Finally we can Convert a **(σ, ×)** sequence into **`\(\bowtie\)`**. $$ \((\sigma_c (R × S)) ≡ (R \bowtie_c S)\) $$ ## Algorithm * We can now apply these transformations to our queries to optimise for execution. * This **algorithm** outline 6 Broad Stages: * **Step 1**: * We use rule (1) to break up the **conjunctive** conditions within any select operations. * **Step 2**: * The next step is to apply the **commutativity** of the **SELECT operation** (rule 2). * The select operations can be moved down the query tree as far as possible. * SELECT operations with attributes from a single table can be moved to a **leaf node**. * SELECT operations that involve attributes from multiple tables represent a **join condition**. * These can only be placed after the tables have been combined. * **Step 3**: * Next we use the rules for **commutativity** and **associativity** of the binary operations. * The SELECT operations with the **lowest selectivity** are moved so they **executed first**. * This should be done so that the select operation is only carried out on already joined relations. * If the SELECT involves attributes from multiple tables. * **Step 4**: * **CARTESIAN PRODUCT** operations are combined SELECT operations to produce a JOIN (rule 12). * **Step 5**: * Using the rules regarding the PROJECT operation can be applied. * The **projection** operations should be pushed down the tree as far possible. * Only the attributes required in the final result or subsequent operations should be retained after each project. * **Step 6**: * Identify subtrees that represent groups that can be executed by a single algorithm. * Figure 19.5 uses this approach to optimise the example shown. * The main idea behind this algorithm is reduce the size of the intermediate results as early as possible. --- ## Exercises for You Provide a query tree optimisation based on the example relation below and the query for each exercise: Relations: * Student(SID, Name, Major, Year) * Enroll(SID, CID, Term, Grade) * Course(CID, Title, Dept, Credits) * Teaches(IID, CID, Term) * Instructor(IID, IName, Dept) --- ### Exercise 1. Return Student.Name for CS students in Year ≥ 3 who earned HD in term '2025-S1'. Relational Algebra: $$ \pi_{name}((\sigma_{Major='CS' AND Year≥3}(Student)) $$ $$ \bowtie_{Student.SID = Enroll.SID} (\sigma_{Term='2025-S1' AND Grade='HD'}(Enroll))) $$ ### Exercise 2. Return (Student.Name, Course.Title) for CS students in Year ≥ 3 who earned HD in term '2025-S1' in a CS course with Credits ≥ 6. Relational Algebra: $$ \pi_{name, Title} (( \sigma_{Major='CS' AND Year>=3}(Student)) $$ $$ \bowtie_{Student.SID = Enroll.SID}( \sigma_{Term='2025-S1' AND Grade='HD'}(Enroll)) $$ $$ \bowtie_{Enroll.CID = Course.CID} (\sigma_{Dept='CS' AND Credits>=6}(Course))) $$ ### Exercise 3. Return (Student.Name, Course.Title, Instructor.IName) for CS students in year ≥ 3 who received grade = 'HD' in term = '2025-S1' for a CS department course with credits ≥ 6 taught by a CS department instructor. Relational Algebra: $$ \pi_{Student.Name, Course.Title, Instructor.IName} ( $$ $$ \sigma_{Student.Major='CS' AND} $$ $$ _{Student.Year≥3 AND} $$ $$ _{Enroll.Term='2025-S1' AND} $$ $$ _{Enroll.Grade='HD' AND} $$ $$ _{Course.Dept='CS' AND} $$ $$ _{Course.Credits≥6 AND} $$ $$ _{Instructor.Dept='CS'}( $$ $$ (((Student \bowtie_{Student.SID = Enroll.SID} Enroll) $$ $$ \bowtie_{Enroll.CID = Course.CID} Course) $$ $$ \bowtie_{Course.CID = Teaches.CID AND Enroll.Term = Teaches.Term} Teaches) $$ $$ \bowtie_{Teaches.IID = Instructor.IID} Instructor)) $$ ---