Implementing Fuzzy Search with OData

[starshinata]

Hi everyone,

Our team is currently working on a project where the client requirement is to implement fuzzy search. However, we have noticed that OData does not support fuzzy search out of the box.

We would like to inquire if there is a recommended approach to achieve this functionality using OData.

We are looking at implementing a custom filter option such as: odata/profiles?$filter=fuzzy(FirstName, 'John') where we can provide a custom implementation for this filter, using a third-party library, in a way that integrates with OData.

However, we are open to other suggestions as well.

Could you please advise us on the best way to approach this? Any guidance, examples, or references to relevant documentation would be greatly appreciated.

Thank you for your assistance.

[julealgon]

I believe the best extension point to add support for this in odata would be to use the built-in $search query. You can implement anything you want behind that operation.

• $compute and $search in ASP.NET Core OData 8

I'd either go with that, or as a fallback I'd write a custom bound action on the entityset.

[starshinata]

Thanks a lot for the help, @julealgon!

[Mhirji]

@starshinata , based on the example you provided in terms of what you are trying to achieve, unless you require a percentage on the probability of the match, you could also use the "contains" operator. This would translate to a like in SQL.

[mikepizzo]

Note that OASIS is considering adding a new search function that could be used in $filter. The only advantage of this over $search is that you could combine the fuzzy search in more ways $search, which is always AND'd with any $filter.

Would such a function, if introduced, be useful to folks?

[marabooy]

@starshinata Do the two workarounds for $search and $filter with contains work for you? Also, please review Mike's post to see if the newly proposed search function suits your case.

[julealgon]

@mikepizzo

Note that OASIS is considering adding a new search function that could be used in $filter. The only advantage of this over $search is that you could combine the fuzzy search in more ways $search, which is always AND'd with any $filter.

Would such a function, if introduced, be useful to folks?

Interesting suggestion. I assume the more specific search function (the one inside $filter) would then also be implementation-dependent, like the external one is today.

I do think it makes sense for the added flexibility it gives.

[Luk164]

I have tried my hand at creating a more powerful search powered by pg_trgm extension in PostgreSQL.

For now it only handles one entity but it should be expandable for others, it defaults to basic ID comparison. (WIP)

It automatically searches for all string and Guid properties and uses them to create a score. Elements with score above threshold in any parameter are returned.

Unfortunately I have hit a limitation with this approach because I cannot sort the elemets by this score. Ideally I would want 0 filtering and just add score to results, then sort by score and return the highest with combination with $top and $skip for pagination, but that seems impossible with current implementation.

I also have a stackoverflow question already open: https://stackoverflow.com/questions/79383858/implementing-a-dynamic-search-using-odata-in-asp-net

This is my experimental implementation:

public class ExperimentalSearchBinder : QueryBinder, ISearchBinder
{
    public Expression BindSearch(SearchClause searchClause, QueryBinderContext context)
    {
        var parameter = Expression.Parameter(context.ElementClrType, "p");

        if (searchClause.Expression is not SearchTermNode node) throw new Exception("Only simple search clauses are allowed");

        switch (context.ElementClrType)
        {
            case { } clrType when clrType == typeof(ComponentModel):
                var properties = typeof(ComponentModel).GetProperties()
                    .Where(p => p.PropertyType == typeof(string) || p.PropertyType == typeof(Guid))
                    .ToList();

                Expression? combinedExpression = null;

                foreach (var propertyInfo in properties)
                {
                    Expression property = Expression.Property(parameter, propertyInfo.Name);
                    if (propertyInfo.PropertyType == typeof(Guid))
                    {
                        property = Expression.Call(property, typeof(Guid).GetMethod("ToString", Type.EmptyTypes)!);
                    }
                    var method = typeof(DatabaseContext).GetMethod(nameof(DatabaseContext.Similarity), [typeof(string), typeof(string)]);

                    if (method is null)
                    {
                        throw new MissingMethodException($"Method not found: {nameof(DatabaseContext.Similarity)}");
                    }

                    var searchTerm = Expression.Constant(node.Text);
                    var similarityCall = Expression.Call(method, property, searchTerm);
                    var comparison = Expression.GreaterThanOrEqual(similarityCall, Expression.Constant(0.1));

                    combinedExpression = combinedExpression == null ? comparison : Expression.OrElse(combinedExpression, comparison);
                }

                if (combinedExpression is null)
                {
                    throw new Exception("Failed to build combinedExpression");
                }

                return Expression.Lambda<Func<ComponentModel, bool>>(combinedExpression, parameter);

            default:
                //Default simply tries to match ID
                //TODO: Make a better default implementation
                var defaultProperty = Expression.Property(parameter, "Id");
                var defaultSearchTerm = Expression.Constant(node.Text);
                var defaultComparison = Expression.Equal(defaultProperty, defaultSearchTerm);

                return Expression.Lambda(defaultComparison, parameter);
        }
    }
}