17 — Design A Proximity Service

“Find me every restaurant within 2 km.”

An ordinary database index cannot answer a “what is near me” question efficiently. Understanding exactly why leads straight to the four standard fixes — geohash, quadtree, S2 and H3 — which all attack the same underlying problem in the same way.

By the end you will be able to take a radius in metres, derive the exact grid resolution that serves it, say how many rows you will scan to return one, and explain to someone else why the answer is never “just index latitude and longitude”.

No prior chapter is required. Every idea borrowed from elsewhere in the book is restated here in a sentence before it is used.

What goes in and what comes out. The service is one function with one shape. Fix that shape in your head before any mechanism:

input     a point on Earth, a radius in metres, and optional filters
          example:  lat = 40.7580, lng = -73.9855, radius = 2000, category = restaurant

output    a ranked list of businesses genuinely inside that circle, each with
          its exact distance from the query point
          example:  [{id, name, distance_m: 143}, {id, name, distance_m: 617}, ...]

Three terms carry the whole chapter, so pin them down now.

• A disc is the region the user asked about: every point within r metres of the query point. The request describes a circle on the map, not a rectangle and not a list of rows.
• An index is a data structure a database keeps beside a table so it can find matching rows without reading all of them.
• A B-tree is the classic index: a sorted tree that stores keys in one order and lets you jump straight to a range of that order. It is one-dimensional — it sorts by one value at a time.

A relational database can answer this question, and it will scan a band of the planet to do it. That single fact is the whole chapter.

A B-tree sorts along one line. A location is two numbers, not one. So every geospatial index ever built is a scheme for flattening two dimensions down to one without losing too much locality.

Locality is the property that points close together on the map get keys close together in the sorted order. It is what makes a range scan over the index return your neighbours instead of strangers, and it is the thing that a naive flattening throws away.

This chapter derives that flattening once — geohash, quadtree, S2, H3 — and the two chapters after it borrow the result rather than repeat it. 18 — Nearby Friends owns the write path when the points move; 19 — Google Maps owns the road graph laid over the same cells.

Three ways candidates lose this question:

• They propose WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ? and move on without pricing it.
• They say “geohash” without being able to say how many bits one character carries.
• They look up the one cell the query point falls in, rather than that cell plus its eight neighbours. That is wrong far more often than it sounds — Two defects and both of them are structural shows it is wrong every single time at some common settings.

Estimation technique is chapter 02. Index mechanics are sql/03.

1. Framing: what decision, and what breaks

One design decision carries the whole chapter, and one property of this particular data makes the problem far easier than it first appears.

The one decision

What is the key you look points up by, given that the query is a disc and a key is a scalar?

A scalar is a single value that can be sorted — a number or a string. That is all a B-tree understands. So the question is how you turn “latitude 40.758, longitude -73.9855” into one sortable value that still puts neighbours next to each other.

Everything else is downstream. Get that key wrong and you land in one of three holes:

• A full scan, because no index applies to the query you actually wrote.
• A wrong answer, because you queried one cell where you needed nine.
• A system that cannot be split across machines, because the index is an in-memory tree that no other process can read. Splitting data across machines is called sharding, and a scheme that cannot be sharded has a hard ceiling at one box.

The property that makes this easy

A restaurant moves address once a decade. That single fact is the gift of this problem: the index is derived, immutable-ish, and rebuildable from the source of truth. The source of truth is the authoritative copy of the data, the one every other copy is derived from.

Static data kills half the hard problems in this book before they start. There is no contention between concurrent writers. There is no consistency protocol needed to agree on an ordering of writes. There is no conflict resolution when two writers disagree, because there are effectively no concurrent writers to disagree.

If a candidate spends the interview on write availability here, they have mis-read the workload.

Three constants about the planet

This chapter and the two after it all measure distances on Earth. The constants are stated once here, and those chapters cite them rather than restating them:

Earth, stated once and used by all three chapters:
  equatorial circumference          40,000,000 m
  1 degree of latitude   40,000,000 / 2 / 180   =  111,111
  surface area                      510,000,000 km^2
  settled land with mapped detail   15,000,000  km^2

The latitude line is worth walking through, because it is the conversion every later section uses to turn degrees into metres. Latitude runs from the South Pole to the North Pole, which is half the way around the globe: 40,000,000 / 2 = 20,000,000 metres. That half-lap spans 180 degrees of latitude. So one degree of latitude is 20,000,000 / 180 = 111,111 metres, everywhere on Earth.

A degree of latitude is the same length everywhere; a degree of longitude is not. Lines of longitude all meet at the poles, so they crowd together as you move away from the equator, and a degree of longitude shrinks with them. That asymmetry is the source of a defect derived in Two defects and both of them are structural and a correction factor used in Deep dive 1 why a b tree on lat and lng cannot do this.

2. Requirements

The functional requirements are ordinary. The five non-functional constraints are the ones that do the work, because each eliminates a whole family of designs.

Functional

• search(lat, lng, radius, filters) returns businesses inside the disc, ranked.
• Radius is one of a small menu: 500 m, 2 km, 5 km, 20 km.
• Business CRUD by owners and by an internal data pipeline. CRUD is create, read, update and delete — the four ordinary write operations on a row.
• Read a single business by id.

Non-functional — these decide the design

Three terms in the table below need glossing first.

• p99 is the 99th percentile latency: the time that 99 out of every 100 requests beat. It describes the slow tail, not the typical case, which is why a design can have a fine average and still fail this.
• Eventual consistency means a write is not visible everywhere immediately, only after some bounded delay. Normally that is a compromise you argue for. Here, as the third row says, it is the actual requirement.
• A hot cell is a single grid cell whose id list is far longer than the mean, so every query that touches it does far more work than the fleet was sized for. Bottlenecks and scaling prices the worst one in this corpus.

The last row is the one to say out loud. Every scheme in this chapter is a candidate generator: it narrows two hundred million points down to a few hundred at the smallest radius on the menu, and to a list you have to cap at the largest (Bottlenecks and scaling). None of them returns the right answer on its own.

3. Back of the envelope

The rest of the chapter spends two numbers derived here: the total size of the corpus, which decides whether sharding is a topic at all, and the density of businesses at a typical query point, which decides how many candidate rows every later scheme has to touch.

Traffic comes first because it is the cheapest to derive, but it turns out to matter least — nothing in this design is shaped by the query rate.

3.1 Traffic

Start with how many searches arrive. DAU is daily active users, the count of distinct people who use the product on a given day. The 86,400 in the third line is the number of seconds in a day (60 x 60 x 24).

DAU                        100,000,000
searches/user/day          5
searches/day               100,000,000 x 5          =  500,000,000
per second                 500,000,000 / 86,400     =  5,787
peak, 2.5x average         5,787 x 2.5              =  14,468
businesses                 200,000,000

The peak figure is the one a fleet is sized on, because traffic is not flat across a day: nobody searches for restaurants at 4 a.m., and everybody does at 7 p.m. The 2.5x multiplier is the usual daily-shape allowance for that bunching.

3.2 Storage

Now the corpus. Add up one business row field by field, then multiply by the row count:

