Desafío de consulta: crear cubos de tamaño par, basados ​​en una medida, no en el recuento de filas

Describiré el problema en términos de cargar un número fijo de camiones con pedidos, de la manera más uniforme posible.

Entradas:

@TruckCount - the number of empty trucks to fill

Un conjunto:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Ordersestán compuestos de uno o más OrderDetails.

El desafío aquí es asignar un TruckIda cada registro.

Un solo pedido no se puede dividir entre camiones.

Los camiones deben estar lo más uniformemente * cargados posible, medidos por sum(OrderDetailSize).

* De manera uniforme: el delta alcanzable más pequeño entre el camión menos cargado y el camión más cargado. Según esta definición, 1,2,3 está más uniformemente distribuido que 1,1,4. Si te ayuda, imagina que eres un algoritmo de estadísticas, creando histogramas de altura uniforme.

No hay consideración para la carga máxima del camión. Estos son camiones elásticos mágicos. Sin embargo, el número de camiones es fijo.

Obviamente, hay una solución que es iterativa: órdenes de asignación de round robin.

Pero, ¿puede hacerse como lógica basada en conjuntos?

Mi interés principal es para SQL Server 2014 o posterior. Pero establecer soluciones basadas para otras plataformas también podría ser interesante.

Esto se siente como territorio Itzik Ben-Gan :)

Mi aplicación en el mundo real es distribuir una carga de trabajo de procesamiento en varios segmentos para que coincida con el número de CPU lógicas. Por lo tanto, cada cubo no tiene un tamaño máximo. Actualizaciones de estadísticas, específicamente. Simplemente pensé que era más divertido abstraer el problema en camiones como una forma de enmarcar el desafío.

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

Mi primer pensamiento fue

select
    <best solution>
from
    <all possible combinations>

La parte de "mejor solución" se define en la pregunta: la diferencia más pequeña entre los camiones más cargados y los menos cargados. La otra parte, todas las combinaciones, me hizo reflexionar.

Considere una situación en la que tenemos tres órdenes A, B y C y tres camiones. Las posibilidades son

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.

Muchos de estos son simétricos. Las primeras seis filas, por ejemplo, difieren solo en qué camión se realiza cada pedido. Como los camiones son fungibles, estos arreglos producirán el mismo resultado. Ignoraré esto por ahora.

Existen consultas conocidas para producir permutaciones y combinaciones. Sin embargo, estos producirán arreglos dentro de un solo cubo. Para este problema, necesito arreglos en varios cubos.

Mirando el resultado de la consulta estándar "todas las combinaciones"

;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.

Noté que los resultados formaron el mismo patrón que la Tabla A. Al dar el salto cognitivo de considerar cada columna como una Orden ¹ , los valores para decir qué camión mantendrá esa Orden y una fila para ser una disposición de las Órdenes dentro de los camiones. La consulta se convierte en

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.

Expandiendo esto para cubrir las catorce Órdenes en los datos de ejemplo, y simplificando los nombres obtenemos esto:

;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.

Elijo mantener los resultados intermedios en tablas temporales por conveniencia.

Los pasos subsiguientes serán mucho más fáciles si los datos se DESVIOTAN por primera 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.

Los pesos se pueden introducir uniéndose a la tabla 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

La pregunta ahora puede responderse encontrando los arreglos que tienen la menor diferencia entre los camiones con más carga y los menos cargados

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

Discusión

Hay muchos problemas con esto. Primero es un algoritmo de fuerza bruta. El número de filas en las tablas de trabajo es exponencial en el número de camiones y pedidos. El número de filas en #Arrangements es (número de camiones) ^ (número de pedidos). Esto no escalará bien.

En segundo lugar, las consultas SQL tienen incrustada la cantidad de Órdenes. La única forma de evitar esto es usar SQL dinámico, que tiene sus propios problemas. Si el número de pedidos es de miles, puede llegar un momento en que el SQL generado sea demasiado largo.

El tercero es la redundancia en los arreglos. Esto hincha las tablas intermedias aumentando enormemente el tiempo de ejecución.

Cuarto, muchas filas en #Arrangements dejan uno o más camiones vacíos. Esto no puede ser la configuración óptima. Sería fácil filtrar estas filas después de la creación. Elegí no hacerlo para mantener el código más simple y enfocado.

En el lado positivo, esto maneja pesos negativos, en caso de que su empresa comience a enviar globos de helio llenos.

Pensamientos

Si hubiera una manera de poblar #FilledTrucks directamente desde la lista de camiones y pedidos, creo que la peor de estas preocupaciones sería manejable. Lamentablemente, mi imaginación tropezó con ese obstáculo. Espero que algún contribuyente futuro pueda proporcionar lo que se me escapó.

¹ Usted dice que todos los artículos para un pedido deben estar en el mismo camión. Esto significa que el átomo de asignación es el Order, no el OrderDetail. Los he generado a partir de sus datos de prueba de esta manera:

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

Sin embargo, no importa si etiquetamos los artículos en cuestión como 'Pedido' o 'Detalle del pedido', la solución sigue siendo la misma.

Mirando sus requisitos del mundo real (lo que supongo es un intento de equilibrar su carga de trabajo en un conjunto de cpus) ...

