R Tree Index

R-Tree Index for Fast Geospatial Queries

If you want to use Yap with a lot of geospatial data (e.g. things with latitude/longitude), it's helpful to use the YapDatabaseRTreeIndex extension to speed things up. From the R-Tree sqlite docs:

An R-Tree is a special index that is designed for doing range queries. R-Trees are most commonly used in geospatial systems where each entry is a rectangle with minimum and maximum X and Y coordinates. Given a query rectangle, an R-Tree is able to quickly find all entries that are contained within the query rectangle or which overlap the query rectangle.

Supported Platforms

• The R-Tree module is included by default in the system sqlite3.dylib on iOS 8 or higher.
• For earlier iOS versions you'll need to compile sqlite yourself.
• Not sure about minimum version for OS X support (maybe 10.10?)

Setup

Adapt these samples to your needs.

Swift

let setup = YapDatabaseRTreeIndexSetup()
let setup = YapDatabaseRTreeIndexSetup()
setup.setColumns(["minLon", "maxLon", "minLat", "maxLat"])
let handler = YapDatabaseRTreeIndexHandler.withObjectBlock({ (d: NSMutableDictionary!, collection: String!, key: String!, object: AnyObject!) -> Void in
    if let item = object as? LonlatObject {
        d["minLon"] = item.lon
        d["maxLon"] = item.lon
        d["minLat"] = item.lat
        d["maxLat"] = item.lat
    }
})

let ext = YapDatabaseRTreeIndex(setup: setup, handler: handler, versionTag: "1.0")
yapDb.db.registerExtension(ext, withName: RTreeTest.indexName)

Obj-C

_rTreeIndex = @"RTreeIndex";
YapDatabaseRTreeIndexSetup *setup = [[YapDatabaseRTreeIndexSetup alloc] init];
[setup setColumns:@[RTreeMinLat,
                    RTreeMaxLat,
                    RTreeMinLon,
                    RTreeMaxLon]];
YapDatabaseRTreeIndexHandler *handler = [YapDatabaseRTreeIndexHandler withObjectBlock:^(NSMutableDictionary *dict, NSString *collection, NSString *key, id object) {
    if ([object isKindOfClass:[BRCDataObject class]]) {
        BRCDataObject *dataObject = object;
        dict[RTreeMinLat] = @(dataObject.coordinate.latitude);
        dict[RTreeMaxLat] = @(dataObject.coordinate.latitude);
        dict[RTreeMinLon] = @(dataObject.coordinate.longitude);
        dict[RTreeMaxLon] = @(dataObject.coordinate.longitude);
    }
}];
YapDatabaseRTreeIndexOptions *options = [[YapDatabaseRTreeIndexOptions alloc] init];
NSSet *allowedCollections = [NSSet setWithArray:@[]];
options.allowedCollections = [[YapWhitelistBlacklist alloc] initWithWhitelist:allowedCollections];
YapDatabaseRTreeIndex *rTree = [[YapDatabaseRTreeIndex alloc] initWithSetup:setup handler:handler versionTag:@"1" options:options];
BOOL success = [self.database registerExtension:rTree withName:self.rTreeIndex];
NSLog(@"%@ %d", self.rTreeIndex, success);

Queries

Swift

var arguments: [CVarArgType] = [minLon, maxLon, minLat, maxLat].map({NSNumber(double: $0)}) // must be var to get a pointer, must be a NSObject to be formatted
let queryString = "WHERE minLon >= ? AND maxLon <= ? AND minLat >= ? AND maxLat <= ?"
let query = withVaList(arguments, { (pointer: CVaListPointer) -> YapDatabaseQuery in
    return YapDatabaseQuery(format: queryString, arguments: pointer)
})
var items: [LonlatObject] = []

yapDb.readConnection.readWithBlock({ (transaction: YapDatabaseReadTransaction) in
    if let index = transaction.ext("rTreeIndex") as? YapDatabaseRTreeIndexTransaction {
        let enumerateBlock: (String!, String!, AnyObject!, UnsafeMutablePointer<ObjCBool>) -> Void = {
            (collection: String!, key: String!, object: AnyObject!, stop: UnsafeMutablePointer<ObjCBool>) in
            if let item = object as? LonlatObject {
                items.append(item)
            }
        }
        index.enumerateKeysAndObjectsMatchingQuery(query, usingBlock: enumerateBlock)
    }
})

return items

Obj-C

- (void) queryObjectsInMinCoord:(CLLocationCoordinate2D)minCoord
                       maxCoord:(CLLocationCoordinate2D)maxCoord
                completionQueue:(dispatch_queue_t)completionQueue
                   resultsBlock:(void (^)(NSArray *results))resultsBlock {
    if (!resultsBlock) {
        return;
    }
    if (!completionQueue) {
        completionQueue = dispatch_get_main_queue();
    }
    NSMutableArray *results = [NSMutableArray array];
    NSString *queryString = [NSString stringWithFormat:@"WHERE %@ >= ? AND %@ <= ? AND %@ >= ? AND %@ <= ?",
                             RTreeMinLon,
                             RTreeMaxLon,
                             RTreeMinLat,
                             RTreeMaxLat];
    
    CLLocationDegrees minLat = minCoord.latitude;
    CLLocationDegrees minLon = minCoord.longitude;
    CLLocationDegrees maxLat = maxCoord.latitude;
    CLLocationDegrees maxLon = maxCoord.longitude;
    
    NSArray *paramters = @[@(minLon),
                           @(maxLon),
                           @(minLat),
                           @(maxLat)];
    YapDatabaseQuery *query = [YapDatabaseQuery queryWithString:queryString parameters:paramters];
    
    [self.readConnection asyncReadWithBlock:^(YapDatabaseReadTransaction *transaction) {
        YapDatabaseRTreeIndexTransaction *rTree = [transaction ext:self.rTreeIndex];
        [rTree enumerateKeysAndObjectsMatchingQuery:query usingBlock:^(NSString *collection, NSString *key, id object, BOOL *stop) {
            if ([object isKindOfClass:[BRCDataObject class]]) {
                [results addObject:object];
            }
        }];
    } completionQueue:completionQueue completionBlock:^{
        resultsBlock(results);
    }];
}

Sample Code

• Swift R-Tree query and setup:
• Obj-C R-Tree query
• Obj-C R-Tree setup