business_id     8 B
name           64 B
address       128 B
lat, lng       16 B    two float64
category        4 B
cell key        8 B    64-bit cell id, section 10
metadata       80 B    hours, phone, rating, price band
                  ------
                   308 B   ->  call it 300 B

200,000,000 x 300                    =  60,000,000,000    B  =  60 GB
x 3 replicas                         =  180,000,000,000   B  =  180 GB

A replica is an identical copy of the data on another machine, kept so that reads can be spread out and so that losing one machine loses nothing.

Sixty gigabytes is the entire commercial geography of Earth, and it fits in RAM on one commodity box (ch 02: 64-256 GB). Say that early, because it deletes the sharding conversation and buys the time to spend on the index, which is the actual question.

3.3 Density, and why it is the number everything else needs

Every later section asks the same question: if I scan this much map, how many rows do I touch? Answering it needs a density — businesses per square kilometre — because candidates = area x density. So derive one now.

global mean    200,000,000 / 15,000,000 km^2       =  13.3   per km^2
Manhattan      60,000 / 59.1 km^2                  =  1,015  per km^2
Wyoming        65,000 / 253,600 km^2               =  0.26   per km^2
skew           1015 / 0.26                         =  3,904

Read the last line as the range the design has to survive: the densest place on the map has roughly four thousand times the businesses per square kilometre of the sparsest. No fixed grid can be the right size for both.

Now pick the working number. Queries do not happen at the global mean, because the global mean averages in the farmland nobody searches from; they happen in towns. Take 50 businesses/km^2 as the density at a typical query point — comfortably above the 13.3 global mean, well below Manhattan’s 1,015 — and use it for every candidate-count estimate below.

That figure is an estimate, not a measurement, and the assumption ledger shows at the end that moving it by ten in either direction changes no box in the design.

4. API sketch

Five endpoints: one search, one read-by-id, and the three writes that let an owner manage their listing. The one to study is the first line — everything after the ? is a knob the index has to cope with.

GET  /v1/search?lat=&lng=&radius=&category=&open_now=&limit=20&cursor=
        -> {items: [{id, name, distance_m, ...}], next_cursor}
GET  /v1/businesses/{id}
POST /v1/businesses            {name, address, lat, lng, category, ...}
PUT  /v1/businesses/{id}
DELETE /v1/businesses/{id}

GET reads, POST creates, PUT replaces and DELETE removes; cursor and next_cursor are an opaque bookmark that lets the client ask for the next page without re-running the whole search.

Two things this signature commits you to.

radius is a request parameter, not a constant. The index must therefore answer at several scales, and The 3x3 query and the 32x cliff shows that costs far more than it sounds — a 2% change in the requested radius can cost 32x the work.

distance_m is returned. You cannot return an exact distance you did not compute, so the server ran a real distance calculation on every row it returned. The cheap grid filter that finds candidates never leaks into the response.

5. Data model

The data splits into two stores with completely different obligations, and that split is the design.

The first store owns the facts and never gets queried by location. The second store owns nothing and answers every location query. Notice that only one of them is written to.

businesses            source of truth, relational, sharded by business_id
  business_id PK, name, address, lat, lng, category, attrs, updated_at

geo_index             derived, in memory, rebuildable, sharded by cell
  cell_id  ->  [business_id, ...]

The geo index holds no truth. It is an inverted index: a map from a key to the list of ids that carry that key. It is the same structure a search engine uses to map a word to the documents containing it. Here the key is a cell id and the value is a list of business ids.

Because it holds no truth, it can be dropped and rebuilt from businesses in minutes. That removes three things you would otherwise have to design:

• A durable write path. Losing the index loses nothing.
• A quorum — an agreement rule where a write is accepted only once enough replicas acknowledge it, derived in ch 06. There is nothing to agree on.
• A conflict story. Two writers cannot disagree about a value nobody writes.

The update path is one-way. A business edit writes the relational row. A change data capture stream — CDC, a feed of committed row changes read off the database’s own transaction log — picks the change up and re-computes that business’s cell.

Cell membership changes only when lat or lng changes, which for 200 M businesses happens a few thousand times a day. The index is 99.99% static, so treat it as a build artifact, not a database.

6. High-level architecture

Put the two stores behind a request path and a shape emerges that never has to fan out across machines.

The diagram has two flows in it. The top half, left to right, is a live search: client, load balancer, search service, then two in-memory reads. The bottom half is the offline loop that keeps the index fresh: the database emits changes, a builder consumes them, and the builder publishes a new index. Nothing in the top half writes to anything.

flowchart LR
    C["Client"] --> LB["Load balancer"]
    LB --> S["Search service<br/>cell lookup + exact filter + rank"]
    S --> GI["Geo index replicas<br/>cell_id -> id list, in RAM"]
    S --> BC["Business cache<br/>id -> attributes"]
    BC --> DB[("Business DB<br/>source of truth")]
    DB --> CDC["CDC stream"]
    CDC --> B["Index builder"]
    B --> GI

    style DB fill:#1d3557,color:#fff
    style GI fill:#2d6a4f,color:#fff
    style BC fill:#2d6a4f,color:#fff
    style B fill:#40916c,color:#fff

The colours follow ch 01’s key:

The search service and the load balancer are uncoloured on purpose: they are stateless, they own nothing, and adding replicas of them is the least interesting decision on the page.

Each box is referred to by name later, so fix them now, in the order a request meets them:

• Client — a phone or browser issuing the search call from Api sketch.
• Load balancer — the front door that spreads incoming requests evenly across identical search servers.
• Search service — does cell lookup, then the exact filter, then ranking, in that order. This is Deep dive 5 the search itself.
• Geo index replicas — full in-RAM copies of the cell_id -> id list map from Data model.
• Business cache — the id -> attributes map that turns a list of ids into rows the caller can read.
• Business DB source of truth — the relational store that owns every business row and is the only thing anyone writes to.
• CDC stream — the change feed off that database.
• Index builder — the offline job that consumes the change feed, recomputes cells, and publishes a new index to the replicas.

Every geo index replica holds the whole index. At 60 GB that is affordable, and it buys one specific thing: a search never crosses a network boundary to a second shard.

That removes the fan-in tail problem that dominates most other read paths in this book. When a request must wait on ten machines, its latency is the slowest of the ten, not the average, so a rare slow response on any one machine shows up in the p99 of every request. With one full copy per replica, there is no fan-in and no compounding.

Scale reads by adding identical replicas behind the load balancer. That is the entire scaling story for this service.

7. Deep dive 1: why a B-tree on lat and lng cannot do this

Every later scheme needs a number to beat rather than a slogan, so start by pricing the design everyone proposes first.

7.1 Why the second column of the index does nothing

Here is the query every candidate writes first. It asks for a bounding box around the query point instead of a circle, on the theory that a box is close enough and boxes are what indexes understand.

SELECT * FROM businesses
WHERE lat BETWEEN 40.7452 AND 40.7632
  AND lng BETWEEN -74.0056 AND -73.9819;

Back it with CREATE INDEX ON businesses (lat, lng). That is a composite index: one B-tree whose sort key is the pair of columns, in the order written.

