Adaptive prefix buckets: how one keystroke becomes ten suggestions

AutoSugges locks the runtime autocomplete path out of PostgreSQL entirely. Everything a keystroke needs — ranked, filtered, addressable — has to already exist before the request arrives. The compiler is the one thing that turns authored rows into that form, and it does it once, at publish time, rather than once per query.

The compiler groups every searchable token by its first two characters — never one — then, per node, decides whether to terminate or branch into one child per distinct next character and recurse. A node terminates when it hits the architecture ceiling of level 5, when its member count already fits the list’s configured display limit so a deeper bucket would only repeat it, or when no depth between here and level 5 would split the group at all.

That last check looks all the way to the ceiling, not one character ahead — a shared substring like "san " across San Diego, San Francisco and San Jose would make a one-step lookahead give up one character before the split that actually matters.

Each bucket assembles about ten pre-ranked suggestions by default, plus metadata about its child buckets. Display order is capped to the list's configured result limit for a non-terminal bucket; a terminal bucket — one with no deeper compiled level to fall back on — retains up to 500 items or 1 MiB, whichever binds first, because it has to answer every longer query on its branch, filtered at the edge.

Crucially, a deeper prefix retains its own eligible items independently — showing the top ten at "da" does not remove anything from what "dal" or "dall" can show. Nothing is lost by narrowing.

Because every node is reached by recursion from level 2, no deep bucket exists without its shallower ancestors, which is what lets the edge truncate a longer-than-compiled query to the longest matching prefix and always find something to filter against. A query for a prefix deeper than anything compiled is served from the longest compiled bucket on that branch and filtered at the edge against the full normalized query — with no additional KV read.

The result is a normal cache-miss query path that costs two KV reads total: one for the key and context, one for the bucket. Everything expensive — ranking, grouping, deciding depth — already happened once, at compile time, for the whole list.