News for hackers. Stuff that matters.
Re:How we built Uber Engineering's highest query-per-second ... by deminature on Thursday November 14, 2019 @02:57PM (#21538784)
It's disappointing to see a highly-upvoted comment from someone that didn't read the article. The article discusses explicitly why R-trees were not used:

>Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route based on the observation that Uber’s business model is city-centric; the business rules and the geofences used to define them are typically associated with a city. This allows us to organize the geofences into a two-level hierarchy where the first level is the city geofences (geofences defining city boundaries), and the second level is the geofences within each city.

Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @05:27PM (#21540183)
I did read the article before posting. They don’t actually explain why they opted to not use an R-tree except to say that they think this organizational structure makes sense intuitively. Unfortunately, intuition here is wrong, and the link I posted specifically benchmarks their solution and shows that if they had done even basic benchmarking they would have seen this.

Now there might be a valid argument for this approach if the geofences are changing constantly and reindexing the R-trees would take too long, but in the end they synchronize everything anyways, and the R-tree could easily be generated on another node, serialized and then unserialized asynchronously before swapping to an updated tree.

Re:How we built Uber Engineering's highest query-per-second ... by icholy on Thursday November 14, 2019 @03:07PM (#21538881)
R-tree will easily outperform that approach.
Re:How we built Uber Engineering's highest query-per-second ... by xtomus on Thursday November 14, 2019 @04:45PM (#21539812)
You can either ship a 2 dimensional linear search approach today or ship an R tree based approach in 2 weeks time. I know which one in choosing if they both meet all of the requirements
Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @05:29PM (#21540193)
Just about every modern language has a well established R-tree library...
Re:How we built Uber Engineering's highest query-per-second ... by icholy on Thursday November 14, 2019 @11:43PM (#21542253)
I mean why stop there? Let's remove the database indexes too. Hell, why use a hashtable when you have lists amirite?