Calculando a mediana com um cursor dinâmico

1. Ordenar os números (em ordem crescente ou decrescente, não importa qual).
2. O número do meio (por posição) na lista ordenada é a mediana.
3. Se houver dois números "igualmente centrais", a mediana será a média dos dois valores centrais.

• Qual ​​é a maneira mais rápida de calcular a mediana?
• Melhores abordagens para mediana agrupada

• Médias pré-SQL 2012

O método 2012 OFFSET-FETCH

Média única de deslocamento

CREATE TABLE dbo.obj
(
    id  integer NOT NULL IDENTITY(1,1), 
    val integer NOT NULL
);
 
INSERT dbo.obj WITH (TABLOCKX) 
    (val)
SELECT TOP (10000000) 
    AO.[object_id]
FROM sys.all_columns AS AC
CROSS JOIN sys.all_objects AS AO
CROSS JOIN sys.all_objects AS AO2
WHERE AO.[object_id] > 0
ORDER BY 
    AC.[object_id];
 
CREATE UNIQUE CLUSTERED INDEX cx 
ON dbo.obj(val, id);

DECLARE @Start datetime2 = SYSUTCDATETIME();
 
DECLARE @Count bigint = 10000000
--(
--    SELECT COUNT_BIG(*) 
--    FROM dbo.obj AS O
--);
 
SELECT 
    Median = AVG(1.0 * SQ1.val)
FROM 
(
    SELECT O.val 
    FROM dbo.obj AS O
    ORDER BY O.val
    OFFSET (@Count - 1) / 2 ROWS
    FETCH NEXT 1 + (1 - @Count % 2) ROWS ONLY
) AS SQ1;
 
SELECT Peso = DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

Média Agrupada OFFSET

CREATE TABLE dbo.Sales
(
    SalesPerson integer NOT NULL, 
    Amount integer NOT NULL
);
 
WITH X AS
(
    SELECT TOP (100) 
        V.number
    FROM master.dbo.spt_values AS V
    GROUP BY 
        V.number
)
INSERT dbo.Sales WITH (TABLOCKX) 
(
    SalesPerson, 
    Amount
)
SELECT 
    X.number,
    ABS(CHECKSUM(NEWID())) % 99
FROM X 
CROSS JOIN X AS X2 
CROSS JOIN X AS X3;
 
CREATE CLUSTERED INDEX cx 
ON dbo.Sales
    (SalesPerson, Amount);

DECLARE @s datetime2 = SYSUTCDATETIME();
 
DECLARE @Result AS table 
(
    SalesPerson integer PRIMARY KEY, 
    Median float NOT NULL
);
 
INSERT @Result
SELECT	d.SalesPerson, w.Median
FROM
(
  SELECT SalesPerson, COUNT(*) AS y
  FROM dbo.Sales
  GROUP BY SalesPerson
) AS d
CROSS APPLY
(
  SELECT AVG(0E + Amount)
  FROM
  (
    SELECT z.Amount
     FROM dbo.Sales AS z WITH (PAGLOCK)
     WHERE z.SalesPerson = d.SalesPerson
     ORDER BY z.Amount
     OFFSET (d.y - 1) / 2 ROWS
     FETCH NEXT 2 - d.y % 2 ROWS ONLY
  ) AS f
) AS w(Median);
 
SELECT Peso = DATEDIFF(MILLISECOND, @s, SYSUTCDATETIME());

Usando um cursor dinâmico

Cursor dinâmico mediano único

1. Crie um cursor rolável dinâmico sobre a lista ordenada de itens.
2. Calcule a posição da primeira linha mediana.
3. Reposicione o cursor usando FETCH RELATIVE .
4. Decida se uma segunda linha é necessária para calcular a mediana.
5. Se não, retorne o valor mediano único imediatamente.
6. Caso contrário, busque o segundo valor usando FETCH NEXT .
7. Calcule a média dos dois valores e retorne.

-- Dynamic cursor
DECLARE @Start datetime2 = SYSUTCDATETIME();
 
DECLARE 
    @RowCount bigint,       -- Total row count
    @Row bigint,            -- Median row number
    @Amount1 integer,       -- First amount
    @Amount2 integer,       -- Second amount
    @Median float;          -- Calculated median
 
SET @RowCount = 10000000;
--(
--    SELECT COUNT_BIG(*) 
--    FROM dbo.obj AS O
--);
 
DECLARE Median CURSOR 
    LOCAL
    SCROLL
    DYNAMIC
    READ_ONLY
FOR
    SELECT 
        O.val
    FROM dbo.obj AS O
    ORDER BY 
        O.val;
 
OPEN Median;
 
-- Calculate the position of the first median row
SET @Row = (@RowCount + 1) / 2;
 
-- Move to the row
FETCH RELATIVE @Row 
FROM Median
INTO @Amount1;
 
IF @Row = (@RowCount + 2) / 2
BEGIN
    -- No second row, median is the single value we have
    SET @Median = @Amount1;
END
ELSE
BEGIN
    -- Get the second row
    FETCH NEXT 
    FROM Median
    INTO @Amount2;
 
    -- Calculate the median value from the two values
    SET @Median = (@Amount1 + @Amount2) / 2e0;
END;
 
SELECT Median = @Median;
 
SELECT DynamicCur = DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

