Проблема производительности рекурсивных SQL-запросов [закрыто]

9

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

Аннотация

У меня есть база данных, она позволяет довольно необычно хранить данные и предоставляет несколько нестандартных функций, которые требуются моему бизнес-процессу. Особенности следующие:

  1. Неразрушающие и неблокирующие обновления / удаления, реализованные с использованием подхода только для вставки, который позволяет восстанавливать данные и автоматически регистрировать данные (каждое изменение связано с пользователем, который внес это изменение)
  2. Мультиверсионные данные (может быть несколько версий одних и тех же данных)
  3. Разрешения на уровне базы данных
  4. Возможная согласованность со спецификацией ACID и безопасностью транзакций создает / обновляет / удаляет
  5. Возможность перемотки назад или быстрой перемотки вашего текущего представления данных в любой момент времени.

Могут быть и другие функции, которые я забыл упомянуть.

Структура базы данных

Все пользовательские данные хранятся в Itemsтаблице в виде строки в кодировке JSON ( ntext). Все операции с базой данных выполняются с помощью двух хранимых процедур, GetLatestи InsertSnashotони позволяют работать с данными подобно тому, как GIT работает с исходными файлами.

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

Также возможно хранить данные в обычных столбцах SQL вместо того, чтобы хранить их в закодированной форме Json. Однако это увеличивает общую сложность.

Чтение данных

GetLatestРезультаты с данными в виде инструкций, рассмотрите следующую диаграмму для объяснения:

Структурная схема

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

Таким образом, вызов в GetLatestтечение следующих временных интервалов ввода приведет к следующим версиям записи:

GetLatest 0, 15  => 1       <= The data is created upon it's first occurance
GetLatest 0, 25  => 2       <= Inserting another version on top of first one overwrites the existing version
GetLatest 0, 30  => 3       <= The overwrite takes place as soon as the data is inserted
GetLatest 0, 45  => 3, 4    <= This is where the conflict is introduced in the system
GetLatest 0, 55  => 4, 5    <= You can still edit all the versions
GetLatest 0, 65  => 4, 6    <= You can still edit all the versions
GetLatest 0, 75  => 4, 6, 7 <= You can also create additional conflicts
GetLatest 0, 85  => 4, 7, 8 <= You can still edit records
GetLatest 0, 95  => 7, 8, 9 <= You can still edit records
GetLatest 0, 105 => 7, 8    <= Inserting a record with `Json` equal to `NULL` means that the record is deleted
GetLatest 0, 115 => 8       <= Deleting the conflicting versions is the only conflict-resolution scenario
GetLatest 0, 125 => 8, X    <= The conflict can be based on the version that was already deleted.
GetLatest 0, 135 => 8, Y    <= You can delete such version too and both undelete another version on parallel within one Snapshot (or in several Snapshots).
GetLatest 0, 145 => 8       <= You can delete the undeleted versions by inserting NULL.
GetLatest 0, 155 => 8, Z    <= You can again undelete twice-deleted versions
GetLatest 0, 165 => 8       <= You can again delete three-times deleted versions
GetLatest 0, 10000 => 8     <= This means that in order to fast-forward view from moment 0 to moment `10000` you just have to expose record 8 to the user.
GetLatest 55, 115  => 8, [Remove 4], [Remove 5] <= At moment 55 there were two versions [4, 5] so in order to fast-forward to moment 115 the user has to delete versions 4 and 5 and introduce version 8. Please note that version 7 is not present in results since at moment 110 it got deleted.

Для того , GetLatestчтобы поддерживать такой эффективный интерфейс каждая запись должна содержать специальные атрибуты службы BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextIdкоторые используются , GetLatestчтобы выяснить , относится ли запись адекватно в отрезок времени , предусмотренного GetLatestаргументов

