PadhaikoAll subjects

Query Processing and Optimization

Database Management System (ENCT 301)

Open in the Padhaiko app

5.1 Query processing, optimization and evaluation

Query processing refers to the range of activities involved in extracting data from a database in response to a high-level declarative query (such as SQL).

Definition

Three Stages of Query Processing

  1. Parsing and Translation: The parser checks SQL syntax, verifies table and attribute names against the system catalog (data dictionary), and translates the query into an internal representation—typically a relational-algebra expression tree.
  2. Optimization: Because a single SQL query can be translated into many equivalent relational-algebra expressions—and each operator can use multiple physical algorithms (e.g., index scan vs. sequential scan, hash join vs. nested-loop join)—the query optimizer selects the evaluation plan with the lowest estimated execution cost.
  3. Evaluation: The query-execution engine takes the chosen evaluation plan (an annotated tree of physical operators), executes it against stored disk files and memory buffers, and returns the resulting tuples.
Query Processing PipelineText
   SQL Query
       |
       v
+------------------------+     Consults      +--------------------+
| Parser & Translator    | <---------------> |   System Catalog   |
+------------------------+                   | (Table/Index Stats)|
       | Relational Algebra Expression       +--------------------+
       v                                                ^
+------------------------+                              |
|    Query Optimizer     | -----------------------------+
+------------------------+
       | Execution (Evaluation) Plan
       v
+------------------------+     Reads/Writes  +--------------------+
| Query-Execution Engine | <---------------> |   Buffer & Disk    |
+------------------------+                   +--------------------+
       |
       v
  Query Output

Measuring Query Cost

The total cost of executing a query is dominated by disk I/O rather than CPU time (on magnetic disks, seeks and block transfers take milliseconds vs. nanoseconds in RAM):

where is the number of disk blocks transferred, is the number of random disk seeks, is the time to transfer one block, and is the average seek time.

Common Physical Operator Cost Formulas (Block Transfers)
Operation / AlgorithmBlock Transfers ()Seeks ()Key Condition
Linear Scan () (worst case; average on candidate key)Scans all blocks sequentially
Binary Search () (for key attribute)File physically sorted on
B+ Tree Primary Index () (height + data block)Key lookup on height- B+ tree
Nested-Loop Join () (worst case) tuples in outer relation
Block Nested-Loop Join () memory buffer blocks available
Merge Join (sorted )Both inputs already sorted on join key
Hash Join () (with recursive partitioning: )Equijoin; partitions fit in memory

5.2 Transformation of relational expressions

Two relational-algebra expressions are equivalent if they generate the exact same set of tuples on every legal database instance. A query optimizer transforms expressions using algebraic equivalence rules to reduce the size of intermediate results.

Fundamental Equivalence Rules of Relational Algebra
Rule NameEquivalence IdentityOptimization Intuition
1. Cascade of Splits conjunctive predicates so individual parts can move below joins.
2. Commutativity of Apply the most selective (filtering) predicate first.
3. Cascade of (if )Eliminate redundant intermediate projections.
4. + to Never materialize a huge Cartesian product before filtering!
5. Commutativity of Place the smaller relation as the outer/build input.
6. Associativity of Join relations that produce the smallest intermediate table first.
7. Pushing past (when uses only attributes of )Shrinks inputs before joining.
8. Pushing past (keeping join attributes in )Drops unused columns early so more tuples fit per memory block.
9. Distributing over Same holds for and .

5.3 Techniques of implementing query optimization - Cost based optimization and heuristic optimization

Query optimizers combine two complementary strategies to transform an initial query tree into a fast physical execution plan:

AspectHeuristic (Rule-Based) OptimizationCost-Based Optimization (CBO)
Core MechanismApplies fixed algebraic rewriting rules that almost always improve performance, without consulting table sizes.Enumerates equivalent plans, estimates I/O + CPU cost using catalog statistics, and picks the minimum-cost plan.
Key Rules / InputsPush and as far down the tree as possible; replace with ; execute tightest filters first.Uses catalog metadata: tuple count , block count , distinct values , min/max histograms, and index heights.
Optimization OverheadVery fast and low CPU overhead.Higher optimization time (exponential search space pruned via dynamic programming, e.g., left-deep join trees).
LimitationCannot distinguish which join order or index access path is actually cheaper for specific data distributions.Sensitive to stale catalog statistics; bad cardinality estimates can pick a poor join algorithm.

Catalog Statistics Used in Cost-Based Optimization


5.4 Query evaluation -Materialization and pipelining

Once an evaluation plan is selected, an operator tree must transfer intermediate results from child operators to parent operators using either materialization or pipelining.

AspectMaterializationPipelining
Execution ModelEvaluates one operator completely at a time, writing its entire output to a temporary disk file before the parent operator starts reading it.Passes output tuples from a child operator directly in memory to its parent operator as soon as they are produced, executing multiple operators concurrently.
Disk I/O OverheadHigh: incurs extra disk writes and reads for every intermediate result.Low: eliminates temporary disk storage between pipelined stages.
Memory & LatencyLow memory pressure; high initial latency before first output row appears.Higher memory needed for pipeline buffers; delivers first output rows quickly.
When Forced (Pipeline Breakers)Always usable. Required for blocking operations like external sorting (ORDER BY), building a hash table, or grouping (GROUP BY without sorted input).Works seamlessly for streaming operators (SELECT filter, PROJECT, index-nested-loop join, merge join on pre-sorted inputs).

