Search in grid is locking the UI in the cell merging demo

[kdinev]

Description

When I try to search for values in the grid cell merging demo, the UI locks.

• igniteui-angular version: 21.1.x
• browser: Edge

Steps to reproduce

1. Open gridCellMerging demo
2. Search for a

Result

The UI locks.

Expected result

The UI shouldn't lock. There should be a loading indicator and the app should be interactive.

Attachments

Attach a sample if available, and screenshots, if applicable.

[mddragnev]

This is a known issue when we have a lot of data, i.e 600k records in this sample. This was researched previously and we can look at it from two sides:

1. We show an implementation with a search input in the samples. This input could be throttled so that it does not call the API on each keydown. This is something that should be done on a sample level.
2. When searching internally the grid creates a collection that contains all the records that match the specific search query. This collection is generated on each call of the API (more specific on each change of the search text). Currently, it goes through every record from the data and every column that has searching enabled resulting in O(N × C × L) time (N- number of records, C- number of columns, L - length of the string value) on each API call. This is inefficient.

Possible solutions:

1. Using prefix tree (Trie) - This is a common data strcture that would have been awesome to use. However, it only works when working with prefixes. IgniteUI search feature works with substrings, so this is not suitable.
2. Using suffix tree/ suffix automaton/ suffix array - At first these sound like a better opportunity. However, building this kind of data structure over 1 million records with multiple fields with multiple string values takes a lot of time and space since we need to keep track of exactly which record and which field is matched over the search query. Those strcutures are optimized for searching in one giant document.
3. Inverted index - (substring -> list of record ids) very fast searches but since we allow any substring search the time needed to process every substring of every field in the data explodes.
4. N-gram index - This is more practical. Instead of storing all substring, we store fixed-length pieces (2 or 3 char substrings) and then build an inverted index over these ngrams. However, building this takes too much time as well. There is also another downside - this works well if we search strings with 2 or more letters. However, for single char searches we must fallback to some other method of searching. (I have tested this and it takes around 25 seconds to build such ngram index over 1 million records with 12 columns)
5. Data preprocessing - First, we generate a cache containing all field values of a single record concatenated without those fields that are not searchable. This way we can do a quick linear scan of the cache against the search query and, perhaps, reduce the records count. Second, do another linear search over the reduced data records to extract the exact number of occurrences.
6. Data preprocessing version 2 - Almost the same, but instead storing only the concatenated values in the cache, we store the formatted values as well. This slows down the cache building which is happening the first time the search API is called, but gives a huge performance boost on the following searches.

However, approches 5 and 6 have higher memory consumption for building this cache - couple of hundreds of MB. We talked about it with @rkaraivanov and decided that it is not worth.
From what I remember using web workers was not possible either.