Problema de desempenho da consulta sql recursiva [fechado]

9

Esta é a sexta vez que estou tentando fazer essa pergunta e é a mais curta também. Todas as tentativas anteriores resultaram em algo mais semelhante a uma postagem do blog do que à pergunta em si, mas garanto que meu problema é real, mas diz respeito apenas a um grande assunto e, sem todos os detalhes contidos nessa pergunta, será não está claro qual é o meu problema. Então aqui vai ...

Resumo

Eu tenho um banco de dados, ele permite armazenar dados de maneira extravagante e fornece vários recursos não padrão exigidos pelo meu processo de negócios. Os recursos são os seguintes:

  1. Atualizações / exclusões não destrutivas e sem bloqueio, implementadas por meio de abordagem somente inserção, que permite a recuperação de dados e o log automático (cada alteração é vinculada ao usuário que fez essa alteração)
  2. Dados de várias versões (pode haver várias versões dos mesmos dados)
  3. Permissões no nível do banco de dados
  4. Consistência eventual com a especificação ACID e criação / atualização / exclusão segura de transações
  5. Capacidade de retroceder ou avançar rapidamente sua visão atual dos dados para qualquer ponto no tempo.

Pode haver outros recursos que eu esqueci de mencionar.

Estrutura de banco de dados

Todos os dados do usuário são armazenados na Itemstabela como string codificada em JSON ( ntext). Todas as operações do banco de dados são realizadas por meio de dois procedimentos armazenados GetLateste InsertSnashotpermitem operar com dados semelhantes ao modo como o GIT opera os arquivos de origem.

Os dados resultantes são vinculados (JOIN) no frontend em um gráfico totalmente vinculado, portanto, na maioria dos casos, não é necessário fazer consultas ao banco de dados.

Também é possível armazenar dados em colunas SQL regulares em vez de armazená-los no formato codificado por Json. No entanto, isso aumenta a complexidade geral.

Lendo dados

GetLatestresultados com dados em forma de instruções, considere o seguinte diagrama para explicação:

Diagrama de estrutura

O diagrama mostra uma evolução das mudanças que já foram feitas em um único registro. As setas no diagrama mostram a versão com base na qual a edição ocorreu (imagine que o usuário esteja atualizando alguns dados offline, paralelamente às atualizações que foram feitas pelo usuário online, nesse caso, seria introduzido conflito, que é basicamente duas versões dos dados em vez de um).

Portanto, a chamada GetLatestnos seguintes intervalos de tempo de entrada resultará nas seguintes versões de registro:

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.

A fim de GetLatestapoiar essa interface de eficiência cada registro deve conter atributos de serviços especiais BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextIdque são usados por GetLatestdescobrir se o registro cai adequadamente para o período de tempo previsto GetLatestargumentos

Inserindo dados

Para dar suporte à eventual consistência, segurança e desempenho das transações, os dados são inseridos no banco de dados através de um procedimento especial de vários estágios.

  1. Os dados são inseridos no banco de dados sem poderem ser consultados pelo GetLatestprocedimento armazenado.

  2. Os dados são disponibilizados para o GetLatestprocedimento armazenado, os dados são disponibilizados no estado normalizado (ou seja denormalized = 0). Enquanto os dados estão no estado normalizado, os campos de serviço BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextIdestão sendo calculado que é realmente lento.

  3. Para agilizar as coisas, os dados estão sendo desnormalizados assim que são disponibilizados para o GetLatestprocedimento armazenado.

    • Como as etapas 1,2,3 foram realizadas em transações diferentes, é possível que ocorra uma falha de hardware no meio de cada operação. Deixando dados em um estado intermediário. Essa situação é normal e, mesmo que isso aconteça, os dados serão recuperados na próxima InsertSnapshotchamada. O código para esta parte pode ser encontrado entre as etapas 2 e 3 do InsertSnapshotprocedimento armazenado.

O problema

A novas funcionalidades (exigidos pelo negócio) me obrigou a refazer especial Denormalizervista que os laços-up todas as características juntos e é usado tanto para GetLateste InsertSnapshot. Depois disso, comecei a ter problemas de desempenho. Se originalmente SELECT * FROM Denormalizerexecutado apenas em frações de segundo, agora leva cerca de 5 minutos para processar 10000 registros.

Eu não sou um profissional de banco de dados e levei quase seis meses apenas para lançar a estrutura de banco de dados atual. E passei duas semanas primeiro fazendo as refatorações e depois tentando descobrir qual é a causa raiz do meu problema de desempenho. Eu simplesmente não consigo encontrá-lo. Estou fornecendo o backup do banco de dados (que você pode encontrar aqui) porque o esquema (com todos os índices) é bastante grande para caber no SqlFiddle, o banco de dados também contém dados obsoletos (mais de 10000 registros) que estou usando para fins de teste . Também estou fornecendo o texto para Denormalizerexibição que foi refatorado e ficou dolorosamente lento:

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