Demand-Driven vs. Producer-Driven Pipelining


5.5 Denormalization for performance

Denormalization is the deliberate introduction of controlled data redundancy into a normalized database schema (usually 3NF/BCNF) to improve read query performance by reducing expensive runtime joins or aggregations.


5.6 Materialized view

Unlike a standard virtual view (which re-runs its underlying SELECT query every time it is queried), a materialized view physically stores the precomputed result tuples on disk like a real table.

Definition

Materialized View and View Maintenance


5.7 Performance tuning

Database performance tuning systematically removes bottlenecks across queries, schemas, indexes, and hardware configuration without changing application correctness:

  1. Index Tuning:
    • Create indexes on columns frequently appearing in WHERE, JOIN ON, ORDER BY, and GROUP BY predicates.
    • Use covering indexes (composite indexes containing all queried columns) to answer queries via index-only scans without touching heap data blocks.
    • Avoid over-indexing write-heavy tables, since every INSERT/UPDATE/DELETE must also update all indexes.
  2. SQL Query Tuning:
    • Select only required columns instead of SELECT * (enables covering indexes and cuts network/memory traffic).
    • Write SARGable (Search ARGument-able) predicates: write HireDate >= '2025-01-01' AND HireDate < '2026-01-01' instead of YEAR(HireDate) = 2025 (wrapping a column in a function disables B+ tree index lookups).
    • Prefer EXISTS over IN on large correlated subqueries, and avoid unnecessary DISTINCT or ORDER BY.
  3. Schema, Statistics & System Tuning:
    • Regularly update catalog statistics (ANALYZE) so the cost-based optimizer picks accurate join orders.
    • Apply table partitioning (horizontal range/hash partitioning) on massive tables, materialized views for heavy reports, or selective denormalization.
    • Tune buffer pool / shared memory size so hot index pages and working sets stay cached in RAM.

Worked Out Examples

Example 5.1

5.1

Consider the relations Student(RollNo, Name, DeptID) and Department(DeptID, DeptName, Building) and the SQL query:

Query to Optimize HeuristicallySQL
SELECT S.Name, D.DeptName
FROM Student S, Department D
WHERE S.DeptID = D.DeptID AND D.Building = 'BCT-Block' AND S.RollNo > 100;

Draw the initial relational-algebra expression tree and apply heuristic optimization step by step to produce the optimized query tree.

Constructing the Initial Expression Tree: Direct translation of FROM WHERE SELECT yields a Cartesian product followed by selection and projection:

Evaluating Student Department first would materialize pairs unnecessarily.

Pushing Selections Down (Equivalence Rules 1 and 7):

Replacing Cartesian Product + Selection with Join & Pushing Projections (Rules 4 and 8): Combine and into an equijoin , and project away unused attributes (Name, DeptID from Student; DeptID, DeptName from Department) before the join:

Answer:

Optimized algebraic expression (evaluated bottom-up):

Each branch filters rows and drops unneeded columns before joining, eliminating the full Cartesian product.

Example 5.2

5.2

Two relations and occupy disk blocks and disk blocks respectively, and memory buffer blocks are available. Compute the disk block transfers (ignoring seeks) required to compute using:

  1. Block Nested-Loop Join with (the smaller relation) as outer vs. as outer.
  2. Sort-Merge Join assuming both and are already sorted on the join attribute.

Block Nested-Loop Join Cost: Out of buffer blocks, reserve block for reading the inner relation and block for output, leaving blocks to buffer chunks of the outer relation.

  • Case A ( as outer, as inner): Number of outer chunks .
  • Case B ( as outer, as inner): Number of outer chunks .

(Placing the smaller relation in the outer loop saves block transfers.)

Sort-Merge Join Cost (Pre-sorted Inputs): When both relations are already sorted on the join key (with no duplicate key spans exceeding memory), each relation is scanned sequentially just once:

Answer:
  1. Block Nested-Loop Join: block transfers with smaller relation as outer (vs. with as outer).
  2. Sort-Merge Join (pre-sorted): block transfers.
Example 5.3

5.3

Catalog statistics for a university database give:

  1. Estimate the number of tuples in the natural join .
  2. Compare the number of block transfers for using Linear Scan (worst case) vs. Binary Search (if sorted on RollNo).

Estimating Natural Join Cardinality: Using the uniform-distribution join cardinality formula on common attribute DeptID:

(Every student matches at most one department because DeptID is the key of Department.)

Comparing Linear Scan vs. Binary Search Block Transfers:

  • Linear Scan (worst case): Scans all blocks.
  • Binary Search (sorted on candidate key RollNo):
Answer:
  1. Estimated join result size = tuples.
  2. Linear Scan transfers blocks (worst case), whereas Binary Search transfers only blocks.

