Does PERCENTILE_CONT still give terrible performance when calculating medians in 2022 versions of SQL Server?

Question

I'm currently reading a book from SQL Server 2014. It, like every other online source that I've found, tells you that PERCENTILE_CONT is a very slow way of calculating medians and does not show the allegedly awful execution plan. Is PERCENTILE_CONT still extremely slow at this task in recent (i.e. 2022 or later) versions of SQL Server?

"Extremely slow" is subjective, so showing that the execution plans don't change between SQL Server 2014 and 2022 will be sufficient. I'd check this myself, but the newest server I have is on the 2012 build.

Answer 1

I presume one of the online sources you refer to is What is the fastest way to calculate the median?

"2012_A" and "2012_B" below refer to queries from that article.

Using similar test data...

CREATE TABLE dbo.obj(id INT IDENTITY(1,1), val INT, PRIMARY KEY (val, id));
 
INSERT dbo.obj(val) 
SELECT TOP (10000000) CRYPT_GEN_RANDOM(3) as val
FROM sys.all_columns AS c 
CROSS JOIN sys.all_objects AS o
CROSS JOIN sys.all_objects AS o2

2012_A with 2014 compat level

Trying on the same SQL Server 2022 instance as the subsequent tests but with the compat level of 120 (SQL Server 2014) took 1 min 56 seconds

--Table 'Worktable'. Scan count 6, logical reads 60127770, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--Table 'obj'. Scan count 1, logical reads 21109, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--CPU time = 82000 ms,  elapsed time = 116489 ms.
SELECT TOP 1 PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY val) OVER () 
FROM dbo.obj
OPTION (USE hint('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_120'))

2012_A in 2022

In SQL Server 2019+ the execution plan can now use batch mode windowed aggregates and this was considerably faster than the previous effort, with an elapsed time of 7.5 seconds, but still is slower than the fastest method proposed in that article (so maybe upgrade this method from "terrible" to "poor") .

--Table 'obj'. Scan count 1, logical reads 21109, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--Table 'Worktable'. Scan count 2, logical reads 918272, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
-- CPU time = 4407 ms,  elapsed time = 7525 ms.
SELECT TOP 1 PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY val) OVER () 
FROM dbo.obj;

PERCENTILE_CONT is implemented as an Analytical function and the entire 10,000,000 source rows are spooled into the right hand Window Aggregate so that they can have the result added onto them once it is calculated. This is inherently going to be resource intensive.

PERCENTILE_CONT couldn't be implemented as a streaming aggregate because you need to read the whole stream to get the count and thus know the rows you care about.

The "winning" method from the SQL Performance article still wins in 2022 - with an elapsed time of around 1 second.

2012_B

--Table 'obj'. Scan count 9, logical reads 21499, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--CPU time = 251 ms,  elapsed time = 133 ms.
DECLARE @c BIGINT = (SELECT COUNT(*) FROM dbo.obj);
 

--Table 'obj'. Scan count 1, logical reads 10567, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--CPU time = 313 ms,  elapsed time = 859 ms.
SELECT  AVG(1.0 * val)
FROM (
    SELECT val FROM dbo.obj
     ORDER BY val
     OFFSET (@c - 1) / 2 ROWS
     FETCH NEXT 1 + (1 - @c % 2) ROWS ONLY
) AS x;

Approximate Result

SQL Server 2022 does include a new aggregate function APPROX_PERCENTILE_CONT though. As this is an aggregate function it does not require an OVER clause - or the TOP 1 I added to the PERCENTILE_CONT query above

--Table 'obj'. Scan count 9, logical reads 21499, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
--CPU time = 4983 ms,  elapsed time = 881 ms.
select APPROX_PERCENTILE_CONT (0.5) WITHIN GROUP (ORDER BY val)
FROM dbo.obj

Whilst the elapsed time was competitive with 2012_B it overall used quite a lot more CPU time and additionally only returns an approximation of the correct result anyway - so for this test I would still prefer 2012_B

Answer 2

Is PERCENTILE_CONT still extremely slow at this task in recent (i.e. 2022 or later) versions of SQL Server?

Yes, it is. None of the percentile facilities are specifically optimized for the median case. The general nature of the implementation (for any percentile, not just 0.5) means it is more flexible, but less efficient than a specific median-only window function or aggregate could be.

---

Using Martin's test data, I found 2012_B ran in about 400ms:

DECLARE @c BIGINT = (SELECT COUNT(*) FROM dbo.obj);

DECLARE @Start datetime2 = SYSUTCDATETIME();

SELECT  AVG(1.0 * val)
FROM (
    SELECT val FROM dbo.obj
     ORDER BY val
     OFFSET (@c - 1) / 2 ROWS
     FETCH NEXT 1 + (1 - @c % 2) ROWS ONLY
) AS x;

SELECT [2012_B] = DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

This can be improved under compatibility level 150 (SQL Server 2019) or later using Batch Mode on Rowstore (BMOR) via a different expression of the same basic algorithm:

DECLARE @c bigint = (SELECT COUNT_BIG(*) FROM dbo.obj);

DECLARE @Start datetime2 = SYSUTCDATETIME();

SELECT 
    IIF
    (
        @c % 2 = 1, 
        SUM(SQ1.val), 
        SUM(SQ1.val) * 5e-1
    ) 
FROM 
(
    SELECT TOP (1 + (1 - @c % 2))
        A.val
    FROM 
    (
        SELECT 
            O.val, 
            rn = ROW_NUMBER() OVER (ORDER BY O.val ASC)
        FROM dbo.obj AS O
    ) AS A
    WHERE
        A.rn >= ((@c - 1) / 2)
    ORDER BY
        A.rn
) AS SQ1;

SELECT BMOR = DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

This implementation runs in around 275ms, with all the expensive operations using batch mode processing (blue highlight).

Note BMOR requires Enterprise Edition or equivalent.