Picture what that B-tree actually stores. It is a list of (lat, lng) pairs sorted by lat first, and by lng only within a single lat value:

(40.7451, -122.4)
(40.7451,  -74.0)
(40.7451,    2.3)
(40.7452, -122.4)   <- lng jumps back to -122: the ordering restarts here,
(40.7452,  -73.9)      and it restarts again at every new lat value
(40.7452,  116.4)

Once your predicate accepts many latitudes, you are not looking at one sorted run of longitudes. You are looking at thousands of independently sorted runs stacked end to end, and there is no single contiguous stretch of the index that holds all the longitudes you want. This is the leftmost prefix rule: a range predicate on the leading column destroys the ordering of everything after it (sql/03).

So the index prunes on latitude and only on latitude. The longitude predicate degrades into a filter applied to every row the latitude scan already produced.

7.2 Pricing the latitude scan

Price a 1 km search at 40.76 degrees north — roughly midtown Manhattan.

Two choices in the arithmetic need defending. The band is 2 x 1,000 metres tall, not 1,000, because a 1 km radius reaches 1 km north and 1 km south of the query point. And the denominator is 130 degrees rather than 180, because rows only exist where people live: taking roughly -50 to +80 degrees as the inhabited band is an estimate, and a generous one — using the full 180 would make the B-tree look better than it is.

latitude band, degrees       2 x 1,000 / 111,111        =  0.018
inhabited latitude span      130 degrees, -50 to +80
fraction of rows in band     0.018 / 130                =  0.0001385
rows scanned                 200,000,000 x 0.0001385    =  27,700

Now the other side of the ratio: how many rows the user actually wanted. The disc is a circle of radius 1 km, so its area is pi x r^2, and at 50 businesses/km^2 from Density and why it is the number everything else needs:

disc area, km^2              3.1416 x 1 x 1             =  3.1416
businesses in disc           3.1416 x 50                =  157
amplification                27,700 / 157               =  176

Amplification is the ratio of rows touched to rows returned — how much wasted work each answer costs. Here the database reads 176 rows for every row it hands back.

The index prunes latitude and the scan then circles the globe: those 27,700 rows include every business in Madrid, Ankara and Beijing that happens to sit on the 40.76 parallel. That sentence is the whole failure, and it is worth saying exactly that way.

7.3 How bad it is depends on whether the index covers

What those 27,700 rows cost depends on whether the database has to leave the index to get them.

A covering index contains every column the query needs, so the database can answer from the index alone. If it does not cover, each matching index entry forces a second lookup into the table itself — a heap fetch — and a heap fetch is a random read from disk at roughly 100 us.

The first row is fatal: 2.77 seconds against a 100 ms budget. The second is merely bad — 27,700 entries at 24 bytes each is 665 kB, and a sequential gigabyte-per-second read of 665 kB takes 0.66 ms.

Bad becomes fatal again the moment you add a second filter. category and open_now cannot go in the index prefix either, for the same leftmost-prefix reason: the leading column is already a range, and everything after a range is unsorted. So every filter you add multiplies the 176x rather than reducing it — the scan is the same size and fewer rows survive it.

7.4 The obvious repair, and why it also fails

The standard rescue is to drop the composite index and use two separate single-column indexes, combined with a bitmap AND: the database collects the matching row ids from each index into a bitmap, then intersects the two bitmaps and only fetches the rows in both.

Price the longitude side. A degree of longitude is shorter than a degree of latitude everywhere except the equator, shrunk by exactly cos(latitude):

1 degree of longitude at 40.76 deg   111,111 x 0.7575   =  84,161
longitude band, degrees              2 x 1,000 / 84,161 =  0.02376
fraction of 360 degrees              0.02376 / 360      =  0.000066
rows in longitude band               200,000,000 x 0.000066  =  13,200
index entries the two scans touch    27,700 + 13,200    =  40,900
work per answer                      40,900 / 157       =  260

The 0.7575 is cos(40.76 degrees). The denominator is the full 360 degrees this time, not an inhabited subset, because longitude does not have an uninhabited band the way latitude does — people live at every longitude.

Two different quantities both want to be called “worse” here, so price both rather than switching between them.

The number that condemned the composite index was time: 27,700 random heap reads. The bitmap AND does not reproduce that, because it reads its 40,900 entries sequentially out of two B-trees and only fetches the 157 survivors from the heap at random:

entry scan, sequential   40,900 x 24 B at 1 GB/s   =  0.98   ms
heap fetches             157 x 100 us              =  15.7   ms
total                                                 16.7   ms
against the composite     2.77 / 0.0167             =  166x   faster

So on wall clock the bitmap AND wins by two orders of magnitude. On work per answer it loses: 260 index entries touched per row returned, against the composite index’s 176.

Work per answer is the quantity to argue from, because it is the one every additional filter multiplies. Add category and you still scan the same 260 entries, you just return fewer rows. By that measure the bitmap AND is the more wasteful of the two plans, not the slower one.

Both are catastrophic against the low single digits a two-dimensional scheme buys, which is the point of pricing them: neither one-dimensional plan is a candidate, and the argument does not depend on which of the two numbers you quote.

7.5 What the failure tells you to build

The failure above is the reason two families of structures exist, rather than “just index both columns”.

An R-tree is a tree of nested bounding boxes. Each entry stores the smallest rectangle enclosing its children, and a search descends only into boxes that overlap the query, so it prunes in both dimensions at once instead of one. The pragmatic answer redis geo and postgis runs the production one.

A space-filling curve is an ordering that threads one continuous line through every cell of a grid, so that cells near each other on the map are usually near each other along the line. Numbering the cells along that line is exactly the flattening of two dimensions into the single sortable scalar a B-tree understands. Deep dive 2 geohash derived and Deep dive 4 s2 and h3 and why hexagons build two of them.

8. Deep dive 2: geohash, derived

The first space-filling curve to build is the oldest and simplest one.

A geohash is a short string that names a rectangle on the map. You build it by repeatedly halving the world: is the point in the east half or the west half, the north half or the south half, and so on. Each answer is one bit, and a longer string means a smaller rectangle.

Points that share a prefix are usually near each other. That is the whole point: it turns a two-dimensional position into a sortable string.

8.1 Bits per character, and where the cell sizes come from

Encoding, done by hand. Take the query point from the top of the chapter, lat = 40.7580, lng = -73.9855, and run the halving. Longitude goes first, then latitude, then longitude again, alternating. At each step you keep the half your point is in and throw the other away:

step  axis  current range              midpoint   point is    bit
1     lng   -180    .. +180              0        west         0
2     lat    -90    .. +90               0        north        1
3     lng   -180    .. 0               -90        east         1
4     lat      0    .. +90             +45        south        0
5     lng    -90    .. 0               -45        west         0

Five bits, 01100, which is 12 in decimal. Look 12 up in geohash’s 32-character alphabet and you get d — the first character of the geohash. Keep going and the point encodes to dr5ru7 at six characters, dr5ru7v at seven.

That is the entire scheme. Every extra character is five more halvings, and any point starting dr5ru is inside the same rectangle as this one.

