Оптимизировать решение для поиска по дереву категорий

Question

Я создаю какое-то приложение для аукциона, и мне нужно решить, как лучше всего решить эту проблему. Я использую BL Toolkit в качестве своего OR Mapper (у него хорошая поддержка Linq) и ASP.NET MVC 2.

Фон

У меня есть несколько Category объектов, которые создаются динамически и сохраняются в моей базе данных как представление этого класса:

class Category
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
}

Теперь каждый объект Category может иметь несколько объектов InformatonClass, представляющих одну информацию в этой категории, например, цену или цвет. Эти классы также динамически создаются администратором и хранятся в базе данных. Есть конкретные для группы категорий. Класс, который представляет это выглядит следующим образом:

class InformationClass
{
    public int Id { get; set; }
    public InformationDataType InformationDataType { get; set; }
    public string Name { get; set; }
    public string Label { get; set; }
}

Теперь у меня есть третья таблица, которая представляет соединение между ними следующим образом:

class CategoryInformation
{
    public int InformationClassId { get; set; }
    public int AuctionCategoryId { get; set; }
}

Задача

Теперь проблема в том, что мне нужно наследовать все категории InformationClass в дочерних категориях. Например, у каждого продукта будет цена, поэтому мне нужно добавить это InformationClass только в мою корневую категорию. Информация о частоте может быть добавлена ​​к базовой категории ЦП, и она должна быть доступна в категориях AMD и Intel, которые будут получены из категории ЦП.

Мне нужно знать, какие InformationClass объекты относятся к указанному Category очень часто в моем приложении.

Так вот мой вопрос. Что будет наиболее оптимальным решением для этой проблемы? У меня есть некоторые идеи, но я не могу решить.

1. Загрузить все категории из базы данных в таблицу Application и извлекать их из этого места каждый раз - поскольку категории не будут меняться слишком часто, это уменьшит количество запросов к базе данных, но все равно потребуется поиск в дереве с использованием Linq-to -Объекты
2. Изобретите (я не знаю, возможно ли это) какой-нибудь причудливый запрос Linq, который может искать в дереве и получать все идентификаторы классов информации, не слишком подчеркивая базу данных.
3. Какие-нибудь другие приятные идеи?

Буду благодарен за любые ответы и идеи. Спасибо всем за советы.

Answer 1

Звучит как случай для идеи, о которой я когда-то писал:

• Древовидные структуры и группы доступности баз данных в SQL с эффективными запросами с использованием транзитивных замыканий

Основная идея заключается в следующем: в дополнение к таблице Category у вас также есть таблица CategoryTC, которая содержит транзитивное замыкание отношения родитель-потомок. Это позволяет вам быстро и эффективно получить список всех категорий предков или потомков определенной категории. В блоге объясняется, как вы можете поддерживать транзитивное закрытие в актуальном состоянии каждый раз, когда создается, удаляется новая категория или изменяются отношения родитель-потомок (это не более двух запросов каждый раз).

В посте для выражения идеи используется SQL, но я уверен, что вы можете перевести его на LINQ.

Вы не указали в своем вопросе, как таблица InformationClass связана с таблицей Category, поэтому я должен предположить, что у вас есть таблица CategoryInformation, которая выглядит примерно так:

class CategoryInformation
{
    public int CategoryId { get; set; }
    public int InformationClassId { get; set; }
}

Затем вы можете получить все информационные классы, связанные с определенной категорией, используя что-то вроде этого:

var categoryId = ...;
var infoClasses = db.CategoryInformation
    .Where(cinf => db.CategoryTC.Where(tc => tc.Descendant == categoryId)
                                .Any(tc => tc.Ancestor == cinf.CategoryId))
    .Select(cinf => db.InformationClass
                      .FirstOrDefault(ic => ic.Id == cinf.InformationClassId));

Имеет ли это смысл? Любые вопросы, пожалуйста, задавайте.

Answer 2

В прошлом (до SQLServer 2005 и до LINQ) при работе с такого рода структурой (или более общий случай направленного ациклического графа, реализованного с помощью таблицы соединений, чтобы элементы могли иметь более одного «родителя») Я либо сделал это, загрузив весь граф в память, либо создав в таблице базы данных обновленную тигром таблицу, которая кэшировалась в отношениях предка и потомка.