Вставка данных

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

  1. Данные просто вставляются в базу данных без возможности запроса GetLatestхранимой процедуры.

  2. Данные становятся доступными для GetLatestхранимой процедуры, данные становятся доступными в нормализованном (то есть denormalized = 0) состоянии. В то время как данные в нормализованном состоянии, поля службы BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, в UpdatedOnNextIdнастоящее время вычисляются , которые очень медленно.

  3. Чтобы ускорить процесс, данные денормализуются, как только они становятся доступными для GetLatestхранимой процедуры.

    • Поскольку шаги 1,2,3 проводятся в разных транзакциях, возможно, что аппаратный сбой может произойти в середине каждой операции. Оставление данных в промежуточном состоянии. Такая ситуация нормальная, и даже если это произойдет, данные будут исцелены в течение следующего InsertSnapshotвызова. Код для этой части можно найти между шагами 2 и 3 InsertSnapshotхранимой процедуры.

Проблема

Новые функции (обязательные для бизнеса) заставили меня изменить специальный Denormalizerвид, который связывает все функции вместе и используется как для, так GetLatestи для других InsertSnapshot. После этого у меня начались проблемы с производительностью. Если изначально он SELECT * FROM Denormalizerвыполнялся всего за доли секунды, то теперь для обработки 10000 записей требуется около 5 минут.

Я не профессионал в области БД, и мне потребовалось почти шесть месяцев, чтобы представить текущую структуру базы данных. И я потратил две недели сначала на проведение рефакторинга, а затем пытался выяснить, в чем причина моей проблемы с производительностью. Я просто не могу найти это. Я предоставляю резервную копию базы данных (которую вы можете найти здесь), потому что схема (со всеми индексами) достаточно велика, чтобы поместиться в SqlFiddle, база данных также содержит устаревшие данные (более 10000 записей), которые я использую для целей тестирования , Также я предоставляю текст для Denormalizerпросмотра, который подвергся рефакторингу и стал мучительно медленным:

ALTER VIEW [dbo].[Denormalizer]
AS
WITH Computed AS
(
    SELECT  currItem.Id,
            nextOperation.id AS NextId,
            prevOperation.FinishedOn AS PrevComputed,
            currOperation.FinishedOn AS CurrComputed,
            nextOperation.FinishedOn AS NextComputed

    FROM Items currItem 
    INNER JOIN dbo.Operations AS currOperation ON currItem.OperationId = currOperation.Id

    LEFT OUTER JOIN dbo.Items AS prevItem ON currItem.PreviousId = prevItem.Id
    LEFT OUTER JOIN dbo.Operations AS prevOperation ON prevItem.OperationId = prevOperation.Id 
    LEFT OUTER JOIN
    (
        SELECT MIN(I.id) as id, S.PreviousId, S.FinishedOn
        FROM Items I
        INNER JOIN
        (
            SELECT I.PreviousId, MIN(nxt.FinishedOn) AS FinishedOn
            FROM dbo.Items I
            LEFT OUTER JOIN dbo.Operations AS nxt ON I.OperationId = nxt.Id
            GROUP BY I.PreviousId
        ) AS S ON I.PreviousId = S.PreviousId 
        GROUP BY S.PreviousId, S.FinishedOn
    ) AS nextOperation ON nextOperation.PreviousId = currItem.Id

    WHERE currOperation.Finished = 1 AND currItem.Denormalized = 0
),

