Spatial Index Improvements #71
Description
With #22 #68 we added a space filling curve based spatial index. With #70 we will integrate it into our API. In this blog post we wrote about it from a high level perspective. This ticket is about potential improvements for the spatial index we can explore and that we didn't get to the bottom of in our very first basic iteration where we favored a simple working solution.
Better binary search
At the moment our binary searches and especially the one we use most (tinygraph_index_bsearch_lt) could benefit from improvements such as: a branchless version, prefetching, switching to a linear scan below a threshold.
Speculative look ahead vs bigmin ✔
At the moment once we leave the query bounding box along the curve, we always compute bigmin (the next z value along the curve inside the bounding box) and jump to it with binary search. But there are cases where the next z value is just a few items ahead: by looking ahead for a threshold we could reduce the number of bigmin computations and binary searches in favor of a simple linear scan of a handful of items. Below are two examples from the lowest level.
The bounding box at its right side divides a lowest z level by half. In this case the z values in the example below alternate between: 1 (in), 2 (out), 3 (in), 4 (out)
------
1 | 2
3 | 4
------The bounding box at its bottom side divides lowest z levels by half. In this case the z values in the example below alternate between: 1 (in), 2 (in), 3 (out), 4 (out), 5 (in), 6 (in), 7 (out), 8 (out)
| |
| 1 2 5 6 |
|------------|
3 4 7 8Above in the first case we only have to look ahead one item and in the second case two items to find the next z value along the curve again, without the need for bigmin or a binary search. One idea could be computing statistics of how often we skip ahead and a histogram of how many items we skip ahead and tune a threshold based on that.
Extend the bounding box to snap to grid
Similar to the idea above where we look ahead a few items along the curve for the next item within the bounding box, the idea here is to extend the bounding box such that it is aligned with a z order level. In the two examples above we could extend the bounding box to the right and to the bottom, respectively, minimizing the in/out changes.
Both ideas have the same effect: reducing bigmin computations and binary searches in favor of linearly scanning through memory for the next handful of items.
Compute z-values on demand
At the moment we compute all z-values and store them in a flat array. We also store the node ids and the longitude and latitude pairs. The observation here is that the z-values (64bit) are the interleaved longitude and latitude pairs (2x32bit). We can go back and forth between them. The reason we store z-values is their computation is not the cheapest.
One idea could be no longer storing the z-values and computng them on-demand only when we need them
- To compute the
[zmin, zmax]range - When we leave the bounding box to compute bigmin
- When we run binary search to jump to bigmin
This probably requires us to run binary search on the node ids and locations and in its comparison compute the z-values on the fly. The upside: we no longer store redundant data and the spatial index gets really small. The downside: it could degrade performance but we need to check how often we really need the z-values and if it's not negligible compared to memory access latency.
Be smart about z-order discontinuities
At the moment we simply interleave the fixed point u32 longitudes and latitudes for the z-value. This means we have no control over where the major discontinuities are. Think: worst case it's splitting apart a city we want to route in and then the start and stop locations would be furthest apart in memory.
One idea here could be first transforming the coordinates (e.g. rotate, translate) such that the major discontinuities occur over water or oceans. Then finding the nearest neighbors and undoing the transformation again before returning results to the user.
SIMD / AVX2
One idea is to scan items within the query bounding box in parallel registers and do the within-bbox comparisons in parallel registers, too. Meaning: we can load up the next eight locations into AVX2 registers and compare them against the bounding box extremes in one go. Note that we need to carefully handle cases where some items are within the bounding box and some are not. The other two cases where either all items are within the bounding box or all items are outside the bounding box are easier to handle.
Look into multiple (two?) curves for orthogonal query properties
At the moment we have a single z-order sorting. In the case of discontinuities (after Z blocks) we compute the next value within the query bounding box (bigmin) and jump to it via binary search. This results into our nearest neighbor search scanning potentially multiple linear memory ranges in memory. The bigger the discontinuity the further apart these ranges are in memory.
The worst case for the z-order curve is when the query bounding box spans across the highest level discontinuity separating the top half from the bottom half. In that case the ranges to scan will be furthest apart in memory.
One idea could be not just storing a single z-order curve but storing a second one e.g. rotated by 90 degrees, see below. Then the original z-order curve has its worst discontinuities top/bottom and the rotated one left/right.
Z N
Idea we could try: For the query bounding box compute the extremes [zmin, zmax] for both curves. Use the curve where the range is the smallest since this indicates the least disruptive discontinuities and the closest distance in memory.
K Nearest Neighbor API (KNN)
At the moment our spatial index allows for bounding box queries (range queries in 2d). There is a second interface we should look into: knn to find the k nearest neighbors. It works like this: find the node in the index, find k neighbors around the node along the curve, pick the one maximizing the distance to the node, run a bounding box query with the maximum one as radius and pick k smallest from the results.