The cache key was the whole problem

We had a query result cache with an 11% hit rate. Everybody’s first instinct, including mine, was that the cache was too small. It was not. The cache was fine. We were asking it the wrong question.

What we were keying on

The original key was a hash of the SQL text, normalised for whitespace:

func Key(sql string, args []any) string {
    normalised := strings.Join(strings.Fields(sql), " ")
    h := sha256.New()
    h.Write([]byte(normalised))
    for _, a := range args {
        fmt.Fprintf(h, "%v", a)
    }
    return hex.EncodeToString(h.Sum(nil))
}

That looks reasonable and it is nearly useless, because these are the same query and three different keys:

SELECT id, name FROM users WHERE org_id = $1 AND deleted_at IS NULL;
SELECT id, name FROM users WHERE deleted_at IS NULL AND org_id = $1;
select id, name from users where org_id = $1 and deleted_at is null;

Six services wrote those queries. Nobody was wrong. The cache just could not tell they matched.

What we changed

Parse to an AST, canonicalise, then hash. Predicate order gets sorted, identifiers get folded, literals get separated from structure.

The part that took three weeks

Not the parser. Agreeing on what “the same query” means.

ORDER BY changes the result, so it stays in the key. LIMIT does too — unless you cache the unlimited result and slice it, which we tried and reverted because memory got worse than the cache miss it saved. A comment does not change the result, so it comes out. A schema qualifier sometimes does, depending on search_path, which is the sort of sentence that ends a meeting.

The rule we landed on:

1. Anything that can change the returned rows stays in the key.
2. Anything that only changes how the query was written comes out.
3. When you cannot decide which category something is in, leave it in. A missed hit is cheap; a wrong hit is a bug report you will not be able to reproduce.

What I would do differently

Measure the key distribution first. We spent the first week tuning eviction because that is the knob a cache exposes. Ten minutes of logging distinct keys per logical query would have pointed straight at the problem — the histogram was absurd, and nobody had looked at it.

The cache was never the bottleneck. The definition was.