RecursionInitialization AS
(
    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,
            currItem.Id AS BranchID,
            COALESCE (C.PrevComputed, C.CurrComputed) AS CreatedOn,
            COALESCE (C.PrevComputed, CAST(0 AS BIGINT)) AS RecoveredOn,
            COALESCE (C.PrevComputed, CAST(0 AS BIGINT)) AS UpdatedOnPrev,
            C.CurrComputed AS UpdatedOnCurr,
            COALESCE (C.NextComputed, CAST(8640000000000000 AS BIGINT)) AS UpdatedOnNext,
            C.NextId AS UpdatedOnNextId,

            0 AS RecursionLevel

    FROM Items AS currItem
    INNER JOIN Computed AS C ON currItem.Id = C.Id
    WHERE currItem.Denormalized = 0

    UNION ALL

    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,
            currItem.BranchId,
            currItem.CreatedOn,
            currItem.RecoveredOn,
            currItem.UpdatedOnPrev,
            currItem.UpdatedOnCurr,
            currItem.UpdatedOnNext,
            currItem.UpdatedOnNextId,

            0 AS RecursionLevel

    FROM Items AS currItem
    WHERE currItem.Denormalized = 1
),
Recursion AS
(
    SELECT *
    FROM RecursionInitialization AS currItem

    UNION ALL

    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,

            CASE
                WHEN prevItem.UpdatedOnNextId = currItem.Id
                THEN prevItem.BranchID
                ELSE currItem.Id
            END AS BranchID,

            prevItem.CreatedOn AS CreatedOn,

            CASE
                WHEN prevItem.Json IS NULL
                THEN CASE
                            WHEN currItem.Json IS NULL
                            THEN prevItem.RecoveredOn
                            ELSE C.CurrComputed
                        END
                ELSE prevItem.RecoveredOn
            END AS RecoveredOn,

            prevItem.UpdatedOnCurr AS UpdatedOnPrev,

            C.CurrComputed AS UpdatedOnCurr,

            COALESCE (C.NextComputed, CAST(8640000000000000 AS BIGINT)) AS UpdatedOnNext,

            C.NextId,

            prevItem.RecursionLevel + 1 AS RecursionLevel
    FROM Items currItem
    INNER JOIN Computed C ON currItem.Id = C.Id
    INNER JOIN Recursion AS prevItem ON currItem.PreviousId = prevItem.Id
    WHERE currItem.Denormalized = 0
)
SELECT  item.Id,
        item.PreviousId,
        item.UUID,
        item.Json,
        item.TableName,
        item.OperationId,
        item.PermissionId,
        item.Denormalized,
        item.BranchID,
        item.CreatedOn,
        item.RecoveredOn,
        item.UpdatedOnPrev,
        item.UpdatedOnCurr,
        item.UpdatedOnNext,
        item.UpdatedOnNextId

FROM Recursion AS item
INNER JOIN
(
    SELECT Id, MAX(RecursionLevel) AS Recursion
    FROM Recursion AS item
    GROUP BY Id
) AS nested ON item.Id = nested.Id AND item.RecursionLevel = nested.Recursion
GO

Вопросы)

Есть два сценария, которые принимаются во внимание, денормализованные и нормализованные случаи:

  1. Глядя на исходное резервное копирование, что делает SELECT * FROM Denormalizerэто мучительно медленным, я чувствую, что есть проблема с рекурсивной частью представления Denormalizer, я пытался ограничить, denormalized = 1но ни одно из моих действий не повлияло на производительность.

  2. После запуска UPDATE Items SET Denormalized = 0он будет делать GetLatestи SELECT * FROM Denormalizerбежать в (первоначально думали , что будет) медленный сценарий, есть способ ускорить процесс, когда мы вычислительными служебных полей BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext,UpdatedOnNextId

заранее спасибо

PS

Я пытаюсь придерживаться стандартного SQL, чтобы сделать запрос легко переносимым на другие базы данных, такие как MySQL / Oracle / SQLite, на будущее, но если нет стандартного SQL, который мог бы помочь, я в порядке, придерживаясь конструкций, специфичных для базы данных.