Bits per character. Geohash encodes the bit string in base32 — which is 2^5, so 5 bits per character, not 4 and not 6. Base32 means each character of the output stands for one of 32 possible values, so it consumes exactly 5 bits. Getting this wrong is the single most common geohash error in an interview.

Cell size. Because the bits alternate starting with longitude, after n bits the two axes have been halved a different number of times:

n = 5 x precision
longitude bits    ceil(n / 2)
latitude bits     floor(n / 2)
cell width        40,000,000 / 2^lng_bits     metres at the equator
cell height       20,000,000 / 2^lat_bits     metres, everywhere

Precision is simply the number of characters in the geohash.

Three things in that block are worth spelling out. The ceil and floor split the bits because longitude takes the odd-numbered steps and latitude the even ones — at n = 25, longitude got steps 1, 3, 5 … 25, which is 13 of them, and latitude got the 12 even ones. Width divides the full 40,000,000 m equatorial circumference by 2 for each longitude halving. Height divides only 20,000,000 m, because latitude spans 180 degrees against longitude’s 360, so its full range is half a lap.

Run the formula at every precision you might use:

Check one row by hand before trusting the rest. Precision 6 is 5 x 6 = 30 bits, split 15 longitude and 15 latitude. Then 2^15 = 32,768, so the width is 40,000,000 / 32,768 = 1,221 m and the height is 20,000,000 / 32,768 = 610 m. That matches the table.

The aspect ratio alternates, and the reason is the unequal spans. Give both axes the same number of bits and you get a 2:1 cell, because longitude started with twice the range to divide. The extra longitude bit at odd precision squares the cell back up.

So precisions 5 and 7 are square, and 4, 6 and 8 are twice as wide as they are tall. That alternation matters in The 3x3 query and the 32x cliff, where the shorter side is the one that decides which precision a radius can use.

How far can this go? A 12-character geohash is 60 bits split 30/30, which at the equator is 40,000,000 / 2^30 = 3.7 cm wide by 20,000,000 / 2^30 = 1.9 cm tall — far past the precision of the coordinate it encodes, so those last characters are noise.

8.2 Two defects, and both of them are structural

Neither defect below can be tuned away — both follow from the construction itself — and the second one hardens into a rule: always query nine cells, never one.

Defect 1: cells are not equal area. A cell’s height is the same everywhere on Earth, because a degree of latitude is. Its width is not: width scales with cos(latitude), because the meridians that bound it converge as you move toward a pole.

At 60 degrees north, cos(60) = 0.5 exactly, which makes the arithmetic easy to see:

precision 6 width at the equator        1,221 m
precision 6 width at 60 deg north       1,221 x 0.5              =  610
area ratio, equator to 60 deg north     1 / 0.5                  =  2

So at 60 degrees north a precision-6 cell is a 610 m square holding half the ground area of its equatorial counterpart, and at fixed density it holds half the businesses.

That means your cell occupancy statistics, your cache sizing and your shard balance all become functions of latitude — a cell in Oslo and a cell in Singapore are not comparable units. Near the poles, where cos(latitude) approaches zero, it degenerates completely.

Defect 2: adjacency is not preserved across a cell boundary, and it fails worst at the top of the tree.

Take two points one metre apart, either side of the prime meridian — the zero-longitude line through Greenwich. Their longitudes have opposite sign, so they fall on opposite sides of the very first halving in the encoding. Their first bit differs. Therefore their geohashes share zero characters. There is no prefix length at which those two neighbours look close.

This is not a quirk of the meridian. It happens at every boundary at every level, because a boundary at any level of the halving throws the two neighbours into different branches. The meridian is just the case where it happens at level one and costs you everything.

So quantify how often looking up a single cell gives the wrong answer.

A disc of radius r fits entirely inside a w by h cell only if the query point sits at least r away from all four edges. That leaves a (w - 2r) by (h - 2r) box of “safe” positions inside the cell. For a query point dropped uniformly at random in the cell, the chance of landing in that box is the product of the two one-dimensional chances:

P(disc inside cell)  =  max(0, (w - 2r) / w)  x  max(0, (h - 2r) / h)

precision 5 and r 500 m   3,883 / 4,883      =  0.795
                          0.795 x 0.795      =  0.633
precision 6 and r 500 m   height 610 is below 2r 1,000, so the term is 0

Substituting for precision 5: the cell is 4,883 m on both sides, 2r is 1,000 m, so 4,883 - 1,000 = 3,883 and 3,883 / 4,883 = 0.795 on each axis. Multiply the two axes and 63.3% of query points are safe.

Precision 6 is worse than a bad probability, it is an impossible one. The cell is only 610 m tall and the disc is 1,000 m across, so the disc cannot fit at any position. The max(0, ...) clamps the height term to zero, and zero times anything is zero.

At precision 6 with a 500 m radius the search disc never fits in one cell — a single-cell lookup is wrong 100% of the time — and even at precision 5 it is wrong for 37% of query points (1 - 0.633). That is why the query is always the centre cell plus its 8 neighbours, and why geohash libraries all ship a neighbours() function.

8.3 The 3x3 query, and the 32x cliff

The nine-cell rule settles correctness; what remains is choosing the precision for a given radius, and that choice walks straight into a discontinuity.

Start from the worst case. Put the query point in the corner of its cell, the least favourable position possible. The 3x3 block still extends one entire cell beyond that corner in both directions. So whatever the query point’s position, the block reaches at least one full cell width and one full cell height past it, and the smaller of those two is the radius you can promise:

guaranteed coverage radius of a 3x3 block  =  min(cell width, cell height)

That picks the precision for you: choose the finest precision whose min(w, h) is at least r. Finest, because smaller cells mean fewer wasted candidates.

Run that rule on the first three of the four radii the product offers (Requirements). Overfetch in the last column is the ratio of map area you scan to map area you asked about — 1.0x would be perfect, and none of these are close.

In the first row, a 500 m radius needs min(w,h) >= 500; precision 7’s 153 m is too small, precision 6’s 610 m is the finest that clears it. Nine precision-6 cells at 0.7451 km^2 each is 6.71 km^2, which at 50 businesses/km^2 is 335 candidates. The disc the user asked about is pi x 0.5^2 = 0.785 km^2. Dividing, 6.71 / 0.785 = 8.5. The other rows read the same way.

Now look at what happens between rows two and three. A 2 km radius fits precision 5, because 4,883 >= 2,000. A 5 km radius does not, because 4,883 < 5,000 — it misses by 117 metres. So you must drop to precision 4, and dropping one character multiplies the cell area by 32:

precision 4 area / precision 5 area    762.94 / 23.84    =  32

Why 32? One character is 5 bits, and each bit halves one axis, so five bits halve the total area five times over: 2^5 = 32.

A 2% increase in requested radius costs 32x the candidate scan, because geohash precision is quantized in factors of 32 per character. That cliff is geohash’s real defect, worse in practice than the equal-area complaint everybody recites.

The fix is to stop letting character boundaries dictate the block size. Stay at the finer precision and query a bigger block: a (2k+1) by (2k+1) square instead of 3x3, with k = ceil(r / min(w, h)) rings around the centre. The 3x3 query is just this formula at k = 1.

