Qual é a maneira mais rápida de calcular a mediana?

CREATE TABLE dbo.EvenRows ( id INT PRIMARY KEY, val INT );
CREATE TABLE dbo.OddRows  ( id INT PRIMARY KEY, val INT );
 
INSERT dbo.EvenRows(id,val) 
          SELECT 1, 6
UNION ALL SELECT 2, 11
UNION ALL SELECT 3, 4
UNION ALL SELECT 4, 4
UNION ALL SELECT 5, 15
UNION ALL SELECT 6, 14
UNION ALL SELECT 7, 4
UNION ALL SELECT 8, 9;
 
INSERT dbo.OddRows(id,val)
          SELECT 1, 6
UNION ALL SELECT 2, 11
UNION ALL SELECT 3, 4
UNION ALL SELECT 4, 4
UNION ALL SELECT 5, 15
UNION ALL SELECT 6, 14
UNION ALL SELECT 7, 4;
 
DECLARE @Median DECIMAL(12, 2);

SQL Server 2000

2000_A – máximo de uma metade, mínimo da outra


Essa abordagem pega o valor mais alto dos primeiros 50%, o valor mais baixo dos últimos 50% e os divide por dois. Isso funciona para linhas pares ou ímpares porque, no caso par, os dois valores são as duas linhas do meio e, no caso ímpar, os dois valores são, na verdade, da mesma linha.


SELECT @Median = (
   (SELECT MAX(val) FROM
     (SELECT TOP 50 PERCENT val 
      FROM dbo.EvenRows ORDER BY val, id) AS t)
 + (SELECT MIN(val) FROM
     (SELECT TOP 50 PERCENT val 
      FROM dbo.EvenRows ORDER BY val DESC, id DESC) AS b)
) / 2.0;

2000_B – #tabela temporária


Este exemplo primeiro cria uma tabela #temp e, usando o mesmo tipo de matemática acima, determina as duas linhas "intermediárias" com a ajuda de uma IDENTITY contígua coluna ordenada pela coluna val. (A ordem de atribuição de IDENTITY os valores só podem ser confiáveis ​​por causa do MAXDOP contexto.)


CREATE TABLE #x
(
  i    INT IDENTITY(1,1),
  val  DECIMAL(12, 2)
);
 
CREATE CLUSTERED INDEX v ON #x(val);
 
INSERT #x(val)
  SELECT val 
  FROM dbo.EvenRows
  ORDER BY val OPTION (MAXDOP 1);
 
SELECT @Median = AVG(val) 
  FROM #x AS x 
  WHERE EXISTS
  (
    SELECT 1 
      FROM #x 
      WHERE x.i - (SELECT  MAX(i) / 2.0 FROM #x) IN (0, 0.5, 1)
  );

SQL Server 2005, 2008, 2008 R2

2005_A – números de linha de duelo


Este exemplo usa ROW_NUMBER() para subir e descer os valores uma vez em cada direção e, em seguida, encontra o "meio" uma ou duas linhas com base nesse cálculo. Isso é bastante semelhante ao primeiro exemplo acima, com uma sintaxe mais fácil:


SELECT @Median = AVG(1.0 * val)
FROM
(
   SELECT val, 
      ra = ROW_NUMBER() OVER (ORDER BY val, id),
      rd = ROW_NUMBER() OVER (ORDER BY val DESC, id DESC)
   FROM dbo.EvenRows
) AS x
WHERE ra BETWEEN rd - 1 AND rd + 1;

2005_B – número da linha + contagem


Este é bastante semelhante ao acima, usando um único cálculo de ROW_NUMBER() e, em seguida, usando o total de COUNT() para encontrar o "meio" uma ou duas linhas:


SELECT @Median = AVG(1.0 * Val)
FROM 
(
  SELECT val, 
     c  = COUNT(*) OVER (),
     rn = ROW_NUMBER() OVER (ORDER BY val)
  FROM dbo.EvenRows
) AS x
WHERE rn IN ((c + 1)/2, (c + 2)/2);

2005_C – variação no número de linhas + contagem


O colega MVP Itzik Ben-Gan me mostrou este método, que obtém a mesma resposta que os dois métodos acima, mas de uma maneira ligeiramente diferente:


SELECT @Median = AVG(1.0 * val)
FROM
(
    SELECT o.val, rn = ROW_NUMBER() OVER (ORDER BY o.val), c.c
    FROM dbo.EvenRows AS o
    CROSS JOIN (SELECT c = COUNT(*) FROM dbo.EvenRows) AS c
) AS x
WHERE rn IN ((c + 1)/2, (c + 2)/2);

SQL Server 2012

2012_A – nova funcionalidade de distribuição


Esta solução usa um cálculo muito direto usando distribuição (se você não quiser a média entre os dois valores do meio no caso de um número par de linhas).


SELECT @Median = PERCENTILE_CONT(0.5) 
  WITHIN GROUP (ORDER BY val) OVER ()
FROM dbo.EvenRows;

2012_B – truque de paginação


Este exemplo implementa um uso inteligente de OFFSET / FETCH (e não exatamente aquele para o qual foi planejado) – simplesmente passamos para a linha que é um antes da metade da contagem e, em seguida, pegamos as próximas uma ou duas linhas, dependendo se a contagem foi par ou ímpar. Obrigado a Itzik Ben-Gan por apontar essa abordagem.


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

Mas qual tem melhor desempenho?

USE tempdb;
GO
 
CREATE TABLE dbo.obj(id INT IDENTITY(1,1), val INT);
 
CREATE CLUSTERED INDEX x ON dbo.obj(val, id);
 
INSERT dbo.obj(val) 
SELECT TOP (10000000) o.[object_id]
FROM sys.all_columns AS c 
CROSS JOIN sys.all_objects AS o
CROSS JOIN sys.all_objects AS o2
WHERE o.[object_id] > 0
ORDER BY c.[object_id];

SELECT val FROM 
(
    SELECT val, rn = ROW_NUMBER() OVER (ORDER BY val)
    FROM dbo.obj
) AS x 
WHERE rn IN (4999999, 5000000, 5000001);

val            rn
----           ----
146099561      4999999
146099561      5000000
146099561      5000001