У каждого из них есть свои преимущества, и выигрыш зависит от частоты обновления, сложности объектов, не связанных с отношениями родитель-потомок, и частоты обновления. В общем, загрузка в память позволяет быстрее выполнять индивидуальный поиск, но при большом графике он не масштабируется также из-за объема памяти, используемого каждым веб-сервером (здесь «каждый», потому что ситуации с веб-фермерским хозяйством - это ситуация, когда элементы, кэшированные в памяти, создают дополнительные проблемы), а это означает, что вам нужно быть очень осторожным в том, как все синхронизировано, чтобы противодействовать этому эффекту.

Третий доступный вариант - поиск предков с помощью рекурсивного CTE:

CREATE VIEW [dbo].[vwCategoryAncestry]
AS
WITH recurseCategoryParentage (ancestorID, descendantID)
AS
(
    SELECT parentID, id
    FROM Categories
    WHERE parentID IS NOT NULL

    UNION ALL

    SELECT ancestorID, id
    FROM recurseCategoryParentage
        INNER JOIN Categories ON parentID = descendantID
)
SELECT DISTINCT ancestorID, descendantID
FROM recurseCategoryParentage

Предполагается, что корневые категории обозначены нулевым parentID.

(Мы используем UNION ALL, так как в любом случае мы собираемся потом ВЫБРАТЬ DISTINCT, и таким образом у нас будет одна операция DISTINCT вместо ее повторения).

Это позволяет нам использовать подход с использованием справочной таблицы без избыточности этой денормализованной таблицы. Компромисс эффективности, очевидно, отличается и, как правило, хуже, чем с таблицей, но не очень (небольшое попадание при выборе, незначительное усиление при вставке и удалении, незначительное увеличение пробела), но гарантия правильности выше.

Я проигнорировал вопрос о том, где LINQ вписывается в это, поскольку компромиссы во многом одинаковы независимо от того, как это запрашивается. LINQ может играть лучше с «таблицами», которые имеют отдельные первичные ключи, поэтому мы можем изменить предложение select на SELECT DISTINCT (cast(ancestorID as bigint) * 0x100000000 + descendantID) as id, ancestorID, descendantID и определить его в качестве первичного ключа в атрибуте [Column]. Конечно, все столбцы должны быть указаны как сгенерированные БД.

---

Edit. Еще немного о компромиссах.

Сравнение подхода CTE с поиском в базе данных:

Pro CTE:

1. Код CTE прост, в приведенном выше виде представлен весь дополнительный код БД, который вам нужен, а необходимый C # идентичен.
2. Код БД находится в одном месте, вместо таблицы и триггера в другой таблице.
3. Вставляет и удаляет быстрее; это не влияет на них, в то время как триггер делает.
4. Несмотря на семантическую рекурсию, планировщик запросов понимает и может справиться с ним, поэтому обычно (для любой глубины) он реализуется всего за два сканирования индекса (вероятно, кластеризованных), двух облегченных катушек, конкатенации и отчетливый вид, а не во множестве сканов, которые вы можете себе представить. Так что, хотя сканирование, конечно, более тяжелое, чем простой просмотр таблиц, оно далеко не так плохо, как кажется на первый взгляд. Действительно, даже характер этих двух сканирований индекса (одна и та же таблица, разные строки) делает его менее дорогим, чем вы могли подумать, читая это.
5. Очень просто заменить это поиском по таблице, если последующий опыт доказывает, что это будет путь.
6. Таблица поиска по своей природе денормализует базу данных. Помимо проблем с чистотой, «неприятный запах» означает, что это нужно будет объяснить и оправдать любому новому разработчику, так как до этого он может просто «выглядеть неправильно», и его инстинкты отправят их в погоню за диким гусем, пытающуюся устранить это.

Таблица поиска Pro:

