Query Processing and Optimization
Open in the Padhaiko app5.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).
Three Stages of Query Processing
- 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.
- 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.
- 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.
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 OutputMeasuring 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.
| Operation / Algorithm | Block 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.
| Rule Name | Equivalence Identity | Optimization 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:
| Aspect | Heuristic (Rule-Based) Optimization | Cost-Based Optimization (CBO) |
|---|---|---|
| Core Mechanism | Applies 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 / Inputs | Push 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 Overhead | Very fast and low CPU overhead. | Higher optimization time (exponential search space pruned via dynamic programming, e.g., left-deep join trees). |
| Limitation | Cannot 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
- : number of tuples in relation .
- : number of disk blocks holding tuples of (, where is the blocking factor).
- : number of distinct values appearing in attribute of relation .
- Selectivity Estimation:
- Equality selection assuming uniform distribution: estimated output tuples (equals if is a candidate key).
- Equijoin : estimated output tuples .
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.
| Aspect | Materialization | Pipelining |
|---|---|---|
| Execution Model | Evaluates 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 Overhead | High: incurs extra disk writes and reads for every intermediate result. | Low: eliminates temporary disk storage between pipelined stages. |
| Memory & Latency | Low 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
- Demand-Driven (Pull / Iterator Model): Most common in RDBMSs. Each operator implements
open(),next(), andclose(). The root callsnext()on its child, pulling one tuple at a time on demand (lazy evaluation). - Producer-Driven (Push Model): Child operators run eagerly as threads/coroutines, pushing produced tuples into bounded memory queues read by parent operators (suspending if the queue fills).
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.
- Common Denormalization Techniques:
- Pre-joining (Merging) Tables: Storing
DeptNamedirectly insideStudentto avoid joiningStudentandDepartmenton every page load. - Storing Derived / Aggregate Attributes: Adding
TotalItemsorOrderTotaldirectly to anOrderstable instead of computingSUM(Price * Qty)acrossOrderLineevery time. - Duplicating Foreign Keys (Shortcut Joins): Adding
DeptIDdirectly toSubmissionso queries skip intermediate joins throughCourseandAssignment.
- Pre-joining (Merging) Tables: Storing
- Trade-offs:
- Pros: Fewer disk joins, predictable low read latency, simpler analytical queries.
- Cons: Larger storage footprint, slower writes (
INSERT/UPDATE/DELETE), and risk of update anomalies unless synchronized via application logic or database triggers.
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.
Materialized View and View Maintenance
- Materialized View: A physically stored table containing the result of a query (often expensive multi-table joins or
GROUP BYaggregations) so subsequent read queries finish almost instantaneously. - View Maintenance: Keeping the materialized view consistent when underlying base tables are modified:
- Immediate Maintenance: Updates the materialized view inside the same transaction that modifies a base table (always fresh, slows down writes).
- Deferred (Periodic) Maintenance: Refreshes the materialized view lazily on a schedule (
REFRESH MATERIALIZED VIEW) or upon read (fast writes, slightly stale reads). - Incremental Maintenance: Computes only the delta changes ( inserted / deleted rows) rather than recomputing the entire view from scratch.
5.7 Performance tuning
Database performance tuning systematically removes bottlenecks across queries, schemas, indexes, and hardware configuration without changing application correctness:
- Index Tuning:
- Create indexes on columns frequently appearing in
WHERE,JOIN ON,ORDER BY, andGROUP BYpredicates. - 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/DELETEmust also update all indexes.
- Create indexes on columns frequently appearing in
- 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 ofYEAR(HireDate) = 2025(wrapping a column in a function disables B+ tree index lookups). - Prefer
EXISTSoverINon large correlated subqueries, and avoid unnecessaryDISTINCTorORDER BY.
- Select only required columns instead of
- 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.
- Regularly update catalog statistics (
Worked Out Examples
5.1
Consider the relations Student(RollNo, Name, DeptID) and Department(DeptID, DeptName, Building) and the SQL query:
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:
Optimized algebraic expression (evaluated bottom-up):
Each branch filters rows and drops unneeded columns before joining, eliminating the full Cartesian product.
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:
- Block Nested-Loop Join with (the smaller relation) as outer vs. as outer.
- 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:
- Block Nested-Loop Join: block transfers with smaller relation as outer (vs. with as outer).
- Sort-Merge Join (pre-sorted): block transfers.
5.3
Catalog statistics for a university database give:
Student: tuples, blocks, .Department: tuples, (DeptIDis the primary key).
- Estimate the number of tuples in the natural join .
- 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):
- Estimated join result size = tuples.
- Linear Scan transfers blocks (worst case), whereas Binary Search transfers only blocks.
Exercises
Practice Exercises — Query Processing & Optimization
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:
- Parsing and Translation: Validates SQL syntax, checks table/attribute names in the system catalog, and translates the query into a relational-algebra tree.
- Optimization: Applies equivalence rules and consults catalog statistics to select the lowest-cost physical evaluation plan.
- 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.
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.
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:
- Split conjunctive selections () and push as far down the tree as possible.
- Push (projections) down as early as possible, discarding unused columns while retaining join/filter attributes.
- Replace Cartesian products followed by join selections () with join operators ().
- Order joins and selections so the most restrictive (smallest-output) operations execute first.
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 ().
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 BYwhen inputs are not pre-sorted on the grouping attributes.
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.
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, orDELETEon 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.
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.
A join is to be computed where occupies blocks and occupies blocks, with buffer blocks.
- Compute the block transfers for a Hash Join (assuming each partition fits in memory, costing ).
- 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):
- Hash Join: block transfers.
- Block Nested-Loop Join: block transfers; Pre-sorted Sort-Merge Join: block transfers.