1. Evita percorrer todo o conjunto (a leitura pára depois que as linhas medianas são encontradas); e
2. Nenhuma cópia temporária dos dados é feita em tempdb , como seria para um cursor estático ou de conjunto de chaves.

DECLARE @Start datetime2 = SYSUTCDATETIME();
 
DECLARE @Count bigint = 10000000
--(
--    SELECT COUNT_BIG(*) 
--    FROM dbo.obj AS O
--);
 
SELECT AVG(1.0 * SQ1.val) FROM 
(
    SELECT
        O.val,
        rn = ROW_NUMBER() OVER (
            ORDER BY O.val)
    FROM dbo.obj AS O WITH (PAGLOCK)
) AS SQ1
WHERE 
    SQ1.rn BETWEEN (@Count + 1)/2 AND (@Count + 2)/2;
 
SELECT RowNumber = DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

Teste de cursor dinâmico mediano agrupado

1. Abra um cursor estático sobre os vendedores e as contagens de linhas.
2. Calcule a mediana para cada pessoa usando um novo cursor dinâmico a cada vez.
3. Salve cada resultado em uma variável de tabela à medida que avançamos.

-- Timing
DECLARE @s datetime2 = SYSUTCDATETIME();
 
-- Holds results
DECLARE @Result AS table 
(
    SalesPerson integer PRIMARY KEY, 
    Median float NOT NULL
);
 
-- Variables
DECLARE 
    @SalesPerson integer,   -- Current sales person
    @RowCount bigint,       -- Current row count
    @Row bigint,            -- Median row number
    @Amount1 float,         -- First amount
    @Amount2 float,         -- Second amount
    @Median float;          -- Calculated median
 
-- Row counts per sales person
DECLARE SalesPersonCounts 
    CURSOR 
    LOCAL
    FORWARD_ONLY
    STATIC
    READ_ONLY
FOR
    SELECT 
        SalesPerson, 
        COUNT_BIG(*)
    FROM dbo.Sales
    GROUP BY SalesPerson
    ORDER BY SalesPerson;
 
OPEN SalesPersonCounts;
 
-- First person
FETCH NEXT 
FROM SalesPersonCounts 
INTO @SalesPerson, @RowCount;
 
WHILE @@FETCH_STATUS = 0
BEGIN
    -- Records for the current person
    -- Note dynamic cursor
    DECLARE Person CURSOR 
        LOCAL
        SCROLL
        DYNAMIC
        READ_ONLY
    FOR
        SELECT 
            S.Amount
        FROM dbo.Sales AS S
        WHERE 
            S.SalesPerson = @SalesPerson
        ORDER BY 
            S.Amount;
 
    OPEN Person;
 
    -- Calculate median row 1
    SET @Row = (@RowCount + 1) / 2;
 
    -- Move to median row 1
    FETCH RELATIVE @Row 
    FROM Person 
    INTO @Amount1;
 
    IF @Row = (@RowCount + 2) / 2
    BEGIN
        -- No second row, median is the single value
        SET @Median = @Amount1;
    END
    ELSE
    BEGIN
        -- Get the second row
        FETCH NEXT 
        FROM Person 
        INTO @Amount2;
 
        -- Calculate the median value
        SET @Median = (@Amount1 + @Amount2) / 2e0;
    END;
 
    -- Add the result row
    INSERT @Result (SalesPerson, Median)
    VALUES (@SalesPerson, @Median);
 
    -- Finished with the person cursor
    CLOSE Person;
    DEALLOCATE Person;
 
    -- Next person
    FETCH NEXT 
    FROM SalesPersonCounts 
    INTO @SalesPerson, @RowCount;
END;
 
---- Results
--SELECT
--    R.SalesPerson,
--    R.Median
--FROM @Result AS R;
 
-- Tidy up
CLOSE SalesPersonCounts;
DEALLOCATE SalesPersonCounts;
 
-- Show elapsed time
SELECT NestedCur = DATEDIFF(MILLISECOND, @s, SYSUTCDATETIME());

DECLARE @s datetime2 = SYSUTCDATETIME();
 
DECLARE @Result AS table 
(
    SalesPerson integer PRIMARY KEY, 
    Median numeric(38, 6) NOT NULL
);
 
INSERT @Result
SELECT 
    S.SalesPerson,
    CA.Median
FROM 
(
    SELECT 
        SalesPerson, 
        NumRows = COUNT_BIG(*)
    FROM dbo.Sales
    GROUP BY SalesPerson
) AS S
CROSS APPLY 
(
    SELECT AVG(1.0 * SQ1.Amount) FROM 
    (
        SELECT
            S2.Amount,
            rn = ROW_NUMBER() OVER (
                ORDER BY S2.Amount)
        FROM dbo.Sales AS S2 WITH (PAGLOCK)
        WHERE
            S2.SalesPerson = S.SalesPerson
    ) AS SQ1
    WHERE 
        SQ1.rn BETWEEN (S.NumRows + 1)/2 AND (S.NumRows + 2)/2
) AS CA (Median);
 
SELECT RowNumber = DATEDIFF(MILLISECOND, @s, SYSUTCDATETIME());

Resumo dos resultados

Desempenho do cache frio

CHECKPOINT;
DBCC DROPCLEANBUFFERS;

Considerações finais