Query Execution Overview

1. Logical vs Physical Algebra

● Logical algebra: Focuses on high-level operations (e.g., SELECT, JOIN, PROJECT)

without considering how the operations are executed.
● Physical algebra: Represents the actual implementation of these operations (e.g.,
nested loop joins, hash joins, index scans).
○ Example: A logical "join" may translate into a physical hash join or nested-loop
join.

2. Plan Caching and Plan Validation

● Plan caching: Storing query execution plans to reuse them for similar queries, saving
compilation time.
○ Example: A frequently executed query might use a cached plan instead of
creating a new one.
● Plan validation: Ensuring the cached plan is still valid, especially if data statistics or
schema have changed.

3. Scans

● Scans: Methods to retrieve data from storage.

○ Full table scan: Reads all rows in a table.
○ Index scan: Utilizes an index to locate rows efficiently.

4. Index, Sort-, and Hash-based Matching Algorithms

● Algorithms used for operations like joins and searches:

○ Index-based: Leverages indexes for efficient lookups or joins.
○ Sort-based: Sorts data first, then performs matching or merging. Useful for
merge joins.
○ Hash-based: Uses hash tables for efficient joins or grouping. Ideal for large
datasets.

Interesting Orderings
● An "interesting ordering" occurs when an operation’s output order aligns with
requirements of a subsequent operation (e.g., sorting data for a merge join).

5. "Access Plans" vs Dataflow Plans

● Access plans: Focus on how to retrieve data from storage (e.g., choosing between an
index scan or table scan).
● Dataflow plans: Represent the flow of data between operations in a query (e.g.,
pipelines in parallel execution).

6. Serial and Parallel Query Execution

● Serial execution: Executes one operation at a time. Simpler but slower for large
queries.
● Parallel execution: Splits the query into tasks to run concurrently on multiple CPUs or
nodes. Faster but more complex.

Co-partitioning

● Ensuring data is partitioned in the same way across different nodes to avoid shuffling
during operations like joins.
○ Example: Partitioning two tables by the same column used in a join.

Interesting Partitioning

● A partitioning scheme that minimizes data movement and optimizes performance for
specific operations.
Query Execution Archicture -

1. Scans & Iterators

● Scans: The methods used to access data, as previously mentioned (e.g., full table
scan, index scan).
● Iterators: Implement a pull-based model for executing queries, where data is
retrieved one row (or block) at a time in a pipeline manner.
○ Example: A nested loop join uses iterators to fetch rows from each input
one by one.

2. Unary Matching

Unary operations process data from a single input:

● Distinct: Eliminates duplicate rows.

● Grouping: Groups rows by one or more columns (e.g., GROUP BY).
● Pivot: Transforms rows into columns or vice versa (useful in analytics).
● Compression: Reduces data size for efficient storage and processing.

3. Binary Operations

Binary operations involve two inputs:

● Joins: Combines rows from two datasets based on a condition. Types include:
○ Inner join: Matches rows with equal keys in both datasets.
○ Outer join: Includes unmatched rows from one or both datasets.
○ Semi join: Checks for the existence of a match in the second dataset but
returns only the first dataset’s rows.
● Set operations: Perform operations like INTERSECT, UNION, or EXCEPT.

Bit Vector (Bloom) Filters

● Bloom filters: Probabilistic data structures used to filter out rows early in the
pipeline.
○ Example: In a join, a Bloom filter can eliminate rows that are definitely not
in the join key set.

4. Nested Iteration
● Nested iteration: Used for implementing nested-loop joins, where one dataset is
scanned for each row of the other dataset.
○ Efficient when one dataset is small or indexed.

5. Parallel Query Execution: Activation & Scheduling

● Activation: How parallel tasks are initiated and coordinated.

● Scheduling: Allocating tasks across available CPUs or nodes to maximize
efficiency.
○ Example: Assigning partitions of a table to different workers for processing
in parallel.

6. Memory Management

● Efficiently managing memory for query execution to handle intermediate results,

buffers, and sort/hash tables.
○ Techniques like spilling to disk are used when memory is insufficient (e.g.,
external sort).

7. Scheduling Bushy Plans

