QST: any idea of the impact of the tweaks used compared to the original algorithm?

[theroggy]

Hallo!

I wonder...

Maybe you know it, but GeoPackage is a rather popular GIS data format based on sqlite. To be able to do fast spatial queries an rtree index is used, which is a standard/built-in feature of sqlite.

I noticed that the creation of an rtree index in sqlite/geopackage can take quite some time for large datasets... So, I wonder if you have an idea on the speed improvements that the changes you applied in your implementation compared to the original rtree paper give.

If they are significant, maybe the sqlite developers would be interested to implement them in their rtree implementation as well?

For reference, a ticket I opened in the sqlite forum regarding this: https://sqlite.org/forum/forumpost/af937a36b3

Regards,
Pieter

[tidwall]

Hi!

I wasn't previously familiar with GeoPackage but I've since had a chance to check out the website. It looks like a really nice format. Using Sqlite for its R-tree ability makes a ton of sense.

I noticed that the creation of an rtree index in sqlite/geopackage can take quite some time for large datasets.

How large is large? If it's only a few million items then perhaps just sorting the data prior to inserting it into Sqlite will give it a boost.

So, I wonder if you have an idea on the speed improvements that the changes you applied in your implementation compared to the original rtree paper give.

The Sqlite R-tree page says it uses the R*tree methods. R*tree is highly optimized for search performance, but less so for one-by-one inserts. I took a quick look at the Sqlite code and made a couple changes to speed stuff up.

https://github.com/tidwall/sqlite-rtree-optz

It's not huge, speedup about 1.5x to 1.8x depending on how spatially ordered the data is.

Though I would bet my hat that a true bulk insert algorithm would be much quicker than inserting each item one-by-one.

If I were to write it from scratch I would probably attempt the route of inserting all items into a single list or table in Sqlite, then order that list by the item's hilbert keys, then use that order to generate all the leafs, then the parent branches up to the root. This would avoid the need for the R-tree to have to dynamically adjust during construction, which is probably where most of the slowness is coming from. Likely having to deal with page caching, table relationships, etc.

I hope this information helps.

[theroggy]

How large is large? If it's only a few million items then perhaps just sorting the data prior to inserting it into Sqlite will give it a boost.

By large I mean some millions up to some tens of millions of items. I also talked about large because of file sizes. Because in the GIS world polygon data is quite common these items will consist of quite some more point, so a few million more complex polygons will result in GeoPackage files of a few GB up to ~15 GB. Files with tens of millions of rows will grow even larger...

I personally encounter cases quite commonly where creating the spatial index takes several minutes.

The rtree index for polygon files contain the minimum bounding rectangles of the polygons... but I suppose the performance behaviour will be similar for points in the rtree compared to rectangles?

I took a quick look at the Sqlite code and made a couple changes to speed stuff up. It's not huge, speedup about 1.5x to 1.8x depending on how spatially ordered the data is.

Wow, thanks for the elaborate tests and for even implementing and testing possible code changes. Indeed not huge, but still quite significant, so it would be great if the changes would get merged.

Though I would bet my hat that a true bulk insert algorithm would be much quicker than inserting each item one-by-one.

Yes, that was my original "feature request" to the sqlite developers. They didn't really react to it, I suppose because this might have quite some more impact on how this would work. Now, the rtree index is implemented as a (virtual) table and you just insert rows into it: all somewhat typical SQL operations. Bulk-loading the rtree index wouldn't be able to work like that so I think they are not too keen on that.

I hope this information helps.

Yes, definitely. I'll point the SQLite developers to your sample code and the test results by posting a link to it in the existing thread on the Sqlite forum if that's OK for you, and hopefully this gets some things rolling.

Thanks again!

[tidwall]

... GeoPackage files of a few GB up to ~15 GB. Files with tens of millions of rows will grow even larger...

Yeah I can see the challenge for sure. I wonder if you're pushing the upper limits of Sqlite R-tree module for loading data. I really think with your kind of dataset, (probably mostly static polygons?) bulk inserts would be ideal.

The rtree index for polygon files contain the minimum bounding rectangles of the polygons... but I suppose the performance behaviour will be similar for points in the rtree compared to rectangles?

Similar, yes. But in my experience a point heavy R-tree is usually a little quicker than one with mostly rectangles at the leaf level. My software typically deals with geolocation data that is dynamically moving, like geofencing programs. So I tailor my R-tree implementations to work with a mix of data that rapidly changes.

I'll point the SQLite developers to your sample code and the test results by posting a link to it in the existing thread on the Sqlite forum if that's OK for you, and hopefully this gets some things rolling.

I'm cool with that. I like what the Sqlite folks are doing and anything to inspire them in the geospatial space would bring me joy.