LINQ Search nvarchar(MAX) column extremely slow using .Contains()

Question

I have a .net core API and I am trying to search 4.4 million records using .Contains(). This is obviously extremely slow - 26 seconds. I am just querying one column which is the name of the record. How is this problem generally solved when dealing with millions of records?

I have never worked with millions of records before so apart from the obvious altering of the .Select and .Take, I haven't tried anything too drastic. I have spent many hours on this though.

The other filters included in the .Where are only used when a user chooses to use them on the front end - The real problem is just searching by CompanyName.

Note; I am using .ToArray() when returning the results.

I have indexes in the database but cannot add one for CompanyName as it is Nvarchar(MAX).

I have also looked at the execution plan and it doesn't really show anything out of the ordinary.

query = _context.Companies.Where(
    c => c.CompanyName.Contains(paging.SearchCriteria.companyNameFilter.ToUpper())
         && c.CompanyNumber.StartsWith(
                string.IsNullOrEmpty(paging.SearchCriteria.companyNumberFilter)
                ? paging.SearchCriteria.companyNumberFilter.ToUpper()
                : ""
            )
         && c.IncorporationDate > paging.SearchCriteria.companyIncorperatedGreaterFilter
         && c.IncorporationDate < paging.SearchCriteria.companyIncorperatedLessThanFilter
    )
    .Select(x => new Company() {
                    CompanyName = x.CompanyName,
                    IncorporationDate = x.IncorporationDate,
                    CompanyNumber = x.CompanyNumber
                }
    )
    .Take(10);

I expect the query to take around 1 / 2 seconds as when I execute a like query in ssms it take about 1 / 2 seconds.

Here is the code being submitted to DB:

Microsoft.EntityFrameworkCore.Database.Command: Information: Executing DbCommand [Parameters=[@__p_4='?' (DbType = Int32), @__ToUpper_0='?' (Size = 4000), @__p_1='?' (Size = 4000), @__paging_SearchCriteria_companyIncorperatedGreaterFilter_2='?' (DbType = DateTime2), @__paging_SearchCriteria_companyIncorperatedLessThanFilter_3='?' (DbType = DateTime2), @__p_5='?' (DbType = Int32)], CommandType='Text', CommandTimeout='30']
SELECT [t].[CompanyName], [t].[IncorporationDate], [t].[CompanyNumber]
FROM (
    SELECT TOP(@__p_4) [c].[CompanyName], [c].[IncorporationDate], [c].[CompanyNumber], [c].[ID]
    FROM [Companies] AS [c]
    WHERE (((((@__ToUpper_0 = N'') AND @__ToUpper_0 IS NOT NULL) OR (CHARINDEX(@__ToUpper_0, [c].[CompanyName]) > 0)) AND (((@__p_1 = N'') AND @__p_1 IS NOT NULL) OR ([c].[CompanyNumber] IS NOT NULL AND (@__p_1 IS NOT NULL AND (([c].[CompanyNumber] LIKE [c].[CompanyNumber] + N'%') AND (((LEFT([c].[CompanyNumber], LEN(@__p_1)) = @__p_1) AND (LEFT([c].[CompanyNumber], LEN(@__p_1)) IS NOT NULL AND @__p_1 IS NOT NULL)) OR (LEFT([c].[CompanyNumber], LEN(@__p_1)) IS NULL AND @__p_1 IS NULL))))))) AND ([c].[IncorporationDate] > @__paging_SearchCriteria_companyIncorperatedGreaterFilter_2)) AND ([c].[IncorporationDate] < @__paging_SearchCriteria_companyIncorperatedLessThanFilter_3)
) AS [t]
ORDER BY [t].[IncorporationDate] DESC
OFFSET @__p_5 ROWS FETCH NEXT @__p_4 ROWS ONLY

SOLVED! With the help of both answers!

In the end as suggested, I tried full-text searching which was lightening fast but compromised accuracy of search results. In order to filter those results more accurately, I used .Contains on the query after applying the full-text search.

Here is the code that works. Hopefully this helps others.

