My ANN index gets slower than brute force the more data I throw at it

My hand-rolled ANN index should beat brute force as data grows. Instead the gap gets worse — 200 rows it's a tie, by 4000 it's 50% slower. Digging into why, in a toy Rust database built to learn how databases actually work.

I've been building a toy database engine in Rust to actually understand how databases work under the hood — append-only KV store, compaction, schema, a hand-written SQL parser. No dependencies, single-threaded, on purpose. The point was never to ship something. The point was to learn.

At the beginning of the project I had Claude wire in support for a vector column, mostly because I kept hearing about vector databases and wanted to know what the fuss was about. I didn't know what I was looking at. It inserted some test coordinates, they got saved, and... that was it. Numbers went in, numbers came back out. I had no real sense of what made this different from just storing an array of floats in a normal column.

I went to Gemini to get a rough overview of what a vector database actually is. That's where "ANN" — approximate nearest neighbor search — first showed up on my radar as the thing that's supposed to make vector search fast.

So I had Claude add a basic ANN index — locality-sensitive hashing (LSH) — and we ran brute force against it at a few sizes:

rows	brute force	ANN (LSH)
200	1.35ms	1.29ms
1000	2.36ms	3.06ms
4000	6.84ms	10.26ms

At 200 rows they're basically tied. By 4000 rows, ANN is about 50% slower than just scanning everything. That's the part that actually bugs me — ANN is supposed to get relatively better as the dataset grows, not worse. Something in my implementation has overhead that scales worse than a plain linear scan does, which means this probably isn't "ANN hasn't hit its crossover point yet" — it's more likely a real bug. Too few hash tables, bad bucket sizing, something in that family. Haven't dug into which yet.

At that point I made a call: shelve the vector stuff. The actual goal of this project was to understand a relational database, and my SQL support was still pretty thin. Spending time tuning an index for a feature that was tacked on for curiosity, before the core of the database could even do basic SQL well, was backwards. So I parked it and went back to SQL.

Fast forward to now — SQL support is at a level I'm comfortable with, and I circled back to vectors. First question: how does data actually get into a vector column in a real app? You can't have a person type in coordinates. That's when I learned the values come from embedding — generated by a small ML model — not something a human ever hand-enters. That was a genuine "duh" moment. This kind of opened my mind to "how can I use this?"

Then I talked it through with Claude — how would I actually use this in one of my existing apps — and that's what led to research into ANN tuning, and into the fact that ANN losing to brute force isn't necessarily a broken implementation, it's often expected until you hit a certain data size, or it's a sign of a specific bug (too few hash tables, poorly chosen hash functions for the vector dimensionality, or bucket sizes so large that a "bucket scan" is nearly a full scan anyway, with hashing overhead stacked on top).

Which is where I am today: not trying to bolt AI-embedding integration onto an app — I've already done that elsewhere — but trying to actually understand why my ANN is bad, fix it, and ideally give my toy engine more than one vector search strategy instead of just one bad one.

And now I dig deeper into the rabbit hole of vector datatype. How deep does this rabbit hole go?