Desafio da consulta: Criando buckets de tamanho uniforme, com base em uma medida e não na contagem de linhas

Descreverei o problema em termos de carregamento de um número fixo de caminhões com pedidos, o mais uniformemente possível.

Entradas:

@TruckCount - the number of empty trucks to fill

Um conjunto:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Orderssão compostos por um ou mais OrderDetails.

O desafio aqui é atribuir um TruckIda cada registro.

Um único pedido não pode ser dividido entre caminhões.

Os caminhões devem ser carregados o mais uniformemente possível, medido por sum(OrderDetailSize).

* Uniformemente: o menor delta possível entre o caminhão menos carregado e o caminhão mais carregado. Por essa definição, 1,2,3 é distribuído de maneira mais uniforme que 1,1,4. Se ajudar, finja que você é o algoritmo de estatísticas, criando histogramas de altura uniformes.

Não há consideração pela carga máxima do caminhão. Estes são caminhões elásticos mágicos. O número de caminhões, no entanto, é fixo.

Obviamente, existe uma solução iterativa - o rodízio rotativo aloca pedidos.

Mas isso pode ser feito como lógica baseada em conjunto?

Meu principal interesse é pelo SQL Server 2014 ou posterior. Mas soluções baseadas em outras plataformas também podem ser interessantes.

Parece o território Itzik Ben-Gan :)

Meu aplicativo no mundo real está distribuindo uma carga de trabalho de processamento em vários buckets para corresponder ao número de CPUs lógicas. Portanto, cada balde não tem tamanho máximo. Atualizações de estatísticas, especificamente. Eu apenas pensei que era mais divertido abstrair o problema em caminhões como uma maneira de enquadrar o desafio.

CREATE TABLE #OrderDetail (
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize tinyint NOT NULL,
TruckId tinyint NULL)

-- Sample Data

INSERT #OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(1  ,100    ,75 ),
(2  ,101    ,5  ),
(2  ,102    ,5  ),
(2  ,103    ,5  ),
(2  ,104    ,5  ),
(2  ,105    ,5  ),
(3  ,106    ,100),
(4  ,107    ,1  ),
(5  ,108    ,11 ),
(6  ,109    ,21 ),
(7  ,110    ,49 ),
(8  ,111    ,25 ),
(8  ,112    ,25 ),
(9  ,113    ,40 ),
(10 ,114    ,49 ),
(11 ,115    ,10 ),
(11 ,116    ,10 ),
(12 ,117    ,15 ),
(13 ,118    ,18 ),
(14 ,119    ,26 )

--> YOUR SOLUTION HERE

-- After assigning Trucks, Measure delta between most and least loaded trucks.
-- Zero is perfect score, however the challenge is a set based solution that will scale, and produce good results, rather
-- than iterative solution that will produce perfect results by exploring every possibility.

