Sql-server – Partition by ascending and descending performance

greatest-n-per-groupsql serversql-server-2012

I have a table, and for a given set of fields a, b and c, I need to get the first and last rows ordered by d and e, and am using ROW_NUMBER to get these rows. The relevant part of the statement is…

ROW_NUMBER() OVER (PARTITION BY a,b,c ORDER BY d ASC, e ASC) AS row_number_start,
ROW_NUMBER() OVER (PARTITION BY a,b,c ORDER BY d DESC, e DESC) AS row_number_end

The execution plan shows two sort operations, one for each. These sort operations make up over 60% of the total cost of the statement (we're talking tens of millions of rows here, the partitions will usually have 1-100 records per partition, mostly under 10)

so it would be good if I could get rid of one of them. I tried to create an index to replicate the sort; this eliminated one of the sort operations but not the latter. (Note that any index created would only be of use for this process, and would be recreated daily as part of an ETL process.)

From inspecting the execution plan, I believe the problem is that when doing a partition by statement, SQL Server insists on ordering by the partitioning columns on an ascending basis. Logically it doesn't matter if you order ascending or descending, and if the optimiser understood this then it could just read the same index backwards to work out row_number_end.

Is there any way I can make the optimiser see sense here, or can someone suggest an alternative approach to reach the same end goal?

Best Answer

Example table and index

CREATE TABLE dbo.Test
(
    a integer NOT NULL,
    b integer NOT NULL,
    c integer NOT NULL,
    d integer NOT NULL,
    e integer NOT NULL
);

CREATE INDEX i1 ON dbo.Test (a, b, c, d, e);

1. Apply solution

SELECT
    DT.a,
    DT.b,
    DT.c,
    FL.d,
    FL.e 
FROM 
(
    -- Could be an indexed view
    SELECT
        T.a,
        T.b,
        T.c
    FROM dbo.Test AS T
    GROUP BY
        T.a,
        T.b,
        T.c
) AS DT
CROSS APPLY 
(
    (
        -- First
        SELECT TOP (1)
            T2.d,
            T2.e
        FROM  dbo.Test AS T2
        WHERE
            T2.a = DT.a
            AND T2.b = DT.b
            AND T2.c = DT.c
        ORDER BY
            T2.d ASC,
            T2.e ASC
    )

    UNION ALL

    (
        -- Last
        SELECT TOP (1)
            T3.d,
            T3.e
        FROM  dbo.Test AS T3
        WHERE
            T3.a = DT.a
            AND T3.b = DT.b
            AND T3.c = DT.c
        ORDER BY
            T3.d DESC,
            T3.e DESC
    )
) AS FL;

Execution plan:

Plan

2. Row Numbering Solution

An alternative, possibly better if there are a small number of rows per group on average: (improved based on a suggestion by Martin Smith)

Query

SELECT
    TF.a,
    TF.b,
    TF.c,
    TF.d,
    TF.e
FROM
(
    SELECT
        T.*,
        rn = ROW_NUMBER() OVER (
                PARTITION BY a,b,c 
                ORDER BY d ASC, e ASC)
    FROM dbo.Test AS T
) AS TF
WHERE
    TF.rn = 1

UNION ALL

SELECT
    TL2.a,
    TL2.b,
    TL2.c,
    TL2.d,
    TL2.e
FROM 
(
    -- TOP (max bigint) to allow an ORDER BY in this scope
    SELECT TOP (9223372036854775807)
        TL.a,
        TL.b,
        TL.c,
        TL.d,
        TL.e
    FROM 
    (
        SELECT
            T.*,
            rn = ROW_NUMBER() OVER (
                    PARTITION BY a,b,c 
                    ORDER BY d DESC, e DESC)
        FROM dbo.Test AS T
    ) AS TL
    WHERE
        TL.rn = 1
    ORDER BY
        -- To allow the optimizer to scan the index backward
        -- (Workaround for PARTITION BY being assumed ASC)
        TL.a DESC,
        TL.b DESC,
        TL.c DESC,
        TL.d DESC,
        TL.e DESC
) AS TL2;

Execution plan:

Plan 2

3. Using LEAD

This is based on the idea that the first row is row number 1, and the last row is the row before the row numbered 1:

SELECT
    L.a,
    L.b,
    L.c,
    L.d,
    L.e
FROM 
(
    -- Add LEAD(1) on numbering
    SELECT 
        N.*,
        next_rn = LEAD(N.rn, 1, 1) OVER (
            PARTITION BY N.a, N.b, N.c
            ORDER BY N.d, N.e) 
    FROM 
    (
        -- Numbered
        SELECT
            T.*,
            rn = ROW_NUMBER() OVER (
                PARTITION BY T.a, T.b, T.c
                ORDER BY T.d, T.e) 
        FROM dbo.Test AS T
    ) AS N
) AS L
WHERE
    -- This row is first, or the next one is
    L.rn = 1
    OR L.next_rn = 1;

Execution plan

Plan 3

To summarize the comment discussion:

  • If you need additional columns returned, simply add them to the queries in the appropriate places and ensure they are included in the index.
  • Once created, queries can potentially benefit from indexes many times. With an explicit sort in the execution plan, the sort happens on every execution. Also, index creation sorts are allowed to dynamically acquire more memory as needed; that is not the case for regular sorts - they get a fixed allocation based on optimizer estimates, and that's it. Exceed the allocation, and the sort spills to disk.
  • The apply approach is optimal for relatively large groups. The estimate is 2 rows per iteration but the 'actual' is over all iterations (SSMS design decision). A very large number of iterations is bad for the apply.
Related Question