How to handle searching Large Lists in Flutter?

Question

I want to ask how I should handle a large list in Flutter. My app gets super slow when I am at a data item that is really deep in the list which I am searching. My list is 70,000+ objects of a data structure large.

The following is how I am "Searching" the list.

Future<Iterable<SomeDataStruct>> _getAllData() async {
    return allData.where((a) => (a.dataTitle.toLowerCase().contains(querySearch.toLowerCase().trim())));
}

Building the list using a ListView.builder inside of a FutureBuilder.

When I search and a result or results from deep inside the list are populated the app is extremely slow to the point where I click a list item and it takes few seconds before it does its onTap. And if I need to change the search query it takes time for the soft keyboard to come back up after I click on the TextField.

Where am I making a mistake or handling this wrong, what should I do to have my huge list searchable without making app unbearable.

EDIT: How I made it not slow down the app after change to code. Is this correct?

String tempQuery;
List<SomeDataStruct> searchResults = [];
Future<List<SomeDataStruct>> _getAllData() async {
    if(querySearch!=tempQuery) {
      tempQuery = querySearch;
      searchResults = allData.where((a) => (a.dataTitle.toLowerCase().contains(querySearch.toLowerCase().trim()))).toList();
    }
    return searchResults;
  }

Answer 1

Contains is expensive

Contains-queries are expensive, because every entry needs to be checked at every position (up to value.length - searchTerm.length) if the search term can be found.

Limiting search support to the beginning of the string would improve performance a lot already. In addition you could create helper data-structures where the whole list of values is split into parts with the same character at the beginning. If the chunks are still too big another level could be added for the 2nd character. The lookup would be fast because there are only a limited number of characters.

Using a database might take off some programming work (maintaining indexes). A database like SQLite could be used with indexes specialized to your kind of queries.

Split into smaller chunks of work to allow the framework to do its work

If you can't limit to "beginning of string"-search, you could still split the data structure into smaller chunks and invoke search for each chunk async. This way the UI gets "some air to breath" to re-render the UI before the next chunk is searched. The search result would be updated incrementally.

Move work off the UI thread

Another way would be to start up another isolate and do the search there. Another isolate can run on another CPU (core) and therefore would not block the UI thread when searching. This way it wouldn't be necessary to split into chunks. It might still be advantageous though to incrementally update the UI instead of keeping the user waiting until the whole search result becomes available.

See also

• https://api.dartlang.org/stable/2.2.0/dart-isolate/dart-isolate-library.html
• https://pub.dartlang.org/packages/isolate
• https://codingwithjoe.com/dart-fundamentals-isolates/

Caching

It might also help improve performance to keep search results in memory. For example if the user enters foo and then presses backspace then you could reuse the search result for fo that you previously calculated already, but that only helps in some cases.

Measuring

Another important point of course is to do benchmarking. Whatever you try to improve performance, create benchmarks to learn what measures have what effect and if it's worth it. You'll learn a lot about your scenario, your data, Dart, ..., and this will allow you to make good decisions.