CocoaTouch, CoreData and binary String Search

Fri, 23. Oct 2009

Categories: de development Tags: Binary Cocoa CoreData iPhone NSPredicate Objective C Search

The query optimiser for NSPredicate queries ontop CoreData/SQLite on the iPhone is a bit rudimentary (cough) and so I had to optimise myself to get binary-search enabled quick results:

+(NSPredicate*)findBySearchTerm:(NSString*)rawTerm within:(BOOL)within context:(NSManagedObjectContext*)context
{
    NSSet *tokens = [MovieM indexTokens:rawTerm];
    if(tokens == nil || tokens.count < = 0)
        return [NSPredicate predicateWithFormat:@"FALSEPREDICATE"];
    NSMutableArray *preds = [NSMutableArray arrayWithCapacity:tokens.count];

    if(within == NO && context != nil)
    {
        // As queries aren't optimised by default we do it ourselves:
        // 1st: find matching entries from the IndexKey table - leveraging it's index:
        NSFetchRequest *fr = [[NSFetchRequest alloc] init];
        fr.entity = [NSEntityDescription entityForName:@"IndexKey" inManagedObjectContext:context];
        NSMutableSet *result = nil;
        NSError *error = nil;
        for(NSString *token in tokens)
        {
            // BETWEEN uses the table-index while BEGINSWITH does not:
            fr.predicate = [NSPredicate predicateWithFormat:@"key BETWEEN {%@, %@}", token, [MovieM upperBoundSearchString:token]];
            NSArray *keys = [context executeFetchRequest:fr error:&error];
            if(error != nil)
                NSLog(@"Oops: %@", error);
            // turn IndexKey entries to movies (join up):
            NSArray *movs = [keys valueForKey:@"movie"];
            // aggregate the results for each token:
            if(result == nil)
                result = [NSMutableSet setWithArray:movs];
            else
                [result intersectSet:[NSSet setWithArray:movs]];
        }
        [fr release];
        return [NSPredicate predicateWithFormat:@"SELF IN %@", result];
    }

    NSPredicate *template = nil;
    if(within)
        template = [NSPredicate predicateWithFormat:@"ANY index.key CONTAiNS $searchTerm"];
    else
        template = [NSPredicate predicateWithFormat:@"ANY index.key BEGINSWITH $searchTerm"];
    for(NSString *token in tokens)
    {
        NSDictionary *params = [NSDictionary dictionaryWithObject:token forKey:@"searchTerm"];
        [preds addObject:[template predicateWithSubstitutionVariables:params]];
    }
    return [NSCompoundPredicate andPredicateWithSubpredicates:preds];
}

Helpers herein are