r = 5,000 m at precision 5   k = ceil(5000 / 4883)      =  2
block                        5 x 5                      =  25 cells
area                         25 x 23.84                 =  596.0  km^2
candidates                   596.0 x 50                 =  29,800
improvement over 3x3 at p4   6,866 / 596.0              =  11.5

Reading it: 5,000 m needs 1.02 cells of reach, ceil rounds that to 2 rings, 2 rings around a centre cell is a 5x5 block of 25 cells, and 25 small cells beat 9 cells that are 32 times bigger.

Eleven and a half times fewer candidates for one line of code, and it generalizes: work in bits rather than characters and the resolution ladder steps by 2 instead of 32.

9. Deep dive 3: quadtrees, and what adaptivity costs

Geohash’s fixed grid cannot adapt to density. One scheme solves that problem outright — and you still would not run it as your online store. Sizing it honestly shows both halves of that sentence.

9.1 What a quadtree is

A quadtree is a tree in which every node covers a square of the map. When a node holds more than a fixed number of points, it splits into four children covering its four quadrants — north-west, north-east, south-west, south-east.

Two kinds of node come out of that rule. A node that has not split is a leaf, and it holds the points themselves. A node that has split is internal, and it holds nothing but pointers to its four children.

The consequence is the whole appeal: it splits only where points are, so it puts its resolution where the data is. A fixed geohash grid cannot do that — every cell is the same size whether it covers Times Square or open ocean.

9.2 Sizing it

Two parameters set the shape of the tree: a bucket size of 100, meaning a leaf splits once it holds more than 100 points, and a mean leaf occupancy of 70, meaning that after all the splitting settles, the average leaf holds 70 points rather than a full 100.

leaves        200,000,000 / 70                =  2,857,143
internal      2,857,143 / 3                   =  952,381
total nodes   2,857,143 + 952,381             =  3,809,524
uniform depth log(2,857,143) / log(4)         =  10.7      ->  11 levels

Two of those lines need justifying.

Internal nodes are (leaves - 1) / 3, approximated here as leaves / 3, because in a full quaternary tree every internal node replaces four leaves with one parent — a net reduction of three — so the count of internal nodes is a third of the leaf count.

Depth is a base-4 logarithm because each level multiplies the node count by four. To reach 2,857,143 leaves you need log(2,857,143) / log(4) = 10.7 levels, rounded up to 11. That is the depth if points were spread evenly. The real tree is shallower over Wyoming and deeper over Manhattan, which is exactly the point of What the adaptivity is worth.

Now memory, at 24 bytes per stored point, 32 bytes of header per leaf, and 64 bytes per internal node for its four child pointers plus bookkeeping:

point entries  200,000,000 x 24                =  4,800,000,000  B
leaf headers   2,857,143 x 32                  =  91,428,576     B
internal nodes 952,381 x 64                    =  60,952,384     B
                                                  -------------
total                                             4,952,380,960  B  =  4.95 GB

The points dominate at 97% of the total; the tree structure itself is almost free.

9.3 What the adaptivity is worth

Put a number on “resolution where the data is”, using the density figures from Density and why it is the number everything else needs.

Each level of a quadtree quarters the area a node covers. So to express a density ratio as a depth difference, ask how many times you have to quarter — which is a base-4 logarithm:

depth difference, Manhattan vs Wyoming   log(3,904) / log(4)   =  5.97

Six extra levels over Manhattan than over Wyoming, automatically, and no geohash precision can be six levels finer in one place than another. That is the entire argument for a quadtree, and it is a real one.

9.4 The bill

Building the tree means inserting every point and walking it down to a leaf. Each level of the walk is one memory reference at 100 ns (ch 02):

build cost   200,000,000 inserts x 11 levels x 100 ns   =  220 s

Three and two-thirds minutes single-threaded (220 / 60 = 3.67). That is fine as a nightly job and useless as an online mutation path, for three reasons:

• The tree is a bespoke in-memory server. It is not a database, not a Redis type, not something a second team can query. Every operational property — snapshotting, warm restart, replica catch-up — is yours to build.
• A leaf split is a structural change. Concurrent readers need either a lock, which blocks them, or a copy-on-write path down the spine, where the writer clones the nodes it touches and swaps in the new root so readers never see a half-modified tree.
• A cell id is not a key. You cannot shard on it the way ch 05 shards on a hash, because sibling leaves must stay reachable from the same parent, so the tree cannot simply be cut into independent pieces.

A quadtree is the right answer when the point set is static and lives in one process, which is exactly this workload — and the wrong answer the moment the points move, which is ch 18.

10. Deep dive 4: S2 and H3, and why hexagons

A quadtree adapts but cannot shard. The modern answer keeps the flat, shardable cell scheme and repairs geohash’s geometry instead — and the two systems that do it disagree about which defect matters.

10.1 The diagonal problem

S2 and H3 each repair one geohash defect, and the repairs are mutually exclusive: one buys equal area and exact containment, the other buys uniform adjacency, and neither buys both.

S2 fixes geohash’s equal-area defect. Instead of gridding latitude and longitude directly, it projects the sphere onto a cube — imagine Earth inflated inside a box, with each surface point pushed straight out to the nearest of the six faces — and then grids each flat face. Cells on a flat face do not stretch and shrink with latitude the way lat/lng cells do.

Over each face it runs a Hilbert curve: a continuous path that visits every square of a grid while keeping nearby squares nearby along the path. Numbering cells in the order the curve visits them is what gives the resulting one-dimensional ordering its locality.

Cell counts follow directly from six faces, each subdivided into four at every level:

cells at level L        6 x 4^L
level 13 cells          6 x 67,108,864            =  402,653,184
level 13 mean area      510,000,000 / 402,653,184 =  1.27  km^2

Level 13 is shown because 1.27 km^2 is the neighbourhood-scale cell this chapter’s radii live at. 4^13 = 67,108,864, times six faces is 402 million cells, and dividing Earth’s 510,000,000 km^2 surface among them gives 1.27 km^2 each.

Two properties come out of that construction, and both are what you cite in an interview:

• Bounded distortion. The area ratio between the largest and smallest cell at a given level is about 2.08. Bounded, unlike geohash’s 1/cos(latitude), which diverges as you approach a pole.
• The id is an integer. A 64-bit S2 cell id is a plain integer whose numeric ordering is the Hilbert ordering, so containment is a prefix test and proximity is usually an integer range. It drops straight into any B-tree or sorted set with no special support.

What S2 does not fix is the square cell’s neighbour geometry. A square has eight neighbours, but they are not all the same distance away. For a square of side s:

edge neighbours    4 at distance                 s
corner neighbours  4 at distance  s x 1.4142  =  1.4142 s
spread                             1.4142 / 1  =  1.41

The 1.4142 is sqrt(2), the diagonal of a unit square.

A k-ring is the set of cells within k neighbour-steps of a starting cell. On a square grid, “one cell away” means two different distances that differ by 41%, so a k-ring is a square — and a square is a bad approximation to a disc.

H3 fixes that instead. It uses hexagons, where all six neighbours share an edge and sit at exactly the same distance. There is no diagonal case at all.

