Chapter19

Fundamentals of Query Optimization

• Conducted by a query optimizer in a Database Management System (DBMS)

• Goal: select best available strategy for executing a query

• Based on information available

• Most RDBMSs use a tree as the internal representation of a query

Query Trees and Heuristics for Query Optimization

• Steps in Query Optimization:

  • Step 1: Scanner and parser generate initial query representation

  • Step 2: Representation is optimized according to heuristic rules

  • Step 3: Query execution plan is developed

• Heuristic Rule Example:

  • Apply SELECT and PROJECT operations before JOIN to reduce file sizes

• Query Trees: Represents relational algebra expressions

• Query Graphs: Represents relational calculus expressions

Heuristic Optimization of Query Trees

• Different query trees can yield the same results; inefficient trees are transformed into optimized versions.

Transformation Example Steps

• Steps to convert a query tree include:

  • Moving SELECT operations down the query tree

  • Applying more restrictive SELECT operations first

  • Replacing CARTESIAN PRODUCT and SELECT with JOIN operations

General Transformation Rules for Algebraic Optimization

• Apply operations that reduce intermediate result size first

• Perform SELECT and PROJECT early to minimize tuples and attributes

• Restrictive SELECT and JOIN operations should be prioritized.

Choice of Query Execution Plans

• Types:

  • Materialized evaluation: Results stored as temporary relations

  • Pipelined evaluation: Results forwarded directly to subsequent operations.

Nested Subquery Optimization

• Unnesting: Removes nested queries, converting them into a single block query

• Alternate technique: Using temporary result tables from subqueries for joins.

Materialized Views

• Defined query results stored in a database, potentially for permanent use, to optimize computation.

Cost-Based Optimization

• Query optimizer estimates and compares execution costs using various strategies.

• Components include:

  • Access costs to secondary storage

  • Disk storage costs

  • Computation costs

Catalog Information Used in Cost Functions

• Information stored in the DBMS catalog aids optimizer efficiency by providing:

  • File size

  • Organization of data

  • Distinct values of attributes

Cost Functions for SELECT Operation

• Search Techniques:

  • S1: Linear search (brute force)

  • S2: Binary search

  • S3: Using primary and hash index operations for efficient retrieval.

Cost Functions for JOIN Operation

• Estimates file size resulting from JOIN operations.

• Performances and efficiencies depend on join selectivity and cardinality.

Dynamic Programming in Cost Optimization

• Solves subproblems efficiently by reusing computed solutions to optimize query execution plans.

Summary of Query Optimization Techniques

• Focus on query trees, heuristic approaches, pipelining, materialized evaluations, and cost-based methodology.

• Integrated approaches and semantic optimizations enhance query performance.