LINQ to Entities search multiple columns, order by total weight of the matches columns

Question

I am implementing a search algorithm and I need to way to search the database over multiple columns. The algorithm will then return a "best match". For example, let's say I have an entity:

public class Person{
    public string Name { get; set; }
    public int Age { get; set; }
    public string Title { get; set; }
}

My search method needs to accept searching over name, age, and title, with all being optional where any combination is possible. All fields have a weight that I will fine-tune in my code for better results. Results should be ordered by a score where score is:

matchedColumn1Weight + matchedColumn2Weight + ... + matchedColumnNWeight

Let's just assume I have this table called people:

Name     Age    Title
-------------------------
Alice    20     Manager
Bob      21     Friend
James    20     Friend
Will     22     Manager

Let's assume Name has a weight of 1, Age a weight of 1 and Title a weight of 1.1. If I search with fields name = null, age = 20, title = Friend, it should first return James and then Bob, then Alice, and then Will.

How do I implement such functionality in LINQ-to-Entities? In other words, I need a LINQ where I query over multiple optional fields, map each item in my database to a total score of columns have matched (where columns have a fixed, preset weight), then order by that score. How do make it?

score 4 · Accepted Answer · edited May 23 '17 at 10:34

Let start with the query:

const decimal nameWeight = 1, ageWeight = 1, titleWeight = 1.1m;

string name = null;
int? age = 20;
string title = (string)"Friend";

var query = from p in db.Persons
            let nameMatch = name == null || p.Name == name
            let ageMatch = age == null || p.Age == age.Value
            let titleMatch = title == null || p.Title == title
            let score = (nameMatch ? nameWeight : 0) + (ageMatch ? ageWeight : 0) + (titleMatch ? titleWeight : 0)
            where nameMatch || ageMatch || titleMatch
            orderby score descending
            select p;

This will work, but the SQL query is not optimal due to the optimal parameters embedded in it. For instance, with the above sample parameters the SQL query is like this:

SELECT 
    [Project1].[Id] AS [Id], 
    [Project1].[Name] AS [Name], 
    [Project1].[Age] AS [Age], 
    [Project1].[Title] AS [Title]
    FROM ( SELECT 
        [Extent1].[Id] AS [Id], 
        [Extent1].[Name] AS [Name], 
        [Extent1].[Age] AS [Age], 
        [Extent1].[Title] AS [Title], 
        (CASE WHEN ((CASE WHEN (@p__linq__0 IS NULL OR [Extent1].[Name] = @p__linq__1) THEN cast(1 as bit) WHEN ( NOT (@p__linq__0 IS NULL OR [Extent1].[Name] = @p__linq__1)) THEN cast(0 as bit) END) = 1) THEN cast(1 as decimal(18)) ELSE cast(0 as decimal(18)) END) + (CASE WHEN ((CASE WHEN (@p__linq__2 IS NULL OR [Extent1].[Age] = @p__linq__3) THEN cast(1 as bit) WHEN ( NOT (@p__linq__2 IS NULL OR [Extent1].[Age] = @p__linq__3)) THEN cast(0 as bit) END) = 1) THEN cast(1 as decimal(18)) ELSE cast(0 as decimal(18)) END) + (CASE WHEN ((CASE WHEN (@p__linq__4 IS NULL OR [Extent1].[Title] = @p__linq__5) THEN cast(1 as bit) WHEN ( NOT (@p__linq__4 IS NULL OR [Extent1].[Title] = @p__linq__5)) THEN cast(0 as bit) END) = 1) THEN 1.1 ELSE cast(0 as decimal(18)) END) AS [C1]
        FROM [dbo].[People] AS [Extent1]
        WHERE ((CASE WHEN (@p__linq__0 IS NULL OR [Extent1].[Name] = @p__linq__1) THEN cast(1 as bit) WHEN ( NOT (@p__linq__0 IS NULL OR [Extent1].[Name] = @p__linq__1)) THEN cast(0 as bit) END) = 1) OR ((CASE WHEN (@p__linq__2 IS NULL OR [Extent1].[Age] = @p__linq__3) THEN cast(1 as bit) WHEN ( NOT (@p__linq__2 IS NULL OR [Extent1].[Age] = @p__linq__3)) THEN cast(0 as bit) END) = 1) OR ((CASE WHEN (@p__linq__4 IS NULL OR [Extent1].[Title] = @p__linq__5) THEN cast(1 as bit) WHEN ( NOT (@p__linq__4 IS NULL OR [Extent1].[Title] = @p__linq__5)) THEN cast(0 as bit) END) = 1)
    )  AS [Project1]
    ORDER BY [Project1].[C1] DESC

