Creating an r-tree index table for bounding box

I'm currently working on setting up a SQLite database using GRDB to store a very simple location-based model (I've simplified the model for the purpose of this question)

struct ExampleModel: Codable, Identifiable, FetchableRecord, PersistableRecord {
    let id: String
    let longitude: Double
    let latitude: Double
}

However, I also need to create an r-tree index table to allow users to pass a bounding box and retrieve all of the persisted elements within this bounding box

struct BoundingBox {
    let minX: Double
    let maxX: Double
    let minY: Double
    let maxY: Double
}

It's the first time I'm having to implement a functionality like this and I'm totally lost on how to get this r-tree index table up and running. What would the database schema look like and how would I even get a bounding box if all I have is a model with a specific location? I'd appreciate some tips!

Solution

Since we use GRDB, given a Model Class like this(I added uid field as a human readable text):

public struct ExampleModel: Codable, FetchableRecord, PersistableRecord, Identifiable {
    // Database PK used for R-Tree joins (nil before insertion)
    public var id: Int64?
    // external identifier as a human readable name.
    public var uid: String
    public var longitude: Double
    public var latitude: Double
    
    public init(id: Int64? = nil, uid: String, longitude: Double, latitude: Double) {
        self.id = id
        self.uid = uid
        self.longitude = longitude
        self.latitude = latitude
    }
    
    public static let databaseTableName = "example"
    
    // Map the `id` property to the `pk` column in the database
    private enum Columns {
        static let pk = Column("pk")
        static let uid = Column("uid")
        static let longitude = Column("longitude")
        static let latitude = Column("latitude")
    }
    
    public func encode(to container: inout PersistenceContainer) throws {
        container[Columns.pk] = id
        container[Columns.uid] = uid
        container[Columns.longitude] = longitude
        container[Columns.latitude] = latitude
    }
    
    public init(row: Row) throws {
        id = row[Columns.pk]
        uid = row[Columns.uid]
        longitude = row[Columns.longitude]
        latitude = row[Columns.latitude]
    }
}

The second thing we need to do is create the schemes:

 
    private func createTables(_ db: Database) throws {
        // 1) Base table: keep string uid, add integer PK for joins with the rtree
        try db.create(table: "example") { t in
            t.column("pk", .integer).primaryKey(onConflict: .replace, autoincrement: true)
            t.column("uid", .text).notNull().unique()      // original String id
            t.column("longitude", .double).notNull()
            t.column("latitude", .double).notNull()
        }
        
        // 2) R-Tree for spatial search (first col MUST be INTEGER)
        try db.execute(sql: """
        CREATE VIRTUAL TABLE example_rtree USING rtree(
          pk,           -- INTEGER row id matching example.pk
          minX, maxX,   -- longitude
          minY, maxY    -- latitude
        );
        """)
    }

R-Trees (specifically R*-Trees in SQLite’s implementation) index rectangles hierarchically: parent nodes bound the rectangles of their children. Querying a box walks the tree, pruning whole subtrees whose MBRs(Minimum Bounding Rectangle) don’t intersect the search region. Here we create the R-Tree with buit-in r-tree module, it has a fixed contract:

The first column must be an integer primary key (pk).
The remaining columns must come in pairs: min, max for each dimension, Here you gave two dimensions (X and Y), so that’s four numbers: minX, maxX, minY, maxY.

Create triggers to the index:

        try db.execute(sql: """
        CREATE TRIGGER example_after_insert AFTER INSERT ON example
        BEGIN
          INSERT INTO example_rtree(pk, minX, maxX, minY, maxY)
          VALUES (new.pk, new.longitude, new.longitude, new.latitude, new.latitude);
        END;
        """)
        
        try db.execute(sql: """
        CREATE TRIGGER example_after_update AFTER UPDATE OF longitude, latitude ON example
        BEGIN
          UPDATE example_rtree
             SET minX = new.longitude, maxX = new.longitude,
                 minY = new.latitude,  maxY = new.latitude
           WHERE pk = new.pk;
        END;
        """)
        
        try db.execute(sql: """
        CREATE TRIGGER example_after_delete AFTER DELETE ON example
        BEGIN
          DELETE FROM example_rtree WHERE pk = old.pk;
        END;
        """)

So that when new entries are added/updated/deleted, their indexes got added/updated/deleted.

When query for enties inside the bounding box:

 public static func fetch(in box: BoundingBox,
                      _ db: Database) throws -> [ExampleModel] {
        let predicateSQL = """
            r.minX >= ? AND r.maxX <= ? AND
            r.minY >= ? AND r.maxY <= ?
            """
        
        // Join base table with rtree by integer pk
        let sql = """
        SELECT e.*
          FROM example AS e
          JOIN example_rtree AS r ON r.pk = e.pk
         WHERE \(predicateSQL)
        """
        
        let args: StatementArguments = [box.minX, box.maxX, box.minY, box.maxY]
        
        return try ExampleModel.fetchAll(db, sql: sql, arguments: args)
    }

Finally, Here is the full example project, checkout and run swift run RTreeExample in the project root folder:

swift run RTreeExample
[1/1] Planning build
Building for debugging...
[4/4] Compiling RTreeExample main.swift
Build of product 'RTreeExample' complete! (0.32s)

 Inserting 5 sample points...

🔍 Searching for points in Tokyo area...

Found 4 points contained in Tokyo bounding box:
  • tokyo_station: (139.7673, 35.6812)
  • shibuya: (139.7016, 35.6598)
  • shinjuku: (139.7036, 35.6896)
  • akihabara: (139.7744, 35.7022)

Done !