Finding objects in Core Data by array attribute, performantly in >10k elements

Question

Short:
I need to find core data objects by a key, which holds a unique immutable array (fixed length, but chosen at runtime) of arbitrary objects (for which not only element membership, but also element order determines uniqueness). NSManagedObject however forbids overriding [isEqual:]. Now what?

---

Long:
I have an entity (see diagram image for entity "…Link") in my Core Data model for which I have to guarantee uniqueness based on an attribute key ("tuple"). So far so good.

The entity's unique attribute however has to be an NSArray.
And to make things a bit more difficult I neither know the class type of the tuple's elements.
Nor do I know the tuple's element count. Well, actually the count is the same for every tuple (per core data context at least), but not known before the app runs.

There must only ever be one instance of my link entity with a given tuple.
And for obvious reason only ever one tuple instance with a given array of arbitrary objects.
Whereas two tuples are to be considered equal if [tuple_1 isEqual:tuple_n] returns YES. NSManagedObject forbids the overriding of [isEqual:] and [hash] though, otherwise things would be pretty much a piece of cake.

"…Tuple" objects are created together with their array of tokens (via a convenience method) and are immutable (and so is each "…Token" and its data attribute). (think of "…Tuple" as a "…Link"'s dictionary key.)

"…Tuple" implements "- (NSArray *)tokens;", which returnes a neatly ordered array of tokens, based on the "order" keys of "…TokenOrder". (Tuples are expected to contain at most 5 elements.)

I however expect to have tens of thousands (potentially even more in some edge cases) of "…Link" objects, which I have to (frequently) find based on their "tuple" attribute.

Sadly I couldn't find any article (let alone solution) for such a scenario in any literature or the web.

Any ideas?

A possible solution I've come up with so far would be:

1. Narrow amount of elements to compare by tuple by adding another attribute to "…Tuple" called "tupleHash", which is pre-calculated on object creation via: Snippet 1

2. Query with NSPredicate for objects of matching tupleHash (narrowing down the list of candidates quite a bit).

3. Find "…Link" featuring given tuple in narrowed candidate list by: Snippet 1

Snippet 1:

NSUInteger tupleHash = [[self class] hash];
for (id token in self.tokens) {
    tupleHash ^= [token.data hash];
}

Snippet 2:

__block NSArray *tupleTokens = someTokens;
NSArray *filteredEntries = [narrowedCandidates filteredArrayUsingPredicate:
  [NSPredicate predicateWithBlock: ^(id evaluatedObject, NSDictionary *bindings) {
    return [evaluatedObject.tuple.tokens isEqualToArray:tupleTokens];
}]];

(Sorry, markdown appears to oppose mixing of lists with code snippets.)

Good idea of or just insane?

Thanks in advance!

Answer 1

As recommended in a comment by Joe Blow I'm just gonna go with SQLite. Core Data simply appears to be the wrong tool here.

Benefits:

• Fast thanks to SQL's column indexing
• No object allocation/initialization on SELECT, prior to returning the results. (which Core Data would require for attribute checks)
• Easily query link tuples using JOINs.
• Easy use of SQLite's JOIN, GROUP BY, ORDER BY, etc
• Little to no wrapper code thanks to EGODatabase (FMDB-inspired SQLite Objective-C wrapper)

Answer 2

I strongly suggest that you calculate a hash for your objects and store it in your database. Your second snippet will seriously hurt performance, that's for sure.

Update:

You don't need to use the hash method of NSArray. To calculate the hash, you can perform a SHA1 or MD5 on the array values, concatenated. There are many algorithms for hashing, these are just two.

You can create a category for NSArray, say myHash to make the code reusable.