Моделирование рекурсии CTE в C #

Скажем, у вас есть следующий CTE, который возвращает уровень некоторых данных дерева (модель смежности), которые у меня есть (взяты из Иерархические данные в Linq - параметры и производительность):

WITH hierarchy_cte(id, parent_id, data, lvl) AS
(
    SELECT id, parent_id, data, 0 AS lvl
    FROM dbo.hierarchical_table
    WHERE (parent_id IS NULL)

    UNION ALL

    SELECT t1.id, t1.parent_id, t1.data, h.lvl + 1 AS lvl
    FROM dbo.hierarchical_table AS t1 
    INNER JOIN hierarchy_cte AS h ON t1.parent_id = h.id
)
SELECT id, parent_id, data, lvl
FROM hierarchy_cte AS result

Мне было интересно, можно ли повысить производительность, выполнив рекурсию на C # вместо SQL. Может ли кто-нибудь показать мне, как выполнять ту же работу, которую CTE выполняет с рекурсивной функцией C #, предполагая, что у меня есть IQueryable, где Tree - это объект, представляющий запись в иерархической таблице? Что-то вроде:

public void RecurseTree(IQueryable<Tree> tree, Guid userId, Guid parentId, int level)
{
    ...
    currentNode.level = x
    ...
    Recurse(tree... ,level + 1)
}

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


sql c# recursion common-table-expression entity-framework-4
person woggles    schedule 03.06.2011    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Рекурсия в SQL Server ужасающе медленная по сравнению, но она работает.

Я должен сказать, что T-SQL несколько ограничен, но изначально он никогда не предназначался для выполнения всех этих операций. Я не верю, что есть какой-либо способ сделать это с помощью IQueryable, если вы намеревались запустить это против своего экземпляра SQL Server, но вы можете сделать это в памяти на машине, на которой выполняется код, используя LINQ-to-Objects в относительно компактный вид.

Вот один из способов сделать это:

class TreeNode
{
    public int Id;
    public int? ParentId;
}

static void Main(string[] args)
{
    var list = new List<TreeNode>{
        new TreeNode{ Id = 1 },
            new TreeNode{ Id = 4, ParentId = 1 },
            new TreeNode{ Id = 5, ParentId = 1 },
            new TreeNode{ Id = 6, ParentId = 1 },
        new TreeNode{ Id = 2 },
            new TreeNode{ Id = 7, ParentId= 2 },
                new TreeNode{ Id = 8, ParentId= 7 },
        new TreeNode{ Id = 3 },
    };

    foreach (var item in Level(list, null, 0))
    {
        Console.WriteLine("Id={0}, Level={1}", item.Key, item.Value);
    }
}

private static IEnumerable<KeyValuePair<int,int>> Level(List<TreeNode> list, int? parentId, int lvl)
{
    return list
        .Where(x => x.ParentId == parentId)
        .SelectMany(x => 
            new[] { new KeyValuePair<int, int>(x.Id, lvl) }.Concat(Level(list, x.Id, lvl + 1))
        );
}
person John Leidegren    schedule 03.06.2011
comment
работал как шарм. затраченное время уменьшилось с 3 секунд до ‹1. Спасибо :) - person woggles; 03.06.2011

arrow_upward
6
arrow_downward

Подлинно рекурсивные лямбды (и, следовательно, Expressions) технически возможны, но безумно. Я также ожидаю, что любой парсер (L2S, EF и т. Д.), Кроме возможно, LINQ-to-Objects просто сойдет с ума, пытаясь распознать это.

Вкратце: вам следует считать этот механизм неподдерживаемым для Expression.

Наконец, обратите внимание, что тот факт, что вы пишете Expression, не означает, что вы выполняете его на C # - на самом деле, вполне вероятно, что наоборот: если вы активно пишете Expression (а не делегат или процедурный код), я предполагаю, что это переходит к синтаксическому анализатору (если вы не использовали .AsQueryable() для отправки его в LINQ-to-Objects).

person Marc Gravell    schedule 03.06.2011