The hexagon arithmetic you need, for a regular hexagon of edge length a. For a hexagon the edge length also equals its circumradius, the distance from centre to corner, which is a coincidence of the hexagon and a convenient one:

area              2.598 x a^2
inradius          0.866 x a          centre to edge midpoint
neighbour spacing 1.732 x a          = 2 x inradius

The inradius is the distance from the centre to the middle of an edge, so it is the radius of the largest disc that fits entirely inside one cell. Neighbour spacing is twice that, because two adjacent hexagons meet edge-to-edge and each contributes one inradius.

H3’s resolutions divide by 7 per level, because seven hexagons approximately tile into one larger hexagon. The base level is 122 cells. Work down to resolution 9, the one every worked example below uses:

resolution 0    510,000,000 / 122          =  4,180,328   km^2
resolution 9    4,180,328 / 40,353,607     =  0.1036      km^2
edge length     sqrt(103,592 / 2.598)      =  199.7       m
inradius        0.866 x 199.7              =  172.9       m
spacing         1.732 x 199.7              =  345.9       m

The divisor 40,353,607 is 7^9 — nine levels of dividing by seven.

The edge length line inverts the area formula. A resolution-9 cell is 0.1036 km^2, which is 103,592 m^2. Since area = 2.598 x a^2, then a = sqrt(area / 2.598) = sqrt(39,874) = 199.7 m. Everything else on the ladder is that a times a constant.

The cost of hexagons: they do not nest. Seven hexagons only approximately tile into one, so a resolution-9 cell is not exactly contained in a resolution-8 cell. Containment is approximate, and roll-up aggregations leak at the edges.

That is the trade in one line: S2 keeps exact containment and gives up uniform adjacency; H3 does the reverse. Neither buys both, which is why both still exist.

10.2 The k-ring, and the radius it actually covers

A request arrives in metres, but a k-ring is measured in steps, and converting between the two is the piece most implementations get wrong.

Start by counting the cells a k-ring holds. It is a filled patch, not a hollow outline: ring j on its own holds exactly 6j cells, so summing 6j from 1 to k and adding the centre cell gives:

cells(k)  =  1 + 3k(k + 1)

k = 1     1 + 3 x 1 x 2      =  7
k = 2     1 + 3 x 2 x 3      =  19
k = 3     1 + 3 x 3 x 4      =  37
k = 4     1 + 3 x 4 x 5      =  61

Now the mismatch nobody derives. A k-ring is a hexagon and the request is a disc, so “k steps” is not a distance. You cannot hand k to a user or take r from one without a conversion.

The number that does the conversion is the inscribed radius: the largest disc, centred on the origin cell’s centre, that the k-ring is guaranteed to contain entirely. Any business inside that disc is definitely in one of your k rings. Anything beyond it might not be.

Where the inscribed radius comes from

The inscribed radius is the distance from the origin’s centre to the nearest point the k-ring does not cover. Because the covered region is a union of hexagons with a jagged outer edge, that nearest uncovered point is not on a flat edge — it is the nearest vertex of the nearest ring-(k+1) cell, tucked into a notch in the boundary.

Hexagon centres sit on a triangular lattice of spacing 1.732 a, and every hexagon vertex lands on a lattice point of a-sized triangles. On such a lattice, squared distances between lattice points are always whole multiples of a^2. That is what makes the third column below a list of integers, and what makes the table checkable instead of something to take on trust.

k rings cover Cells hexagons; the nearest uncovered vertex sits at a distance d whose square is the third column times a^2; the square root of that is the exact radius you can promise, in units of a. The last column is a simpler expression that never exceeds the exact one, which is what makes it safe to ship.

Check the two irrational rows by taking the square roots yourself: sqrt(13) = 3.6056 and sqrt(43) = 6.5574, matching the fourth column.

Two patterns fall out of the lattice. Odd k lands exactly on (3k + 1) / 2 times a — giving 2, 5 and 8 — because the nearest uncovered vertex sits straight along a lattice axis, which makes the squared distance a perfect square. Even k puts that vertex off-axis, so the value comes out irrational: larger than the safe bound, but not a round number you could have guessed.

Since the exact value is never below 1.5 k a, that expression is a safe lower bound, and inverting it gives the formula you actually ship:

inscribed radius(k)  >=  1.5 k a          and hence
k                    =   ceil(r / (1.5 a))

Why you cannot pick k by eye

Work the 1 km case at H3 resolution 9, where a = 199.7 m:

1.5 a                  1.5 x 199.7        =  299.6   m
k                      ceil(1000 / 299.6) =  4

Now here is why the exact column matters, and it is the best small trap in this chapter. k = 3 looks obviously sufficient: three rings of cells spaced 346 m apart is well over a kilometre of cells. But read the exact inscribed radius for k = 3 off the table — 5.000 a — and substitute:

k = 3 exact            5.000 x 199.7      =  998.5   m

One and a half metres short of the requested kilometre. A k = 3 query silently misses businesses in a thin crescent at the outer edge of every single request. Nothing errors, nothing is slow, and no test written against a city centre will ever catch it. The safe bound picks k = 4 and is right by construction.

What the tighter cover costs

Being right by construction is not free — k = 4 scans 61 cells where k = 3 would have scanned 37. Price the waste:

cells at k = 4         61
area                   61 x 0.1036        =  6.32   km^2
disc area, r = 1 km    3.1416 x 1 x 1     =  3.1416
overfetch              6.32 / 3.1416      =  2.01

Sixty-one cells at 0.1036 km^2 each is 6.32 km^2 scanned to answer a question about 3.1416 km^2 — an overfetch of 2.01x.

Compare that against geohash at the same radius, because comparing at different radii is meaningless. The 3x3 query and the 32x cliff’s 8.5x is a 500 m figure and its 17.1x is a 2 km figure. Neither is a 1 km number, so redo both schemes at 1 km from scratch:

geohash on character boundaries, r = 1 km
  min(w, h) >= 1,000 forces precision 5
  9 cells                            9 x 23.84       =  214.6  km^2
  overfetch                          214.6 / 3.1416  =  68.3
geohash with the (2k+1) fix at precision 6
  k                                  ceil(1000/610)  =  2
  5 x 5 block                        25 x 0.7451     =  18.63  km^2
  overfetch                          18.63 / 3.1416  =  5.93
H3 resolution 9, k = 4               61 x 0.1036     =  6.32   km^2
  overfetch                          6.32 / 3.1416   =  2.01

Two times overfetch against geohash’s 5.9x with the (2k+1) fix, and 68x if you stay on character boundaries — all three at r = 1 km. Quoting the 17.1x here would be comparing two schemes at two different radii, and it would flatter H3 by understating what geohash can actually do.

Two reasons for the win, and both are geometry rather than engineering:

• A hexagon is closer to a disc than a rectangle is, so less of what you scan falls outside the circle.
• The resolution ladder steps by 7 rather than 32, so you are never forced up to a cell several times too big just because your radius crossed a boundary.

None of this returns an answer on its own. Cells narrow 200 M points to 61 cells; an exact distance test narrows 61 cells to the answer. The textbook exact test is the haversine formula, the standard way to compute great-circle distance between two latitude-longitude pairs on a sphere — though Deep dive 5 the search itself explains why you should not actually call it.

