I built a minimal backend that searches a huge dataset and returns the 10 most popular matches. I wanted to find the bottlenecks in a simple search implementation and measure how each optimization changed performance. I started with the simplest version and improved it step by step, using the same data and query prefixes throughout. At the end of the final version, the query time for a single keyword a drops from 2.6 seconds to 2.9 milliseconds.
It is written in Go, with the standard library only. There is one search endpoint and one HTML page, both served by the same Go program. The code, the results and the git tags for each level are in the repo: https://github.com/bhowmik94/autocomplete-10M.
A query for the one-letter prefix a over 13.5 million places took 2.6 seconds in my first version. In the final version it takes 2.9 milliseconds. A longer prefix like dhaka went from 2.4 seconds to under 2 microseconds.
Disclaimer: These benchmarks measure the search function, not a deployed API.
Dataset and method
Data: I used the allCountries file from GeoNames, which has 13,472,243 rows. Each row is a place: a city, a village, a district and so on. The file has 19 columns, and I use only four: ID, name, country code and population.
I developed everything on cities15000 first, a smaller file with about 34,000 rows, and moved to allCountries once the naive version worked. I chose GeoNames over other free datasets, like Wikipedia article titles, because it has a population column, which gives a clear way to rank the results. The data is licensed under CC BY 4.0 and comes from GeoNames.
Ranking: Matches are sorted by population, highest first. If two places have the same population, the higher ID wins. Matching is case-insensitive and ignores leading spaces. I kept the ranking basic on purpose, because it was not the primary goal of this study.
Machine: AMD Ryzen 5 5500U, Windows, 12 threads, Go 1.26.4.
Benchmark prefixes: I measured four prefixes that behave very differently. The block size is the number of places whose name starts with the prefix. I estimated it from the memory the Level 1 version allocates, so treat it as approximate.
| Prefix | Block size | Why it is in the set |
|---|---|---|
a |
about 590,000 | Huge block |
dha |
about 12,000 | Medium block |
dhaka |
about 200 | Small block |
xyzq |
0 | No match |
Keeping it fair: Every level runs on the same data, the same prefixes and k = 10. I ran the same benchmark cases against every implementation. A separate test compares each version with the naive one for every prefix in a small dataset. The naive version is slow but simple, so I used it as the reference for correct answers. Before building each level, I wrote down what I expected to measure and compared it afterwards.
Level 0: the naive version
For every query, the naive version goes through all rows, lowercases each name, checks whether it starts with the prefix, collects the matches, sorts them by population and returns the top 10.
On the 34,000-row file, a query for dha took about 3.5 ms. On the full file it took about 1.4 seconds. That is roughly 105 ns per row in both cases, so the cost grows in line with the number of rows. A prefix with no match (xyzq) took as long as dha, which shows that the cost is the scan itself, not the matching. The one-letter prefix a was the slowest, because about 590,000 places match it and have to be collected and sorted.
| Prefix | Time per query | Memory per query | Allocations per query |
|---|---|---|---|
a |
1.76 s | 414 MB | 13.47 million |
dha |
1.41 s | 244 MB | 13.47 million |
dhaka |
1.47 s | 242 MB | 13.47 million |
xyzq |
1.45 s | 242 MB | 13.47 million |
The allocation count is the useful clue. It is one allocation per row, which is the lowercase copy of every name that is created on every query. That is why even a prefix with no matches allocates 242 MB. In the naive version, memory depends on the size of the dataset, not on the size of the matching block.
Loading the full file took about 9.8 seconds and the heap was 993.5 MB afterwards. Getting there needed one memory fix. Go’s strings.Split returns pieces that point into the original text, so keeping a single city name keeps the whole file text alive. On the small file the heap after loading was 10.2 MB. Copying each name with strings.Clone brought it down to 2.5 MB with the same load time. On the full file the unused text would have been over a gigabyte.
Level 1: sort once, binary search
The naive version repeats the same work on every query. Level 1 does that work once, at startup:
- Each place gets a
LowerNamefield, computed once when the data is loaded. - The whole list is sorted once by that field.
After sorting, all places whose names start with the same prefix sit next to each other in one unbroken stretch of the array. I call this stretch the block.
Two binary searches find the block: one for its start, one for its end.
To find the end, I search for the prefix with its last character incremented—for example, dha becomes dhb. Every dha match sorts before that boundary. Then I copy the block, sort the copy by population and return the first 10. The copy is important since the block is a window into the shared array, and sorting it in place would reorder the index for every later query.
The speedup has a price. The extra lowercase names raised the heap from 993.5 MB to 1,403.6 MB. The one-time sort takes about 10 seconds on top of about 10 seconds of parsing, so startup is now about 20 seconds.
| Prefix | Naive | Level 1 | Level 1 memory per query | Speedup |
|---|---|---|---|---|
a |
2.64 s | 144 ms | 37.7 MB | about 18x |
dha |
2.34 s | 2.1 ms | 771 KB | about 1,100x |
dhaka |
2.39 s | 19 µs | 14 KB | about 124,000x |
xyzq |
2.33 s | 572 ns | 32 B | about 4 million x |
A note on the naive column: after the data was sorted, the naive version ran slower than in my first measurement (2.3 to 2.6 seconds instead of 1.4 to 1.8), although its code had not changed. I suspect cache misses: the sorted records still point to names laid out in file order. I haven’t tested that explanation. Every speedup in this article compares numbers from the same run.
Two things stand out. A no-match query takes 572 ns: it only needs two binary searches. For matching queries, time depends on the block size. a matches about 590,000 places and takes 144 ms; dha matches about 12,000 and takes 2.1 ms. The number of allocations is constant (6), but the bytes still grow with the block, because the block is copied and sorted.
Level 2: do not sort what you will not use
Level 1 copies and sorts 590,000 places to return 10 of them. Level 2 walks the block once and keeps a list of the best 10 places seen so far, sorted best first. Most places are worse than the current tenth-best result, so I skip them. If a place is better, I move it into the right position. Otherwise it replaces the worst one and moves up to its position. There is no copy and no sort. For k = 10, a small sorted slice is enough. I did not try a heap, which should only help for a large k.
| Prefix | Level 1 | Level 2 | Level 2 memory per query | Speedup over Level 1 |
|---|---|---|---|---|
a |
144 ms | 2.9 ms | 708 B | about 49x |
dha |
2.13 ms | 47 µs | 712 B | about 45x |
dhaka |
19.3 µs | 1.9 µs | 712 B | about 10x |
xyzq |
572 ns | 454 ns | 8 B | about 1.3x |
Memory per query is now about 700 bytes (the ten places), no matter how big the block is. The no-match prefix barely changed, since it was already just two binary searches.
The remaining 2.9 ms for a looks like a memory limit. The block contains about 590,000 records of 64 bytes each, or roughly 38 MB. Scanning it in 2.9 ms works out to about 13 GB/s—close to the bandwidth I’d expect from a laptop. The loop only needs the population and the ID of each place, but it pulls in all 64 bytes. So the limit is now the memory layout, not the algorithm.
Across both steps:
| Prefix | Naive | Level 1 | Level 2 | Total speedup |
|---|---|---|---|---|
a |
2.64 s | 144 ms | 2.9 ms | about 900x |
dha |
2.34 s | 2.1 ms | 47 µs | about 50,000x |
dhaka |
2.39 s | 19 µs | 1.9 µs | about 1.3 million x |
xyzq |
2.33 s | 572 ns | 454 ns | about 5 million x |
Serving it over HTTP
There is one search endpoint, for example, GET /suggest?q=dha&limit=5. The default limit is 10, and values outside 1–50 are clamped. Non-integer values return a 400 response. The search function is a field of the server struct, so any of the three levels can run behind the same endpoint.
Go handles each request in its own goroutine, so many requests read the index at the same time. That is safe because nothing modifies the index after startup: each query only reads it and builds its own 10-place result. If a query had sorted the shared array in place, requests would have corrupted each other. A test with 50 concurrent requests, using Go’s httptest package, runs against the handler.
The HTML page is a single static file served by the same Go program at /. Serving it from the same place as the API avoids CORS issues and keeps the project small.
Limitations
- No end-to-end load test. The timings above call the Go functions directly. They leave out the network, HTTP parsing and JSON encoding, so a real request takes longer. Everything ran on one laptop.
- Estimates. The block sizes are estimated from allocated memory, and the slowdown of the naive version on sorted data is an untested guess. The naive version was measured with five iterations per prefix, because each run takes seconds.
-
Basic search quality. Only the name is matched, with no accent folding, so
munchendoes not find München. Alternate names are not indexed, places with the same name are listed separately, and ranking uses population only. - Startup and memory. Startup takes about 20 seconds and the index needs about 1.4 GB of RAM per instance.
What could come next
- Store populations and IDs in separate compact arrays, so the scan for
areads a few bytes per place instead of 64. - Use a range-maximum structure (a sparse table or a segment tree) with a heap, so the cost depends on k and not on the block size.
- Precompute the top 10 for the shortest prefixes.
- Compare against Postgres with an index and a cache, and deploy it to the cloud.
What I learned
- Write predictions down before measuring. It shows you what you did not understand yet.
- Allocation counts show where time goes. 13.47 million allocations per query pointed straight at the lowercasing of every name.
- Cost can depend on the part of the data a query touches, not on the dataset size. After Level 1, a query over 13.5 million places that matches nothing takes 572 ns.
- Memory layout can matter as much as the algorithm. Level 2 runs at roughly the speed of memory, and the naive version may have got slower just because the data was reordered.
- Keep the slow, simple version. The naive version was my reference for correct answers in every test.
Code, results and git tags: https://github.com/bhowmik94/autocomplete-10M. Data: GeoNames, CC BY 4.0.
Top comments (10)
Sorting 590,000 matches just to keep 10 is a painful image. Did the one-pass top 10 change how you think about block size at all?
Thanks for your question. Yes, it certainly did. The one-pass approach let me walk the block just once, just keeping a podium of the "best 10" so far. It's far less painful and requires less computation and storage. In case of a large block size (e.g., 590,000), I am thinking of keeping pre-computed prefix blocks, which should improve speed and memory further (I assume).
Would precomputed blocks pay off only for the shortest prefixes, or is that worth it across the board?
I assume precomputed blocks would only pay off for shortest prefixes. It depends on the size of the matching block. If the block is significantly large (~590,000 entries), then its worthwhile to store a precomputed block. For smaller blocks the tradeoff could be negligible.
The 590,000 case is the clear win. Where does the cutoff stop being worth it for you?
The cutoff could be matching blocks with at most three prefixes (
d,dh,dha). After three prefixes, the matching block size is so small that it's overkill to store precomputed blocks for them. But again, this is purely estimation. I will need to run an actual experiment to confirm this.Three prefixes as the cutoff makes sense, past that the blocks are small enough to just scan.
Thanks for separating search-function timing from API latency. How does the index behave for skewed prefixes under concurrent requests, and what memory overhead does the final structure add?
Thanks, great questions!
Memory: the original struct had four fields, as the article mentions. After adding the additional field (
lowerName), the heap memory went from 993 MB to 1,403 MB, so about +410 MB. I measured the heap after loading, not the peak during startup (parse and sort), which may be higher.Skewed prefix: single-threaded, the cost follows the size of the block of matching names, at ~ 5 ns per place. A one-letter prefix (~ 590k places) takes 2.9 ms, a three-letter one (~ 12k) takes 47 µs, and dhaka takes 1.9 µs. The index is read-only after startup, so concurrent requests don’t lock or block each other, and I tested 50 concurrent requests for correctness. I haven’t measured throughput under concurrent load yet. But this could be a natural next step for benchmarking.
The heap delta is a worthwhile trade-off if it stays inside the deployment envelope. I’d also capture peak startup memory and build time, since parse-plus-sort spikes often decide whether an otherwise fast read-only index is viable in a container.