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:

 1+(NSPredicate*)findBySearchTerm:(NSString*)rawTerm within:(BOOL)within context:(NSManagedObjectContext*)context
 2{
 3    NSSet *tokens = [MovieM indexTokens:rawTerm];
 4    if(tokens == nil || tokens.count < = 0)
 5        return [NSPredicate predicateWithFormat:@"FALSEPREDICATE"];
 6    NSMutableArray *preds = [NSMutableArray arrayWithCapacity:tokens.count];
 7
 8    if(within == NO && context != nil)
 9    {
10        // As queries aren't optimised by default we do it ourselves:
11        // 1st: find matching entries from the IndexKey table - leveraging it's index:
12        NSFetchRequest *fr = [[NSFetchRequest alloc] init];
13        fr.entity = [NSEntityDescription entityForName:@"IndexKey" inManagedObjectContext:context];
14        NSMutableSet *result = nil;
15        NSError *error = nil;
16        for(NSString *token in tokens)
17        {
18            // BETWEEN uses the table-index while BEGINSWITH does not:
19            fr.predicate = [NSPredicate predicateWithFormat:@"key BETWEEN {%@, %@}", token, [MovieM upperBoundSearchString:token]];
20            NSArray *keys = [context executeFetchRequest:fr error:&error];
21            if(error != nil)
22                NSLog(@"Oops: %@", error);
23            // turn IndexKey entries to movies (join up):
24            NSArray *movs = [keys valueForKey:@"movie"];
25            // aggregate the results for each token:
26            if(result == nil)
27                result = [NSMutableSet setWithArray:movs];
28            else
29                [result intersectSet:[NSSet setWithArray:movs]];
30        }
31        [fr release];
32        return [NSPredicate predicateWithFormat:@"SELF IN %@", result];
33    }
34
35    NSPredicate *template = nil;
36    if(within)
37        template = [NSPredicate predicateWithFormat:@"ANY index.key CONTAiNS $searchTerm"];
38    else
39        template = [NSPredicate predicateWithFormat:@"ANY index.key BEGINSWITH $searchTerm"];
40    for(NSString *token in tokens)
41    {
42        NSDictionary *params = [NSDictionary dictionaryWithObject:token forKey:@"searchTerm"];
43        [preds addObject:[template predicateWithSubstitutionVariables:params]];
44    }
45    return [NSCompoundPredicate andPredicateWithSubpredicates:preds];
46}

Helpers herein are