9

This is the sixth time I'm trying to ask this question and it's the shortest one too. All the previous attempts were resulting with something more similar to a blog post rather than the question itself, but I assure you that my problem is real, it's just that it concerns one large subject and without all those details that this question contains it will be not clear what my problem is. So here goes...

Abstract

I have a database, it allows storing data in kinda fancy way and provides several non-standard features that are required by my business-process. The features are the following:

  1. Non-destructive and non-blocking updates/deletes implemented via insert-only approach, that allows data recovery and automatic logging (each change is tied up to user who made that change)
  2. Multiversion data (there can be several versions of the same data)
  3. Database-level permissions
  4. Eventual consistency with ACID specification and transaction-safe creates/updates/deletes
  5. Ability to rewind or fast-forward your current view of data to any point in time.

There may be other features that I've forgot to mention.

Database structure

All user data is stored in Items table as JSON encoded string (ntext). All database operations are conducted via two stored procedures GetLatest and InsertSnashot, they allow to operate on data similar to how GIT operates source files.

The resulting data is linked (JOINed) on the frontend into fully linked graph so there is no need in making database queries in most cases.

It's also possible to store data in regular SQL columns instead of storing them in Json encoded form. However that increases the overall complexity strain.

Reading data

GetLatest results with data in form of instructions, consider the following diagram for explanation:

Structure diagram

The diagram shows an evolution of changes that were ever made to a single record. The arrows on the diagram show the version based on which the edit is happened (Imagine that the user is updating some data offline, in parallel to updates that were made by online user, such case would introduce conflict, which is basically two versions of data instead of one).

So calling GetLatest within following input timespans will result with following record versions:

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.

In order for GetLatest to support such efficient interface each record should contain special service attributes BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextId that are used by GetLatest to figure out whether the record falls adequately into the timespan provided for GetLatest arguments

Inserting data

In order to support the eventual consistency, transaction safety and performance, data is inserted into database via special multistage procedure.

  1. The data is just inserted into database without being capable of being queried by GetLatest stored procedure.

  2. The data is made available for the GetLatest stored procedure, the data is made available in normalized (i.e. denormalized = 0) state. While the data is in normalized state, the service fields BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextId are being computed which is really slow.

  3. In order to speed things-up, the data is being denormalized as soon as it is made available for GetLatest stored procedure.

    • Since steps 1,2,3 conducted within different transactions it is possible that a hardware failure may occur in the middle of each operation. Leaving data in an intermediate state. Such situation is normal and even if it will happen, the data will get healed within following InsertSnapshot call. The code for this part can be found in-between steps 2 and 3 of InsertSnapshot stored procedure.

The problem

A new features (required by business) forced me to refactor special Denormalizer view which ties-up all the features together and is used for both GetLatest and InsertSnapshot. After that I've began experiencing performance problems. If originally SELECT * FROM Denormalizer executed just in fractions of second so now it takes nearly 5 minutes to process 10000 records.

I'm not a DB pro and it took me nearly six months just to come out with current database structure. And I have spent two weeks first to make the refactorings and then trying to figure out what's the root cause for my performance problem. I just can't find it. I'm providing the database backup (which you can find here) because the schema (with all the indexes) is rather large to fit into SqlFiddle, the database also contains obsolete data (10000+ records) that I'm using for test purposes. Also I'm providing the text for Denormalizer view that got refactored and became painfully slow:

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

The question(s)

There are two scenarios that are taken into consideration, the denormalized and normalized cases:

  1. Looking to original backup, what makes the SELECT * FROM Denormalizer so painfully slow, I feel like there is a problem with recursive part of the Denormalizer view, I've tried restricting denormalized = 1 but non of my actions affected performance.

  2. After running UPDATE Items SET Denormalized = 0 it would make GetLatest and SELECT * FROM Denormalizer run into (originally thought to be) slow scenario, is there a way to speed things up when we are computing service fields BranchId, RecoveredOn, CreatedOn, UpdatedOnPrev, UpdatedOnCurr, UpdatedOnNext, UpdatedOnNextId

Thank you in advance

PS

I'm trying to stick to standard SQL to make the query easily portable to other databases such as MySQL / Oracle / SQLite for future, but if there is no standard sql that might help I'm ok with sticking to database-specific constructs.

closed as off-topic by Kin Shah, Max Vernon, mustaccio, Colin 't Hart, Paul White Sep 25 '15 at 3:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Tip of the iceberg - the question or comments reveal an underlying issue that would need extensive investigation by a consultant or database vendor support team: issues like this do not fit the SE Q&A model well. For more information see this meta post." – Kin Shah, Max Vernon, mustaccio, Colin 't Hart, Paul White
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    With regard to standard SQL and the DBs you list: you are using a CTE here and they are not supported by mySQL and there are some syntax variations between the major implementations. Also they are an optimisation fence in postgres currently which could be a large performance concern. None of that should stop you using them, with a tree in "adjacency list" form they are usually the right tool for the job, but where compatibility is a concern these points are things to be aware of before they bite you so you can be prepared for any extra work needed when migration to other DBMSs becomes reality. – David Spillett Sep 24 '15 at 11:14
  • Thank you, I'm trying to stick to standard SQL as much as possible. The reason for that is that I believe it should reduce the amount of problems in future, when it will be required to migrate existing code to other Databases. It is not always it is possible. There is also time factor which is part of equation. I've spent half year settling current database structure... I would like it to contain standard-only constructs, but if it will require 10 more years, it's not the way to go... So if you see that there is more standard refactoring possible I will be happy to accept it... – Lu4 Sep 24 '15 at 12:56
  • 1
    No, that sounds like a pragmatic way to deal with the differing priorities and complications in cases like this. I just brain dumped the issues that sprung to mind in case you had not come across them yet (better to know now, even if it isn't possible/practical to do anything about it right now, than be bitten by surprise in production!). – David Spillett Sep 24 '15 at 14:04
9

@Lu4 .. I voted to close this question as "Tip of Iceberg" but using query hint you will be able to run it under 1 sec. This query can be refactored and can use CROSS APPLY, but it will be a consulting gig and not as an answer in a Q&A site.

Your query as is will run for 13+ mins on my server with 4 CPU and 16GB RAM.

enter image description here

I changed your query to use OPTION(MERGE JOIN) and it ran under 1 sec

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

enter image description here

Note that you cannot use query hints in a view, so you have to figure out an alternative of making your view as an SP or any workaround

  • 1
    thank you very much on this, taking into account that the question is far from stackoverflow standards it makes your effort twice valuable for me. I will do my homework on CROSS APPLY and try to figure out the OPTION (MERGE JOIN). Its not obvious now what seems to be the problem with that query however I'm pretty sure that I will figure it out, thank you once again – Lu4 Sep 23 '15 at 23:33
  • @Lu4 The problem is that the query optimizer isn't choosing (or generating) the best execution plan. The query hint in this case 'encourages' the optimizer to use a specific strategy to implement the join. See Join Hints (Transact-SQL) for more details. – Kenny Evitt Sep 24 '15 at 13:47
  • CROSS APPLY is great but I'd suggest reading up on execution plans and how to analyze them before trying to make use of query hints. – Kenny Evitt Sep 24 '15 at 13:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.