Costing an AI-powered SQL filter

What it is

An AI-SQL query runs an LLM on every row. One WHERE clause asks the model true or false about each record. Before running the query, an engine wants to know how long it will take on a given model and GPU. Profiling answers that, but you redo it for every new model, GPU, and workload. The roofline model answers with arithmetic instead: count the work a query demands, divide by what the hardware can deliver, and you get a speed-of-light latency, the fastest the query could run.

The method comes from a Full Stack Data Lab (Carnegie Mellon) post by Arnav Dhariya and Shreya Shankar, built for Quail, their AI-SQL execution engine. Quail uses the estimate to pick between query plans.

The core idea: compute time or memory time, whichever is longer

Every GPU kernel does two things: it computes, and it moves data between HBM (the GPU's main memory) and the chip. A modern GPU overlaps the two, so the slower of them sets the kernel's time, not their sum.

Π (pi) is the GPU's peak compute rate in FLOP/s. β (beta) is its memory bandwidth in bytes/s. Divide the work a kernel needs by each ceiling and take the larger quotient. The ratio of work to data, operational intensity I = FLOPs / Bytes, decides which ceiling binds. The crossover sits at the ridge point I* = Π / β. Above the ridge point the kernel is compute-bound. A kernel below it is memory-bound, starved for data.

How it works, step by step

1. Split the forward pass into three parts — the linear projections (query, key, value, output), the attention, and the MLP block. Each has its own FLOP count and byte count.
2. Count the work. A dense matmul over the model's weights costs about 2 FLOPs per parameter per token. The bytes are the weights and activations each part reads from HBM.
3. Divide by the ceilings and take the max per part. Projections and MLP run in FP8; attention runs in BF16 under FlashAttention, so each part uses its own Π.
4. Sum the three parts to get one filter's latency over the whole batch of rows.
5. For a chain of filters, reuse the KV cache. The first filter encodes each document once; later filters read those cached key/value vectors and pay only for their own question.
6. Order the filters so a cheap one that rejects most rows runs first and shrinks the set the later filters must ask about.
7. Add the per-filter times for the query's speed-of-light estimate.

What binds: compute or memory

Each part of the forward pass sits on a different side of the ridge point, and the side moves with how many tokens you push through at once.

Batch enough rows together and the projections and MLP become compute-bound, with the matmuls keeping the Tensor Cores busy. Attention stays small until requests get long, because a short review moves little data for the arithmetic it triggers.

A worked filter: 5,000 reviews in 6.64 seconds

The setup: Qwen3-4B in FP8 (3.6×10⁹ non-embedding parameters, 36 layers, grouped-query attention with 8 KV heads), one H100, and 5,000 IMDB reviews averaging 298.8 tokens each. The filter F₁ asks whether a review mentions a positive aspect. Every request is a preamble, the review, and the question; the model answers with a single token.

DOCUMENT:
<the review text>
Evaluate TRUE or FALSE for the following question: <filter predicate>

→ output: one token, true or false

The hardware ceilings that go into the roofline:

Running F₁ over all 5,000 reviews takes 16 forward passes. The roofline gives each part a compute time and a memory time, and you pay the larger.

Every part is compute-bound, so memory time never shows up in the bill. The MLP block is the single biggest cost. Total: 6.64 seconds to run an LLM over 5,000 reviews.

Chaining filters, and why the order matters

Real queries chain several filters with AND. The trick is the KV cache. The first filter processes each review once. Call that the scan, about 1.3 ms per document. That work produces key/value vectors for the preamble and the document, and those stay cached. Every later filter reuses them and pays only the ask: its own question tokens plus the one output token, about 0.2 ms. The scan dwarfs the ask, so the second and third filters are nearly free next to the first.

Because each filter passes only some rows to the next, the order sets how many documents reach each ask. The authors rank filters the way Hellerstein and Stonebraker ranked expensive database predicates: by cost over rejection power.

Here s_i is selectivity, the fraction of rows that pass. A low rank means the filter is cheap to ask and throws out a lot, so it goes first. Sort ascending by rank; the sort costs O(m log m) for m filters.

F₂ rejects 77% of reviews and is the cheapest to ask, so it leads. The engine runs F₂ → F₁ → F₃, not the written order. The payoff is modest because most of the cost is encoding each document once, which you pay no matter the order:

Leading with F₁ instead of F₂ costs about 4.7% more. The whole three-filter query lands at 6.87 s, just above the 6.64 s for F₁ alone, because KV reuse makes the two extra filters almost free.

Fitting the batch in memory

The KV cache has to fit in HBM. The authors budget it from the 80 GB on the card: about 76 GB usable, minus 4.5 GB for the FP8 weights and 18.08 GB for temporary buffers, leaves 53.42 GB for the cache. One document's prefix KV runs about 44.4 MB, so roughly 1,200 documents fit at once and the 5,000 reviews run in five batches. The query-wide estimate works out to 1.34×10¹⁶ FLOPs and about 6.86 seconds.

Limits and what to check