Advanced SQL Performance Tuning: Window Functions, Recursive CTEs, and Partitioning

A financial dashboard team builds a report showing customer running transaction balances over time.

To compute the running total for each row, the initial application developer writes a correlated subquery:

SELECT t1.id, t1.account_id, t1.created_at, t1.amount,
       (SELECT SUM(t2.amount) 
        FROM transactions t2 
        WHERE t2.account_id = t1.account_id 
          AND t2.created_at <= t1.created_at) AS running_balance
FROM transactions t1
WHERE t1.account_id = 94012;

Against 100,000 account transactions, this single query takes 14.2 seconds to complete.

The database engine is forced to execute an $\mathcal{O}(N^2)$ operation, scanning all preceding transactions repeatedly for every single output row.

By rewriting the query using a Window Function:

SELECT id, account_id, created_at, amount,
       SUM(amount) OVER (
           PARTITION BY account_id 
           ORDER BY created_at 
           ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
       ) AS running_balance
FROM transactions
WHERE account_id = 94012;

Execution time drops from 14.2 seconds to 0.012 seconds (12 milliseconds)—an over 1,000x performance speedup.

How do advanced SQL constructs like Window Functions, Recursive CTEs, and Table Partitioning transform complex database analytical processing?

1. Window Functions Under the Hood

Unlike standard GROUP BY aggregations (which collapse multiple rows into a single summary output row), Window Functions compute aggregate metrics across a window frame of rows while preserving the individual identity of every underlying row.

Anatomy of a Window Function

FUNCTION() OVER (
    PARTITION BY partition_column   -- 1. Divides dataset into logical buckets
    ORDER BY sort_column            -- 2. Sorts rows within each partition bucket
    FRAME_CLAUSE                    -- 3. Defines active row window boundary
)

Frame Execution Mechanics

During execution, the database engine processes window functions using a 3-step pipeline:

[ Unsorted Dataset ] ---> Sort Operator ---> [ Partition Buckets (Sorted) ]
                                                     |
                                                     v (Window Iterator Frame)
                                           [ Slide Frame Buffer ]
                                                     |
                                                     v
                                           [ Compute Aggregate Result ]

Sort Phase: The engine sorts the dataset by PARTITION BY columns first, then ORDER BY columns second.
Buffer Sliding Frame: As the Volcano iterator steps through rows, it maintains a small in-memory frame buffer of active window tuples (e.g., UNBOUNDED PRECEDING to CURRENT ROW).
Single Pass Calculation: The running total is accumulated linearly in $\mathcal{O}(N)$ time during a single pass over the sorted frame buffer.

2. Hierarchical Traversals with Recursive CTEs

Relational tables are flat sets of rows. However, real-world domain data often forms trees or directed graphs (e.g., organizational charts, category hierarchies, dependency chains).

Before Recursive Common Table Expressions (CTEs), querying a tree hierarchy required executing multiple nested application network queries.

A Recursive CTE solves this inside a single SQL statement by executing an iterative loop:

WITH RECURSIVE org_tree AS (
    -- 1. Anchor Member (Base Case)
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- 2. Recursive Member (Iterative Step)
    SELECT e.id, e.name, e.manager_id, ot.depth + 1
    FROM employees e
    JOIN org_tree ot ON e.manager_id = ot.id
)
SELECT * FROM org_tree;

Internal Execution Loop

      [ Step 1: Anchor Query ]  ---> Populates Intermediate Queue (Depth 1)
                 |
                 v
      [ Step 2: Recursive Join ] ---> Joins Queue against employees table
                 |
                 +<--- New Rows Found? (Loop until queue is EMPTY)
                 |
                 v
      [ Step 3: Emit Final Consolidated Dataset ]

Anchor Execution: Executes the non-recursive anchor member query, inserting initial root rows into a temporary working queue table.
Iterative Evaluation: Executes the recursive query, joining the working queue against the target table.
Termination Condition: New matching tuples replace the working queue. The engine repeats the loop automatically until the working queue returns zero new rows, preventing infinite loops.

3. Table Partitioning & Partition Pruning

When a table grows to hundreds of millions of rows (e.g., historical application log entries), even B+ Tree indexes become large and expensive to fit in RAM.

Table Partitioning splits a single logical table into multiple smaller physical table files (.ibd) on disk based on a partitioning rule.

                         [ Logical Table: audit_logs ]
                                      |
       +------------------------------+------------------------------+
       |                              |                              |
       v                              v                              v
[ Partition p2025 ]            [ Partition p2026 ]            [ Partition p2027 ]
(order_date < '2026-01-01')    (order_date < '2027-01-01')    (order_date < '2028-01-01')

Partitioning Strategies

CREATE TABLE audit_logs (
    id BIGINT NOT NULL,
    log_date DATE NOT NULL,
    payload TEXT,
    PRIMARY KEY (id, log_date)
)
PARTITION BY RANGE (YEAR(log_date)) (
    PARTITION p2024 VALUES LESS THAN (2025),
    PARTITION p2025 VALUES LESS THAN (2026),
    PARTITION p2026 VALUES LESS THAN (2027),
    PARTITION p_future VALUES LESS THAN MAXVALUE
);

The Cost-Based Optimizer & Partition Pruning

When you run a query filtering on the partition key:

SELECT * FROM audit_logs 
WHERE log_date BETWEEN '2026-03-01' AND '2026-03-31';

During query compilation, the Cost-Based Optimizer performs Partition Pruning:

The engine checks table partition definitions and determines that matching records exist only inside physical partition file p2026.
It completely ignores files p2024, p2025, and p_future, opening only the p2026.ibd data file.

EXPLAIN SELECT * FROM audit_logs WHERE log_date = '2026-03-15';

The partitions column in the EXPLAIN output displays p2026. Physical disk I/O is reduced by 75% instantly!

Maintenance Benefits of Partitioning

To drop historical log data older than 2 years from a non-partitioned table:

DELETE FROM audit_logs WHERE log_date < '2024-01-01'; 
-- Triggers millions of row locks, massive undo logs, and fragmentation!

With partitioning, dropping historical data is an instant $\mathcal{O}(1)$ file deletion operation:

ALTER TABLE audit_logs DROP PARTITION p2024;
-- Instantly unlinks the physical file from disk in 5 milliseconds!

Summary & Next Steps

Advanced SQL techniques utilize database optimizer capabilities to streamline analytical processing:

Window Functions (OVER) aggregate data across sliding partition frame buffers in linear $\mathcal{O}(N)$ time.
Recursive CTEs (UNION ALL) traverse graph and tree structures in-database using working queues.
Table Partitioning splits massive tables into physical file segments.
Partition Pruning optimizes query execution by bypassing irrelevant disk partitions during planning.

In the final post of this master series—Post 20: Building a Custom Transactional Storage Engine in Java—we tie together everything we’ve learned by implementing a working database engine from scratch!

References & Further Reading

Transaction Processing Performance Council (TPC). TPC Benchmark C (TPC-C) Specification Version 5.11. TPC Standard.
Kropyvnytskyy, A., & Zaitsev, P. (2020). Sysbench Benchmarking Tool Reference Manual. Open Source Documentation.
Gregg, B. (2020). Systems Performance: Enterprise and the Cloud (2nd Edition). Addison-Wesley.