findAll() performance issue on RealmList queries with @Index'ed fields

[jpmcosta]

Goal

I'm developing and Android application and I initially run into this issue while trying to optimize the search time when querying for objects (Item objects). I was initially running queries using the sort() method, which had some performance issues in large databases. Trying to solve this issue, I created multiple ItemPage objects to hold a list of Item objects in their intended order. That way I would be able to search for Item objects faster and in a more granular manner (which allowed me to update the UI at a faster rate).

I noticed some inconsistencies (and issues) regarding the performance of findAll() when querying the different ItemPage's RealmList objects and created a test project to reproduce that issue.

Actual Results

When querying for objects in RealmList, it seems that:

1. calls to findAll() are slower if the fields being queried are @Indexed (might be intended)
2. calls to findAll() become really slow if the objects in RealmList are also placed out of their natural order

Steps & Code to Reproduce

I have created a simplified Android project to reproduce the issue: https://github.com/jpmcosta/RealmTestProject/tree/98d3bbb24f0c289f1e5d7c987541248ee8a9101c

Below are the general ideas of the project. They are bit difficult to explain, but it should be easy to understand once you run the project.

• Realm objects: Item, SubItem, ItemPage

public class Item extends RealmObject {

    @PrimaryKey
    public Long id;

    public SubItem subItem = null;

    public Boolean isBookmarked = false;

    @Index // Removing this index seems to speed up findAll().
    public long removedAt = NO_TIME;

    @LinkingObjects("items")
    public final RealmResults<ItemPage> itemPages = null;
}

public class ItemPage extends RealmObject {

    @PrimaryKey
    public Long id;

    public RealmList<Item> items;
}

public class SubItem extends RealmObject {

    @PrimaryKey
    public Long id;

    @Index
    public String name = STRING_EMPTY;
}

• there are 50_000 Item objects
• each Item holds a single SubItem
• the Item's name is held by its SubItem
• there are 10 ItemPage objects
• each ItemPage holds 5_000 Item objects
• there are two main actions in the project: querying and moving
• querying (bottom fab) will query all ItemPages.items for items containing "A" and not removed (removedAt != NO_TIME); it will then toggle their Item.isBookmarked flag
• moving (upper fab) will move the last Item containing "A" to a different ItemPage (adding it to the middle of ItemPage.items)

Steps to reproduce:

• the first time you run the application run some queries by clicking on the bottom fab
  • it should show that all findAll() calls have similar times (around 20ms)
• after running some queries start moving the item by clicking on the top fab
• every time you click on the top fab, the item will be moved to a different ItemPage
• if you run the queries again, by clicking on the bottom fab, you will notice that one of the findAll() calls is a lot slower than the others (varies from 115ms, for ItemPage$0, to 1100ms!, for ItemPage$9); the slower ItemPage is the ItemPage with the out of order Item

Extra:

• if you remove @Index from Item.removedAt you stop noticing any issues
  • findAll() times decrease to ~8ms for most queries
  • there is no penalty when you move the Item
• I was initially writing this issue as a "query" issue; however, I realized that findAll() might be lazy or not depending on whether or not the fields are @Indexed; still, I feel this is an issue, because having to wait 1100ms for a call that usually takes 20ms should not be normal

Version of Realm and tooling

Realm version: 5.14.0

Realm Sync feature enabled: No

Android Studio version: 3.5

Android Build Tools version: 28.0.3

Gradle version: 5.4.1

[realm-probot[bot]]

Hey - looks like you forgot to add a T-* label - could you please add one (if you have access to add labels)?

[finnschiermer]

Isn't it just the sorting taking time here, and not the querying?

[jpmcosta]

I believe that there's no sorting involved in this issue. This is the transaction at hand:

final RealmResults<Item> items = itemPage.items.where()
        .contains("subItem.name", "A")
        .equalTo("removedAt", NO_TIME)
        .findAll();
for (Item item : items) {
    item.isBookmarked = !item.isBookmarked;
}

An Item is moved between to different ItemPage.items lists. If (and only if) its removedAt property is indexed, there's a performance penalty depending on which ItemPage holds it. The performance decreases as ItemPage.items ids are more distant from the original item.id.

[finnschiermer]

Sorry, got mislead by @beczesz comment above which mentions sorting.

[beczesz]

Sorry, got mislead by @beczesz comment above which mentions sorting.

Indeed sorry about that, I just saw that my response was misleading, removed it.