Do Nothing: My Database’s Optimization Strategy

Intro

In a previous job, Spike (* obv. not real name) was the person you called when the documentation, the code, and common sense had all failed you. He was good at it. But after more than a decade of the same questions, he had developed one small defense mechanism.

Spike started many of those calls with the same question:

“Why do you even want to know that?”

It was more than pure rudeness. It was triage, delivered with genuine curiosity. Half of the questions dissolved once the caller had to explain the goal. The other half either became shorter and better, and Spike would stay on the line until they were solved. He was not refusing to help per se; he was refusing to optimize the first bad idea that reached his desk. Good engineers loved him for it. They just learned to bring a reason.

Be like Spike.

Before making an operation faster, I want to know why it exists. Before adding threads or generating code, I want to know what data it still touches. And before believing an answer, I want a measurement that can prove it wrong.

The order that usually survives contact with a workload is this:

Produce fewer intermediate results. Make each survivor cheaper. Then optimize what remains.

Cypherlite is called PatinaDB now. Version 0.22.0 is my latest internal dev revision, and its query-planning manual now gives the engine receipts: access paths, statistics, factorized operators, bounded memory, warnings, and the cases where none of them are allowed to fire. This is not a production-readiness claim. It is a tour through the ways a query engine can decline work.

It is a post about a philosophy I keep reiterating on relearning every time I stray from it: delete work before you optimize it.

Benchmarks first, stories later

My oldest bias is data structures first. Your data’s representation determines which operations you need, what sits together, and what you have to chase through memory. I like algorithms. I like them less when their main job is compensating for a bad layout.

But a persuasive explanation is not evidence. I know because I’ve built optimization traps specifically to watch them fail.

Back in 2022, I opened a SIMD experiment with Knuth’s warning that premature optimization is the root of all evil, and then walked straight into the trap on purpose. The result had everything premature optimization deserves: handwritten intrinsics, four times the code, no portability, and performance that ranged from useful to slower than the plain implementation. LLVM was apparently unimpressed by how clever my handwritten version was supposed to be.

Then I gave the same treatment to memory layout. Better locality, more useful data per cache line, a persuasive explanation. The single-threaded benchmark agreed.

The multithreaded benchmark did not. The simple implementation won again.

That reversal was the lesson I wanted to get across in those blog-posts. Once several workers processed row-adjacent windows, the original layout used cache lines better than the supposedly improved one. “Better locality” had never been a property of the layout alone; it depended on who accessed which bytes, and when.

The trap only works because the first explanation feels so convincing. The multithreaded benchmark is the cure.

So when the next sections introduce predicate placement, statistics, factorized branches, and the execution engine, treat each of them as a suspect. The workload gets the final vote.

The cheapest row is the one you never produce

Consider an innocent-looking graph query:

MATCH (p:Person)-[:COMMENTED]->(t:Ticket)-[:HAS_LABEL]->(l:Label)
WHERE l.name = 'database'
RETURN p.team, count(*) AS comments
ORDER BY comments DESC
LIMIT 10

Five lines of Cypher. Plenty of room to waste work.

Start from every person, and you may expand relationships that could never match the label. Start from the label, and the first expansion is already constrained. Check the label name after expanding every ticket, and you have manufactured candidates merely to discard them. Load properties before applying the filters that need them, and each doomed candidate picks up a memory bill on its way out.

Start by deciding which work never needs to happen. Early predicate evaluation reduces the data reaching downstream operators; choosing an entry point changes how many candidates exist before any operator gets expensive (CMU).

The next question is whether those candidates need to become rows at all.

Our query asks for a count per team. It does not need every person, ticket, and label combination materialized as a separate intermediate tuple. If the pattern can be split into independent branches around a pivot, PatinaDB’s factorized operators can read those branches and combine their multiplicities instead of building the cross product row by row (PatinaDB query planning). “Compact” does not mean “semantically free”: multiplicities must survive the aggregation, or the count becomes fiction (Kùzu).

The same refusal to materialize the pile applies to cyclic patterns, and this is where 0.22.0 gets its best trick. With a binary join plan, a triangle or four-cycle creates a large intermediate result before a later join closes the cycle. Worst-case-optimal joins intersect sorted adjacency lists instead of building that pile first (Mhedhbi & Salihoglu). PatinaDB ships exactly that: closing-edge probes, multi-way intersection, and a leapfrog join for cyclic patterns, with the cost model deciding when the intersection is worth it (PatinaDB query planning). The triangle never becomes a pile. The engine counts branches and intersects lists; it does not manufacture rows it intends to throw away.

Predicate placement, entry choice, and factorized branches look different on a whiteboard. At runtime, they all reduce the same thing: the intermediate matches the engine is willing to create.

The Kùzu paper also shows the trade-off. Keeping results factorized can conflict with accessing graph data sequentially. Fewer logical tuples can mean less convenient physical reads. Optimization is not a checklist; it is a negotiation with the workload.

The statistics catalog is deliberately boring in the right way: label counts, present counts, distinct values, min/max, and a small histogram. It changes which plan runs, never which result is correct. It is cached, tagged by write generation, and local to each node rather than replicated (PatinaDB query planning).

A histogram can be wrong in a more educated way than a heuristic. Cardinality-estimation errors can materially affect plan quality (Dutt et al.). That is why the planner’s Decisions: section and PROFILE matter: I want to see what the optimizer believed, which access path it chose, and what execution actually did.

Then stop touching memory

Suppose the plan now produces fewer matches. Each survivor still has a physical bill: identifier resolution, label checks, cache lookups, property reads, and the state it passes to the next operator.

At this point, “make the operator faster” is the wrong first question. The better one is what does each remaining match still touch?