//query = _context.Companies //.Where(c => c.CompanyName.StartsWith(paging.SearchCriteria.companyNameFilter.ToUpper()) //&& c.CompanyNumber.StartsWith(string.IsNullOrEmpty(paging.SearchCriteria.companyNumberFilter) ? paging.SearchCriteria.companyNumberFilter.ToUpper() : "") //&& c.IncorporationDate > paging.SearchCriteria.companyIncorperatedGreaterFilter && c.IncorporationDate < paging.SearchCriteria.companyIncorperatedLessThanFilter) //.Select(x => new Company() { CompanyName = x.CompanyName, IncorporationDate = x.IncorporationDate, CompanyNumber = x.CompanyNumber }).Take(10);

            query = _context.Companies.Where(c => EF.Functions.FreeText(c.CompanyName, paging.SearchCriteria.companyNameFilter.ToUpper()));

            query = query.Where(x => x.CompanyName.Contains(paging.SearchCriteria.companyNameFilter.ToUpper()));

(I temporarily excluded the other filters for simplicity)

Answer 1

Welcome to stack overflow. It looks like you are suffering from at least one of these three problems in your code and your architecture.

First: indexing

You've mentioned that this cannot be indexed but there is support in SQL Server for full text indexing at the very least.

.Contains

This method isn't exactly suitable for the size of operation you're performing. If possible, perhaps as a last resort, consider moving to a parameterized query. For now, however, it looks like you want to keep your business logic in the .net code rather than spreading it into SQL and that's a worthy plan.

c.IncorporationDate

Date comparison can be a little costly in SQL Server. Once you're dealing with so many millions of rows you might get a lot of performance benefit from correctly partitioned tables and indexes.

Consider whether or not these rows can change at all. Something named IncoporationDate sounds like it definitely should not be changed. I suspect you may want to leverage that after reading the rest of these.

Answer 2

When you run the query in SSMS, it's probably cached for subsequent calls. The original query probably took similar time as the EF query. That said, there are disadvantages to parametrised queries - while you can better reuse execution plans in a parametrised query, this also means that the execution plan isn't necessarily the best for the actual query you're trying to run right now.

For example, if you specify a CompanyNumber (which is easy to find in an index due to the StartsWith), you can filter the data first by CompanyNumber, thus making the name search trivial (I assume CompanyNumber is unique, so either you get 0 records, or you get the one you get by CompanyNumber). This might not be possible for the parametrised query, if its execution plan was optimized for looking up by name.

But in the end, Contains is a performance killer. It needs to read every single byte of data in your table's CompanyName field; which usually means it has to read every single row, and process much of its data. Searching by a substring looks deceptively simple, but always carries heavy penalties - its complexity is linear with respect to data size.

One option is to find a way to avoid the Contains. Users often ask for features they don't actually need. StartsWith might work just as well for most of the cases. But that's a business decision, of course.

Another option would be finding a way to reduce the query as much as possible before you apply the Contains filter - if you only allow searching for company name with other filters that narrow the search down, you can save the DB server a lot of work. This may be tricky, and can sometimes collide with the execution plan collission issue - you might want to add some way to avoid having the same execution plan for two queries that are wildly different; an easy way in EF would be to build the query up dynamically, rather than trying for one expression:

var query = _context.Companies;
if (!string.IsNullOrEmpty(paging.SearchCriteria.companyNameFilter))
  query = query.Where(c => c.CompanyName.Contains(paging.SearchCriteria.companyNameFilter));
if (!string.IsNullOrEmpty(paging.SearchCriteria.companyNumberFilter))
  query = query.Where(c => c.CompanyNumber.StartsWith(paging.SearchCriteria.companyNumberFilter));

// etc. for the rest of the query

This means that you actually have multiple parametrised queries that can each have their own execution plan, more in line with what the query actually does. For some extreme cases, it might also be worthwhile to completely prevent execution plan caching (this is often useful in reports).

The final option is using full-text search. You can find plenty of tutorials on how to make this work. This works essentially by splitting the unformatted string data to individual words or phrases, and indexing those. This means that a search for "hello world" doesn't necessarily return all the records that have "hello world" in the name, and it might also return records that have something else than "hello world" in the name. Think Google Search rather than Contains. This can often be a great method for human-written text, but it can be very confusing for the user who doesn't understand why you'd return search results that are completely different from what he was searching for. It also often doesn't work well if you need to do partial searches (e.g. searching for "Computer" might return "Computer, Inc.", but searching for "Comp" might return nothing).

The first option is likely the fastest, and closest to what the users would expect. It has the weakness that it can't search in the middle, though. The second option is the most correct, and might make your query substantially faster, especially in the most common cases with good statistics. The third option is probably about as fast as the first one, but can be tricky to setup properly, and can be confusing for your users. It does also provide you with more powerful ways to query the text data (e.g. using wildcards).