● Bushy plans: Query execution plans where multiple subtrees are processed
independently before being combined.
○ Example: (A JOIN B) JOIN (C JOIN D) is a bushy plan because the two
joins (A JOIN B) and (C JOIN D) can be executed in parallel.
○ Scheduling: Determines the order and concurrency of executing these
subtrees.
Query execution – scans

1. Per Storage Format: open(), next(), close() Methods

● These are the basic operations of the iterator interface:

○ open(): Initializes the scan, preparing it to retrieve data
(e.g., open files or establish connections).
○ next(): Retrieves the next record in the scan.
○ close(): Cleans up resources after the scan is completed.

Row vs Column Stores

● Row stores:
Data is stored row by row (useful for OLTP
workloads).
● Column stores: Data is stored column by column (optimized for
analytical workloads like OLAP).
○ Scans in column stores can skip irrelevant columns,
improving efficiency.
Indexes

● Indexes (e.g., B-tree, Hash) facilitate faster lookups during scans

by avoiding a full table scan.

2. Read-Ahead & Buffer Pool Pollution

● Read-ahead: Pre-fetching data into memory before it’s needed,

improving performance for sequential scans.
● Buffer pool pollution: Occurs when read-ahead loads large
amounts of data that aren't frequently accessed, displacing
more useful cached data.

3. Index- vs Storage-Order Scans

 ● Index-order scan: Retrieves data in the order defined by an
index. Useful for range queries or sorting.
● Storage-order scan: Reads data in the physical order it is stored
on disk (sequential access).

4. Merging Scan (e.g., in LSM Forests)

● Log-Structured Merge (LSM) Trees: A storage format optimized

for write-heavy workloads.
○ Data is written to multiple levels (SSTables) and
periodically merged.
● Merging scans: Combine data from multiple levels (sorted runs)
into a single result, skipping duplicates and maintaining order.

5. Shared Scans

● When multiple queries or operations need the same data, a

shared scan retrieves the data once and shares it among them.
○ Example: Two queries scanning the same table might
share the scan to reduce I/O costs.

6. Opportunistic Scan (Buffer Pool)

● Uses data already available in the buffer pool to avoid redundant

I/O.
○ Example: If a recent query loaded a table into memory,
subsequent queries can "opportunistically" reuse this
data.

7. Sampling Scans
 ● Instead of reading the entire dataset, a sampling scan retrieves a
subset of the data for approximate query processing or
statistical analysis.
○ Example: Selecting 1% of rows to estimate an aggregate.

8. “Zone” Filters

● A zone filter is an optimization that skips irrelevant data based

on metadata or min/max statistics.
○ Example: In a column store, if a column chunk contains
values outside the range of interest, it can be skipped
entirely.
○ Similar to Bloom filters or partition pruning.
Query execution – iterators

1. Scans, Sort, Filter, (Project)

● These are common operations implemented using iterators:

○ Scans: Retrieve rows from storage.
○ Sort: Orders rows based on one or more columns.
○ Filter: Applies a condition to decide which rows pass
through (e.g., WHERE clause).
○ Project: Selects specific columns from the input rows (e.g.,
SELECT column1, column2).

2. Order-, Index-, and Hash-Based Unary & Binary Matching

● Unary matching: Operations applied to a single dataset:

○ Example: Removing duplicates (DISTINCT), sorting, or
filtering rows.
● Binary matching: Operations involving two datasets:
○ Example: Joins or set operations (INTERSECT, UNION).

Matching Techniques:

● Order-based: Leverages sorted data (e.g., merge join).

● Index-based: Uses indexes to efficiently locate matching rows
(e.g., index nested-loop join).
● Hash-based: Uses hash tables for fast matching (e.g., hash join).

3. “printf”, “assert”, Verification (Sort Order, Partitioning, …)

● These debugging and validation tools ensure correctness in

query execution:
○ printf: Used to log intermediate states for debugging.
 ○ assert: Verifies conditions during execution (e.g.,
ensuring data is sorted before a merge).
○ Verification: Checks properties like sort order, partitioning,
or group consistency to ensure operators are functioning
as expected.

