NaN and Inf results in search of all nodes in rtree

[krkeshav]

Describe the bug
NaN or Inf causes rtree to search all nodes which causes performance issues

To Reproduce
Eg. intersects namespace objects circle NaN NaN 1
Try with huge dataset

Expected behavior
I expected it to throw an error

Logs
If applicable, provide logs, panics, system messages to help explain your problem.

Operating System (please complete the following information):

• OS: [e.g. Linux / Mac OS]
• CPU: [e.g. amd64 / arm64 / Apple Silicon / Intel]
• Version: All versions including latest
• Container: k8s/docker/local

Additional context
Depending on CPU provided and size of dataset, the queries can range from few seconds to almost 1 minute.

[tidwall]

It's probably best to avoid having NaN points from being inserted into the rtree.

An NaN point should be treated as an empty point. This is how many geometry libraries work, but for some reason Tile38 is isn't doing this. The bug appears to be here.

tile38/internal/collection/collection.go

Lines 108 to 118 in 7d1b0d4

	func (c *Collection) indexDelete(item *object.Object) {
	if !item.Geo().Empty() {
	c.spatial.Delete(rtreeItem(item))
	}
	}
	func (c *Collection) indexInsert(item *object.Object) {
	if !item.Geo().Empty() {
	c.spatial.Insert(rtreeItem(item))
	}
	}

The Empty() for a NaN point is returning false, but it should return true.

Likely the slowdown that you are encountering is similar to the null island effect, where the coordinate 0,0 will end up over-populating the rtree leaf nodes with a bunch of duplicate entries, causing terrible query times.

In reality this can happen with any duplicate tuple, not just 0,0. Nonfinite coords NaN,NaN, Inf,Inf and normal coords like -112,33 can cause this. If you have a ton of duplicates, you'll feel the grind.

Your PR #794 returns an error on SET. But this'll probably break deployments that expect NaN points to be treated as empty, it'll also crash the server when reloading aofs that contains existing NaN Points.

[krkeshav]

Ack, I'll remove the checks on set and check the behaviour of collection.go file which you mentioned.

Currently I don't have any NaN or Inf in stored polygons but still facing slowdown in search queries and from what I found its checking every node in rtree. That's why I added validations on search. Are the validations in search fine or is there some way to return early in rtree search 🤔?
rtree search

[tidwall]

The most important thing to avoid is having any NaN points in the rtree.

For queries, yes an all-NaN rectangle search will always intersect all nodes. yuck.

This can probably be fixed by checking the min/max rectangle for (NaN,NaN) prior to running the rtree.Search function in the collection.go file.

tile38/internal/collection/collection.go

Lines 404 to 418 in efa3caa

	func (c *Collection) geoSearch(
	rect geometry.Rect,
	iter func(o *object.Object) bool,
	) bool {
	alive := true
	min, max := rtreeRect(rect)
	c.spatial.Search(
	min, max,
	func(_, _ [2]float32, o *object.Object) bool {
	alive = iter(o)
	return alive
	},
	)
	return alive
	}

If it's all NaN then ignore the search.

[krkeshav]

Updated the PR for search. Let me know if this check can be added in any other type of search.

Also, regarding avoiding NaN points in tree, I tried adding coordinates with NaN, NaN by modifying coordinates inside AOF, redis-cli and conn.Write([]byte(...)) and it failed throwing an error invalid data. So, ig its not possible to add this in rtree via geojson objects which makes sense because it makes the json invalid.

I will look into other type of inputs, but it may take more time so I will probably raise another PR for that.

[tidwall]

I merged the PR for the search, but there's still the empty detection for Point(NaN NaN) that needs to be addressed. I'm investigating now. But I wonder the best solution is to update the GeoJSON library and the Point.Empty() SimplePoint.Empty() functions to detect for NaN.

[tidwall]

I just pushed a fix that detects NaN points for insertions too.
All NaN points or rects will now be transparently ignored by the rtree.
I think this issue is now resolved and I'll be pushing a release soon.
Let me know if you see any additional related problems on you side.
Thanks!