Multiple Row_Number() Calls in a Single SQL Query

Question

Hi Everyone,

I'm trying to setup some data to calculate multiple medians in SQL Server 2008, but I'm having a performance problem. Right now, I'm using this pattern ([another example bottom). Yes, I'm not using a CTE, but using one won't fix the problem I'm having anyways and the performance is poor because the row_number sub-queries run in serial, not parallel.

Here's a full example. Below the SQL I explain the problem more.

-- build the example table    

CREATE TABLE #TestMedian (
    StateID INT,
    TimeDimID INT,
    ConstructionStatusID INT,

    PopulationSize BIGINT,
    SquareMiles BIGINT
);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 100000, 200000);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 200000, 300000);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 300000, 400000);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 100000, 200000);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 250000, 300000);

INSERT INTO #TestMedian (StateID, TimeDimID, ConstructionStatusID, PopulationSize, SquareMiles)
VALUES (1, 1, 1, 350000, 400000);

--TruNCATE TABLE TestMedian

    SELECT
     StateID
     ,TimeDimID
     ,ConstructionStatusID
     ,NumberOfRows = COUNT(*) OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID)
     ,PopulationSizeRowNum = ROW_NUMBER() OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID ORDER BY PopulationSize)
     ,SquareMilesRowNum = ROW_NUMBER() OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID ORDER BY SquareMiles)
     ,PopulationSize
     ,SquareMiles
    INTO #MedianData
    FROM #TestMedian

    SELECT MinRowNum = MIN(PopulationSizeRowNum), MaxRowNum = MAX(PopulationSizeRowNum), StateID, TimeDimID, ConstructionStatusID, MedianPopulationSize= AVG(PopulationSize) 
    FROM #MedianData T
    WHERE PopulationSizeRowNum IN((NumberOfRows + 1) / 2, (NumberOfRows + 2) / 2)
    GROUP BY StateID, TimeDimID, ConstructionStatusID

    SELECT MinRowNum = MIN(SquareMilesRowNum), MaxRowNum = MAX(SquareMilesRowNum), StateID, TimeDimID, ConstructionStatusID, MedianSquareMiles= AVG(SquareMiles) 
    FROM #MedianData T
    WHERE SquareMilesRowNum IN((NumberOfRows + 1) / 2, (NumberOfRows + 2) / 2)
    GROUP BY StateID, TimeDimID, ConstructionStatusID


    DROP TABLE #MedianData
    DROP TABLE #TestMedian

The problem with this query is that SQL Server executes both of the "ROW__NUMBER() OVER..." sub-queries in serial, not in parallel. So if I have 10 of these ROW__NUMBER calculations, it'll calculate them one after the other and I get linear growth, which stinks. I have an 8-way 32GB system I'm running this query on and I would love some parallelism. I'm trying to run this type of query on a 5,000,000 row table.

I can tell its doing this by looking at the query plan and seeing the Sorts in the same execution path (displaying the query plan's XML wouldn't work real well on SO).

So my question is this: How can I alter this query so that the ROW_NUMBER queries are executed in parallel? Is there a completely different technique I can use to prepare the data for multiple median calculations?

Answer 1

Each ROW_NUMBER requires the rows to be sorted first. Since your two RNs have different ORDER BY conditions, the query must produce the result, then order it for first RNs (it may be orderred already by), produce the RN, then order it for second RN and produce the second RN result. There simply isn't any magic pixie dust that can materialize a row number value without counting where the row is in the required order.

Answer 2

I am not sure that it can parallelize this, because it needs to do nonpartitioned (wrt population vs square miles) scans. They'll conflict with each on disk, so it has to get everything into memory at least once, first and then it might be eligible for parallelizing, if it's big enough.

In any event, the following performs significantly (40%) faster for me:

;WITH cte AS (
    SELECT
        StateID
        ,TimeDimID
        ,ConstructionStatusID
        ,NumberOfRows = COUNT(*) OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID)
        ,PopulationSizeRowNum = ROW_NUMBER() OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID ORDER BY PopulationSize)
        ,SquareMilesRowNum = ROW_NUMBER() OVER (PARTITION BY StateID, TimeDimID, ConstructionStatusID ORDER BY SquareMiles)
        ,PopulationSize
        ,SquareMiles
    FROM TestMedian
)
, ctePop AS (
    SELECT MinPopNum = MIN(PopulationSizeRowNum)
    , MaxPopNum = MAX(PopulationSizeRowNum)
    , StateID, TimeDimID, ConstructionStatusID
    , MedianPopulationSize= AVG(PopulationSize) 
    FROM cte T
    WHERE PopulationSizeRowNum IN((NumberOfRows + 1) / 2, (NumberOfRows + 2) / 2)
    GROUP BY StateID, TimeDimID, ConstructionStatusID
)
, cteSqM AS (
    SELECT MinSqMNum = MIN(SquareMilesRowNum)
    , MaxSqMNum = MAX(SquareMilesRowNum)
    , StateID, TimeDimID, ConstructionStatusID
    , MedianSquareMiles= AVG(SquareMiles) 
    FROM cte T
    WHERE SquareMilesRowNum IN((NumberOfRows + 1) / 2, (NumberOfRows + 2) / 2)
    GROUP BY StateID, TimeDimID, ConstructionStatusID
)
SELECT s.StateID, s.TimeDimID, s.ConstructionStatusID
, MinPopNum, MaxPopNum, MedianPopulationSize
, MinSqMNum, MaxSqMNum, MedianSquareMiles
FROM ctePop p
JOIN cteSqM s ON s.StateID = p.StateID
    AND s.TimeDimID = p.TimeDimID
    AND s.ConstructionStatusID = p.ConstructionStatusID

Also, the sorts themselves should get parallelized once they get big enough. You'll need test rows at least 100,000 before that might happen though.

---

OK, yep, I get parallelism after I load it up enough with this statement:

INSERT INTO TestMedian 
SELECT abs(id)%3,abs(id)%2,abs(id)%5, abs(id), colid * 10000
  From master.sys.syscolumns, (select top 10 * from master.dbo.spt_values)a

Answer 3

Some lateral thinking: If you need this data often and/or quickly, and the underlying data set doesn't change frequently (for reasonably high values of "frequently"), could you precalculate any of these values and store them in some form of pre-aggregated table?

(Yep, this is demonormalization, but if you need performance over all else, it's worth considering.)