4. Exchange/Shuffle (Parallelism)

● In parallel query execution, data often needs to be redistributed

across processing nodes:
○ Exchange: Transfers data between nodes to achieve the
required distribution.
○ Shuffle: Redistributes data based on a key (e.g., for joins or
grouping).
Example:

● In a join, data from two tables might be shuffled so rows with the
same key end up on the same node.

5. Spool (Shared Intermediate Results)

● Spool: Temporarily stores intermediate results for reuse.

○ Example: If two operations in a query need the same
intermediate data, the spool avoids recomputing it.
○ Particularly useful in queries with common subexpressions
or recursive operations.
Modifying an Existing Sort Order

Case 1: Segmented Sorting (From A to A,B)

Objective: Extend an existing sort order (on column A) to a more

refined sort order (on columns A, B).

Example:

Input: Data sorted by column A only.

A|B

--+--

1|x

1|y

2|z

2|w

Task: Sort by A first and then by B within each segment of A.

Approach:

Divide the dataset into segments where the value of A is the same.

Perform sorting on B within each segment.

Output:

A|B

--+--

1|x

1|y
2|w

2|z

Use Case: This is useful when you need to refine existing order
without re-sorting the entire dataset.

Case 2: Merging Pre-Existing Runs (From A,B to B)

Objective: Change the sort order of pre-sorted data (from A, B to just

B).

Example:

Input: Data sorted by A, B.

A|B

--+--

1|x

1|y

2|w

2|z

Task: Re-sort by B only, disregarding the A column.

Approach:

Identify runs of data already sorted by A, B (e.g., [1,x, y] and [2, w, z]).

Merge these runs while reordering by B.

Output:
B|A

--+--

w|2

x|1

y|1

z|2

Use Case: This is common in queries where the primary sort key
becomes less relevant or when merging datasets with overlapping
sort orders.

Key Techniques Involved

Segmented Sorting: Efficient sorting within independent subsets of

data.

Merging Pre-Existing Runs: Reuses existing sorted order to reduce

sorting effort (e.g., as in merge sort).

Efficiency: Both approaches minimize computational cost compared

to fully re-sorting the dataset.
Query execution – unary matching

1. Unary Matching Operations

These are common operations in query execution:

● DISTINCT: Eliminates duplicate rows.

● GROUP BY: Groups rows based on column values and applies
aggregate functions (e.g., SUM, COUNT).
● PIVOT: Reshapes data, turning rows into columns (e.g., creating
a summary table).
● Compression: Reduces data size by identifying patterns or
redundancies.
● Expensive actions:
○ Fetch: Retrieving additional data, potentially requiring
multiple I/O operations.
○ Lookup join: Fetching rows from another table for
matching (e.g., using an index).
○ Nested iteration: Repeatedly scanning data (inefficient
unless optimized).
○ User-Defined Functions (UDFs): Custom operations
defined by users, which can be computationally expensive.

2. Algorithms for Unary Matching

Order-Based Algorithms

● In-Stream Grouping (e.g., Rollup):

○ Groups data as it is read in order, without requiring a full
sort.
○ Example: Incrementally aggregating data for GROUP BY
when input data is pre-sorted on the grouping keys.
○ Rollup: A type of aggregation that computes subtotals and
grand totals across multiple levels.
● In-Sort Grouping:
 ○ Requires the input to be sorted beforehand.
○ Groups rows with the same key by iterating through the
sorted data.
○ Example: Sorting on group_key and then aggregating
values for each group sequentially.
Hash-Based Grouping (“Hash Aggregation”)

● Uses a hash table to track groups and their aggregates.

○ Example: For each row, hash the GROUP BY column, look
up the hash table, and update the aggregate value.
● Advantages: Efficient for large, unsorted data.
● Challenges: Requires memory to store the hash table and can
spill to disk if memory overflows.
Index-Based Grouping (“Poor Man’s Hash Aggregation”)

● Uses an index (e.g., B-tree) instead of a hash table to group data.

○ Example: Perform lookups on an index to identify groups
and update aggregates.
● Advantages: Avoids building a hash table from scratch if an
index already exists.
● Disadvantages: Typically slower than hash-based grouping.