SELECT max(TruckOrderDetailSize) - MIN(TruckOrderDetailSize) AS TruckMinMaxDelta
FROM 
(SELECT SUM(OrderDetailSize) AS TruckOrderDetailSize FROM #OrderDetail GROUP BY TruckId) AS Truck


DROP TABLE #OrderDetail

Meu primeiro pensamento foi

select
    <best solution>
from
    <all possible combinations>

A parte "melhor solução" é definida na pergunta - a menor diferença entre os caminhões mais carregados e os menos carregados. A outra parte - todas as combinações - me fez parar para pensar.

Considere uma situação em que temos três ordens A, B e C e três caminhões. As possibilidades são

Truck 1 Truck 2 Truck 3
------- ------- -------
A       B       C
A       C       B
B       A       C
B       C       A
C       A       B
C       B       A
AB      C       -
AB      -       C
C       AB      -
-       AB      C
C       -       AB
-       C       AB
AC      B       -
AC      -       B
B       AC      -
-       AC      B
B       -       AC
-       B       AC
BC      A       -
BC      -       A
A       BC      -
-       BC      A
A       -       BC
-       A       BC
ABC     -       -
-       ABC     -
-       -       ABC

Table A: all permutations.

Muitos destes são simétricos. As seis primeiras linhas, por exemplo, diferem apenas em qual caminhão cada pedido é feito. Como os caminhões são fungíveis, esses arranjos produzirão o mesmo resultado. Vou ignorar isso por enquanto.

Existem consultas conhecidas para produzir permutações e combinações. No entanto, isso produzirá arranjos dentro de um único balde. Para esse problema, preciso de arranjos em vários baldes.

Analisando a saída da consulta padrão "todas as combinações"

;with Numbers as
(
    select n = 1
    union
    select 2
    union
    select 3
)
select
    a.n,
    b.n,
    c.n
from Numbers as a
cross join Numbers as b
cross join Numbers as c
order by 1, 2, 3;


  n   n   n
--- --- ---
  1   1   1
  1   1   2
  1   1   3
  1   2   1
 <snip>
  3   2   3
  3   3   1
  3   3   2
  3   3   3

Table B: cross join of three values.

Observei que os resultados formaram o mesmo padrão da Tabela A. Ao dar o salto de considerar cada coluna como uma ordem ¹ , os valores para dizer qual caminhão manterá essa ordem e uma linha para ser um arranjo de ordens dentro de caminhões. A consulta então se torna

select
    Arrangement             = ROW_NUMBER() over(order by (select null)),
    First_order_goes_in     = a.TruckNumber,
    Second_order_goes_in    = b.TruckNumber,
    Third_order_goes_in     = c.TruckNumber
from Trucks a   -- aka Numbers in Table B
cross join Trucks b
cross join Trucks c

Arrangement First_order_goes_in Second_order_goes_in Third_order_goes_in
----------- ------------------- -------------------- -------------------
          1                   1                    1                   1
          2                   1                    1                   2
          3                   1                    1                   3
          4                   1                    2                   1
  <snip>

Query C: Orders in trucks.

Expandir isso para cobrir os quatorze pedidos nos dados de exemplo e simplificar os nomes que obtemos:

;with Trucks as
(
    select * 
    from (values (1), (2), (3)) as T(TruckNumber)
)
select
    arrangement = ROW_NUMBER() over(order by (select null)),
    First       = a.TruckNumber,
    Second      = b.TruckNumber,
    Third       = c.TruckNumber,
    Fourth      = d.TruckNumber,
    Fifth       = e.TruckNumber,
    Sixth       = f.TruckNumber,
    Seventh     = g.TruckNumber,
    Eigth       = h.TruckNumber,
    Ninth       = i.TruckNumber,
    Tenth       = j.TruckNumber,
    Eleventh    = k.TruckNumber,
    Twelth      = l.TruckNumber,
    Thirteenth  = m.TruckNumber,
    Fourteenth  = n.TruckNumber
into #Arrangements
from Trucks a
cross join Trucks b
cross join Trucks c
cross join Trucks d
cross join Trucks e
cross join Trucks f
cross join Trucks g
cross join Trucks h
cross join Trucks i
cross join Trucks j
cross join Trucks k
cross join Trucks l
cross join Trucks m
cross join Trucks n;

Query D: Orders spread over trucks.

Eu escolho manter os resultados intermediários em tabelas temporárias por conveniência.

As etapas subseqüentes serão muito mais fáceis se os dados não forem liberados pela primeira vez.

select
    Arrangement,
    TruckNumber,
    ItemNumber  = case NewColumn
                    when 'First'        then 1
                    when 'Second'       then 2
                    when 'Third'        then 3
                    when 'Fourth'       then 4
                    when 'Fifth'        then 5
                    when 'Sixth'        then 6
                    when 'Seventh'      then 7
                    when 'Eigth'        then 8
                    when 'Ninth'        then 9
                    when 'Tenth'        then 10
                    when 'Eleventh'     then 11
                    when 'Twelth'       then 12
                    when 'Thirteenth'   then 13
                    when 'Fourteenth'   then 14
                    else -1
                end
into #FilledTrucks
from #Arrangements
unpivot
(
    TruckNumber
    for NewColumn IN 
    (
        First,
        Second,
        Third,
        Fourth,
        Fifth,
        Sixth,
        Seventh,
        Eigth,
        Ninth,
        Tenth,
        Eleventh,
        Twelth,
        Thirteenth,
        Fourteenth
    )
) as q;

Query E: Filled trucks, unpivoted.

Os pesos podem ser introduzidos ingressando na tabela Pedidos.

select
    ft.arrangement,
    ft.TruckNumber,
    TruckWeight = sum(i.Size)
into #TruckWeights
from #FilledTrucks as ft
inner join #Order as i
    on i.OrderId = ft.ItemNumber
group by
    ft.arrangement,
    ft.TruckNumber;

Query F: truck weights

Agora, a pergunta pode ser respondida encontrando-se o (s) arranjo (s) com a menor diferença entre os caminhões mais carregados e os menos carregados

select
    Arrangement,
    LightestTruck   = MIN(TruckWeight),
    HeaviestTruck   = MAX(TruckWeight),
    Delta           = MAX(TruckWeight) - MIN(TruckWeight)
from #TruckWeights
group by
    arrangement
order by
    4 ASC;

Query G: most balanced arrangements

Discussão

Existem muitos problemas com isso. Primeiro, é um algoritmo de força bruta. O número de linhas nas tabelas de trabalho é exponencial no número de caminhões e pedidos. O número de linhas em # Arranjos é (número de caminhões) ^ (número de pedidos). Isso não vai escalar bem.

Segundo: as consultas SQL têm o número de pedidos incorporado. A única maneira de contornar isso é usar o SQL dinâmico, que possui problemas próprios. Se o número de pedidos estiver na casa dos milhares, poderá chegar um momento em que o SQL gerado se tornará muito longo.

Terceiro: a redundância nos acordos. Isso incha as tabelas intermediárias, aumentando enormemente o tempo de execução.

Quarto, muitas linhas em #Arrangements deixam um ou mais caminhões vazios. Esta não pode ser a configuração ideal. Seria fácil filtrar essas linhas na criação. Decidi não fazer isso para manter o código mais simples e focado.

No lado positivo, isso lida com pesos negativos, caso sua empresa comece a enviar balões de hélio cheios!

Pensamentos

Se houvesse uma maneira de preencher a #FilledTrucks diretamente da lista de caminhões e pedidos, acho que a pior dessas preocupações seria administrável. Infelizmente, minha imagem tropeçou nesse obstáculo. Minha esperança é que algum colaborador futuro possa suprir aquilo que me escapou.

¹ Você diz que todos os itens de um pedido devem estar no mesmo caminhão. Isso significa que o átomo de atribuição é a Ordem, não o Detalhe da Ordem. Eu os criei a partir dos dados de teste assim:

select
    OrderId,
    Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;

Não faz diferença, porém, se rotularmos os itens em questão como 'Pedido' ou 'Detalhe da solicitação', a solução permanecerá a mesma.

Analisando seus requisitos do mundo real (que eu suponho que seja uma tentativa de equilibrar sua carga de trabalho em um conjunto de cpus) ...

Existe uma razão para você precisar pré-atribuir processos a buckets / cpus específicos? [Tentando entender seus requisitos reais ]

Para o seu exemplo de 'atualizações de estatísticas', como você sabe quanto tempo uma operação específica levará? E se uma determinada operação tiver um atraso inesperado (por exemplo, fragmentação acima da planejada / excessiva de tabela / índice, o usuário de execução prolongada txn bloqueia uma operação de 'atualização de estatísticas')?

Para fins de balanceamento de carga, normalmente eu gero a lista de tarefas (por exemplo, lista de tabelas para atualizar as estatísticas) e coloco a lista em uma tabela (temporária / temporária).

A estrutura da tabela pode ser modificada de acordo com seus requisitos, por exemplo:

create table tasks
(id        int             -- auto-increment?

,target    varchar(1000)   -- 'schema.table' to have stats updated, or perhaps ...
,command   varchar(1000)   -- actual command to be run, eg, 'update stats schema.table ... <options>'

,priority  int             -- provide means of ordering operations, eg, maybe you know some tasks will run really long so you want to kick them off first
,thread    int             -- identifier for parent process?
,start     datetime        -- default to NULL
,end       datetime        -- default to NULL
)

Em seguida, inicio o número X de processos simultâneos para executar as operações reais de 'atualização de estatísticas', com cada processo executando o seguinte:

• coloque uma trava exclusiva no tasks mesa (garante que nenhuma tarefa seja escolhida por mais de um processo; deve ser um bloqueio relativamente curto)
• encontre 'primeira' linha onde start = NULL('primeiro' seria determinado por você, por exemplo, ordenar por priority?)
• atualizar conjunto de linhas start = getdate(), thread = <process_number>
• confirmar atualização (e liberar bloqueio exclusivo)
• anote ide target/commandvalores
• execute a operação desejada contra target(alternativamente, execute command) e quando terminar ...
• atualizar taskscomend = getdate() where id = <id>
• repita acima até que não haja mais tarefas para executar

Com o design acima, agora tenho uma operação balanceada dinamicamente (principalmente).

NOTAS:

• Eu tento fornecer algum tipo de método de priorização para poder iniciar as tarefas mais longas com antecedência; enquanto alguns processos estão trabalhando nas tarefas em execução mais longas, os outros processos podem percorrer a lista de tarefas em execução mais curtas
• se um processo ocorrer com um atraso não planejado (por exemplo, usuário txn de bloqueio e execução prolongada), outros processos podem 'pegar a folga' continuando a retirar a operação 'próxima disponível' de tasks
• o design do tasks tabela deve fornecer outros benefícios, por exemplo, um histórico de tempos de execução que você pode arquivar para referência futura, um histórico de tempos de execução que pode ser usado para modificar prioridades, fornecer um status das operações atuais etc.
• Embora o 'bloqueio exclusivo' taskspossa parecer um pouco excessivo, lembre-se de que precisamos planejar o possível problema de 2 (ou mais) processos que tentam obter uma nova tarefa ao mesmo tempo , portanto, precisamos garantir uma tarefa é atribuído a apenas um processo (e sim, você pode obter os mesmos resultados com uma instrução 'update / select' combinada - dependendo dos recursos da linguagem SQL do RDBMS); a etapa de obtenção de uma nova 'tarefa' deve ser rápida, ou seja, a 'trava exclusiva' deve durar pouco e, na realidade, os processos serão atingidos de tasksmaneira bastante aleatória e, portanto, será pouco obstrutiva.

Pessoalmente, acho esse tasksprocesso orientado por tabela um pouco mais fácil de implementar e manter ... em oposição a um processo (geralmente) mais complexo de tentar pré-atribuir mapeamentos de tarefas / processos ... ymmv.

Obviamente, no seu exemplo de faz de conta, você não pode ter seus caminhões voltando à distribuição / armazém para o próximo pedido; portanto, é necessário pré-atribuir seus pedidos a vários caminhões (tendo em mente que a UPS / Fedex / etc também precisa atribuir com base nas rotas de entrega para reduzir o tempo de entrega e o uso de gás).

No entanto, no seu exemplo do mundo real ('atualização de estatísticas'), não há razão para que as atribuições de tarefas / processos não possam ser feitas dinamicamente, garantindo assim uma melhor chance de equilibrar a carga de trabalho (entre cpus e em termos de redução do tempo de execução geral) .

OBSERVAÇÃO: Eu vejo rotineiramente as pessoas (TI) tentando pré-atribuir suas tarefas (como uma forma de balanceamento de carga) antes de executar as tarefas, e em todos os casos, ele acaba precisando ajustar constantemente o processo de pré-atribuição para executar levar em consideração questões de tarefas que variam constantemente (por exemplo, nível de fragmentação na tabela / índice, atividade simultânea do usuário etc.).

crie e preencha a tabela numérica como desejar. Essa é apenas uma criação.

 create table tblnumber(number int not null)

    insert into tblnumber (number)
    select ROW_NUMBER()over(order by a.number) from master..spt_values a
    , master..spt_values b

    CREATE unique clustered index CI_num on tblnumber(number)

Tabela de caminhão criada

CREATE TABLE #PaulWhiteTruck (
Truckid int NOT NULL)

