Найти подходящие предметы по сложной комбинации атрибутов

Question

В моей базе данных есть элементы, которые отражают атрибуты документов, заполняемых пользователями. Каждое значение, указанное в документе, например, Вы выбираете определенный параметр для поля или устанавливаете флажок, становитесь элементом / атрибутом в моей таблице.

Такими атрибутами могут быть: Курильщик, Некурящий, Регион (Европа, США, ...), Краска для волос

В таблицах это выглядит примерно следующим образом:

Document
ID | Name
1  | doc-1
2  | doc-2
3  | doc-3

Attribute
ID | Name
1  | Smoker
2  | Non-Smoker
3  | Region-Europe
4  | Region-USA
5  | Hair-Brown
6  | Hair-Blond

Item
ID | Document | Attribute
1  | 1        | 1
2  | 1        | 4
3  | 2        | 2
4  | 2        | 3
5  | 2        | 5
6  | 3        | 2
7  | 3        | 6

Чтобы предлагать возможности поиска, у пользователей должна быть возможность создавать общие запросы. Например, я хотел бы найти документы, которые имеют следующие атрибуты:

(Smoker AND Region-USA) OR (Non-Smoker AND Region-Europe AND Hair-Blond)

(в результате будет найден документ № 1)

Как я могу выполнить такой запрос наиболее эффективным способом, и, возможно, использовать EF-core и linq-to-sql, чтобы перенести его в SQL? Как я могу на самом деле запросить это в плане SQL наиболее эффективным способом?

Я могу сделать это довольно легко в памяти, но, поскольку моя база данных содержит более 100 тыс. Элементов, это может стать довольно медленным.

Спасибо за любую помощь в этом!

---

Обновление : Схожие вопросы по SO

• Дизайн базы данных для тегов

Answer 1

Вот класс расширения LINQ, чтобы помочь с построением запросов.Я оставляю разбор выражения и построение правильного запроса в качестве упражнения для читателя:).

Во-первых, вот основа для того, что мы будем строить:

public class DocItemJoin {
    public Documents d { get; set; }
    public IEnumerable<int> ig { get; set; }
}

var DocItems = Document.GroupJoin(Item, d => d.ID, i => i.Document, (d, ig) => new DocItemJoin { d = d, ig = ig.Select(i => i.Attribute) });

// (Smoker AND Region-USA) OR (Non-Smoker AND Region-Europe AND Hair-Blond)    
var ans = DocItems.Where(dig => (dig.ig.Contains(1) && dig.ig.Contains(4)) || (dig.ig.Contains(2) && dig.ig.Contains(3) && dig.ig.Contains(6)))
                  .Select(dig => dig.d);

Использование DocItemsв качестве базы мы можем запросить для каждого атрибута, используя Contains.

Используя библиотеку расширений, мы можем динамически построить тот же запрос:

var whereLeft = 1.HasAttrib().qAnd(4.HasAttrib());
var whereRight = 2.HasAttrib().qAnd(3.HasAttrib()).qAnd(6.HasAttrib());
var whereBody = whereLeft.qOr(whereRight);
var ans = DocItems.Query(whereBody);

Наконец, вот класс расширениястроит Expression деревья:

public static class QueryBuilder {
    private static MethodInfo containsMethod = typeof(Enumerable).GetMethods().Single(mi => mi.Name == "Contains" && mi.GetParameters().Length == 2).MakeGenericMethod(typeof(int));

    public static MethodCallExpression qContains(this Expression p, int attrib) => Expression.Call(containsMethod, p, Expression.Constant(attrib));
    public static BinaryExpression qAnd(this Expression l, Expression r) => Expression.AndAlso(l, r);
    public static BinaryExpression qOr(this Expression l, Expression r) => Expression.OrElse(l, r);

    static ParameterExpression digParm = Expression.Parameter(typeof(DocItemJoin), "dig");
    static MemberExpression digParmig = Expression.Property(digParm, "ig");

    public static MethodCallExpression HasAttrib(this int attrib) => digParmig.qContains(attrib);

    static Expression<Func<DocItemJoin, Documents>> selectLambda = Expression.Lambda<Func<DocItemJoin, Documents>>(Expression.Property(digParm, "d"), digParm);

    public static IQueryable<Documents> Query(this IQueryable<DocItemJoin> src, Expression whereBody)
        => src.Where(Expression.Lambda<Func<DocItemJoin, bool>>(whereBody, digParm)).Select(selectLambda);
}

Answer 2

Дополнительные исследования показали, что я уже ожидал: можно использовать решение, использующее оператор SQL IN, и оно фактически работает для удобной передачи этих запросов на сервер, но, возможно, не столь эффективно для большого количества тегов.

К счастью, пользователи не будут выполнять очень сложные запросы на регулярной основе и будут тратить немного времени на сложные запросы, поэтому я могу пренебречь этим в моем случае.

Чтобы связать источники для этих утверждений:

• https://stackoverflow.com/a/48480/8504288
• https://dba.stackexchange.com/a/176816

Чтобы в общих чертах набросать окончательное решение, вот код для этого:

Используя оператор IN в подзапросе, я могу отфильтровать все документы, к которым применен определенный атрибут. Комбинируя эти операторы IN с помощью AND / OR, я могу построить желаемое выражение.

SELECT i.Document
FROM   Item i INNER JOIN Attribute a on i.Attribute = a.ID
WHERE
    i.Document IN (
       SELECT ii.Document 
       FROM Item ii INNER JOIN Attribute ai on ii.Attribute = ai.ID
       WHERE ai.Name = "Smoker"
    )
    AND
    i.Document IN (
       SELECT ii.Document 
       FROM Item ii INNER JOIN Attribute ai on ii.Attribute = ai.ID
       WHERE ai.Name = "Region-USA"
    )
    OR
    i.Document IN (
       SELECT ii.Document 
       FROM Item ii INNER JOIN Attribute ai on ii.Attribute = ai.ID
       WHERE ai.Name = "Non-Smoker"
    )
    AND
    i.Document IN (
       SELECT ii.Document 
       FROM Item ii INNER JOIN Attribute ai on ii.Attribute = ai.ID
       WHERE ai.Name = "Region-Europe"
    )
    AND
    i.Document IN (
       SELECT ii.Document 
       FROM Item ii INNER JOIN Attribute ai on ii.Attribute = ai.ID
       WHERE ai.Name = "Hair-Blond"
    )

Улучшение производительности

Чтобы ограничить количество JOIN, необходимых в подзапросах, можно сначала выбрать идентификаторы необходимых атрибутов.

SELECT ID, Name FROM Attribute WHERE Name in ('Smoker', 'Non-Smoker', ...)

Используя эти идентификаторы, подзапрос будет выглядеть намного проще, поскольку мы сможем пропустить JOIN:

SELECT i.Document
FROM   Item i INNER JOIN Attribute a on i.Attribute = a.ID
WHERE
    i.Document IN (SELECT ii.Document FROM Item ii WHERE ii.Attribute = 1) -- Smoker
    AND
    i.Document IN (SELECT ii.Document FROM Item ii WHERE ii.Attribute = 4) -- Region-USA
    OR
    ...

---

Обновление

Измеренное время для обоих заходов

Я выполнил запрос, аналогичный указанному выше: (1 И 2) ИЛИ (3 И 4 И 4) на SQL Server с разумным размером набора Документов (130), Элементов (4122) и Атрибутов ( ~ 400). Следующие времена могут быть измерены на моей машине:

• 1-й подход, с JOIN в подзапросе IN: ~ 12 секунд
• 2-й подход, сначала поиск атрибута по идентификатору: ~ 3,5 с