3. Abstract Interfaces: Row Formats & Methods

● Query execution engines often deal with data in various formats.

Abstract interfaces standardize:
○ Row Formats: How rows are represented in memory (e.g.,
row-based, column-based, or hybrid).
○ Methods: Operations defined for interacting with these
rows (e.g., retrieving column values, modifying data).
● Goal: Decouple the physical storage from query execution logic,
enabling flexibility across different storage formats.
Query Execution – Binary Matching

Binary matching involves operations that compare and combine two

datasets, such as joins and set operations. Here's a detailed
explanation of the components mentioned:

1. Joins

Joins combine rows from two datasets based on a matching

condition.

● Inner Join: Combines rows where the join condition is satisfied.

○ Example: SELECT * FROM A INNER JOIN B ON A.key =
B.key.
● Outer Join: Includes rows even when there is no match, with
NULL values for missing columns:
○ Left Outer Join: Includes all rows from the left table.
○ Right Outer Join: Includes all rows from the right table.
○ Full Outer Join: Includes all rows from both tables.
● Semi Join: Returns rows from the left table that match rows in
the right table but does not include columns from the right table.
● Mark Join: Adds a boolean column indicating whether a match
exists for each row in the left table.

2. Set Operations

Set operations compare datasets based on their contents, rather than

rows or columns:

● Intersect: Returns common rows between two datasets.

● Except: Returns rows in one dataset but not the other.
● Union: Combines rows from both datasets, optionally removing
duplicates (UNION ALL keeps duplicates).
3. Algorithms for Joins

Index-Based Algorithms: Index Nested-Loops Join

● Approach:
For each row in the outer table, use an index on the
inner table to find matching rows.
● When to Use: Efficient if the inner table has an index on the join
key.
● Drawback: High overhead if many lookups are required or if the
index is not selective.
Sort-Based Algorithms

● Merge Join:
○ Both datasets are sorted on the join key, and a single pass
merges them.
○ Efficient for large datasets with pre-sorted inputs or when
sorting is inexpensive.
● Zigzag Merge Join:
○ A variation of merge join that efficiently handles multiple
sorted inputs or overlapping ranges.
Hash-Based Algorithms

● Hash Join:
○ The smaller dataset is hashed on the join key, and the
larger dataset is probed against the hash table.
○ When to Use: Suitable for large datasets where sorting is
not feasible.
○ Variants:
■ Adaptive Join: Dynamically switches between join
strategies based on data characteristics (e.g.,
memory availability).
■ Symmetric Hash Join: Allows early output by building
hash tables for both datasets and probing them
incrementally.
4. Filters

Filters improve performance by reducing unnecessary computations:

● Bit Vector Filter:

○ A compact structure that indicates possible matches. It is
built during the join and helps eliminate non-matching
rows early.
○ Example: Used in hash joins to filter rows that cannot
match.
● Minimum/Maximum Filters:
○ Apply range constraints to eliminate rows outside the join
range.

5. Co-Group-By

● Definition: Groups two datasets on the same key and aggregates

them simultaneously.
● Example: When combining datasets with GROUP BY on the same
key, this can save computational resources by sharing the
grouping logic.

Summary of Strategies

Algorithm Strengths When to Use

Index Efficient with indexed Small outer table,

Nested-Loops inner table. indexed inner table.
Merge Join Fast with sorted Pre-sorted or small
datasets. datasets.

Hash Join Handles large, unsorted Large datasets, no

datasets. indexes available.

Adaptive Join Flexible to data Uncertain data size or

characteristics. distribution.

Bit Vector Eliminates non-matching Join keys with high

Filters rows early. selectivity.

Efficient binary matching relies on understanding the size, indexing,

and distribution of your datasets to select the appropriate algorithm.
Query Execution – Important Basics

This section touches upon critical optimization techniques and considerations for efficient query
execution. Here’s a breakdown:

1. Asynchronous Fetch

● Definition: Overlaps the fetching of data from storage with computation to avoid delays
caused by slow I/O operations.
● Advantage: Improves performance by keeping the processor busy while waiting for I/O.
● Example: Fetching the next block of rows while processing the current block.

