How to port simple spatial index using SQLite R-Trees to Postgres?

Question

I have implemented a simple spatial indexing schema based on bounding boxes by following the SQLite R*Tree tutorial, which has given me the following schema:

CREATE VIRTUAL TABLE events_region USING rtree(
    id,              -- primary key
    xmin, xmax,      -- minimum and maximum X coordinate
    ymin, ymax,      -- minimum and maximum Y coordinate
);

I want to now port this schema to Postgres (but not using PostGIS in order to cut down on dependencies). I know that this should be possible using a GIST index (as R-trees have been phased out, with GIST now filling their role), but I'm struggling to work out how to go about this.

If PostGIS solves your problem, then why don't you use it? Just set it up when you install Postgres. It's a one time thing. — , Feb 03 '15 at 06:31
So, you want a [`gist`](http://www.postgresql.org/docs/current/static/indexes-types.html) index on a [`box`](http://www.postgresql.org/docs/current/static/datatype-geometric.html) column/expression? Have you tried [`box_ops`](http://www.postgresql.org/docs/current/static/gist-builtin-opclasses.html)? Of course, for more advanced indexing/searching I also recommend PostGIS. — pozs, Feb 03 '15 at 13:02

Ciro Santilli OurBigBook.com · Answer 1 · 2023-07-13T19:51:57.240

Here's an example with points rather than boxes:

time psql -c 'create table t(p point)'
time psql -c "insert into t select (point(
  '(' || generate_series || ',' || generate_series || ')')
) from generate_series(1, 10000000)"
time psql -c 'create index on t using gist(p)'
time psql -c "select count(*) from t
  where p <@ box '(1000000,1000000),(9000000,2000000)'"

This creates a line of 10m points, and queries the count of points within the box with lower left (x=1m, y=1m) and upper right (x=9m, y=2m):

  count  
---------
 1000001
(1 row)

Index creation took 100s on my SSD, which a bit sad. But well. Query was 0.2, but this was bout by iterating a bunch of data, query with limit 100 on empty region was 0.035s which is good, it is definitely being accelerated.

point is a type on itself as listed at: https://www.postgresql.org/docs/current/datatype-geometric.html. I don't see how to create spatial indexes on pre-existing integer columns which is a shame.

The weird operator <@ means "contained in". https://www.postgresql.org/docs/15/functions-geometry.html documents some of the other weird geometric operators, and https://www.postgresql.org/docs/15/gist-builtin-opclasses.html lists which geometric types support what.

To more closely match the SQLite schema, you would want to setup the database with box types instead of point types, and then determine the correct weird operator of choice, likely either <@ or && for intersection.

This was a good source on this obscure PostgreSQL feature: https://medium.com/postgres-professional/indexes-in-postgresql-5-gist-86e19781b5db examples are very rare to come by!

Tested on Ubuntu 23.04, PostgreSQL 15.3, Lenovo ThinkPad P51, SSD: Samsung MZVLB512HAJQ-000L7 512GB SSD, 3 GB/s nominal speed.

How to port simple spatial index using SQLite R-Trees to Postgres?

1 Answers1

Linked