Any way to speed up this string heavy query?

var addressDuplicates = allBusinessAddressIds.AsEnumerable().AsParallel().
    Where(ba => currentBusinessAddress.AddressLine1.ApproximatelyEquals(ba.AddressLine1, options, tolerance)
                 && currentBusinessAddress.City.Equals(ba.City) 
                 && ba.CountyCode.Equals(currentBusinessAddress.CountyCode)
                 && currentBusinessAddress.Zip.Equals(ba.Zip)
                 && ba.BusinessAppId != appId).
    ToList();

The above query is designed to find duplicates based on the city, zip, county code, and fuzzy equal on the first line of the address. However, this query takes around 20 seconds to complete. That query is hit 6695 times with 6635 values. Any thoughts on speeding this up?

It is within a Parallel.ForEach loop as well for additional speed. My theory is that the string comparisons (all of those are strings, including the zip) is what is slowing down the query.

The allBusinessAddressIds is not an EF object, but rather a custom object I created. The currentBusinessAddress, however, is an EF object.

Adding AsEnumerable().AsParallel() had no impact on the search speed.

ApproximatelyEquals is from the FuzzyString library with the Tolerance set to Strong and the options that are being passed is simply UseLongestCommonSubstring.

So the question is a bit vague so my answer will be a bit vague as well. The thing is, you have the test case, you need to profile it and see what is slow, try changes and evaluate which change make it faster.

General tip: Parallelize only once and do it on the highest level that makes sense. So if you allready have a parallel foreach loop, do not use parallelism inside of that.

I suspect that your ApproximatelyEquals is a bit slow so the first change I'd try is to check zip code and city before comparing the addresses. Remember, the && operator short-circuits, and the fuzzy match means you'll get more true results from that comparison. By checking the faster and stricter items first, you can make the conditional expression more efficient, where the slower part of the expression only needs to run if and only if the others all pass.

And to reduce the number of calls, you can break the problem into smaller chunks. Use ToLookup() to group all items into buckets according to zip and cifty and then try to find duplicates inside of those chunks.

For the reasoning: Suppose you have 1000 entries that are evenly distributed across 40 combinations of zip/city.
Then this code:

for (int i = 0; i < 999; i++)
  for (int j = i+1; j < 1000; j++)
    if(compare(i, j))
      duplicates.Add(i, j);

Calls compare 500k times (give or take)
Whereas this:

var groups = items.ToLookup(...); // 40 groups
foreach(var group in groups)
  for (int i = 0; i < group.Count-1; i++)
    for (int j = i+1; j < group.Count; j++)
      if(compare(i, j))
        duplicates.Add(i, j);

Will call compare only 40 * 25 * 12 = 12k times.

The summary: If a part of the work is quadratic, many smaller chunks are better than all in one.