sql-server sql-server-2012 query-performance LU4
источник
1
Что касается стандартного SQL и перечисленных вами БД: вы используете здесь CTE, и они не поддерживаются mySQL, и существуют некоторые синтаксические различия между основными реализациями. Кроме того, в настоящее время они являются забором оптимизации в postgres, что может быть большой проблемой производительности. Ничто из этого не должно помешать вам использовать их: с деревом в форме «списка смежности» они, как правило, являются подходящим инструментом для работы, но в случаях, когда важна совместимость, об этих моментах следует помнить, прежде чем они кусают вас, чтобы вы могли быть подготовиться к любой дополнительной работе, необходимой для перехода на другие СУБД.
Дэвид Спиллетт
Спасибо, я стараюсь как можно больше придерживаться стандартного SQL. Причина в том, что я считаю, что это должно уменьшить количество проблем в будущем, когда потребуется перенести существующий код в другие базы данных. Это не всегда возможно. Существует также фактор времени, который является частью уравнения. Я потратил полгода на то, чтобы уладить текущую структуру базы данных ... Я бы хотел, чтобы она содержала только стандартные конструкции, но если потребуется еще 10 лет, это не тот путь ... Так что, если вы видите, что есть больше возможен стандартный рефакторинг. Я буду рад принять его ...
Lu4
1
Нет, это звучит как прагматичный способ справиться с различными приоритетами и сложностями в подобных случаях. Я просто сообразил, что возникли проблемы, если вы еще не сталкивались с ними (лучше знать сейчас, даже если сейчас невозможно / практически невозможно что-либо сделать с этим, чем быть застигнутым врасплох в производстве!) ).
Дэвид Спиллетт

Ответы:

9

@ Lu4 .. Я проголосовал за то, чтобы закрыть этот вопрос как "Совет Айсберга", но используя подсказку запроса, вы сможете запустить его менее чем за 1 секунду. Этот запрос может быть реорганизован и может использоваться CROSS APPLY, но это будет консультационная работа, а не ответ на сайте вопросов и ответов.

Ваш запрос будет работать более 13 минут на моем сервере с 4 ЦП и 16 ГБ ОЗУ.

введите описание изображения здесь

Я изменил ваш запрос для использования, OPTION(MERGE JOIN)и он работал менее 1 секунды

set nocount on 
set statistics io on
set statistics time on
;WITH Computed AS
(
    SELECT  currItem.Id,
            nextOperation.id AS NextId,
            prevOperation.FinishedOn AS PrevComputed,
            currOperation.FinishedOn AS CurrComputed,
            nextOperation.FinishedOn AS NextComputed

    FROM Items currItem 
    INNER JOIN dbo.Operations AS currOperation ON currItem.OperationId = currOperation.Id

    LEFT OUTER JOIN dbo.Items AS prevItem ON currItem.PreviousId = prevItem.Id
    LEFT OUTER JOIN dbo.Operations AS prevOperation ON prevItem.OperationId = prevOperation.Id 
    LEFT OUTER JOIN
    (
        SELECT MIN(I.id) as id, S.PreviousId, S.FinishedOn
        FROM Items I
        INNER JOIN
        (
            SELECT I.PreviousId, MIN(nxt.FinishedOn) AS FinishedOn
            FROM dbo.Items I
            LEFT OUTER JOIN dbo.Operations AS nxt ON I.OperationId = nxt.Id
            GROUP BY I.PreviousId
        ) AS S ON I.PreviousId = S.PreviousId 
        GROUP BY S.PreviousId, S.FinishedOn
    ) AS nextOperation ON nextOperation.PreviousId = currItem.Id

    WHERE currOperation.Finished = 1 AND currItem.Denormalized = 0
),

