Core Data search optimization

I'm working on a search feature in one of my Core Data based apps and I'm trying to gather everyone's tips on search optimization to get it as fast as I possibly can. The search needs to be fast enough that it can deliver near-instantaneous results for database of 20,000+ objects.

What I've done so far (as far as optimization goes)

• Implemented the technique shown in WWDC 2010 session 137, creating a keyword entity and creating a to-many relationship from my main object entities to it. The keyword entity's name attribute is indexed, and keywords are created during the initial import procedure by splitting apart relevant strings in the main entities and normalizing them (stripped of case and diacritics)
• Using >= and < binary comparators instead of BEGINSWITH, e开发者_C百科tc. My predicate format is:

SUBQUERY(keywords, $keyword, ($keyword.name >= $LB) AND ($keyword.name < $UB)).@count != 0

Where $LB is the lower bounds string and $UB is upper bounds. I create a compound AND predicate using this format and the array of search terms.

Right now, I'm executing a fetch once (when the user types the first letter) using a fetch batch size of about 20, and then narrowing down the search results using NSArray's -filteredArrayUsingPredicate method as they continue typing. I also prefetch the keywords relationship because this is used to filter. The part that takes up the most time, obviously, is the initial fetch. There's a noticeable delay of ~1-2s on a library of around 15,000 objects. Time profiling shows that it is indeed the fetch that is causing the delay:

http://cl.ly/3a1b2022452M2V323f2H

One other thing thats worth noting is that I have to fetch multiple entities for the results. All of the entities have a ranking attribute, but I can't fetch more than one at once so I'm forced to fetch them separately, combine them into a single array, and then sort manually via -sortedArrayUsingDescriptors.

Any tips on how to speed this up would be greatly appreciated.

EDIT: Based on @ImHuntingWabbits' suggestions:

After adding a KeywordFirstChar entity, my data model (simplified) would look like this:

Now, the questions is how would I write a predicate for the Car entity that fetches based on KeywordFirstChar? The only thing I can think of would be this:

SUBQUERY(keywords, $keyword, $keyword.firstChar.char == %@) where %@ is the character to search for, but I don't know how this would be much more efficient considering that it still has to enumerate over keywords, unless I misinterpreted the suggestions.

Your query is highly optimized, I think you've already taken a good number of steps. As far as the first character press, you're doin it wrong.

You're still scanning 15k records for the first character hit, and likely matching a great number of them.

You could further optimize it by indexing your keyword index, creating two new entities:

• KeywordFirstChar
• KeywordFirstTwoChars

Both with a to-many relationship to the keywords they point to.

if (searchPredicate.length == 1) {
    //search on KeywordFirstChar
} else if (searchPredicate.length == 2) {
    //search on KeywordFirstTwoChars
} else {
    //search on keyword
}

This way your table scan will go over max 26 and 676 rows respectively, which should be rather trivial. Just make sure the relationship is in the prefetched relationship key paths on the fetch request so you indeed get the data off disk.

Edit (Object Retrieval):

You can follow the relationship key path, so it would be something like this:

 [fetchRequest setRelationshipKeyPathsForPrefetching:[NSArray arrayWithObject:@"keyword.sourceObject"]];

Where keyword is the relationship to the Keyword entity, and sourceObject is the object that you want to eventually retrieve.

Edit (Predicate):

The predicate is essentially the same, just change the names to match the new entity (name might not map to name, instead firstChar or some other property).