¿Hay alguna razón por la que necesita preasignar procesos a cubos / cpus específicos? [Intentando entender tus requisitos reales ]

Para su ejemplo de 'actualizaciones de estadísticas', ¿cómo sabe cuánto tiempo llevará una operación en particular? ¿Qué sucede si una operación determinada se encuentra con un retraso inesperado (p. Ej., Una fragmentación excesiva de la tabla / índice o tabla excesiva, el usuario txn de larga ejecución bloquea una operación de 'actualización de estadísticas')?

Para fines de equilibrio de carga, generalmente genero la lista de tareas (por ejemplo, la lista de tablas para tener estadísticas actualizadas) y coloco dicha lista en una tabla (temporal / reutilizable).

La estructura de la tabla se puede modificar según sus requisitos, por ejemplo:

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
)

A continuación, inicio X número de procesos concurrentes para realizar las operaciones reales de 'actualización de estadísticas', y cada proceso realiza lo siguiente:

• coloque un bloqueo exclusivo en la tasksmesa (asegura que ninguna tarea sea recogida por más de un proceso; debe ser un bloqueo relativamente de corta duración)
• encuentre la 'primera' fila donde start = NULL('primero' sería determinado por usted, por ejemplo, ¿ordenar por priority?)
• conjunto de filas de actualización start = getdate(), thread = <process_number>
• confirmar actualización (y liberar bloqueo exclusivo)
• tomar nota de idy target/commandvalores
• realizar la operación deseada contra target(alternativamente, ejecutar command) y cuando haya terminado ...
• actualizar tasksconend = getdate() where id = <id>
• repita lo anterior hasta que no haya más tareas que realizar

Con el diseño anterior, ahora tengo una operación equilibrada dinámicamente (en su mayoría).

NOTAS

• Intento proporcionar algún tipo de método de priorización para poder comenzar las tareas más largas por adelantado; Mientras que un par de procesos están trabajando en las tareas más largas, los otros procesos pueden pasar por la lista de tareas más cortas
• Si un proceso se encuentra con un retraso no planificado (p. ej., ejecución prolongada, bloqueo del usuario txn), otros procesos pueden 'recuperar la holgura' al continuar retirando la operación 'siguiente disponible' tasks
• El diseño de la taskstabla debe proporcionar otros beneficios, por ejemplo, un historial de tiempos de ejecución que puede archivar para referencia futura, un historial de tiempos de ejecución que puede usarse para modificar prioridades, proporcionar un estado de las operaciones actuales, etc.
• Si bien el 'bloqueo exclusivo' taskspuede parecer un poco excesivo, tenga en cuenta que tenemos que planificar el posible problema de 2 (o más) procesos que intentan obtener una nueva tarea al mismo tiempo exacto , por lo que debemos garantizar una tarea se asigna a un solo proceso (y sí, puede obtener los mismos resultados con una instrucción combinada 'actualizar / seleccionar', dependiendo de las capacidades del lenguaje SQL de su RDBMS); el paso de obtener una nueva 'tarea' debe ser rápido, es decir, el 'bloqueo exclusivo' debe ser de corta duración y, en realidad, los procesos se ejecutarán tasksde manera bastante aleatoria, por lo que de todos modos habrá poco bloqueo

Personalmente, encuentro que este tasksproceso impulsado por la tabla es un poco más fácil de implementar y mantener ... en comparación con un proceso (generalmente) más complejo de tratar de preasignar asignaciones de tareas / procesos ... ymmv.

Obviamente, para su ejemplo de fantasía, no puede hacer que sus camiones vuelvan a la distribución / almacén para el próximo pedido, por lo que debe preasignar sus pedidos a varios camiones (teniendo en cuenta que UPS / Fedex / etc. también deben asignar en función de las rutas de entrega para reducir los tiempos de entrega y el uso de gas).

Sin embargo, en su ejemplo del mundo real ('actualización de estadísticas') no hay ninguna razón por la cual las asignaciones de tareas / procesos no se puedan realizar dinámicamente, lo que garantiza una mejor oportunidad de equilibrar la carga de trabajo (en cpus y en términos de reducir el tiempo de ejecución general) .

NOTA: rutinariamente veo a personas (de TI) que intentan preasignar sus tareas (como una forma de equilibrio de carga) antes de ejecutar dichas tareas, y en todos los casos, él / ella tiene que modificar constantemente el proceso de preasignación para realizar en consideración problemas de tareas que varían constantemente (p. ej., nivel de fragmentación en la tabla / índice, actividad concurrente del usuario, etc.).

cree y complete la tabla de números como desee. Esta es una creación única.

 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)

Mesa creada para camiones

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 )

He creado una OrderSummarytabla

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 mi valor Delta y avíseme si está mal

;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 

Puede verificar el resultado de CTE1, tiene todo lo posible Permutation and Combination of order along with their size.

Si mi enfoque es correcto hasta aquí, entonces necesito ayuda de alguien.

Tarea pendiente :

Filtrar y dividir el resultado de CTE1en 3 partes ( Truck count) de modo que Orderidsea ​​único entre cada grupo y cada parte T ruckOrderSizeesté cerca de Delta.