2. Poor Man’s Merge Join

● Definition: A simplified or approximate merge join used when full sorting isn’t feasible or
necessary.
● How it Works:
○ Uses partially ordered data to perform a merge-like operation without the
overhead of complete sorting.
○ Often relies on "interesting orderings" already present in the data.

3. Smooth Scans

● Definition: A scan technique that minimizes performance degradation caused by

uneven access patterns.
● Example: Balancing disk reads across multiple partitions to avoid hot spots.

4. Bit Vector Filtering

● Definition: A compact, probabilistic filter used to eliminate non-matching rows early in

query execution.
● Usage:
○ Common in hash joins to filter rows that can’t possibly match.
○ Reduces the size of data that needs further processing.
5. Segmented Execution

● Definition: Executes a query in independent segments, which can be processed in

parallel or sequentially.
● Advantages:
○ Efficient use of system resources.
○ Allows partial results to be computed and reused.

6. Dynamic Degree of Parallelism (DDP)

● Definition: Adjusts the level of parallelism dynamically during query execution based on
system load or query progress.
● Advantage: Prevents resource contention and optimizes performance in real-time.

7. Bottom-Up Activation

● Definition: Starts query execution with the most basic operations (e.g., scans) and
propagates results upwards in the query plan.
● Example: In a tree-structured query plan, the leaves (data sources) are processed first,
and intermediate nodes (joins, aggregates) are activated as their inputs become
available.

8. MDAM Search (Multi-Dimensional Access Method)

● Definition: Optimized search over multi-dimensional indexes, often used for complex
predicates.
● Example: Efficiently querying a dataset with conditions like (A > 10 AND B < 20).

9. Adaptive Join

● Definition: A join technique that adjusts its execution strategy based on runtime
information.
● Variants:
○ Switch between nested-loops, hash join, or merge join based on available
memory and data characteristics.
○ Output early results (symmetric join).
10. Group + Join

● Definition: Combines grouping and joining operations into a single pass to improve
performance.
● Example: Instead of grouping after a join, the group-by logic is integrated during the join
phase.

11. In-Stream Roll-Up

● Definition: Computes aggregate summaries (e.g., totals, averages) incrementally as

data flows through the query plan.
● Example: Calculating cumulative totals for a GROUP BY query without storing all
intermediate results.

12. Performance Cliffs vs Continuous Cost Functions

● Performance Cliffs:
○ Abrupt drops in performance caused by exceeding system limits, like memory
capacity or disk bandwidth.
○ Example: A hash join that spills to disk due to insufficient memory.
● Continuous Cost Functions:
○ Gradual performance degradation as workload increases.
○ Goal: Avoid performance cliffs by ensuring system behavior follows a continuous
cost function.

Summary of Concepts
Concept Primary Use Benefit

Asynchronous Fetch Overlapping I/O with Minimizes idle time.

computation.

Poor Man’s Merge Simplified join using partial Reduces sorting overhead.
Join order.

Smooth Scans Balanced data access. Avoids hotspots in storage access.

Bit Vector Filtering Early elimination of rows. Reduces data size for further
processing.

Segmented Modular query processing. Enables parallelism and result reuse.

Execution

DDP Dynamic resource Adapts to system conditions in

management. real-time.

MDAM Search Multi-dimensional queries. Efficient predicate evaluation on

indexes.

Adaptive Join Flexible join strategies. Handles varying data and resource
constraints.

In-Stream Roll-Up Incremental aggregation. Low memory footprint for

aggregates.

Performance Cliffs Identifying resource limits. Ensures robust query execution

plans.
Query Execution – Important Techniques

This section focuses on optimization strategies for query execution, particularly for handling
large datasets and improving performance by using advanced techniques for sorting, merging,
and resource allocation.

1. Efficient External Merge Sort

Definition: External merge sort is a sorting algorithm used when the dataset is too large to fit in
memory and must be sorted by accessing data from external storage (like disk). The goal is to
minimize I/O operations while sorting.

