Skip to content

The Planet as a Prefix

Edit source

Turning the whole Earth into search terms a plain text index can answer.

Part 6 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. This one is the largest single idea in the pile: htm, the mesh that let a text search engine answer questions about space.

“Find me documents within five kilometers of here” is not a text query. A search index is superb at one thing, which documents contain this term, and a distance is not a term. You could bolt a separate spatial database onto the side, run two systems, and join them. Or you could find a way to turn where into what, a place into a word the index already knows how to match. That second path is the Hierarchical Triangular Mesh, and it is the most quietly clever thing in the whole engine.

Start with the sphere and tile it, not with a latitude/longitude grid, but with triangles. Project an octahedron onto the sphere to get eight spherical triangles, then recursively split each one into four smaller triangles, again and again, as deep as you want resolution. Each of these trixels gets a name: a root, N or S, followed by one digit 0, 1, 2, 3 for each level of subdivision you descended. N01230... is a specific triangle a few levels down, and the triangle one level shallower is just N0123, its name with the last digit trimmed.

That naming is the entire trick, because it makes the name a spatial key. Two points that are close on the sphere fall into the same triangle for many levels before they split apart, so they share a long name prefix. Trim digits off a name and you zoom out to the trixel that contains it. And because the mesh is nested, a trixel’s 64-bit id covers a contiguous range of ids: its whole subtree, every point inside it, is one [start, end] interval. A neighborhood is a prefix. A region is a set of ranges.

Now the search engine’s own machinery does the geometry for free. Index each point under its trixel id. To answer “within five kilometers of here,” you turn that circle into the set of trixels that cover it and hand their id ranges to the index as ordinary term ranges, the same range query it would run on a date or a price. No spatial join, no second database. The text index answers a question about space because you taught space to spell.

The obvious tiling is a lat/long grid, and it is a trap. Lines of longitude converge at the poles, so grid cells shrink to slivers up north and balloon at the equator: the cells are wildly unequal in area, and the math degenerates exactly where the Earth is least forgiving. A recursively subdivided triangular mesh has none of that. Every trixel splits into four roughly-equal children the same way everywhere on the sphere, poles included, so resolution is even and the geometry never hits a singularity. The shape of the tiling is doing real work; a triangle is the piece that tiles a ball without lying about the poles.

Naming a point is easy. The work is going the other way: given a query region, produce the minimal set of trixels that cover it. htm supplies the pieces for that, a Constraint (a spherical cap, a circular area cut off the sphere by a plane) and the tests between a cap and a trixel, and Xapiand’s geometry layer ranges a region with them by a recursive descent of the mesh. At each trixel it asks one of three questions: is this triangle entirely inside the region (emit its whole id range and stop, you have covered a huge area with one interval), entirely outside (drop it, and its whole subtree with it), or partial (recurse into its four children and decide again). Fully-inside and fully-outside are what keep the answer small; you only pay resolution along the boundary of the region, not its area. The set algebra on top, trixel_union, trixel_intersection, and their range equivalents, lets Xapiand build a polygon or an EWKT geometry out of caps and combine them into one term set.

That is the piece that let a text engine answer real geo queries, circles, polygons, arbitrary geometries, without a spatial index sitting beside it. It ships as two compiled units and leans on one sibling familiar, cartesian, for turning latitude and longitude into the unit-sphere vectors the mesh runs on.

The next familiar goes the opposite direction from a whole planet. It is a single number with no ceiling at all, and the one operation on it that nearly everyone gets wrong.