RecursionInitialization AS
(
    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,
            currItem.Id AS BranchID,
            COALESCE (C.PrevComputed, C.CurrComputed) AS CreatedOn,
            COALESCE (C.PrevComputed, CAST(0 AS BIGINT)) AS RecoveredOn,
            COALESCE (C.PrevComputed, CAST(0 AS BIGINT)) AS UpdatedOnPrev,
            C.CurrComputed AS UpdatedOnCurr,
            COALESCE (C.NextComputed, CAST(8640000000000000 AS BIGINT)) AS UpdatedOnNext,
            C.NextId AS UpdatedOnNextId,

            0 AS RecursionLevel

    FROM Items AS currItem
    INNER JOIN Computed AS C ON currItem.Id = C.Id
    WHERE currItem.Denormalized = 0

    UNION ALL

    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,
            currItem.BranchId,
            currItem.CreatedOn,
            currItem.RecoveredOn,
            currItem.UpdatedOnPrev,
            currItem.UpdatedOnCurr,
            currItem.UpdatedOnNext,
            currItem.UpdatedOnNextId,

            0 AS RecursionLevel

    FROM Items AS currItem
    WHERE currItem.Denormalized = 1
),
Recursion AS
(
    SELECT *
    FROM RecursionInitialization AS currItem

    UNION ALL

    SELECT  currItem.Id,
            currItem.PreviousId,
            currItem.UUID,
            currItem.Json,
            currItem.TableName,
            currItem.OperationId,
            currItem.PermissionId,
            currItem.Denormalized,

            CASE
                WHEN prevItem.UpdatedOnNextId = currItem.Id
                THEN prevItem.BranchID
                ELSE currItem.Id
            END AS BranchID,

            prevItem.CreatedOn AS CreatedOn,

            CASE
                WHEN prevItem.Json IS NULL
                THEN CASE
                            WHEN currItem.Json IS NULL
                            THEN prevItem.RecoveredOn
                            ELSE C.CurrComputed
                        END
                ELSE prevItem.RecoveredOn
            END AS RecoveredOn,

            prevItem.UpdatedOnCurr AS UpdatedOnPrev,

            C.CurrComputed AS UpdatedOnCurr,

            COALESCE (C.NextComputed, CAST(8640000000000000 AS BIGINT)) AS UpdatedOnNext,

            C.NextId,

            prevItem.RecursionLevel + 1 AS RecursionLevel
    FROM Items currItem
    INNER JOIN Computed C ON currItem.Id = C.Id
    INNER JOIN Recursion AS prevItem ON currItem.PreviousId = prevItem.Id
    WHERE currItem.Denormalized = 0
)
SELECT  item.Id,
        item.PreviousId,
        item.UUID,
        item.Json,
        item.TableName,
        item.OperationId,
        item.PermissionId,
        item.Denormalized,
        item.BranchID,
        item.CreatedOn,
        item.RecoveredOn,
        item.UpdatedOnPrev,
        item.UpdatedOnCurr,
        item.UpdatedOnNext,
        item.UpdatedOnNextId

FROM Recursion AS item
INNER JOIN
(
    SELECT Id, MAX(RecursionLevel) AS Recursion
    FROM Recursion AS item
    GROUP BY Id
) AS nested ON item.Id = nested.Id AND item.RecursionLevel = nested.Recursion
OPTION (MERGE JOIN)

set nocount oFF 
set statistics io OFF
set statistics time OFF

введите описание изображения здесь

Обратите внимание, что вы не можете использовать подсказки запросов в представлении, поэтому вам нужно найти альтернативу сделать ваше представление в качестве SP или любого обходного пути

Кин Шах
источник
1
Большое спасибо за это, учитывая, что этот вопрос далек от стандартов stackoverflow, это делает ваши усилия вдвойне ценными для меня. Я сделаю свою домашнюю работу на CROSS APPLY и постараюсь выяснить ВАРИАНТ (MERGE JOIN). Сейчас не очевидно, в чем проблема с этим запросом, однако я вполне уверен, что я это
выясню,
@ Lu4 Проблема в том, что оптимизатор запросов не выбирает (или не генерирует) лучший план выполнения. В этом случае подсказка запроса «стимулирует» оптимизатор использовать определенную стратегию для реализации объединения. Посмотрите Подсказки Соединения (Transact-SQL) для получения дополнительной информации.
Кенни Эвитт
CROSS APPLYэто здорово, но я бы посоветовал прочитать планы выполнения и проанализировать их, прежде чем пытаться использовать подсказки запросов.
Кенни Эвитт