11. Deep dive 5: the search itself

Walking a single request end to end shows something uncomfortable: the spatial work — the part the chapter has spent ten sections on — is not where the latency goes.

Six steps, top to bottom, and only steps two and three touch the grid. Everything below the Fetch cell id lists box is ordinary data work — and that is where the time goes.

flowchart TD
    Q["lat, lng, r, filters"] --> K["Pick k or precision<br/>from r and cell size"]
    K --> C["Fetch cell id lists<br/>9 geohash cells, or 61 H3 cells"]
    C --> H["Hydrate candidates<br/>from business cache"]
    H --> F["Exact distance filter<br/>plus category, open_now"]
    F --> R["Rank and truncate to limit"]
    R --> O["Response with distance_m"]

The same six steps in words:

1. The request arrives as lat, lng, r, filters.
2. The service picks k or a precision from r and the cell size, using the formulas from The 3x3 query and the 32x cliff and The k ring and the radius it actually covers.
3. It fetches the cell id lists — 9 in-memory lookups for a 3x3 geohash block, or 61 for an H3 k = 4 ring.
4. It hydrates the candidates from the business cache, meaning it turns each bare id into a full row with coordinates and attributes.
5. It applies the exact distance filter, plus category and open_now.
6. It ranks, truncates to limit, and emits the response with distance_m on every item.

11.1 The spatial work is free; the hydration is not

Cost the spatial part first, using the 500 m geohash case at 335 candidates — a 3x3 block, so nine cell lookups, not the 61 an H3 k = 4 ring would cost at 1 km. Both a cell lookup and a distance test are single memory references at 100 ns:

cell lookups     9 x 100 ns                  =  0.0000009  s
distance test    335 x 100 ns                =  0.0000335  s
total CPU                                       0.0000344  s  =  34 us

Thirty-four microseconds against a 100 ms budget: the spatial part of a proximity search is free.

Now cost the part that is not free. Hydration is a network call to a cache, not a memory reference, and ch 02 prices one at 0.5 ms. The only question is how many of them you make:

hydration, one round trip per candidate   335 x 0.5 ms   =  167.5  ms
budget                                                      100    ms
hydration, one batched multi-get          1 x 0.5 ms     =  0.5    ms

Hydrated serially, this design misses its own latency target by 1.7x (167.5 / 100), and the fix is not a faster cache — it is one batched multi-get for all 335 ids.

That is the sentence to say out loud. The spatial work is 34 microseconds. The attribute work is either half a millisecond or 167 milliseconds. The only thing standing between those two outcomes is whether the candidate list leaves the process as one request or as 335. Say MGET, or the equivalent pipelined batch, and say it before anyone asks.

That reframes the design: the hot path is a business_id -> attributes cache, which is an ordinary key-value problem rather than a geospatial one.

Be careful which half of that cache’s economics you quote, because ch 02 flags conflating the two as the classic slip. With hit rate h, the load left on the store behind the cache is QPS x (1-h), a straight line that falls to zero. The reduction factor is 1/(1-h), a hyperbola that diverges. What sizes the business DB here is the line; what makes the last nine of hit rate worth chasing is the hyperbola.

11.2 Four details that are easy to get wrong

1. Use the equirectangular approximation, not haversine, for the filter. The equirectangular approximation treats a small patch of the sphere as flat and corrects longitude for latitude — the same cos(latitude) correction from The obvious repair and why it also fails:

dx = dlng x 111,111 x cos(lat)
dy = dlat x 111,111
d  = sqrt(dx^2 + dy^2)

Over a few kilometres that is accurate to well under a metre, and it skips the four trigonometric calls haversine needs. Compute cos(lat) once for the query point, not once per candidate — the query point does not move between candidates.

2. Filter before you rank, and rank on the hydrated row. Ranking is a business decision — distance, rating, sponsorship — and does not belong in the index. If ranking needs a model, that is the two-stage pattern from ml/01: a cheap stage generates candidates and an expensive stage scores them, with the cell query playing the cheap stage.

3. Cache the cell lists, not the query results. A query result is keyed by (lat, lng, r, filters), which is effectively unique per user, so it will almost never be asked for twice and the cache entry is dead on arrival. A cell list is keyed by cell_id and is shared by everyone standing in that cell. Cache what is shared.

4. Size that cache with the right density. This is the subtle one. The 50/km^2 from Density and why it is the number everything else needs is the density at a typical query point, explicitly not the mean over settled land.

Watch what happens if you use it anyway. Pricing 20 M cells at 50 x 0.7451 = 37 ids each implies 20,131,526 x 37.255 = 750 million businesses — against a corpus of 200 million. The number refutes itself.

The mean list length is not an assumption at all. It is forced by the corpus: every business is in exactly one cell, so the mean is just businesses divided by cells.

populated precision-6 cells   15,000,000 / 0.7451     =  20,131,526
mean ids per cell             200,000,000 / 20,131,526 =  9.93
mean id bytes                 9.93 x 8                =  79.5
per-entry overhead            cell key + hash-map bookkeeping  =  32
bytes per entry               79.5 + 32               =  111.5  ->  call it 112
cache size                    20,131,526 x 112        =  2,254,730,912  B  =  2.25 GB

Line by line: 15,000,000 km^2 of settled land divided by a 0.7451 km^2 precision-6 cell gives 20.1 million cells with anything in them. Spreading 200 million businesses across those cells gives 9.93 ids per cell on average. Each id is an 8-byte integer, so 79.5 bytes of ids, plus 32 bytes for the cell key and the hash-map bookkeeping around the entry. Round 111.5 up to 112 and multiply by the cell count.

Two and a quarter gigabytes, not the six you get by pricing every cell at the density of a query point.

The 37-ids figure is not wrong about the cells people query — a busy cell really does hold about that many. It is wrong as a mean over 20 million cells, most of which are farmland. Sizing a whole cache on a hot-path density is the same class of error as sizing a fleet on a peak and then billing it at the average.

12. The pragmatic answer: Redis GEO and PostGIS

You do not write any of the above. Two products already implement all of it, and the interview answer is knowing which one to pick and where each stops working.

Redis GEO stores a 52-bit geohash as the score in a sorted set — a Redis structure that keeps members ordered by a numeric score and supports range queries over it — and implements GEOSEARCH ... BYRADIUS as exactly the neighbour scan from The 3x3 query and the 32x cliff plus an exact filter.

members                200,000,000
bytes per member       150 B  skiplist node, hash entry, member string
memory                 200,000,000 x 150   =  30,000,000,000  B  =  30 GB

The 150 bytes is the sum of the three structures Redis keeps per member: a node in the skiplist that maintains the sorted order, an entry in the hash that maps member to score, and the member string itself.

PostGIS is the geospatial extension to PostgreSQL. It puts a GiST index on a geography column and answers ST_DWithin. GiST — the Generalized Search Tree — is here acting as the R-tree of What the failure tells you to build. There is no cell scheme at all — nested bounding boxes all the way down, and they split wherever the data is dense rather than on a fixed grid.

At roughly 40 bytes per index entry — a bounding box plus a row pointer — the whole index is small enough to stay in the database’s page cache:

index entries          200,000,000 x 40 B  =  8,000,000,000  B  =  8 GB

Side by side. The row that decides most real choices is the third one, not the first: PostGIS answers the search and returns the attributes in a single query, while Redis GEO gives you ids and leaves the hydration of Deep dive 5 the search itself to you.

In that table, AOF is Redis’s append-only file, a log of every write command that can be replayed after a crash, and ACID is the relational guarantee that a transaction is atomic, consistent, isolated and durable.

Where you outgrow Redis GEO: the geo commands are single-key, so the whole 30 GB set lives on one node and one core services each search. Replicas scale reads and nothing scales the key. The escape hatch is genuinely easy here and worth stating: a search request carries its own location, so region is a natural shard key — one instance per continent, routed by the query coordinate, with a scatter to two instances only for queries within r of a region boundary.

Where you outgrow PostGIS: the same place every relational deployment does (sql/03), and much later than people expect. At 14,468 peak queries per second against an 8 GB index that is fully cached, this is a read-replica problem, not an architecture problem.

Build the S2 or H3 index only when you need cells as a join key — when traffic, demand forecasts, delivery zones and surge pricing all need to be aggregated on the same grid, so the cell id becomes the column several datasets are joined on. That is a data-platform reason, not a latency reason, and it is the honest one.

13. Bottlenecks and scaling

The list of things that actually run out is notably short — and storage, write throughput and consistency are all missing from it, each deleted by an earlier section.

Nothing here needs sharding by data. That is unusual for this book and it is the direct consequence of the Back of the envelope result that the corpus is 60 GB.

14. Failure modes

A working proximity service fails by returning quietly wrong answers. That is the failure class that matters here, because none of these crashes anything, none of them shows up in an error rate, and the first three are invisible unless you go looking.

The antimeridian is the 180-degree line where longitude wraps from +180 to -180, and map matching is snapping a raw coordinate onto the road it was actually on, which needs metre-level accuracy that a 32-bit float cannot hold.

15. Alternatives rejected

When an interviewer proposes something simpler, this is the table to have ready — each alternative with the number that kills it.

16. Interviewer pushback

Six questions separate a candidate who memorized “use geohash” from one who derived it. Each comes with the answer it deserves.

“Why not just use PostGIS and stop?”

For 200 M static points at 14,468 peak queries per second, that is my recommendation, and I would say so in the first two minutes. The index is 8 GB, it caches entirely, and the query planner is better than anything I would write. I would move to a cell scheme when cells become a join key for other systems — demand aggregation, zone pricing — or when the point set starts moving, which is a completely different write path.

“How many bits is a geohash character?”

Five. Base32. Twelve characters is 60 bits, split 30/30, which is roughly a 3.7 cm cell at the equator — finer than the coordinate it encodes. The split alternates starting with longitude, so odd precisions are square and even ones are 2:1 wide, because longitude spans twice the range.

“Why query nine cells when the point is in one?”

Because a cell boundary is arbitrary and a disc is not. At precision 6 the cell is 1,221 by 610 m, so a 500 m disc cannot fit inside it at any position — the containment probability is exactly zero. Even at precision 5, where the cell is 4,883 m square, 37% of query points land within 500 m of an edge. Neighbours are not a safety margin, they are the correct query.

“Hexagons sound like decoration. What do they actually buy?”

Two things I can put numbers on. All six neighbours are equidistant, where a square grid’s diagonal neighbours are 41% further, so a k-ring is a meaningful distance and a square ring is not. And the resolution ladder steps by 7 instead of geohash’s 32, so a 5 km request does not get forced onto a 763 km^2 cell. Compared at the same 1 km radius, those two take overfetch from geohash’s 68x on character boundaries — or 5.9x once you query a (2k+1) block instead of 3x3 — down to 2.0x. The cost is that H3 cells do not nest exactly, so hierarchical roll-ups are approximate.

“A business in Manhattan and one in Wyoming — same index?”

Same index, and that is the case for the quadtree over the flat grid: it puts six extra levels over Manhattan automatically. But I would not run a quadtree online, because it has no shard key and a leaf split blocks readers. With a flat cell scheme I handle the 3,904x density skew by capping the per-cell list and dropping to a finer resolution inside dense cells, which is the same adaptivity at query time instead of build time.

“What breaks first as you grow?”

Not storage — 60 GB and 200 M points is one box. The first thing that breaks is the tail of the density distribution: the p99 query is in a dense cell with 20x the mean candidates, and it fails the latency target long before the median notices. I would alert on candidates-scanned per query, not on latency, because that leads the symptom.

The assumption ledger

Every design is a set of assumptions with a diagram attached, and the diagram is only correct relative to them. The ledger below collects everything this chapter has leaned on, so that you can state the design’s foundations in twenty seconds and say what replaces the design when each one fails.

Sort each assumption into one of three bins.

• State it — you are free to pick a value, and being wrong costs a re-derivation and nothing more.
• Ask it — the answer moves a policy or a threshold, so it is worth an interviewer’s time.
• Load-bearing — if this is wrong the design is not suboptimal, it is invalid. A box appears or disappears, rather than the count inside a box changing.

The one-line test, from ch 03: move the assumption an order of magnitude in each direction and ask whether the set of boxes changes, or only the number of machines inside them.

The one to mark explicitly as not load-bearing is the 50 businesses/km^2 density. It is the most-used number in the chapter and the most suspicious-looking, so it draws the challenge. Move it an order of magnitude in either direction and not one box changes.

At one tenth the density, the precision-6 candidate list is 33.5 instead of 335 and the search gets faster. At ten times it, the list is 3,353 and you cap it per cell — which is a tuning constant already in Bottlenecks and scaling, not a new component.

What density cannot do is change the ratio of scanned rows to returned rows, because it multiplies both sides of that ratio equally. The 176x amplification that condemns the B-tree, the 32x cliff, and the 8.5x and 2.01x overfetch figures are all density-independent.

The one place density is not a free parameter is the Deep dive 5 the search itself cache sizing, where the mean list length is fixed by the corpus rather than assumed — which is exactly why 50/km^2 must not be substituted for it. Knowing all this saves you from defending a number that cannot sink the design, and lets you spend the challenge on the five that can.

The sentence that makes this visible to an interviewer: “This design rests on five things. One, the points are static, which is what removes the write path and lets the index be a rebuildable artifact. Two, the corpus is 60 GB, which is what lets every replica hold everything and removes sharding from the conversation. Three, the answer must be exact, which is what makes cells a filter rather than an answer and forces the nine-cell query. Four, the radius varies, which is what makes precision selection a derivation rather than a constant. Five, a day of staleness is acceptable, which is what keeps the builder offline. The density figure everything is counted with is not one of them — it scales the counts and changes nothing structural.”

Cheat sheet

Every line below is derived somewhere above; this table is the recall test, not the explanation.

Related: 18 — Nearby Friends takes this index and makes the points move; 19 — Google Maps lays a road graph over the same cells; 05 — Consistent Hashing is the partitioner the business table uses; sql/03 — Database Internals is the index behaviour Deep dive 1 why a b tree on lat and lng cannot do this prices.