insert into #PaulWhiteTruck
values(113),(203),(303)

declare @PaulTruckCount int
Select @PaulTruckCount= count(*) from #PaulWhiteTruck

CREATE TABLE #OrderDetail (
id int identity(1,1),
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize int NOT NULL,
TruckId int NULL
)

INSERT
#OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(
1 ,100 ,75 ),(2 ,101 ,5 ),
(2 ,102 ,5 ),(2 ,103 ,5 ),
(2 ,104 ,5 ),(2 ,105 ,5 ),
(3 ,106 ,100),(4 ,107 ,1 ),
(5 ,108 ,11 ),(6 ,109 ,21 ),
(7 ,110 ,49 ),(8 ,111 ,25 ),
(8 ,112 ,25 ),(9 ,113 ,40 ),
(10 ,114 ,49 ),(11 ,115 ,10 ),
(11 ,116 ,10 ),(12 ,117 ,15 ),
(13 ,118 ,18 ),(14 ,119 ,26 )

Eu criei uma OrderSummarytabela

create table #orderSummary(id int identity(1,1),OrderId int ,TruckOrderSize int
,bit_value AS
CONVERT
(
integer,
POWER(2, id - 1)
)
PERSISTED UNIQUE CLUSTERED)
insert into #orderSummary
SELECT OrderId, SUM(OrderDetailSize) AS TruckOrderSize
FROM #OrderDetail GROUP BY OrderId