PatinaDB’s access paths carry the same idea into storage. A typed edge key can prove fixed-hop membership without expanding a whole adjacency; a direct typed-edge EXISTS can become one index seek; a primary-label ID already stored in the edge key can remove a redundant lookup (PatinaDB query planning). These are not general traversal magic. They are narrow proofs that let one record answer a question that would otherwise require several reads.

The principle is simple: if information has already been fetched, let it answer as much as possible. If the query never needs it, leave it alone.

That sounds exactly like the seductive logic behind my cache-line experiment: if I’ve already paid for the bytes, make them useful. It worked beautifully until the access pattern changed. “Useful bytes” depend on the workload. They are not a property of the layout.

Derived indexes and cached structures deserve the same suspicion. They can make repeated access cheaper, but they are not a new source of truth. PatinaDB’s own wide-index work is a good warning: a smaller representation did not guarantee fewer physical reads under every access path, and constrained-memory tests found cases where primary scans read more from disk despite a smaller index (PatinaDB query planning).

Every derived structure sends an invoice: memory, construction work, write maintenance, and consistency with the reader’s snapshot. A stale cache is just a rumor with a hash map. I want those costs in the benchmark, not in a footnote under the victory chart.

Rust helps me keep that invoice visible. Ownership and borrowing make me ask who owns an intermediate result, whether the next operator can borrow it, and why anything is being cloned. Send and Sync express whether ownership or shared access can cross thread boundaries (Rust ownership, Rust Send/Sync). The language does not choose a good representation for me; it makes some consequences harder to ignore.

Confidence in a design is cheap. The borrow checker remains unimpressed by confidence; it wants an ownership proof.

Make the remainder faster

Only after reducing matches and memory traffic do I want to talk about execution machinery.

Morsel-driven execution uses fine-grained runtime scheduling: workers receive small input fragments, and the degree of parallelism can change during execution instead of being frozen into the plan (Leis et al.). PatinaDB applies the same suspicion to its aggregate and join work: memory admission is part of execution, blocking operators have bounded state, and past the configured limits the query fails loudly instead of quietly becoming a different answer (PatinaDB query planning).

Throwing 32 threads at 12 rows is not scalability. It’s a bonfire with a job scheduler.

JIT belongs at the same stage. Query compilation can specialize operators, fuse pipelines, keep values in registers, and avoid intermediate materialization. Those are useful savings on work that actually has to run.

The compiled-versus-vectorized study by Kersten and colleagues shows why this is not a religious war. Data-centric compilation executed fewer instructions and helped cache-resident, computationally intensive work. Vectorized execution was better at hiding cache-miss latency in some memory-bound cases. Both could scale across cores. The workload decided which property mattered.

That is still my working hypothesis, not a result: for traversal-heavy graph workloads, planning and data layout should matter more to multicore scalability than JIT-compiling the chosen plan. Settling it would require an actual compiled alternative and a controlled experiment.

But the order makes sense either way. Parallelism can execute bad work faster. JIT can execute it with less overhead. Neither makes the work necessary.

You can compile a full graph scan into beautiful machine code. It will still be a full graph scan.

Correctness sets the boundaries

There is one constraint around every stage: you may not delete semantics.

Specialized paths apply only where their guards can prove the semantics fit. Duplicates, filters, nulls, relationship uniqueness, snapshots: all the annoying cases still apply. openCypher’s rules for relationship uniqueness and null behavior are exactly the kind of details an optimized path cannot quietly discard (openCypher).

The same rule applies to failure. PatinaDB’s COUNT and EXISTS paths propagate subplan failures instead of converting them into an empty-looking answer. Property reads, storage errors, timeouts, and memory-limit errors are not zero counts or false existence results (PatinaDB query planning). Cached data must agree with the reader’s snapshot; snapshot-based visibility is part of a database’s isolation contract, not merely a read optimization (PostgreSQL).

Rust’s guardrails help with resource ownership and concurrency, but memory safety does not establish database correctness. The borrow checker does not care about your cardinality estimate. I still need profiling, differential tests, crash tests, and workloads capable of ruining my evening.

A faster wrong answer is still a wrong answer. Just with better marketing.

Where 0.22.0 stands

The manual reads less like a feature checklist than a list of ways to avoid work: value-index point lookups, IN-list seeks, prefix scans, compound range seeks, index-served ordering, bounded top-K, keyset pagination, group-by-count scans, direct relationship counts, factorized branch counts, closing-edge probes, leapfrog intersection for cyclic patterns, and narrow existence paths. The common thread is not “look how many tricks we have.” It is “look how little the engine is allowed to touch when the proof is good enough” (PatinaDB query planning).

Some of those proofs are intentionally narrow. Factorized operators need an admitted shape and memory scope. Grouped factorized paths consult the degree catalog when the cost model is enabled. A fixed traversal can reuse a typed edge key only after direction, labels, properties, and relationship uniqueness have been accounted for. An existence fast path can answer with one seek, but only for the shape it can prove. That is the point: a fast path without a guard is just a shortcut to a wrong answer.

The remaining work is also less photogenic. Wider index keys change the physical trade-offs rather than producing a universal win. Cost estimates still need more estimated-versus-actual evidence under skew, memory pressure, and failure injection. Query compilation remains where it belongs: behind a controlled experiment, not behind enthusiasm.

Do less

Reduce the number of matches. Reduce what each match costs. Then optimize the work that remains.

Correctness sets the boundaries. Measurement decides what survives.

Every operation has to justify its existence. If it doesn’t contribute to the answer, it goes.

Self-help Singh would probably recommend that I stop building a database and go have three or four beers and then take a nap. Problem is: I write my best Rust when slightly drunk, and my motivation knows no limit after two Mass.

His advice has a home in the executor for now.