The SQLite R*Tree Module

110 points by mpsq 5 years ago | 15 comments

bob1029 5 years ago |

I have started to play around with building a software rasterizer from scratch, and I am wondering if this might be something that I could potentially leverage to cheat at some of the math problems. The document mentions CAD, but I am not sure if the performance is such that real-time (i.e. 30+fps) queries would be feasible over meaningful datasets.

Does anyone have any experience directly using SQL for this sort of thing? I feel like there is something here with being able to define a 3d scene in terms of normalized SQL tables, and then running queries over them in order to produce intermediate/final output.

kragen 5 years ago | |

I don't have any experience using SQL for that kind of thing, but in http://canonical.org/~kragen/sw/dev3/sqlitescene.py I'm getting a bit over 800 frames per second on my laptop, including rotating the scene in SQL — about 2400 queries per second — so I think it's plausible to use SQLite for this kind of thing. But I don't know if that kind of performance is consistent, which is a big deal for real-time graphics. (The worst-case frame time I get on that data set over sixty thousand frames is 3.8 ms though so it might be OK.)

Using SQL for this kind of thing would definitely be a very weird choice. So it's super awesome and I look forward to hearing about whether it works out.

jjmod 5 years ago | |

It might be feasible if you use sqlite's in-memory feature, because hitting the disk on each query is way too slow for a real-time application.

Why not just use an r-tree library for the language you're using? It'll be faster and easier to work with. Since scene data is usually hierarchial, sql doesn't seem like a great choice for storing it

vlovich123 5 years ago | | |

Page cache and SQLite cache means you don’t actually end up hitting the disk usually. Also SSDs are pretty fast and NVMEs more so.

Maybe when you first start or access a new piece of data for the first time you maybe get a hiccup (maybe not - always profile to figure out how your specific application performs). If hiccups like that actually manifest, a nice way to solve that would be to attach the on-disk DB to the in-memory one, copy everything over (and maybe detach). If that DB is ever mutable at runtime, just copy the changes back in a background transaction to the on-disk DB (in this case I wouldn’t detach probably). This way you still get the persistence of the disk with the performance of RAM.

daliusd 5 years ago | |

https://www.sqlite.org/famous.html - there is at least one CAD company ;)

phaedrus 5 years ago | |

You might have some success using hand-coded routines for the last / hardest-working portion of the rasterizer, and just use SQLite to translate data from a format produced by the front-end to a format that matches the back-end.

I'm interested in relational programming for 3D meshes. For example what if we could use the form of a query to write a routine that splits a 3D mesh (creating new triangles at the boundary?)

bob1029 5 years ago | | |

The mesh manipulation is what interests me as well. I feel like SQL allows for a unique opportunity to explore solutions that would otherwise be impractical/difficult to experiment with using hand-coded imperative methods.

aidos 5 years ago | |

I’ve used it by running it memory from python as a temporary dB. In my case it was just for simple bounds checking queries but it worked incredibly well.

I’m not sure about trying to get 30fps out of it though - might be a stretch!

yowlingcat 5 years ago |

Having used this in production before, it's an absolutely fantastic tool for specific use cases. My use case was indexing fairly static medium cardinality geo data for lookup within a microservice that we hit from our primary monolith. You get fast spatial indexes and essentially zero additional operational overhead.

centimeter 5 years ago |

I love SQLite's software model (embeddable library rather than a separate binary), but I often sorely miss the rich data model provided by postgres. I miss things like strong type checking, special types to represent times/coordinates/etc., and advanced index types like GiST indices.

hagibborim 5 years ago | |

How close does DuckDB get to fulfilling your needs?

centimeter 5 years ago | | |

Doesn’t look like it has rich types or advanced indices.

yread 5 years ago |

Note that even though it's a module lot of distributions of Sqlite come with it enabled. You can check it by running

PRAGMA compile_options;

and looking for ENABLE_RTREE

jokoon 5 years ago |

Mmmmh does spatialite use it? I guess yes. Spatialite is great even though the queries are a little tedious.