The dynamic query part can simply be optimized by using the ReduceConstPredicates helper method that I recently wrote and posted here "Nullable object must have a value" exception after checking for null on a non-primitive/non-struct object and here How to write dynamic where clause for join range varible. All you need is to say at the end:

query = query.ReduceConstPredicates();

and the generated SQL becomes:

SELECT 
    [Project1].[Id] AS [Id], 
    [Project1].[Name] AS [Name], 
    [Project1].[Age] AS [Age], 
    [Project1].[Title] AS [Title]
    FROM ( SELECT 
        [Extent1].[Id] AS [Id], 
        [Extent1].[Name] AS [Name], 
        [Extent1].[Age] AS [Age], 
        [Extent1].[Title] AS [Title], 
        cast(1 as decimal(18)) + (CASE WHEN ((CASE WHEN ([Extent1].[Age] = @p__linq__0) THEN cast(1 as bit) WHEN ([Extent1].[Age] <> @p__linq__0) THEN cast(0 as bit) END) = 1) THEN cast(1 as decimal(18)) ELSE cast(0 as decimal(18)) END) + (CASE WHEN ((CASE WHEN ([Extent1].[Title] = @p__linq__1) THEN cast(1 as bit) WHEN ([Extent1].[Title] <> @p__linq__1) THEN cast(0 as bit) END) = 1) THEN 1.1 ELSE cast(0 as decimal(18)) END) AS [C1]
        FROM [dbo].[People] AS [Extent1]
    )  AS [Project1]
    ORDER BY [Project1].[C1] DESC

P.S. Here is the source code of the method used:

public static class QueryableExtensions
{
    public static IQueryable<T> ReduceConstPredicates<T>(this IQueryable<T> source)
    {
        var reducer = new ConstPredicateReducer();
        var expression = reducer.Visit(source.Expression);
        if (expression == source.Expression) return source;
        return source.Provider.CreateQuery<T>(expression);
    }

    class ConstPredicateReducer : ExpressionVisitor
    {
        private int evaluateConst;
        private bool EvaluateConst { get { return evaluateConst > 0; } }
        private ConstantExpression TryEvaluateConst(Expression node)
        {
            evaluateConst++;
            try { return Visit(node) as ConstantExpression; }
            catch { return null; }
            finally { evaluateConst--; }
        }
        protected override Expression VisitUnary(UnaryExpression node)
        {
            if (EvaluateConst || node.Type == typeof(bool))
            {
                var operandConst = TryEvaluateConst(node.Operand);
                if (operandConst != null)
                {
                    var result = Expression.Lambda(node.Update(operandConst)).Compile().DynamicInvoke();
                    return Expression.Constant(result, node.Type);
                }
            }
            return EvaluateConst ? node : base.VisitUnary(node);
        }
        protected override Expression VisitBinary(BinaryExpression node)
        {
            if (EvaluateConst || node.Type == typeof(bool))
            {
                var leftConst = TryEvaluateConst(node.Left);
                if (leftConst != null)
                {
                    if (node.NodeType == ExpressionType.AndAlso)
                        return (bool)leftConst.Value ? Visit(node.Right) : Expression.Constant(false);
                    if (node.NodeType == ExpressionType.OrElse)
                        return !(bool)leftConst.Value ? Visit(node.Right) : Expression.Constant(true);
                    var rightConst = TryEvaluateConst(node.Right);
                    if (rightConst != null)
                    {
                        var result = Expression.Lambda(node.Update(leftConst, node.Conversion, rightConst)).Compile().DynamicInvoke();
                        return Expression.Constant(result, node.Type);
                    }
                }
            }
            return EvaluateConst ? node : base.VisitBinary(node);
        }
        protected override Expression VisitConditional(ConditionalExpression node)
        {
            if (EvaluateConst || node.Type == typeof(bool))
            {
                var testConst = TryEvaluateConst(node.Test);
                if (testConst != null)
                    return Visit((bool)testConst.Value ? node.IfTrue : node.IfFalse);
            }
            return EvaluateConst ? node : base.VisitConditional(node);
        }
        protected override Expression VisitMember(MemberExpression node)
        {
            if (EvaluateConst || node.Type == typeof(bool))
            {
                var expressionConst = node.Expression != null ? TryEvaluateConst(node.Expression) : null;
                if (expressionConst != null || node.Expression == null)
                {
                    var result = Expression.Lambda(node.Update(expressionConst)).Compile().DynamicInvoke();
                    return Expression.Constant(result, node.Type);
                }
            }
            return EvaluateConst ? node : base.VisitMember(node);
        }
        protected override Expression VisitMethodCall(MethodCallExpression node)
        {
            if (EvaluateConst || node.Type == typeof(bool))
            {
                var objectConst = node.Object != null ? TryEvaluateConst(node.Object) : null;
                if (objectConst != null || node.Object == null)
                {
                    var argumentsConst = new ConstantExpression[node.Arguments.Count];
                    int count = 0;
                    while (count < argumentsConst.Length && (argumentsConst[count] = TryEvaluateConst(node.Arguments[count])) != null)
                        count++;
                    if (count == argumentsConst.Length)
                    {
                        var result = Expression.Lambda(node.Update(objectConst, argumentsConst)).Compile().DynamicInvoke();
                        return Expression.Constant(result, node.Type);
                    }
                }
            }
            return EvaluateConst ? node : base.VisitMethodCall(node);
        }
    }
}

