References of Current Spatial Join Algorithm

[TheHillBright]

Hi @Maxxen , I'm very happy to see the new spatial join operator in duckdb and its improvement! I understand from the blog post that currently it's using R-index based join algorithm. I would like to understand more about the algorithm besides the bits described in the post. I wonder if there's a standard name for the algorithm that the duckdb spatial join essentially implements? It would be even better if you're aware of any academic papers describing this algorithm.

[Maxxen]

Hello!

Not sure if there is name for the "spatial join" algorithm itself, it basically works the same as a regular database "hash-join", but instead of creating a hash-table we create an r-tree on the smaller side join input which we use to find candidate matches when we later pass through the left-side input.

The r-tree construction and probing algorithm is inspired by the flatbush implementation, but with some smaller modifications to make it possible to "suspend" and ongoing lookup if we find more matches than we can fit into a duckdb "vector". Kyle wrote an amazing guide on understanding the original Flatbush code, which I highly recommend!

[TheHillBright]

Thanks for the flatbush bits. I've just quickly looked at your implementation. My understanding is that you create single R-tree index on the build-side table. If my understanding is correct, then I find umaiacs.umd.edu/~hjs/pubs/jacoxtods07.pdf the indexed nested loop join at page 50 looks very similar to the algorithm you implemented, with the index part using r-tree. Do you @Maxxen agree that spatial_join in the current duckdb-spatial extension is an efficient implementation of this algorithm?