1. Хотя выбор CTE быстрее, чем можно себе представить, поиск по-прежнему выполняется быстрее, особенно если он используется как часть более сложного запроса.
2. Хотя CTE (и ключевое слово WITH, используемое для их создания) являются частью стандарта SQL 99, они относительно новы, и некоторые разработчики их не знают (хотя я думаю, что этот конкретный CTE настолько прост для чтения, что он считаетсяв любом случае, как хороший пример обучения, так что, возможно, это действительно про CTE!)
3. Хотя CTE являются частью стандарта SQL 99, они не реализуются некоторыми базами данных SQL, включая более старые версии SQLServer (которыепо-прежнему используется), что может повлиять на любые усилия по переносу.(Хотя они поддерживаются Oracle, и Postgres среди других, так что на данный момент это может и не быть проблемой).
4. Это довольно легко заменить позже версией CTE, если последующий опыт подсказывает, что вам следует.

Сравнение (обоих) вариантов db-heavy с кэшированием в памяти.

Pro In-Memory:

1. Если ваша реализация действительно не отстой, это будет намного быстрее, чем поиск в БД.
2. Это делает возможной некоторую вторичную оптимизацию после этого изменения.
3. Переход с БД на оперативную память достаточно сложен, еслипоследующее профилирование показывает, что путь в память - это путь.

Pro Querying DB:

1. Время запуска может быть очень медленным при использовании в памяти.
2. Изменения в данных намного проще.Большинство пунктов являются аспектами этого.Действительно, если вы пойдете по маршруту в памяти, тогда вопрос о том, как обрабатывать изменения, делающие недействительной кэшированную информацию, становится совершенно новой постоянной проблемой на протяжении всего срока жизни проекта, а не тривиальной вообще.
3. Есливы используете в памяти, вам, вероятно, придется использовать это хранилище в памяти даже для операций, где оно не имеет значения, что может усложнить его совместимость с остальным кодом доступа к данным.
4. Нет необходимости отслеживать изменения и обновлять кеш.
5. Нет необходимости гарантировать, что каждый веб-сервер в решении для веб-фермы и / или веб-сада (определенный уровень успеха потребует этого) точнота же степень свежести.
6. Аналогичным образом, степень масштабируемости для разных машин (насколько можно увеличить производительность на 100%, удваивая число веб-серверов и ведомых устройств БД).
7. Прив памяти использование памяти может стать очень высоким, если либо (а) количество объектов велико, либо (б) размеробъекты (поля, особенностроки, коллекции и объекты, которые сами имеют жало или коллекцию).Возможно, «нам нужен больший веб-сервер» объем памяти, и это касается каждой машины в ферме.7а.Такое интенсивное использование памяти особенно похоже на продолжение роста по мере развития проекта.
8. Если изменения не приведут к немедленному обновлению хранилища в памяти, решение в памяти будет означать, что представление, используемое людьми вплата за администрирование этих категорий будет отличаться от того, что видят клиенты, до тех пор, пока они не будут синхронизированы.
9. Повторная синхронизация в памяти может быть очень дорогой.Если вы не очень умны с этим, это может вызвать случайные (для пользователя) огромные скачки производительности.Если вы сообразительны с этим, это может усугубить другие проблемы (особенно с точки зрения поддержания разных машин на одинаковом уровне свежести).
10. Если вы не сообразительны в оперативной памяти, эти всплески могутнакапливать, ставя машину в долгосрочное зависание.Если вы умны, избегая этого, вы можете усугубить другие проблемы.
11. очень трудно перейти из оперативной памяти к попаданию в БД, если это окажется правильным решением.

Ничто из этого не опирается со 100% -ной уверенностью на то или иное решение, и я, конечно, не собираюсь давать четкий ответ, поскольку это преждевременная оптимизация.Что вы можете сделать a priori , так это принять разумное решение, которое, вероятно, будет оптимальным решением.Независимо от того, что вы идете, вы должны профиль после, особенноесли код окажется узким местом и, возможно, изменится.Вы также должны делать это в течение всего срока службы продукта, так как как изменения в коде (исправления и новые функции), так и изменения в наборе данных, безусловно, могут изменить оптимальный вариант (на самом деле, он может меняться от одного к другому, а затем возвращаться кпредыдущий, на протяжении всей жизни).Вот почему я включил соображения о простоте перехода от одного подхода к другому в приведенном выше списке плюсов и минусов.