Query Processing and Optimization in Advanced Databases
Introduction to Query Processing and Optimization
In network and hierarchical database management systems (DBMSs), low-level procedural query language is generally embedded within a high-level programming language. In these systems, it is the programmer’s responsibility to select the most appropriate execution strategy for data retrieval.
With declarative languages such as SQL, the user specifies what data is required rather than how it is to be retrieved. This approach relieves the user of the burden of knowing what constitutes a good execution strategy.
Declarative languages give the DBMS more control over system performance.
There are two main techniques used for query optimization:
Heuristic rules that order operations within a query.
Comparing different strategies based on relative costs and selecting the one that minimizes resource usage.
Disk access is the dominant cost in query processing for centralized DBMS environments.
Definitions and Aims of Query Processing (QP) and Optimization (QO)
Query Processing refers to the activities involved in retrieving data from a database. The aims are to:
Transform a query written in a high-level language (e.g., SQL) into a correct and efficient execution strategy expressed in a low-level language that implements Relational Algebra (RA).
Execute the strategy to retrieve the required data.
Query Optimization is the activity of choosing an efficient execution strategy for processing a query. Because there are many equivalent transformations of the same high-level query, the aim is to choose the one that minimizes resource usage.
The general goal is to reduce the total execution time of the query, and it may also reduce the response time.
The problem is computationally intractable with a large number of relations; therefore, the strategy adopted is reduced to finding a near-optimum solution.
Example 21.1: Comparing Different Execution Strategies
Scenario: Find all Managers who work at a London branch.
SQL Query:
SELECT * FROM Staff s, Branch b WHERE s.branchNo = b.branchNo AND (s.position = ‘Manager’ AND b.city = ‘London’);
Equivalent Relational Algebra Strategies:
(1)
(2)
(3)
Assumptions for Cost Comparison:
1,000 tuples in Staff.
50 tuples in Branch.
50 Managers total.
5 London branches.
No indexes or sort keys available.
Results of intermediate operations are stored on disk.
Cost of the final write is ignored.
Tuples are accessed one at a time.
Cost (in disk accesses):
(1)
(2)
(3)
Cartesian product and join operations are much more expensive than selection. The third option significantly reduces the size of relations being joined together, leading to the lowest cost.
Phases of Query Processing
Query processing consists of four main phases:
Decomposition: Includes parsing and validation.
Optimization: Selecting the best plan based on heuristics or cost.
Code Generation: Producing executable code from the plan.
Execution: Running the generated code to produce output.
Workflow Breakdown:
Step 1: High-level language query (SQL) enters Query Decomposition.
Step 2: Relational algebra expression is produced. This and the following two steps happen at Compile Time.
Step 3: Query Optimization uses System Catalog, Database Statistics, and the RA expression to create an Execution Plan.
Step 4: Code Generation creates Generated Code.
Step 5: Runtime Query Execution uses the Generated Code and the Main Database to produce the Query Output at Runtime.
Dynamic versus Static Optimization
There are two times when the first three phases of query processing can be carried out:
Dynamic Optimization: Carried out every time the query is run.
Advantages: Information and statistics are up to date.
Disadvantages: Performance of the query is affected because optimization happens at runtime; time constraints may prevent finding the absolute optimum strategy.
Static Optimization: Carried out when the query is first submitted.
Advantages: Removal of runtime overhead and more time to find a truly optimum strategy.
Disadvantages: The chosen execution strategy may no longer be optimal when the query is eventually run if statistics change.
A hybrid approach can be used to overcome the disadvantages of both methods.
Query Decomposition Stages
The aims of decomposition are to transform a high-level query into a Relational Algebra query and verify that the query is syntactically and semantically correct.
Stages of Decomposition:
Analysis: The query is analyzed lexically and syntactically using compiler techniques. The system verifies that relations and attributes exist and that operations are appropriate for the object type.
Example of Rejection:
SELECT staff_no FROM Staff WHERE position > 10;is rejected becausestaff_nois not defined for the Staff relation (should bestaffNo) and the comparison>10is incompatible withposition(a variable character string).The query is then transformed into an internal representation, typically a Relational Algebra Tree (RAT).
Normalization: Converts the query into a normalized form for easier manipulation. Predicates can be converted into:
Conjunctive Normal Form: e.g.,
Disjunctive Normal Form: e.g.,
Semantic Analysis: Rejects queries that are incorrectly formulated or contradictory.
A query is incorrectly formulated if components do not contribute to the generation of the result.
A query is contradictory if its predicate cannot be satisfied by any tuple.
Accuracy check algorithms exist mainly for queries without disjunction and negation.
Relation Connection Graph: A node is created for each relation and the result. Edges represent joins or projections. If the graph is not connected, the query is incorrectly formulated.
Normalized Attribute Connection Graph: A node is created for each attribute or constant 0. Edges represent joins or selections. Weights are assigned based on inequality conditions (e.g., results in weight ; results in weight from ). A cycle with a negative valuation sum indicates a contradictory query.
Simplification: Detects redundant qualifications, eliminates common sub-expressions, and uses idempotency rules of boolean algebra to make the query more efficient. It considers access restrictions, view definitions, and integrity constraints.
Query Restructuring: The final stage of decomposition aimed at providing a more efficient implementation.
Internal Representation: Relational Algebra Tree
Elements of a Relational Algebra Tree:
Leaf Nodes: Represent base relations.
Non-leaf Nodes: Represent intermediate relations produced by RA operations.
Root: Represents the final query result.
Direction: The sequence is directed from the leaf nodes up toward the root.
Transformation Rules for Relational Algebra Operations
Selection Rules:
Cascade of Selection:
Commutativity of Selection:
Projection Rules:
Cascade of Projection: . Only the last projection in a sequence is required.
Selection and Projection:
Commutativity: If predicate involves only attributes in the projection list , then:
Join Rules:
Commutativity of Theta Join (and Cartesian Product): and . This also applies to Equijoins and Natural Joins.
Commutativity of Selection and Theta Join/Cartesian Product: If selection predicate involves only attributes of one relation (R), then: .
If predicate is conjunctive () where involves R and involves S:
Commutativity of Projection and Theta Join/Cartesian Product: If projection list and join condition features only attributes of , then: . If the join condition contains attributes not in L, a final projection is required: .
Set Operations:
Commutativity of Union and Intersection: and . Set difference is NOT commutative.
Commutativity of Selection and Set Operations: . This applies to and as well.
Commutativity of Projection and Union: .
Associativity: Union, Intersection, Cartesian product, and Natural Join are always associative. . Theta Join is associative if the condition involves only attributes from S and T: .
Heuristical Processing Strategies
Perform Selection operations as early as possible.
Keep predicates on the same relation together.
Combine Cartesian product with a subsequent Selection into a Join operation if the predicate represents a join condition.
Rearrange leaf nodes using associativity so that nodes with the most restrictive selections are executed first.
Perform Projection as early as possible and keep projection attributes on the same relation together.
Compute common expressions once. If a result is reuseable and not too large, store and reuse it, which is useful for querying views.
Database Statistics for Cost Estimation
Statistics are stored in the system catalog to assist in cost estimation. Keeping these current can be problematic; updates may occur periodically (e.g., nightly) or when the system is idle.
Statistics for Relation R:
: Number of tuples in R.
: Blocking factor of R.
: Blocks required to store R.
Statistics for Attribute A of Relation R:
: Number of distinct values for attribute A.
, : Minimum and maximum possible values for attribute A.
: Selection cardinality; the average number of tuples satisfying an equality condition on A.
Statistics for Multilevel Index I on Attribute A:
: Number of levels in index I.
: Number of leaf blocks in index I.
Selection Operation Strategies and Cost Estimates
Linear Search (Unordered file, no index):
Equality on key attribute:
Other conditions:
Binary Search (Ordered file, no index):
Predicate on key attribute A:
General estimate:
Equality of Hash Key: Expected cost is 1 (assuming no overflow).
Equality Condition on Primary Key (Primary Index):
Inequality Condition on Primary Key:
Equality Condition on Clustering (Secondary) Index:
Equality Condition on Non-Clustering Index:
Inequality Condition on Secondary B+-Tree Index:
Composite Predicates (Conjunction): If one attribute is indexed/ordered, use that strategy and check retrieved records; or use a composite index; or use record pointers from multiple secondary indexes.
Selection with Disjunction: If any term requires a linear search, the whole selection uses a linear search. Optimization is possible only if every term has an index/sort order.
Join Operation Strategies and Cost Estimates
Cardinality Estimation for Join (Relation T = R join S):
Cartesian Product:
If A is key of R:
If B is key of S:
Otherwise: or
Block Nested Loop Join:
Basic cost:
Using database buffer ():
If R fits in buffer:
Indexed Nested Loop Join:
If join attribute A in S is the Primary Key:
Sort-Merge Join:
Most efficient for Equijoins when relations are sorted. If both are sorted: .
If R needs sorting, add:
Hash Join:
Partitions relations based on a hash function. Estimated cost:
Projection and Pipelining
Projection involves removing attributes and eliminating duplicate tuples.
Duplicate elimination is required if the projection does not include a key, using:
Sorting:
Hashing: Partitioning and elimination phase. Cost involves .
Cardinality of Projection (S = projection of R):
If key is included:
Single non-key attribute:
Otherwise:
Processing Models:
Materialization: Output of one operation is stored in a temporary relation.
Pipelining (On-the-fly): Results passed directly between operations without temporary storage, saving disk I/O. Usually implemented as separate processes or threads.
Tree Structures:
Left-deep trees: Appeal to QO because inner relations are always base relations. This reduces the search space for optimum strategy and allows for dynamic processing.