Selecionar dados divididos em grupos distribuídos uniformemente por valor

Eu gostaria de selecionar em 4 grupos os dados de uma tabela com a soma de valores nos grupos da forma mais distribuída possível. Tenho certeza de que não estou explicando isso com clareza o suficiente, então tentarei dar um exemplo.

Aqui eu uso o NTILE (4) para criar os 4 grupos:

SELECT Time, NTILE(4) OVER (ORDER BY Time DESC) AS N FROM TableX

Time -  N
-------------
10  -   1
 9  -   2
 8  -   3
 7  -   4
 6  -   1
 5  -   2
 4  -   3
 3  -   4
 2  -   1
 1  -   2

Na consulta e resultado acima, as outras colunas foram omitidas por questões de brevidade.

Então você pode ver os grupos também da seguinte maneira:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  6    5    4    3
  2    1    
---  ---  ---  ---
 18   15   12   10  Sum Totals of Time

Observe que a soma total de tempo usando o NTile não é realmente equilibrada entre os grupos. Uma melhor distribuição dos valores de tempo seria, por exemplo:

  1    2    3    4
---  ---  ---  ---
 10    9    8    7
  3    5    4    6
  1         2
---  ---  ---  ---
 14   14   14   13  Sum Totals of Time

Aqui, a soma dos totais de tempo é distribuída de maneira mais uniforme nos 4 grupos.

Como posso fazer isso através de uma instrução TSQL?

Além disso, devo dizer que estou usando o SQL Server 2012. Se você tiver algo que possa me ajudar, me avise.

Eu te desejo um bom dia.

Stan

Aqui está uma facada em um algoritmo. Não é perfeito e, dependendo de quanto tempo você deseja gastar para refiná-lo, provavelmente há outros pequenos ganhos a serem feitos.

Vamos supor que você tenha uma tabela de tarefas a serem executadas por quatro filas. Você sabe a quantidade de trabalho associada à execução de cada tarefa e deseja que todas as quatro filas tenham uma quantidade quase igual de trabalho, para que todas as filas sejam concluídas aproximadamente ao mesmo tempo.

Primeiro, particionaria as tarefas usando um modulado, ordenado por seu tamanho, de pequeno a grande porte.

SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0

As ROW_NUMBER()ordens de cada linha por tamanho, então atribui um número de linha, a partir de 1. Este número da linha é atribuído um "grupo" (o grpcoluna) numa base round-robin. A primeira linha é o grupo 1, a segunda linha é o grupo 2, depois a 3, a quarta recebe o grupo 0 e assim por diante.

time ROW_NUMBER() grp
---- ------------ ---
   1            1   1
  10            2   2
  12            3   3
  15            4   0
  19            5   1
  22            6   2
...

Para facilitar o uso, estou armazenando as colunas timee grpem uma variável de tabela chamada @work.

Agora, podemos realizar alguns cálculos nesses dados:

WITH cte AS (
    SELECT *, SUM([time]) OVER (PARTITION BY grp)
             -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset
    FROM @work)
...

A coluna _grpoffseté quanto o total timepor grpdifere da média "ideal". Se o total timede todas as tarefas for 1000 e houver quatro grupos, idealmente deve haver um total de 250 em cada grupo. Se um grupo contiver um total de 268, esse grupo será _grpoffset=18.

A idéia é identificar as duas melhores linhas, uma em um grupo "positivo" (com muito trabalho) e outra em um grupo "negativo" (com muito pouco trabalho). Se pudermos trocar grupos nessas duas linhas, poderemos reduzir o absoluto _grpoffsetde ambos os grupos.

Exemplo:

time grp total _grpoffset
---- --- ----- ----------
   3   1   222         40
  46   1   222         40
  73   1   222         40
 100   1   222         40
   6   2   134        -48
  52   2   134        -48
  76   2   134        -48
  11   3   163        -21
  66   3   163        -21
  86   3   163        -21
  45   0   208         24
  71   0   208         24
  92   0   208         24
