Fundamentals of Database Systems - Query Optimization

Fundamentals of Database Systems - Query Optimization

• Query optimization is conducted by a query optimizer in a DBMS
• The goal is to select the best strategy for query execution
• Optimization is based on available information
• Most relational database management systems (RDBMS) use a tree structure to represent a query internally

Query Trees and Heuristics

• A query tree is a graphical representation of how a query is executed

• Initial query representation is generated by scanners and parsers

• The representation is optimized using heuristic rules

• Finally, the query execution plan is developed, executing operations based on available access paths and files

• A heuristic rule example: applying SELECT and PROJECT operations before JOIN operations minimizes the size of files that need to be joined

• Another example: query trees represent relational algebra expressions while query graphs represent relational calculus expressions

Query Trees and Query Graphs (Q2 Example)

• Figure 19.1 displays query trees corresponding to a relational algebra for query Q2.
• The initial (canonical) query tree for SQL query Q2, is an example
• Query graphs are the counterpart for relational calculus expressions for Q2

Query Trees and Heuristics (continued)

• The query tree shows specific operations in a particular execution order and is preferable to the query graph scheme
• Relational nodes are displayed in single circles in a query graph
• Constants are represented by constant nodes
• Conditions are represented as edges. and attributes to be retrieved are shown in brackets.

Heuristic Optimization of Query Trees

• Multiple different query trees can be used in the same query to get the same results
• Figure 19.1b shows the initial tree for query Q2; it is inefficient and is not executed
• Instead the optimizer transforms into an equivalent final query tree

Query Transformation Example

• Figures 19.2(a)-(e) demonstrate steps in converting a query tree through optimization
• Operations like moving select operations down the query tree
• More restrictive SELECT operations should be applied before other similar operations
• Converting Cartesian products and SELECT to JOIN operations

General Transformation Rules for Rational Algebra Equations

• Transformations are helpful in query optimization. Examples:
• Cascading operations by breaking down a selection condition into individual operations
• Commutativity of σ (selection) and π (projection) operations

Summary of Heuristics for Algebraic Optimization

• Execute SELECT and PROJECT operations as early as possible to reduce tuple and attribute counts.
• Apply operations that reduce intermediate result sizes.
• Execute the most restrictive SELECT and JOIN operations before other similar operations

Choice of Query Execution Plans

• Materialized evaluation: temporarily saving the result of an operation as a separate relation
• Pipelined evaluation: directing the result of an operation directly to the next query sequence operation

Nested Subquery Optimization

• Query optimization, also called unnesting, removes nested queries and combines inner and outer queries.
• Queries connected with 'IN' or 'ANY' can always be restructured into a single query block
• Creating temporary result tables from subqueries and using them in joins allows for alternate query techniques.

Subquery (View) Merging Transformation

• Inline views and FROM clause subqueries can be merged to generate a view merging operation
• Views containing select-project-join operations are considered simple views subject to view merging

Subquery (View) Merging Transformation (continued)

• Delaying Group By after joins reduces data subjected to grouping when selectivity is low
• Performing Group By early reduces the amount of data subjected to subsequent joins
• The optimizer determines if to merge GROUP-BY views based on estimated cost.

Materialized Views

• Database views are defined as queries
• Materialized views store the results of queries, potentially permanently or temporarily
• In optimization, using materialized views avoids much of the original query’s computation
• Materialized views are easier to read when needed than recomputing values from scratch

Incremental View Maintenance

• View updates are made incrementally by accounting for changes since the last update
• Examples of operations: Join, Selection, Projection, Intersection, and Aggregation

Use of Selectives in Cost-Based Optimization

• Query optimizer estimates and compares costs of execution strategies to choose the lowest cost strategy
• Compiled queries are well suited and interpreted queries are done at run time
• Cost estimates slow down response time.

Use of Selectives in Cost-Based Optimization (continued)

• For a given query subexpression, multiple equivalence rules apply
• A cost metric is used to determine space and time requirements
• Optimization involves keeping cheapest alternatives and pruning more expensive ones, using appropriate search strategies.
• Scope is for a query block
• Global optimization covers multiple query blocks

Cost Components for Query Execution

• Cost components for query execution include access cost to secondary storage, disk storage cost, computation cost, memory usage cost, and communication cost

Catalog Information Used in Cost Functions

• DBMS catalogs store information used for optimizer calculations.
• Information stored includes file size, organization, levels of multilevel indexes, distinct values in attributes, and attribute selectivity (selection cardinality).
• Selection cardinality estimates the number of records that satisfy a specific condition on an attribute.

Histograms

• Tables or data structures record data distribution.
• RDBMS stores histograms for important attributes

Cost Functions for SELECT Operation

• Notation for cost formulas.
• Examples for cost functions: Linear Search (S1), Binary Search (S2), Using primary indexes (S3a),hash keys (S3b).,Ordering indexes (S4), clustering indexes (S5), secondary indexes (S6).

Cost Functions for SELECT Operation (continued)

• Dynamic programming cost-based optimization approach.
• Subproblems are solved just once when a problem's subproblems all have subproblems.

Cost Functions for the JOIN Operation

• Cost Functions for the join operation involve estimating the resulting file size from the join operation
• Join selectivity is the ratio of the size of the resulting file to the size of the Cartesian product files used for joining
• Simple formulas for determining join selectivity and cardinality are also provided

Cost Functions for the JOIN Operation (continued)

• J1:Nested-loop join
• J2:index-based nested loop join
• J3:Sort-merge join
• J4:Partition-hash join
• Special consideration for semi-join, anti-join functions are also discussed.

Cost Functions for the JOIN Operation (continued)

• Multirelation queries and their join ordering choices, including left-deep, right-deep, and bushy join trees
• Physical optimization involves determining the execution decision at the physical level.
• Cost-based physical optimization techniques like top-down and bottom-up approaches are outlined.
• Heuristics make some cost optimizations unnecessary.
• For selections, use index scans whenever possible
• Left-deep trees generally preferred, working well for common algorithms, and able to generate fully pipelined plans

Example to Illustrate Cost-Based Query Optimization

• Example of query Q2 and its query tree from Figure 19.1(a), considering information about the relations.

Additional Issues Related to Query Optimization

• Size estimation for other operations: Projection, Aggregation, Outer join
• Query plan caching (saving execution plans for later use).
• Top-k results, and limits strategy generation.

An Example of Query Optimization in Data Warehouses

• Star transformation optimization attempts to minimize required data set from the fact table.
• Techniques include classic star transformation, bitmap index star transformation, and joining back.

Overview of Query Optimization in Oracle

• Oracle's physical optimizer is cost-based and scopes a single query block.
• Estimated cost calculation is done using statistics about objects, resources, and memory required.
• Global query optimizer integrates logical and physical optimization phases.
• Adaptive optimization uses a feedback loop to enhance previous decisions.

Overview of Query Optimization in Oracle (continued)

• Array processing and hints are described. Application developer specified hints are embedded within the SQL statement. Hints include types like access path, join order, join method and enable/disable transformations.
• Outline used to preserve execution plans.
• SQL plan management is crucial

Semantic Query Optimization

• Semantic optimization uses database schema constraints to effectively modify a query into a more efficient one.

Summary

• Query trees are vital for query optimization.
• Heuristics improve query efficiency.
• Query trees are reorganized for better execution.
• Pipelining and materialized evaluation optimize query execution.
• Oracle's cost-based approach and semantic optimization features are further detailed.

This quiz delves into the essentials of query optimization within database management systems. It covers the role of query optimizers, the use of query trees, and heuristics that enhance query execution strategies. Understand the significance of structured representations in improving database performance.