Problem z wydajnością kwerend rekurencyjnych [zamknięty]

9

Po raz szósty próbuję zadać to pytanie i jest ono również najkrótsze. Wszystkie poprzednie próby skutkowały czymś bardziej podobnym do postu na blogu niż samym pytaniem, ale zapewniam cię, że mój problem jest prawdziwy, po prostu dotyczy jednego dużego tematu i bez tych wszystkich szczegółów, które zawiera to pytanie, będzie nie jest jasne, jaki jest mój problem. A więc proszę ...

Abstrakcyjny

Posiadam bazę danych, która pozwala na przechowywanie danych w fantazyjny sposób i zapewnia kilka niestandardowych funkcji wymaganych przez mój proces biznesowy. Dostępne są następujące funkcje:

  1. Nieniszczące i nieblokujące aktualizacje / usuwania realizowane za pomocą metody wstawiania, która umożliwia odzyskiwanie danych i automatyczne rejestrowanie (każda zmiana jest powiązana z użytkownikiem, który ją wprowadził)
  2. Dane multiwersji (może istnieć kilka wersji tych samych danych)
  3. Uprawnienia na poziomie bazy danych
  4. Ostateczna zgodność ze specyfikacją ACID i bezpieczne transakcje tworzy / aktualizuje / usuwa
  5. Możliwość przewijania do tyłu lub do przodu bieżącego widoku danych w dowolnym momencie.

Mogą istnieć inne funkcje, o których zapomniałem wspomnieć.

Struktura bazy danych

Wszystkie dane użytkownika są przechowywane w Itemstabeli jako ciąg znaków ( ntext) zakodowany w JSON . Wszystkie operacje na bazach danych są przeprowadzane za pomocą dwóch procedur składowanych GetLatesti InsertSnashotpozwalają one operować na danych podobnych do tego, w jaki sposób GIT obsługuje pliki źródłowe.

Dane wynikowe są połączone (JOINed) na interfejsie użytkownika w postaci w pełni połączonego wykresu, więc w większości przypadków nie ma potrzeby wykonywania zapytań do bazy danych.

Możliwe jest również przechowywanie danych w zwykłych kolumnach SQL zamiast przechowywania ich w postaci zakodowanej w Json. Jednak to zwiększa ogólne obciążenie złożoności.

Odczytywanie danych

GetLatestwyniki z danymi w postaci instrukcji, wyjaśnij poniższy schemat :

Schemat struktury

Diagram pokazuje ewolucję zmian, które kiedykolwiek zostały wprowadzone w jednym rekordzie. Strzałki na diagramie pokazują wersję, na podstawie której dokonano edycji (Wyobraź sobie, że użytkownik aktualizuje niektóre dane offline, równolegle z aktualizacjami dokonanymi przez użytkownika online, taki przypadek wprowadziłby konflikt, czyli zasadniczo dwie wersje danych zamiast jednego).

Wywołanie GetLatestw następujących przedziałach czasowych wejściowych spowoduje następujące wersje rekordów:

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.

W celu GetLatestwspierania takiego wydajnego interfejsu każdy zapis powinien zawierać specjalne atrybuty serwisowych BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextIdktóre są wykorzystywane przez GetLatestdowiedzieć się, czy rekord przypada odpowiednio w przedziale czasu przewidzianym dla GetLatestargumentów

Wstawianie danych

W celu zapewnienia ostatecznej spójności, bezpieczeństwa i wydajności transakcji dane są wprowadzane do bazy danych za pomocą specjalnej procedury wielostopniowej.

  1. Dane są po prostu wstawiane do bazy danych, bez możliwości zapytania przez GetLatestprocedurę przechowywaną.

  2. Dane są udostępniane dla GetLatestprocedury przechowywanej, dane są udostępniane w stanie znormalizowanym (tj. denormalized = 0). Podczas gdy dane są w stanie znormalizowanym, pola serwisowe BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextIdsą obliczane, który jest bardzo powolny.

  3. Aby przyspieszyć proces, dane są denormalizowane, gdy tylko zostaną udostępnione do GetLatestprocedury składowanej.

    • Ponieważ kroki 1, 2, 3 przeprowadzane w ramach różnych transakcji, może wystąpić awaria sprzętu w trakcie każdej operacji. Pozostawienie danych w stanie pośrednim. Taka sytuacja jest normalna i nawet jeśli tak się stanie, dane zostaną wyleczone w ramach następnego InsertSnapshotpołączenia. Kod dla tej części można znaleźć pomiędzy krokami 2 i 3 InsertSnapshotprocedury składowanej.

Problem

Nowe funkcje (wymagane przez biznes) zmusiły mnie do zmiany specjalnego Denormalizerwidoku, który łączy wszystkie funkcje razem i jest używany zarówno do, jak GetLatesti do InsertSnapshot. Potem zacząłem mieć problemy z wydajnością. Jeśli pierwotnie został SELECT * FROM Denormalizerwykonany w ułamku sekundy, teraz przetworzenie 10000 rekordów zajmuje prawie 5 minut.

Nie jestem profesjonalistą DB i zajęło mi prawie sześć miesięcy, aby wyjść z obecną strukturą bazy danych. Spędziłem dwa tygodnie, najpierw dokonując refaktoryzacji, a następnie próbując dowiedzieć się, jaka jest podstawowa przyczyna mojego problemu z wydajnością. Po prostu nie mogę tego znaleźć. Zapewniam kopię zapasową bazy danych (którą można znaleźć tutaj), ponieważ schemat (ze wszystkimi indeksami) jest dość duży, aby zmieścił się w SqlFiddle, baza danych zawiera również przestarzałe dane (ponad 10000 rekordów), których używam do celów testowych . Dostarczam również tekst do Denormalizerpodglądu, który został zrefaktoryzowany i stał się boleśnie powolny:

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