As questões)

Há dois cenários que são levados em consideração, os casos desnormalizados e normalizados:

  1. Olhando para o backup original, o que torna a SELECT * FROM Denormalizertarefa tão dolorosamente lenta, sinto que há um problema com parte recursiva da exibição Denormalizer, tentei restringir, denormalized = 1mas algumas das minhas ações afetaram o desempenho.

  2. Depois de executar o UPDATE Items SET Denormalized = 0que faria GetLateste SELECT * FROM Denormalizercorrer para (originalmente pensado para ser) cenário de lenta, há uma maneira de acelerar as coisas quando estamos computação campos de serviços BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext,UpdatedOnNextId

Agradeço antecipadamente

PS

Estou tentando aderir ao SQL padrão para tornar a consulta facilmente portável para outros bancos de dados como MySQL / Oracle / SQLite para o futuro, mas se não houver um sql padrão que possa ajudar, estou bem em aderir a construções específicas do banco de dados.

Lu4
fonte
11
Com relação ao SQL padrão e aos DBs que você lista: você está usando um CTE aqui e eles não são suportados pelo mySQL e há algumas variações de sintaxe entre as principais implementações. Eles também são uma barreira de otimização no postgres atualmente, o que pode ser uma grande preocupação de desempenho. Nada disso deve impedi-lo de usá-los. Com uma árvore em forma de "lista de adjacências", eles geralmente são a ferramenta certa para o trabalho, mas onde a compatibilidade é uma preocupação, esses pontos são coisas que você deve saber antes de mordê-lo para que você possa ser preparado para qualquer trabalho extra necessário quando a migração para outros DBMSs se tornar realidade.
David Spillett
Obrigado, estou tentando manter o SQL padrão o máximo possível. A razão para isso é que acredito que deve reduzir a quantidade de problemas no futuro, quando será necessário migrar o código existente para outros bancos de dados. Nem sempre é possível. Também há fator de tempo que faz parte da equação. Passei meio ano estabelecendo a estrutura atual do banco de dados ... Gostaria que ele contenha construções apenas padrão, mas se isso exigir mais 10 anos, não é o caminho a seguir ... Então, se você perceber que há mais refactoring padrão possível eu vou ser feliz em aceitá-la ...
LU4
11
Não, isso parece uma maneira pragmática de lidar com as diferentes prioridades e complicações em casos como esse. Eu acabei de despejar os problemas que me vieram à mente, caso você ainda não os tivesse encontrado (é melhor saber agora, mesmo que não seja possível / prático fazer algo sobre isso agora, do que ser mordido de surpresa na produção! )
David Spillett 24/09

Respostas:

9

@ Lu4 .. Votei para fechar esta pergunta como "Tip of Iceberg", mas usando a dica de consulta, você poderá executá-la em menos de 1 segundo. Essa consulta pode ser refatorada e pode ser usada CROSS APPLY, mas será um trabalho de consultoria e não como resposta em um site de perguntas e respostas.

Sua consulta como está será executada por mais de 13 minutos no meu servidor com 4 CPU e 16 GB de RAM.

insira a descrição da imagem aqui

Alterei sua consulta para uso OPTION(MERGE JOIN)e ela foi executada em menos de 1 segundo

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

insira a descrição da imagem aqui

Observe que você não pode usar dicas de consulta em uma exibição, portanto, é necessário descobrir uma alternativa de torná-la um SP ou qualquer solução alternativa.

Kin Shah
fonte
11
muito obrigado por isso, tendo em conta que a questão está longe dos padrões de stackoverflow, torna seu esforço duas vezes valioso para mim. Farei minha lição de casa no CROSS APPLY e tentarei descobrir a OPÇÃO (MERGE JOIN). A sua não é óbvio agora que parece ser o problema com essa consulta no entanto eu tenho certeza que eu vou descobrir isso, obrigado mais uma vez
LU4
@ Lu4 O problema é que o otimizador de consultas não está escolhendo (ou gerando) o melhor plano de execução. A dica de consulta neste caso 'incentiva' o otimizador a usar uma estratégia específica para implementar a junção. Consulte Dicas de junção (Transact-SQL) para obter mais detalhes.
precisa saber é o seguinte
CROSS APPLYé ótimo, mas eu sugiro ler os planos de execução e como analisá-los antes de tentar usar as dicas de consulta.
precisa saber é o seguinte