The SQLite R*Tree Module (opens in new tab)

(sqlite.org)

110 pointsmpsq5y ago15 comments

15 comments

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.

kragen5y 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.

jjmod5y 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

vlovich1235y 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.

1 more reply

daliusd5y ago

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

phaedrus5y 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?)

bob10295y 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.

aidos5y 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!

yowlingcat5y 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.

centimeter5y 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.

hagibborim5y ago

How close does DuckDB get to fulfilling your needs?

centimeter5y ago

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

yread5y 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

jokoon5y ago

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

j / k navigate · click thread line to collapse

15 comments

bob10295y ago

kragen5y ago

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.

jjmod5y 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

vlovich1235y 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.

1 more reply

daliusd5y ago

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

phaedrus5y ago

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?)

bob10295y ago

aidos5y 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!

yowlingcat5y ago

centimeter5y ago

hagibborim5y ago

How close does DuckDB get to fulfilling your needs?

centimeter5y ago

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

yread5y 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

jokoon5y ago

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

j / k navigate · click thread line to collapse