Optimize the performance of `IN` operator for indexed properties

[nalexn]

Problem

The issue was first reported over 6 years ago on stack overflow, but is still actual for latest realm versions.

When you use the predicate key IN %@ and supply a collection with a substantially large number of values (over a thousand), the filtering happens SO slowly that doing filtering outside the query element-by-element outperforms it by 50x, despite being inefficient on its own.

let values = Set(["value_1", "value_2", ..., "value_40000"])

// 1. Complete query with IN operator: over 25secs

let results = realm.objects(MyObject.self)
       .filter("key IN %@", values)
       // same for new syntax:
       // .where { $0.key.in(values) }

// 2. Filter outside realm: under 0.45secs

let results = realm.objects(MyObject.self)
      .filter { values.contains($0.key) }

---

The use case when this is needed:
We run a complex query on a large data set, which is done on a background thread so the UI isn't blocked. It passes a set of resulting objects' ids to the main thread, where we can quickly query objects by ids without blocking the UI.

Solution

It looks like the operator <key> IN <collection> is translated into <key> == value_1 OR <key> == value_2 OR ..., which works well on small sets of values, but quickly degrades when the collection is large enough.

I hope there is a way to optimize this part of the algorithm, at least when the supplied collection supports O(1) element presence check, like for Set<String>.

Alternatives

There is really no alternative to this API other than hacks like supplying a subset of the collection for values, or filtering manually after the query

How important is this improvement for you?

Would be a major improvement

Feature would mainly be used with

Local Database only

[sync-by-unito]

➤ PM Bot commented:

Jira ticket: RCOCOA-2443

[Jaycyn]

I am having difficulty reproducing this issue.

We created a PersonClass with a number of properties including a key property of type String

class PersonClass: Object {
    @Persisted(primaryKey: true) var _id: ObjectId
    @Persisted var key = ""
     ....

We then have a function that creates 100,000 PersonClass with the key property populated with "person" + an index from 0 to 99,999. e.g. the Realm file will contain PersonClass objects with key values of person0, person1, person2....person99999.

We then use the code posted in your report, to query the key property for a random selection of 50,000 PersonClass objects. So values will be 50,000 array objects: [person12, person87453, person4533...]

func handleButton1() {
    guard let realm = gGetRealm() else { return }

    let num = 49999
    var values = [String]()
    for _ in 0...num {
        let randomNum = (0...num).randomElement() ?? num
        let v = "person\(randomNum)"
        values.append(v)
    }

    print("performing query")
    let startTime = Date()
    let results = realm.objects(PersonClass.self).where { $0.key.in(values) }
    print("Load completed of \(results.count)")
    let elapsed = Date().timeIntervalSince(startTime)
    print("elapsed time of \(elapsed)")
}

and the output to console is:

Load completed of 31621
elapsed time of 1.6968810558319092

In the above test, an in query using 50,000 values was performed on 100,000 objects in 0.096 seconds.

[nalexn]

Ok, I'll see if I can hand you a better code snippet that repros this issue

[nalexn]

@Jaycyn Ok, I found what was missing - the key property has to be indexed:

class PersonClass: Object {
    @Persisted(primaryKey: true) var _id: ObjectId
    @Persisted(indexed: true) var key = ""
}

this alone increases the query time from 0.24 seconds without index to 12.3 seconds when indexed.

But, if you add another indexed string property and query with && like so:

class PersonClass: Object {
    @Persisted(primaryKey: true) var _id: ObjectId
    @Persisted(indexed: true) var key1 = ""
    @Persisted(indexed: true) var key2 = ""
}

realm.objects(PersonClass.self).where {
      $0.key1.in(values) && $0.key2 == "<some_value>"
}

... the query takes several minutes to complete!

[Jaycyn]

The code I provided above has no indexing at all and as you can see completes in approximately 1.5s.

While describing the issue is important, being able to duplicate it is equally important - that will help eliminate other issues; environmental, additional code running etc.

Can you provide a minimal, duplicatable example?

[nalexn]

@Jaycyn that's the duplicatable example - add indexing to your sample and the performance would be much worse

[Jaycyn]

Hmm. I changed the key to being indexed

@Persisted(indexed: true) var key = ""

and the result is still an avg of 1.5s

[nalexn]

Ok, I'll just copy-paste the entire sample so we don't miss anything:

// Object definition
class PersonClass: Object {
    @Persisted(primaryKey: true) var _id: ObjectId
    @Persisted(indexed: true) var key1 = ""
    @Persisted(indexed: true) var key2 = ""
}

let num = 49999

// Object generation
let objects = (0...num).map { index in
    let obj = PersonClass()
    obj._id = .generate()
    obj.key1 = "person\(index)"
    obj.key2 = "salt\(index % 3)"
    return obj
}
try! realm.write {
    realm.add(objects, update: .all)
}

var values = [String]()
for _ in 0...num {
    let randomNum = (0...num).randomElement() ?? num
    let v = "person\(randomNum)"
    values.append(v)
}

// Testing the query performance
if #available(iOS 16.0, *) {
    let elapsedTime = ContinuousClock().measure {
        print("performing query")
        let results = realm.objects(PersonClass.self).where {
            $0.key1.in(values) && $0.key2 == "salt0"
        }
        let total = realm.objects(PersonClass.self).count
        print("Load completed of \(results.count) objects (\(total) total)")
    }
    print("\(elapsedTime)")
}

[Jaycyn]

Well, that's a very odd thing; I was able to duplicate the issue using that code.

A few observations and more info:

The issue only occurs when the object has two indexed properties and a query is performed using .where on one property using .in, and the query also includes && on the other property querying for a specific string.

In other words, the query works perfect if it's one OR the other

let results = realm.objects(PersonClass.self).where { $0.key1.in(values) } //works fine: 1.5s average

let results = realm.objects(PersonClass.self).where { $0.key2 == "salt0"  } //works fine: .03s average

let results = realm.objects(PersonClass.self).where { $0.key1.in(values) && $0.key2 == "salt0" } //does NOT work fine

Even splitting it up and performing two separate queries does not work

let results1 = realm.objects(PersonClass.self).where { $0.key1.in(values)  } //does not work fine
let results2 = results1.where { $0.key2 = "salt0" }

Note after the fact: this is not resolved to "separate queries" Realm combines them into one, so it's just one NSPredicate

[Jaycyn]

Update that due to realm being lazy-loading, the query is not actually executed until the print statement, and the issue is duplicated leaving that in so this original post was inaccurate and edited.

--- below is incorrect ---
Take your code and comment out the print statement and run it

        let elapsedTime = ContinuousClock().measure {
            print("performing query")
            let results = realm.objects(PersonClass.self).where { $0.key.in(values) && $0.key2 == "salt0" }
            let total = realm.objects(PersonClass.self).count
                   //print("Load completed of \(results.count) objects (\(total) total)")  //commented
        }
        print("\(elapsedTime)")

This is the issue

print(results.count)

This code now works correctly

print("performing query")
let startTime = Date()
let results = realm.objects(PersonClass.self).where { $0.key.in(values) && $0.key2 == "salt0" }
let elapsed = Date().timeIntervalSince(startTime)
print("elapsed time of \(elapsed)")

performing query
elapsed time of 0.11012506484985352