Calhacks 2025 – Query Challenge

A submission to AppLovin's query planner challenge at Cal Hacks 2025. See an example run here.

Summary: we achieve a ~1300x speedup compared to the baseline implementation (~45s to ~30ms) on an M3 Pro with 18 GB RAM. Preprocessing takes 300.5 seconds (~5 minutes).

Figure 1: A comparison of the baseline implementation to our submission (v1). Note the log scale: v1 is over three orders of magnitude faster.

On our custom set of 25 additional validation queries, we achieve a ~120x speedup (~205s to ~1.72s).

Setup

This project uses uv to manage Python packages, which can be installed here.

To evaluate a set of queries (provided as a JSON file):

PYTHONPATH=. uv run benchmark/run.py \
            --data-dir data/data \
            --out-dir results/v1-baseline-full \
            --solution=v1 \
            --queries queries/baseline.json \
            --verbose \
            --num-runs=1

You can pass the directory to the expected results for correctness checks. For example:

PYTHONPATH=. uv run benchmark/run.py \
            --data-dir data/data \
            --out-dir results/v1-baseline-full \
            --solution=v1 \
            --queries queries/baseline.json   \
            --expected-dir results/results-full \
            --verbose  \
            --num-runs=1

Design

We use four main techniques to optimize query performance.

Efficient on-disk storage layout

Instead of storing the data in CSV files and re-reading via read_csv on each query, we can pre-process the table into parquet files for significantly more efficient IO. In particular, we allow each thread to store its own parquet shard.

With the default ROW_GROUP_SIZE = 122880, each of the 10 shards (for each thread) has around ~160 row groups.

SELECT num_row_groups FROM parquet_file_metadata('tmp/events.parquet/data_0.parquet');
> 163

This means that there's a fair chunk of overhead spent on reading per-group metadata. We can afford to store much more data in memory - given we have ~10 threads, we should aim for num_row_groups around ~20.

Using ROW_GROUP_SIZE = 1M, we see significant improvements on the majority of queries (22x improvement on baseline from optimized layout alone).

Materialized views

Materialized views let us pre-aggregate common query patterns and can easily improve query times 10-100x (note: DuckDB doesn't have materialized views, so we just create new tables).

Although we could create arbitrarily many pre-aggregated tables to account for various query patterns, I chose a small set of general MVs (see src/mv.py for the definitions). In particular, I have a set of "slow/large" MVs and a corresponding set of faster/smaller ones for common use cases.

For each of the ID types (advertiser_id, publisher_id, user_id), I've constructed a slow/large table grouped by (type, day, country, <id>). This answers common questions like:

• How much in total bids did a particular advertiser make on a certain day?
• How many impressions were served to users in JP?

Even though these tables are fairly large (advertiser_full is ~10M rows), they are still significantly smaller than events with 245M rows.

On the faster side, I have a set of small MVs (e.g. mv_day_fast, mv_time_fast and mv_auction_fast) that have ~10K rows and act as a quick cache if a query can be written to hit them.

Note: this is a tradeoff between pre-processing time and query performance. I've only set up a handful of common MVs, but have tried to make it as easy as possible to add new MVs. All it takes is updating the registry in src/mv.py – the corresponding SQL will be automatically generated.

Intelligent query planning & rewriting

The query planner (src/planner.py) is responsible for rewriting the query to hit a particular materialized view. This happens in two steps:

1. Find the set of feasible MVs that support the query
2. Score each feasible MV based on estimated cost heuristics

Feasibility Check

We can only substitute a table for an MV if:

• the group-by of the MV fully covers the group-by of the query and any filters
• all select columns/aggregates can be derived from the MV

For the last point, we make a micro-optimization to derive AVG from SUM and COUNT, which lets us cut down on the number of bytes we need to save.

Intelligent scoring

The key idea here is that the cost of the query is approximately linear to the # of filtered rows and the # of rows that need to be rolled-up. Luckily, we can pre-compute these statistics during the pre-loading phase.

In the preload, we batch together a number of COUNT and COUNT(DISTINCT) calls to cache:

1. the number of rows in the MV
2. the number of distinct values per column
3. the top-k most common values and their count per column (to improve estimates)

Then, estimating the number of filtered rows looks like:

num_filtered_rows = num_rows
for f in filters:
  if f.value in top_k:
    num_filtered_rows *= top_k[f.col][f.value] / distinct[f.col][f.value]
  else:
    num_filtered_rows *= 1 / distinct[f.col][f.value]

Next, there's additional cost if the MV has higher granularity than the query. For example, if the query groups by (type, day, hour) but the closest MV groups by (type, day, hour, minute), DuckDB will need to rollup the values in the minute. We can approximate this rollup cost as:

num_rolled_up = 1
for col in mv.group_by:
  if col not in query.group_by:
    num_rolled_up *= distinct[col]

Finally, I computed the total cost as a linear combination of the two. These are all rough hyperparameters and require more tuning in the future.

Example

This is taken directly from the v1 solution when trying to optimize the following query:

Query:

{'select': ['day', {'SUM': 'bid_price'}], 'from': 'events', 'where': [{'col': 'type', 'op': 'eq', 'val': 'impression'}], 'group_by': ['day']}

Logs from verbose=True:

Considering mv_auction_id_full: cost 80316988.0
Considering mv_advertiser_id_full: cost 7132445.0
Considering mv_publisher_id_full: cost 4868461.0
Considering mv_user_id_full: cost 72091914.0
Considering mv_day_fast: cost 366.0    <--- planner rewrites query to use `mv_day_fast`
Considering mv_time: cost 6252631.0

Efficient caching and warmup

The last significant optimization was warming up the DuckDB buffer manager and OS cache. This lets subsequent queries hit warm pages and avoid direct disk reads.

To do this, I ran ANALYZE mv_... for each of the materialized views. Any similar operation that scans all of the data (e.g. COUNT(*)) should have the same effect.

I timed this on my validation suite; the variation makes it hard to tell, but this step offers some speedup and doesn't hurt subsequent performance in any way.

Miscellaneous: using enums for types; re-computing AVG from SUM/CNT; ZSTD compression.

Implementation

Benchmarking

We implemented a generic Solution class (benchmark/solution.py), which both the baseline and v1 solutions inherit from.

Additionally, we provide options to:

• benchmark over multiple runs (--num-runs)
• plot stats (benchmark/plot_stats.py)
• compare against a ground-truth directory of results (--expected-dir)

Materialized Views

To avoid duplicated SQL and code, we created a custom MaterializedView class that can automatically generate the corresponding CREATE TABLE SQL statement. This lets us manage the set of MVs solely from Python and automatically handle routing.

The logic for the planner and assembler can be found in src/planner.py and src/assembler.py. We automatically convert aggregates like SUM(bid_price) to a normalized name sum_bid_price.

Testing

For rigorous testing, we generated an additional set of 25 validation queries (found in queries/validation.json). This let us confidently experiment with various choices for the materialized view, without overfitting to the provided 5 examples.