Exercises

Practice Exercises — Query Processing & Optimization

Question 1

List and explain the three major steps of query processing with a neat diagram, and define the two primary metrics used to measure disk I/O cost of a query execution plan.

Three Steps of Query Processing:

  1. Parsing and Translation: Validates SQL syntax, checks table/attribute names in the system catalog, and translates the query into a relational-algebra tree.
  2. Optimization: Applies equivalence rules and consults catalog statistics to select the lowest-cost physical evaluation plan.
  3. Evaluation: The query-execution engine runs the chosen operator tree using buffer memory and disk storage to return tuples.

Disk I/O Cost Metrics: Query cost is measured primarily by combining:

  • Number of block transfers (): Total data/index blocks read from or written to disk.
  • Number of disk seeks (): Number of random disk head movements required when blocks are non-contiguous.
Answer:

The three stages are (1) Parsing and Translation, (2) Optimization, and (3) Evaluation. Query I/O cost is modeled as , measuring block transfers and random disk seeks.

Question 2

Distinguish between heuristic (rule-based) optimization and cost-based optimization. State any four heuristic transformation rules used to optimize a relational-algebra query tree.

Heuristic vs. Cost-Based Optimization:

  • Heuristic optimization applies deterministic algebraic rules to shrink intermediate relations without checking table statistics (fast, low overhead, ignores data skew).
  • Cost-based optimization generates alternative equivalent plans and estimates their I/O + CPU cost using system-catalog statistics (, histograms), selecting the plan with minimum estimated cost.

Four Heuristic Optimization Rules:

  1. Split conjunctive selections () and push as far down the tree as possible.
  2. Push (projections) down as early as possible, discarding unused columns while retaining join/filter attributes.
  3. Replace Cartesian products followed by join selections () with join operators ().
  4. Order joins and selections so the most restrictive (smallest-output) operations execute first.
Answer:

Heuristic optimization rewrites query trees using fixed rules (pushing and down, replacing with , executing tightest filters first), whereas cost-based optimization compares estimated execution costs using catalog statistics ().

Question 3

Compare materialization and pipelining in query evaluation. Under what circumstances is pipelining not possible between two consecutive operators?

Materialization vs. Pipelining:

  • Materialization evaluates each operator completely and writes its entire intermediate output to temporary disk storage before passing it to the parent operator.
  • Pipelining passes output tuples directly in memory buffers from producer to consumer operators concurrently, avoiding intermediate disk I/O and reducing time-to-first-row.

When Pipelining Is Blocked (Pipeline Breakers): Pipelining cannot stream directly across blocking operators that must consume all input tuples before producing any output tuple—for example:

  • External Sorting (ORDER BY) or sort-phase of Sort-Merge Join.
  • Hash-table build phase of a Hash Join (must hash the entire build relation before probing begins).
  • Aggregate GROUP BY when inputs are not pre-sorted on the grouping attributes.
Answer:

Materialization writes intermediate outputs to temporary disk files between operators, whereas pipelining streams tuples directly in memory. Pipelining is blocked by pipeline-breaking operations such as sorting (ORDER BY), building a hash table, or unsorted GROUP BY aggregation.

Question 4

Explain denormalization and materialized views as performance-optimization techniques. What trade-offs do they introduce for write-heavy OLTP workloads?

Denormalization and Materialized Views:

  • Denormalization intentionally merges normalized tables or stores derived/duplicated attributes in base tables to eliminate expensive multi-table joins on frequent reads.
  • Materialized views physically cache the precomputed result of complex join/aggregate queries on disk so read queries scan the stored summary directly instead of recomputing it.

Write-Workload Trade-Offs:

  • Update Overhead: Every INSERT, UPDATE, or DELETE on base data must update duplicated columns (denormalization) or refresh cached summaries (materialized views).
  • Consistency Risk & Storage: Improperly synchronized denormalized tables risk update anomalies; deferred materialized views can serve slightly stale data; both consume additional disk space.
Answer:

Denormalization embeds controlled redundancy into base tables to skip joins, and materialized views precompute and store query results on disk. Both accelerate read-heavy queries at the expense of extra storage, slower writes, and consistency/refresh overhead in OLTP workloads.

Question 5

A join is to be computed where occupies blocks and occupies blocks, with buffer blocks.

  1. Compute the block transfers for a Hash Join (assuming each partition fits in memory, costing ).
  2. Compute the block transfers for a Block Nested-Loop Join with as the outer relation, and compare with Sort-Merge Join if both and are already sorted.

Hash Join Block Transfers: Reading and to partition (), writing partitions to disk (), and reading partitions back for probing () totals:

Block Nested-Loop Join vs. Pre-sorted Sort-Merge Join:

  • Block Nested-Loop Join ( outer, outer buffer blocks):
  • Sort-Merge Join (already sorted):
Answer:
  1. Hash Join: block transfers.
  2. Block Nested-Loop Join: block transfers; Pre-sorted Sort-Merge Join: block transfers.
← Database Constraints and NormalizationFile Structure and Hashing →