● Offset-Value Codes:
○ What It Is: A technique for representing data in a way that reduces the amount of
data transferred from disk by encoding the differences (offsets) between values
instead of the full values.
○ Benefit: Reduces data size during sorting, leading to fewer disk accesses.
● Graceful Degradation:
○ What It Is: The ability of the sorting algorithm to scale with available memory. If
memory is limited, the algorithm adjusts to perform efficiently despite having less
space to work with.
○ Benefit: Ensures that even with constrained resources, the sort operation
remains efficient.
● Operations like 'Distinct', 'Group By', 'Pivot', 'Top':
○ These operations are often performed during or after sorting to organize data.
For example:
■ Distinct removes duplicates,
■ Group By aggregates data,
■ Pivot reorganizes data based on key values,
■ Top is used to return a fixed number of top rows based on some criteria.
● Instant Aggregation, Wide Merging:
○ Instant Aggregation: A technique where aggregation (e.g., sum, count) is
applied as soon as data is read or streamed, instead of waiting until after all data
is processed.
○ Wide Merging: A merging strategy that handles wide (many-column) datasets
more efficiently, merging sorted runs or partitions while minimizing memory
usage.
● Co-group-by:
○ What It Is: A technique that allows for performing multiple group-by operations
on different columns simultaneously.
○ Benefit: Optimizes performance by reducing the number of passes over the data.
2. MDAM Merge: Segmented Sort + Merging “Natural” Runs

● MDAM (Multi-Dimensional Access Method) merge refers to the strategy of sorting and
merging data in multi-dimensional indexes.
● Segmented Sort: Breaks down the data into manageable segments that can be sorted
and processed independently, reducing I/O and memory overhead.
● Merging “Natural” Runs: Combines pre-sorted runs of data (that may already follow
some natural order) into a larger sorted output without needing full-scale sorting.

3. Load Balancing, Tail Balancing

● Load Balancing:
○ Distributes data processing tasks evenly across all available resources (e.g.,
processors, memory, nodes) to avoid bottlenecks.
○ Ensures that no single resource is overwhelmed with too much work, improving
overall throughput.
● Tail Balancing:
○ What It Is: Focuses on managing the final stages of a query, where the
remaining data may be small but requires significant processing.
○ Benefit: Optimizes the execution of query plans by focusing resources on the
end of the process, ensuring that even the "tail" end of the query performs
efficiently.

4. Prior Order ⇒ Progress Estimation ⇒ Resource Allocation

● Prior Order:
○ Establishes the initial sequence of operations in a query execution plan, taking
into account factors like data distribution, available indexes, and system
resources.
● Progress Estimation:
○ What It Is: A method of estimating how much progress will be made at each step
of the query execution based on the data and operations involved.
○ Benefit: Helps in predicting how much time or resources each step of the
execution will require, allowing for better optimization decisions.
● Resource Allocation:
○ What It Is: The dynamic allocation of system resources (like CPU, memory, disk
I/O) based on the progress of the query.
○ Benefit: Allows for adaptive resource management, ensuring the query runs as
efficiently as possible without overloading the system.
Summary of Key Concepts
Technique Description Benefit

Efficient External Sorting large datasets by Reduces disk access,

Merge Sort minimizing I/O operations. improves sorting performance.

Offset-Value Codes Encoding differences between Reduces data size, optimizing

values for storage. disk usage.

Graceful Adjusts sorting performance based Ensures efficient sorting even

Degradation on available memory. under constrained resources.

Operations Data organization operations Organizes data efficiently

('Distinct', 'Group during sorting. during or after sorting.
By')

Instant Aggregation, Aggregating data during sorting; Improves performance by

Wide Merging efficient merging. minimizing memory usage.

Co-group-by Simultaneously grouping by Optimizes performance with

multiple columns. fewer data passes.

MDAM Merge Multi-dimensional data sorting and Improves multi-dimensional

merging. query performance.

Load Balancing Evenly distributing processing Prevents bottlenecks and

tasks across resources. maximizes throughput.

Tail Balancing Optimizing the final stages of query Ensures efficient final-phase
processing. query execution.

Prior Order ⇒ Pre-determined sequence of Allows better resource

Progress Estimation operations based on resource management and query
estimates. planning.