Effective T-SQL for Median

  • Is this an effective way to find median?

    CREATE TABLE #T (i TINYINT);

    GO

    INSERT INTO #T

    SELECT ABS(CHECKSUM(NEWID())) % 250

    GO 1000

    ;WITH t AS (SELECT i, ROW_NUMBER() OVER (ORDER BY i) AS n, count(*) OVER (PARTITION BY (SELECT NULL)) AS c FROM #T)

    SELECT

    AVG(i) AS Median

    FROM t

    WHERE

    ( c % 2 = 1 AND n = ((c-1)/2)+1 )

    OR (c % 2 = 0 AND (n = c / 2 OR n = c / 2 + 1))

  • Last week I came up with this option. I haven't made performace tests. Maybe you could help me with that.

    DECLARE @test-2TABLE(

    myintint)

    INSERT INTO @test-2 VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9);

    WITH CTE AS(

    SELECT myint,

    NTILE( 2) OVER( ORDER BY myint) tile

    FROM @test-2

    )

    SELECT CASE WHEN SUM( CASE WHEN tile = 1 THEN 1 END) = SUM( CASE WHEN tile = 2 THEN 1 END)

    THEN (MAX( CASE WHEN tile = 1 THEN myint END) + MIN( CASE WHEN tile = 2 THEN myint END))/2.0

    ELSE MAX( CASE WHEN tile = 1 THEN myint END) END

    FROM CTE

    Luis C.
    General Disclaimer:
    Are you seriously taking the advice and code from someone from the internet without testing it? Do you at least understand it? Or can it easily kill your server?

    How to post data/code on a forum to get the best help: Option 1 / Option 2
  • Fortunately for you SQL 2012 has much better Windowing Function support. Look into the PERCENTILE_CONT function. I also HIGHLY recommend you purchase Itzik Ben-Gan's SQL Server 2012 High-Performance TSQL Using Window Functions book.

    Best,
    Kevin G. Boles
    SQL Server Consultant
    SQL MVP 2007-2012
    TheSQLGuru on googles mail service

  • TheSQLGuru (7/30/2013)


    Fortunately for you SQL 2012 has much better Windowing Function support. Look into the PERCENTILE_CONT function. I also HIGHLY recommend you purchase Itzik Ben-Gan's SQL Server 2012 High-Performance TSQL Using Window Functions book.

    This is awesome thanks!

  • dkschill (7/30/2013)


    Is this an effective way to find median?

    CREATE TABLE #T (i TINYINT);

    GO

    INSERT INTO #T

    SELECT ABS(CHECKSUM(NEWID())) % 250

    GO 1000

    ;WITH t AS (SELECT i, ROW_NUMBER() OVER (ORDER BY i) AS n, count(*) OVER (PARTITION BY (SELECT NULL)) AS c FROM #T)

    SELECT

    AVG(i) AS Median

    FROM t

    WHERE

    ( c % 2 = 1 AND n = ((c-1)/2)+1 )

    OR (c % 2 = 0 AND (n = c / 2 OR n = c / 2 + 1))

    First and foremost, for your sample data, don't use GO 1000. You will find a tally table works much better for this kind of thing.

    WITH t(i) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) FROM sys.all_objects)

    INSERT INTO #T

    SELECT ABS(CHECKSUM(NEWID()))%200

    FROM t

    WHERE i<=1000;

    My non-2012 solution is:

    ;WITH t(i,n,c) AS

    ( SELECT i,

    ROW_NUMBER() OVER (ORDER BY i),

    COUNT(*) OVER (PARTITION BY (SELECT NULL))

    FROM #T)

    SELECT

    AVG(i) AS Median

    FROM t

    WHERE (c%2=1 AND n=((c-1)/2)+1) OR (c%2=0 AND (n=c/2 OR n=c/2+1));

    I tested this against Louis' solution (Brilliant use of NTILE BTW) and, though it appears to produce a better query plan (more parallelism, lower est. query cost) it runs about the same speed as what Louis put together (~7 seconds/1 million rows on my crappy test box [4-cpu, 4gb ram test]).

    Edit: code formatting messed up.

    "I cant stress enough the importance of switching from a sequential files mindset to set-based thinking. After you make the switch, you can spend your time tuning and optimizing your queries instead of maintaining lengthy, poor-performing code."

    -- Itzik Ben-Gan 2001

  • Thanks for your reply! I am always looking to learn more.

  • TheSQLGuru (7/30/2013)


    Fortunately for you SQL 2012 has much better Windowing Function support. Look into the PERCENTILE_CONT function. I also HIGHLY recommend you purchase Itzik Ben-Gan's SQL Server 2012 High-Performance TSQL Using Window Functions book.

    Just an interesting FYI...

    I have never used PERCENTILE_CONT but I do have Server 2012 High-Performance TSQL Using Window Functions. With the same sample data from earlier (#T), this is a modified version of Ben-Gan's 2012-based solution using PERCENTILE_COUNT:

    WITH t(r,m) AS

    (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)),

    PERCENTILE_CONT(0.5) WITHIN GROUP(ORDER BY i) OVER(PARTITION BY NULL)

    FROM #T

    )

    SELECT m AS median

    FROM t

    WHERE r=1;

    Though it is much simpler, Ben-Gan's 2012-PERCENTILE_CONT solution is about twice as slow as any other solution posted thus far. Again, just an FYI.

    "I cant stress enough the importance of switching from a sequential files mindset to set-based thinking. After you make the switch, you can spend your time tuning and optimizing your queries instead of maintaining lengthy, poor-performing code."

    -- Itzik Ben-Gan 2001

  • Thanks for the example!

  • The original query can be formulated a little bit more elegantly as this:

    ;WITH t(i,n,c) AS

    ( SELECT i,

    ROW_NUMBER() OVER (ORDER BY i),

    COUNT(*) OVER (PARTITION BY (SELECT NULL))

    FROM #T)

    SELECT

    AVG(i) AS Median

    FROM t

    WHERE 2*n-c BETWEEN 0 AND 2;

    This version should be slightly faster because of the simpler expression in the WHERE clause

    /SG

  • TheSQLGuru (7/30/2013)


    Fortunately for you SQL 2012 has much better Windowing Function support. Look into the PERCENTILE_CONT function. I also HIGHLY recommend you purchase Itzik Ben-Gan's SQL Server 2012 High-Performance TSQL Using Window Functions book.

    +1 great book!

    Need an answer? No, you need a question
    My blog at https://sqlkover.com.
    MCSE Business Intelligence - Microsoft Data Platform MVP

  • Stefan_G (8/1/2013)


    The original query can be formulated a little bit more elegantly as this:

    ;WITH t(i,n,c) AS

    ( SELECT i,

    ROW_NUMBER() OVER (ORDER BY i),

    COUNT(*) OVER (PARTITION BY (SELECT NULL))

    FROM #T)

    SELECT

    AVG(i) AS Median

    FROM t

    WHERE 2*n-c BETWEEN 0 AND 2;

    This version should be slightly faster because of the simpler expression in the WHERE clause

    /SG

    Awesome! I enjoy math; so proving this to myself was a lot of fun. Thanks for the new trick!

  • Alan.B (7/31/2013)


    TheSQLGuru (7/30/2013)


    Fortunately for you SQL 2012 has much better Windowing Function support. Look into the PERCENTILE_CONT function. I also HIGHLY recommend you purchase Itzik Ben-Gan's SQL Server 2012 High-Performance TSQL Using Window Functions book.

    Just an interesting FYI...

    I have never used PERCENTILE_CONT but I do have Server 2012 High-Performance TSQL Using Window Functions. With the same sample data from earlier (#T), this is a modified version of Ben-Gan's 2012-based solution using PERCENTILE_COUNT:

    WITH t(r,m) AS

    (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)),

    PERCENTILE_CONT(0.5) WITHIN GROUP(ORDER BY i) OVER(PARTITION BY NULL)

    FROM #T

    )

    SELECT m AS median

    FROM t

    WHERE r=1;

    Though it is much simpler, Ben-Gan's 2012-PERCENTILE_CONT solution is about twice as slow as any other solution posted thus far. Again, just an FYI.

    Yep, but the book covers other non-2012 solutions for median as well (and has lots of other great stuff in it) so it was definitely worth the recommendation.

    I will add that it is quite amazing how varied solutions to the same problem can be achieved in TSQL, and just as amazing how varied the performance characteristics of those solutions can be!! :w00t:

    Best,
    Kevin G. Boles
    SQL Server Consultant
    SQL MVP 2007-2012
    TheSQLGuru on googles mail service

  • One of the main reasons I love to post here! I will have to check out that book...it was mentioned a number of times yesterday during the 24 Hours of PASS.

  • dkschill (8/1/2013)


    One of the main reasons I love to post here! I will have to check out that book...it was mentioned a number of taps yesterday during the 24 Hours of PASS.

    Personally I think ANYTHING written by Itzik is worth reading and/or having in your SQL Server library! 🙂

    Best,
    Kevin G. Boles
    SQL Server Consultant
    SQL MVP 2007-2012
    TheSQLGuru on googles mail service

Viewing 14 posts - 1 through 13 (of 13 total)

You must be logged in to reply to this topic. Login to reply