Pytania)

Pod uwagę brane są dwa scenariusze, przypadki zdenormalizowane i znormalizowane:

  1. Patrząc na oryginalną kopię zapasową, co sprawia, że SELECT * FROM Denormalizertak boleśnie powolne, wydaje mi się, że jest problem z rekurencyjną częścią widoku Denormalizera, próbowałem ograniczyć, denormalized = 1ale nie moje działania wpłynęły na wydajność.

  2. Po uruchomieniu UPDATE Items SET Denormalized = 0sensownie GetLatesti SELECT * FROM Denormalizerprowadzony w (pierwotnie uważano) powolny scenariusz, czy istnieje sposób, aby przyspieszyć, gdy jesteśmy obliczeniowych pól serwisowych BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext,UpdatedOnNextId

Z góry dziękuję

PS

Staram się trzymać standardowego SQL, aby zapytanie było łatwo przenośne w innych bazach danych, takich jak MySQL / Oracle / SQLite na przyszłość, ale jeśli nie ma standardowego kodu SQL, to może pomóc mi trzymać się konstrukcji specyficznych dla bazy danych.

Lu4
źródło
1
W odniesieniu do standardowego SQL i wymienionych DB: używasz CTE tutaj i nie są one obsługiwane przez mySQL, a między głównymi implementacjami występują pewne różnice w składni. Są one również ogrodzeniem optymalizacyjnym w postgresie, co może być dużym problemem w zakresie wydajności. Nic z tego nie powinno powstrzymywać Cię od korzystania z nich, ponieważ drzewo w formie „listy sąsiedztwa” są zwykle właściwym narzędziem do pracy, ale tam, gdzie liczy się kompatybilność, należy wziąć pod uwagę te kwestie, zanim cię ugryzą, abyś mógł być przygotowany na każdą dodatkową pracę potrzebną, gdy migracja do innych DBMS stanie się rzeczywistością.
David Spillett
Dziękuję, staram się jak najbardziej trzymać standardowego SQL. Powodem tego jest to, że uważam, że powinno to zmniejszyć liczbę problemów w przyszłości, kiedy będzie wymagana migracja istniejącego kodu do innych baz danych. Nie zawsze jest to możliwe. Istnieje również czynnik czasu, który jest częścią równania. Spędziłem pół roku, ustalając aktualną strukturę bazy danych ... Chciałbym, aby zawierała tylko standardowe konstrukcje, ale jeśli zajmie to 10 lat, nie jest to właściwa droga ... Więc jeśli zobaczysz, że jest więcej możliwe standardowe refaktoryzacje Z przyjemnością to zaakceptuję ...
Lu4
1
Nie, to brzmi jak pragmatyczny sposób radzenia sobie z różnymi priorytetami i komplikacjami w takich przypadkach. Właśnie wyrzuciłem mózg na myśl, które przyszły mi na myśl na wypadek, gdybyś jeszcze ich nie spotkał (lepiej wiedzieć teraz, nawet jeśli nie jest to możliwe / praktyczne, aby coś z tym zrobić w tej chwili, niż dać się zaskoczyć podczas produkcji! ).
David Spillett

Odpowiedzi:

9

@ Lu4 .. Głosowałem za zamknięciem tego pytania jako „Tip of Iceberg”, ale używając podpowiedzi zapytania, będziesz mógł uruchomić je w ciągu 1 sekundy. To zapytanie może zostać refaktoryzowane i można z niego korzystać CROSS APPLY, ale będzie to koncert konsultacyjny, a nie odpowiedź na stronie pytań i odpowiedzi.

Twoje zapytanie w tej formie będzie działać przez ponad 13 minut na moim serwerze z 4 procesorami i 16 GB pamięci RAM.

wprowadź opis zdjęcia tutaj

Zmieniłem zapytanie, aby było używane OPTION(MERGE JOIN)i działało poniżej 1 sekundy

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

wprowadź opis zdjęcia tutaj

Pamiętaj, że w widoku nie można używać wskazówek dotyczących zapytań, dlatego należy wymyślić alternatywę dla utworzenia widoku jako SP lub dowolnego obejścia

Kin Shah
źródło
1
dziękuję bardzo za to, biorąc pod uwagę, że pytanie jest dalekie od standardów przepełnienia stosu, sprawia, że ​​twój wysiłek jest dla mnie dwukrotnie cenny. Odrobię pracę domową na aplikacji CROSS APPLY i spróbuję wymyślić OPCJĘ (POŁĄCZ ŁĄCZENIE). Teraz nie jest oczywiste, na czym polega problem z tym zapytaniem, ale jestem pewien, że to
rozwiążę,
@ Lu4 Problem polega na tym, że optymalizator zapytań nie wybiera (ani nie generuje) najlepszego planu wykonania. Wskazówka dotycząca kwerendy w tym przypadku „zachęca” optymalizatora do zastosowania określonej strategii do implementacji sprzężenia. Aby uzyskać więcej informacji, zobacz Wskazówki dotyczące dołączania (Transact-SQL) .
Kenny Evitt,
CROSS APPLYjest świetny, ale proponuję przeczytać o planach wykonania i analizować je przed próbą skorzystania ze wskazówek dotyczących zapytań.
Kenny Evitt