DECLARE @max integer =
POWER(2,
(
SELECT COUNT(*) FROM #orderSummary 
)
) - 1
declare @Delta int
select @Delta= max(TruckOrderSize)-min(TruckOrderSize)   from #orderSummary

Verifique meu valor Delta e deixe-me saber se está errado

;WITH cte 
     AS (SELECT n.number, 
                c.* 
         FROM   dbo.tblnumber AS N 
                CROSS apply (SELECT s.orderid, 
                                    s.truckordersize 
                             FROM   #ordersummary AS s 
                             WHERE  n.number & s.bit_value = s.bit_value) c 
         WHERE  N.number BETWEEN 1 AND @max), 
     cte1 
     AS (SELECT c.number, 
                Sum(truckordersize) SumSize 
         FROM   cte c 
         GROUP  BY c.number 
        --HAVING sum(TruckOrderSize) between(@Delta-25) and (@Delta+25) 
        ) 
SELECT c1.*, 
       c.orderid 
FROM   cte1 c1 
       INNER JOIN cte c 
               ON c1.number = c.number 
ORDER  BY sumsize 

DROP TABLE #orderdetail 

DROP TABLE #ordersummary 

DROP TABLE #paulwhitetruck 

Você pode verificar o resultado do CTE1, tudo isso é possível Permutation and Combination of order along with their size.

Se minha abordagem estiver correta até aqui, preciso de ajuda de alguém.

Tarefa pendente:

filtre e Divida o resultado CTE1em até 3 partes ( Truck count), de modo Orderidexclusivo entre cada grupo e cada parte T ruckOrderSizeesteja próxima ao Delta.