This worked great! How come I completely forgot about `let` keyword :) — Can Poyrazoğlu, May 15 '16 at 05:43
Are you sure this works with navigation properties? I have an `IQueryable` where I include navigation properties, and having a `let` condition over navigation properties fails with no apparent reason. non-navigation properties (e.g. string match over direct string property) works fine though. — Can Poyrazoğlu, May 16 '16 at 11:37
I can't say 100%, but if you give me an example, I can check :) Something like `Person.Department.Name` ? — Ivan Stoev, May 16 '16 at 11:39
Exactly. but it turned out to be a sneaky error at my side. and *yes*, it works perfectly :) — Can Poyrazoğlu, May 16 '16 at 13:44

jdweng · Answer 2 · 2016-05-14T12:56:45.897

0

You can make your class IComparable like code below which is used by the Sort method. You can create a more sophisticated sort algorithm using similar code. the CompareTo returns -1 (less), 0 equal, and +1 (more).

    public class Person : IComparable 
    {
        public string Name { get; set; }
        public int Age { get; set; }
        public string Title { get; set; }
        public List<string> order { get; set; }


        public int CompareTo(object _other)
        {
            Person other = (Person)_other;
            int results = 0;

            if (this.Name != other.Name)
            {
                results = this.Name.CompareTo(other.Name);
            }
            else
            {
                if (this.Age != other.Age)
                {
                    results = this.Age.CompareTo(other.Age);
                }
                else
                {
                    results = this.Title.CompareTo(other.Title);
                }
            }

            return results;
        }

edited May 14 '16 at 12:56

answered May 14 '16 at 12:55

jdweng

33,250
2
15
20

Will this be translated to a SQL with no problem? – Can Poyrazoğlu May 14 '16 at 12:56
Yes. The sort method uses the default CompareTo() method build into the Net library. Adding IComparable with custom CompareTo() overrides the default method. So it will work with any method like sort, compare, equal. – jdweng May 14 '16 at 13:03
Oh, then maybe I could write a helper method instead of writing directly into the class, as "this" sorting algorithm is not always the case. Thanks, I'll be trying it. – Can Poyrazoğlu May 14 '16 at 13:04
But this is just the sorting part, how do I write the compound query itself in the first place? – Can Poyrazoğlu May 14 '16 at 13:06
1

It definitely will **not** be translated to SQL – Ivan Stoev May 14 '16 at 13:06

LINQ to Entities search multiple columns, order by total weight of the matches columns

2 Answers2