iPhone: Speeding up a search that's polling 17,000 Core Data objects

Question

I have a class that conforms to UISearchDisplayDelegate and contains a UISearchBar. This view is responsible for allowing the user to poll a store of about 17,000 objects that are currently managed by Core Data. Everytime the user types in a character, I created an instance of a SearchOperation (subclasses NSOperation) that queries Core Data to find results that might match the search. The code in the search controller looks something like:

- (void)filterContentForSearchText:(NSString*)searchText scope:(NSString*)scope
{
 // Update the filtered array based on the search text and scope in a secondary thread 
 if ([searchText length] < 3) {
  [filteredList removeAllObjects]; // First clear the filtered array.
  [self setFilteredList:NULL];
  [self.tableView reloadData];
     return;
 }
    NSDictionary *searchdict = [NSDictionary dictionaryWithObjectsAndKeys:scope, @"scope", searchText, @"searchText", nil];
 [aSearchQueue cancelAllOperations];
 SearchOperation *searchOp = [[SearchOperation alloc] initWithDelegate:self dataDict:searchdict];
 [aSearchQueue addOperation:searchOp];
}

And my search is rather straight forward. SearchOperation is a subclass of NSOperation. I overwrote the main method with the following code:

- (void)main 
{ 
 if ([self isCancelled]) {
  return;
 }

 NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
 NSEntityDescription *entity = 
 [NSEntityDescription entityForName:@"MyEntity" inManagedObjectContext:managedObjectContext];
 NSFetchRequest *fetchRequest = [[NSFetchRequest alloc] init];
 [fetchRequest setEntity:entity]; 
 NSPredicate *predicate = NULL;
    predicate = [NSPredicate predicateWithFormat:@"(someattr contains[cd] %@)", searchText];
 [fetchRequest setPredicate:predicate];
 NSError *error = NULL;
 NSArray *fetchResults = [managedObjectContext executeFetchRequest:fetchRequest error:&error];
 [fetchRequest release];

 if (self.delegate != nil)
  [self.delegate didFinishSearching:fetchResults];

 [pool drain];
}

This code works, but it has several issues.

• It's slow. Even though I have the search happening in a separate thread other than the UI thread, querying 17,000 objects is clearly not optimal.

• If I'm not careful, crashes can happen. I set the max concurrent searches in my NSOperationQueue to 1 to avoid this.

What else can I do to make this search faster? I think preloading all 17,000 objects into memory might be risky. There has to be a smarter way to conduct this search to give results back to the user faster.

Answer 1

Organise the data as a tree? That way you can easily check if the next letter along works ...

Edit: thinking about this more. If you set up a tree that has an array of pointers that is every supported input character you can easily jump to the right place in the array at that point in the tree to see whether there is another level to the tree there. It'll cost ya a fair bit more in memory usage but will be very quick ...

A further edit: If you want to save a tonne of memory then you could easily set up a file that would be incredibly quick to scan through. If you take into account the fact that at every level node in the tree there is a fixed number of possible items then you can easily seek very quickly to the location you want in the file. This is O(1) for each character you enter. Therefore you have a search in O(n) for everything the user types.

Answer 2

What type of persistent store are you using? SQLite or Binary?

Assuming SQLite, are you indexing the columns that you are searching?

I am guessing you are initially displaying the data using a NSFetchedResultsController right? If not, why not? The cache in the NSFetchedResultsController will help greatly with this issue.

If you are using a NSFetchedResultsController then change your search so that instead of hitting the disk each time, hit the data that is already in memory. By accessing the array of [myFetchController fetchedObjects] you can use a NSPredicate against it to filter your results. That is the first letter pressed.

From there, you take your already filtered array and filter it again each time a new key is pressed. This will cause the search to speed up as you narrow the search.

UPDATE

In that case your initial search is going to be slow. BUT, once you have the initial search from the first character entered you can then filter against that array as opposed to going back out to disk and that should be nearly instantaneous.

You can improve your initial search by:

• Index the columns that are searched
• If extended ascii is an issue create a flattened text column to search against and index that.