Query Processing & Optimization Notes
# Query Processing & Optimization ## Introduction * Query processing and optimization are crucial for database management systems. * Efficiency in query processing is vital for DBMS performance. * Query optimization techniques aim to select efficient execution plans, minimizing runtime and resource usage (disk I/O, CPU time, etc.). ## Query Processing * Query processing transforms high-level queries into efficient execution plans in a low-level language. * The query processor chooses the best plan to respond to database requests. * Upon receiving a query, the database system undergoes a series of query compilation steps before execution. ## Relational Algebra Expression Example * Consider the query: "Find the names of all customers who have an account at any branch located in Brooklyn." * Relational algebra expression: * Optimized expression: ## Equivalent Transformations * Generating query-evaluation plans involves: * Generating logically equivalent expressions. * Estimating the cost of each evaluation plan. * The query optimizer utilizes equivalence rules to transform expressions into logically equivalent ones. * Equivalence rules allow replacing one expression form with another logically equivalent one. ## Pictorial Representation of Equivalences * Illustrations depict how expressions (E1, E2, E3) can be transformed based on different equivalence rules. ## Example Instance * Using relations branch, account, and depositor, the expression, ## General Query Processing Flow * **Users** submit queries in high-level languages (e.g., SQL). * **Query Decomposer**: * Translates SQL into relational algebra using equivalency, idem-potency, and transformation rules from a global database dictionary. * Performs scanning, parsing, and validation to ensure query syntax is correct and that relations/attributes exist in the database catalog. * **Syntax Analyzer**: Checks syntax and verifies relations/attributes used in the query are defined in the database. * **Query Optimizer**: * Substitutes equivalent expressions to improve efficiency. * **Cost Module**: * Uses statistical data and estimation formulas. * **Join Manager** * **Query Code Generator**: * Generates code to execute the query. * Estimates access plan costs and selects the optimal plan. * **Runtime Database Processor**: * Executes the code. * **Output**: * Query result is outputted to user. ## Syntax Analyzer * The syntax analyzer parses the query into tokens and verifies compliance with language grammar rules. * If errors are found, the query is rejected, and an error code with explanation is returned. ## Simple Grammar Form * QUERY = SELECT CLAUSE + FROM CLAUSE + WHERE CLAUSE * SELECT\_CLAUSE = 'SELECT' + * FROM\_CLAUSE = 'FROM' + * WHERE\_CLAUSE = 'WHERE' + VALUE1 OP VALUE2 * VALUE1 = VALUE / COLUMN\_NAME * VALUE2 = VALUE / COLUMN\_NAME * OP = +, -, /, * ## Example Query * ```sql SELECT COLUMN1, COLUMN2, COLUMN3, COLUMN4 FROM TEST1 WHERE COLUMN2 > 50000 AND COLUMN3 = 'DELHI' AND COLUMN4 BETWEEN 10000 AND 80000; ``` ## Query Decomposition * Transforms a high-level query into a relational algebra query and checks its syntactic and semantic correctness. * Decomposes the query into query blocks, which are the basic units. * Nested queries are identified as separate query blocks. ## Query Decomposition Process * SQL (Relational Calculus Query) is transformed through: * **Query Analysis** * **Query Normalization** using Equivalence Rules * **Semantic Analysis** * **Query Simplifier** using Idempotency Rules * **Query Restructuring** using Transformation Rules * Resulting in Algebraic Expressions (Relational algebra query) ## Query Analysis * Lexical and syntactical analysis is performed to find syntax errors, similar to conventional programming compilers. * A syntactically legal query is validated against the system catalog. * Ensures that database objects (relations and attributes) referred to by the query are defined in the database. * Verifies the correctness of relationships between attributes and relations according to the system catalog. ## Query Tree Example * A visual representation of a query and its decomposition into operations. * Shows the flow of data and operations, with leaf nodes representing base relations or data sources.
## Query Tree Example 2 * SELECT views From Channel Where Views > 1000; * Shows the flow of data and operations, with leaf nodes representing base relations or data sources. * Using formulas RAσp1:views>1000(channel) → πviews (views>1000 ## Query Normalization * The primary goal is to avoid redundancy. * Converts the query into a normalized form that can be more easily manipulated. * Applies equivalency rules to simplify projection and selection operations.
## Query Normalization Forms * Predicate is converted into one of the following normal forms: * **Conjunctive Normal Form (CNF)**: Sequence of conjuncts connected by 'AND' operator. Each conjunct contains terms connected by 'OR'. Example: (A OR B) AND (A OR C) * **Disjunctive Normal Form (DNF)**: Sequence of disjuncts connected by 'OR' operator. Each disjunct contains terms connected by 'AND'. Example: (A AND B) OR (A AND C)
## Semantic Analyzer * Reduces the number of predicates by rejecting incorrect or contradictory queries. * A query is incorrectly formulated if its components do not contribute to the result. * A query is contradictory if its predicate cannot be satisfied by any tuple in the relation.
## Query Simplifier * Detects redundant qualifications, eliminates common sub-expressions, and transforms sub-graphs to more efficiently computed forms. * Integrity constraints, view definitions, and access restrictions are introduced. * The final form of simplification is obtained by applying the idempotence rules of Boolean Algebra.
## Idempotence Rules of Boolean Algebra | Rule | Description | Rule Format | | --- | --- | --- | | 1. | PRED AND PRED → PRED | | | 2. | PRED AND TRUE → PRED | | | 3. | PRED AND FALSE → FALSE | | | 4. | PRED AND NOT (PRED) → FALSE | | | 5. | PRED1 AND (PRED1 OR PRED2) → PRED1 | | | 6. | PRED OR PRED → PRED | | | 7. | PRED OR TRUE → TRUE | | | 8. | PRED OR FALSE → PRED | | | 9. | PRED OR NOT (PRED) → TRUE | | | 10. | PRED1 OR (PRED1 AND PRED2) → PRED1 | |
## Query Restructuring * Reconstructs the query for more efficient implementation. * Transformation rules convert relational algebra expressions into equivalent, more efficient forms. * The query becomes a relational algebra program consisting of operations on relations. ## Query Optimization * Chooses an efficient execution strategy. * Minimizes resource usage (I/O and CPU time). * Validates user privileges during the validation phase. * Uses existing statistics for tables and columns (number of rows, indexes, etc.). ## Query Optimization Inputs * Relational algebra query tree from the query simplifier. * Estimation formulas to determine the cardinality of intermediate result tables. * A cost model. * Statistical data from the database catalog. * Output: Execution plan in the form of an optimized relational algebra query. ## Query Optimization Considerations * A query has many possible execution strategies. * Basic issues in query optimization: * How to use available indexes. * How to use memory. * Determining the order of joins. * Aim is a reasonable, not always optimal, approach. ## Techniques for Implementing Query Optimization * Heuristic rules. * Systematic estimation of the cost of different execution strategies. ## Query Optimization Process * **Query Decomposer** produces simplified relational algebra query trees. * **Query Optimizer** receives the query trees, estimation formulas, and statistical data from the database catalog. * The **Cost Model** helps estimate the cost of different execution plans. * The **Execution (Action) Plan Generator** and **JOIN Manager** generate execution plans in the form of optimized relational algebra queries. ## Structure of Query Evaluation Plan * An evaluation plan defines the algorithm for each operation and how execution is coordinated. ## References * List of resources used to prepare the lecture.