----
=727

Com um total geral de 727, cada grupo deve ter uma pontuação de cerca de 182 para que a distribuição seja perfeita. A diferença entre a pontuação do grupo e 182 é o que estamos colocando na _grpoffsetcoluna.

Como você pode ver agora, no melhor dos mundos, devemos mover cerca de 40 pontos no valor de linhas do grupo 1 para o grupo 2 e cerca de 24 pontos do grupo 3 para o grupo 0.

Aqui está o código para identificar essas linhas candidatas:

    SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp,
                 neg._row AS _neg_row, neg.grp AS _neg_grp
    FROM cte AS pos
    INNER JOIN cte AS neg ON
        pos._grpoffset>0 AND
        neg._grpoffset<0 AND
        --- To prevent infinite recursion:
        pos.moved<4 AND
        neg.moved<4
    WHERE --- must improve positive side's offset:
          ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND
          --- must improve negative side's offset:
          ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset)
    --- Largest changes first:
    ORDER BY ABS(pos.[time]-neg.[time]) DESC
    ) AS x ON w._row IN (x._pos_row, x._neg_row);

Estou me unindo à expressão de tabela comum que criamos antes cte: Por um lado, grupos com um positivo e _grpoffset, por outro, grupos com negativos. Para filtrar ainda mais quais linhas devem coincidir entre si, a troca das linhas dos lados positivo e negativo deve melhorar _grpoffset, ou seja, aproximar-se de 0.

O TOP 1e ORDER BYseleciona a "melhor" correspondência para trocar primeiro.

Agora, basta adicionar um UPDATEe fazer um loop até que não haja mais otimização a ser encontrada.

TL; DR - aqui está a consulta

Aqui está o código completo:

DECLARE @work TABLE (
    _row    int IDENTITY(1, 1) NOT NULL,
    [time]  int NOT NULL,
    grp     int NOT NULL,
    moved   tinyint NOT NULL,
    PRIMARY KEY CLUSTERED ([time], _row)
);

WITH cte AS (
    SELECT 0 AS n, CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time]
    UNION ALL
    SELECT n+1,    CAST(1+100*RAND(CHECKSUM(NEWID())) AS int) AS [time]
    FROM cte WHERE n<100)

INSERT INTO @work ([time], grp, moved)
SELECT [time], ROW_NUMBER() OVER (ORDER BY [time])%4 AS grp, 0
FROM cte;



WHILE (@@ROWCOUNT!=0)
    WITH cte AS (
        SELECT *, SUM([time]) OVER (PARTITION BY grp)
                 -SUM([time]) OVER (PARTITION BY (SELECT NULL))/4 AS _grpoffset
        FROM @work)

    UPDATE w
    SET w.grp=(CASE w._row
               WHEN x._pos_row THEN x._neg_grp
               ELSE x._pos_grp END),
        w.moved=w.moved+1
    FROM @work AS w
    INNER JOIN (
        SELECT TOP 1 pos._row AS _pos_row, pos.grp AS _pos_grp,
                     neg._row AS _neg_row, neg.grp AS _neg_grp
        FROM cte AS pos
        INNER JOIN cte AS neg ON
            pos._grpoffset>0 AND
            neg._grpoffset<0 AND
            --- To prevent infinite recursion:
            pos.moved<4 AND
            neg.moved<4
        WHERE --- must improve positive side's offset:
              ABS(pos._grpoffset-pos.[time]+neg.[time])<=pos._grpoffset AND
              --- must improve negative side's offset:
              ABS(neg._grpoffset-neg.[time]+pos.[time])<=ABS(neg._grpoffset)
        --- Largest changes first:
        ORDER BY ABS(pos.[time]-neg.[time]) DESC
        ) AS x ON w._row IN (x._pos_row, x._neg_row);