Programming at Light Speed: Building the Gravity Query Engine

With the release of pgrust v0.4-beta, our new query engine, Gravity, is now as much as 3x faster than ClickHouse on ClickBench, the benchmark that ClickHouse themselves designed to show off how fast ClickHouse is.

Even better, Gravity achieves that speed while supporting the full Postgres SQL dialect and type system.

In a couple of previous posts, I wrote about how we used batching, operator fusion, and SIMD to make pgrust hundreds of times faster than Postgres for analytical queries, and how we built a copy-and-patch JIT compiler that compiles stencils in 5 microseconds.

For pgrust v0.4, we wanted to go all the way and build a query compiler that generates optimal machine code for any SQL query. That is why we built Gravity. Normally, when engineers try to make software faster, they work from the bottom up. They run a benchmark, look at a flamegraph, find a hotspot, and figure out how to speed up their code by 15% or 20%. The problem with working from the bottom up is that you don't know what the ceiling is. You might be 20% away from the fastest possible code the hardware can run, or you might be 100x away.

When we started building Gravity, we flipped this question around. We asked ourselves: how fast can a database actually be? Instead of incrementally speeding up our existing query engine, we wanted to start from the physical speed limit of our hardware and file format and work backward. I like to call this “programming at light speed”.

When we ran those handwritten Rust programs, they executed queries roughly 4x faster than existing analytical databases like ClickHouse across the board. We then mined those hand-tuned Rust loops for optimizations we could incorporate into Gravity.

Our goal for Gravity became simple: for any SQL query, JIT compile machine code at runtime that gets within 20% of the handwritten Rust code Claude wrote directly against our file format. The General Architecture of Gravity Our main goal when designing Gravity's architecture was to give ourselves a ton of flexibility in the generated output. We knew that if we made it easy to change Gravity to emit whatever low-level optimizations a query needed, it would become much easier for us to close the gap and approach light speed. Instead of hardcoding execution patterns or stitching fixed stencils together, we structured Gravity as a multi-stage compiler pipeline that progressively lowers a high-level Postgres plan down to raw assembly: SQL Query -> Postgres Plan -> Pipeline Graph -> Lisp IR -> Assembly To see what a query looks like at each stage of the compilation process, let’s take the following query: SELECT UserID, extract(minute FROM EventTime) AS m, MIN(URL), COUNT(*) FROM hits WHERE URL LIKE '%google%' GROUP BY UserID, m ORDER BY COUNT(*) DESC LIMIT 10; Stage 1: The Postgres Plan Gravity does not replace Postgres' parser or query planner.

When the query arrives, the pgrust planner analyzes the table statistics and produces a standard query plan. Limit (cost=...

rows=10) -> Sort (Sort Key: count(*) DESC) -> HashAggregate (Group Key: userid, extract(minute FROM eventtime)) -> Seq Scan on hits (Filter: (url ~~ '%google%')) Stage 2: The Pipeline Graph Next, Gravity takes the query plan and converts it into a “pipeline graph”. This is an intermediate representation that expresses how data will flow throughout the query execution. Each pipeline represents how a row is transformed and operated on throughout the query. Here is a sketch of what the Pipeline graph looks like for our query: graph pipelines=3 breakers=2 root=p2 p0 eligible end=breaker(slot=0 HashAgg) source range rel=hits am=pgrc lanes Attr(UserID):byval8 Attr(EventTime):byval8 Attr(URL):dict4 filter like(URL, param0) project (key0=UserID, key1=extract_minute(EventTime), agg0=min(URL), agg1=count_star()) p1 serial end=breaker(slot=1 TopK) source breaker slot=0 topk k=10 order=agg1:DESC p2 serial end=sink source breaker slot=1 project (UserID, m, min_url, count) -> wire In this case, the query is split into three pipelines: p0 takes the rows out of the hits table, filters for rows where the url contains “google”, and then inserts the rows into a hash table to calculate COUNT(*) and MIN(url) grouped by the user_id and minute of the event time p1 takes the resulting hash table and puts them into a heap of size 10 to calculate the 10 groups with the highest COUNT(*) p2 takes the resulting heap and pulls out the rows and sends them over the wire Stage 3: The Lisp IR Next, Gravity compiles each pipeline into a single function in our Lisp-based, assembly-like intermediate representation.

Because the IR is general, we can fuse the scan, filter, projection, and aggregation inside p0 into whatever loop structure we want.

(condbr v2585 (b211) (b35 ...)))

; no -> fetch the next batch (block b213 ((v2587 i64)) ; ── read the row's columns ── (Seq Scan) (v2591 (ptr_add v105 v2587 8 0)) ; &EventTime[row] (v2592 (ptr_add v109 v2587 8 0)) ; &UserID[row] (v2593 (ptr_add v113 v2587 4 0)) ; &URL[row] (dictionary code) (v2612 (loadz i32 v2593 0)) ; ── WHERE URL LIKE '%google%' ── (Filter) (v2616 (load i64 (ptr_add v2605 (ushr v2612 6) 8 0))) (v2621 (iand (ushr v2616 (iand v2612 63)) 1)) ; one bit per distinct URL ;; … ; row fails -> straight to the next row ) (block b227 () ; ── extract(minute FROM EventTime) ── (Projection) (v2695 (load i64 v2591 0)) (v2711 (iadd v2695 211813660800000000)) (v2715 (umulh (ushr v2711 10) 10746007285463371)) (v2720 (isub v2711 (imul (ushr v2715 11) 3600000000))) (v2726 (ushr (imul (ushr v2720 8) 18764999) 42)) ; minute (v2732 (load i64 v2592 0)) ; UserID ;; … ) (block b229 () ; ── GROUP BY UserID, m ── (HashAggregate) (v2897 (icmp eq v2576 v2732)) ; same UserID as the group in registers?

(v2899 (iand v2897 v2898)) (condbr v2901 (b249) (b250))) ; no -> write it to the hash table (b250), start a new group (block b249 () ; ── MIN(URL), COUNT(*) ── (HashAggregate) (v2903 (loadz i32 v2593 0)) ; this row's URL code (v2911 (icmp ule v2903 (iand v2581 4294967295))) (v2912 (select v2911 v2908 v2581)) ; MIN: keep the smaller code (v2921 (iadd v2584 1)) ; COUNT(*) += 1 (br b228 v2576 v2577 v2578 v2579 v12 v2912 v2913 v2915 v2921)) (block b228 (...)