Wyzwanie związane z zapytaniem: tworzenie wiader o równej wielkości w oparciu o liczbę miar, a nie wierszy

Opiszę problem w kategoriach załadowania stałej liczby ciężarówek z zamówieniami, tak równo, jak to możliwe.

Wejścia:

@TruckCount - the number of empty trucks to fill

Zestaw:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Ordersskładają się z jednego lub więcej OrderDetails.

Wyzwaniem jest przypisanie TruckIddo każdego rekordu.

Pojedynczego zamówienia nie można podzielić na ciężarówki.

Ciężarówki powinny być możliwie równomiernie * obciążone, mierzone według sum(OrderDetailSize).

* Równomiernie: najmniejsza możliwa do osiągnięcia delta między najmniej obciążoną ciężarówką a najbardziej obciążoną ciężarówką. Według tej definicji 1,2,3 jest bardziej równomiernie rozłożone niż 1,1,4. Jeśli to pomaga, udawaj, że jesteś algorytmem statystycznym, tworząc nawet histogramy wysokości.

Nie bierze się pod uwagę maksymalnego obciążenia ciężarówki. To magiczne, elastyczne ciężarówki. Liczba ciężarówek jest jednak stała.

Istnieje oczywiście iteracyjne rozwiązanie - okrągły robin przydziela zamówienia.

Ale czy można to zrobić jako logikę opartą na zestawie?

Moje główne zainteresowania to SQL Server 2014 lub nowszy. Ciekawe mogą być również rozwiązania oparte na zestawach dla innych platform.

To wygląda jak terytorium Itzika Ben-Gana :)

Moja aplikacja w świecie rzeczywistym rozkłada obciążenie przetwarzania na wiele segmentów dopasowanych do liczby logicznych procesorów. Dlatego każde wiadro nie ma maksymalnego rozmiaru. W szczególności aktualizacje statystyk. Pomyślałem, że fajniej jest streścić problem na ciężarówki jako sposób ujęcia wyzwania.

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

Moją pierwszą myślą było

select
    <best solution>
from
    <all possible combinations>

Część „najlepszego rozwiązania” została zdefiniowana w pytaniu - najmniejsza różnica między najbardziej obciążonymi i najmniej obciążonymi ciężarówkami. Druga część - wszystkie kombinacje - spowodowała, że ​​zastanowiłem się.

Rozważmy sytuację, w której mamy trzy zamówienia A, B i C oraz trzy ciężarówki. Możliwości są

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.

Wiele z nich jest symetrycznych. Na przykład pierwsze sześć rzędów różni się tylko tym, w jakiej ciężarówce jest składane każde zamówienie. Ponieważ ciężarówki można zamieniać, te aranżacje przyniosą ten sam rezultat. Na razie zignoruję to.

Znane są zapytania dotyczące tworzenia permutacji i kombinacji. Powodują one jednak ustalenia w ramach jednego segmentu. W przypadku tego problemu potrzebuję uzgodnień między wieloma segmentami.

Patrząc na wynik standardowego zapytania „wszystkie kombinacje”

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

Zauważyłem, że wyniki uformowały taki sam wzór jak w Tabeli A. Dokonując sprytnego skoku biorąc pod uwagę każdą kolumnę jako Zamówienie ¹ , wartości określające, która ciężarówka będzie utrzymywać to Zamówienie, a rząd jako układ Zamówień w ciężarówkach. Zapytanie staje się następnie

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.

Rozwijając to, aby objąć czternaście zamówień w przykładowych danych, i upraszczając nazwy, otrzymujemy to:

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

Dla wygody wybieram przechowywanie wyników pośrednich w tabelach tymczasowych.

Kolejne kroki będą znacznie łatwiejsze, jeśli dane zostaną po raz pierwszy UNPIVOTED.

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.

Wagi można wprowadzić, łącząc się z tabelą Zamówienia.

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

Można teraz odpowiedzieć na pytanie, znajdując układy, które mają najmniejszą różnicę między najczęściej załadowanymi i najmniej załadowanymi ciężarówkami

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

Dyskusja

Jest z tym bardzo wiele problemów. Po pierwsze, jest to algorytm brutalnej siły. Liczba wierszy w tabelach roboczych jest wykładnicza pod względem liczby ciężarówek i zamówień. Liczba wierszy w #Arrangements to (liczba ciężarówek) ^ (liczba zamówień). To nie będzie dobrze skalować.

Po drugie, zapytania SQL mają osadzoną liczbę zamówień. Jedynym sposobem na obejście tego jest użycie dynamicznego SQL, który ma własne problemy. Jeśli liczba zamówień jest w tysiącach, może przyjść czas, kiedy wygenerowany SQL stanie się zbyt długi.

Trzecia to nadmiarowość w ustaleniach. Powoduje to nadmierne powiększanie tabel pośrednich, zwiększając znacznie czas działania.

Po czwarte, wiele wierszy w #Arrangements pozostawia jedną lub więcej ciężarówek pustych. Nie może to być optymalna konfiguracja. Łatwo byłoby odfiltrować te wiersze podczas tworzenia. Zdecydowałem się tego nie robić, aby kod był prostszy i bardziej skoncentrowany.

Z drugiej strony ma to wpływ na ujemne ciężary, jeśli Twoje przedsiębiorstwo zacznie kiedykolwiek wysyłać wypełnione balony z helem!

Myśli

Gdyby istniał sposób na wypełnienie #FilledTrucks bezpośrednio z listy ciężarówek i zamówień, myślę, że najgorszym z tych problemów można by zaradzić. Niestety moja wyobraźnia natknęła się na tę przeszkodę. Mam nadzieję, że jakiś przyszły współpracownik może być w stanie dostarczyć to, co mi umknęło.

¹ Mówisz, że wszystkie elementy zamówienia muszą znajdować się w tej samej ciężarówce. Oznacza to, że atomem przypisania jest Zamówienie, a nie Zamówienie Szczegóły. Wygenerowałem je z danych testowych w ten sposób:

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

Nie ma jednak znaczenia, czy oznaczymy przedmiotowe pozycje „Zamów”, czy „Szczegóły zamówienia”, rozwiązanie pozostaje takie samo.

Patrząc na twoje wymagania w świecie rzeczywistym (zakładam, że próbuję zrównoważyć twoje obciążenie pracą przez zestaw procesorów) ...

Czy istnieje powód, dla którego trzeba wstępnie przypisywać procesy do określonych segmentów / procesorów? [Próbuje zrozumieć twoje prawdziwe wymagania]

Na przykład „aktualizacji statystyk”, skąd wiesz, ile czasu zajmie dana operacja? Co się stanie, jeśli dana operacja napotka nieoczekiwane opóźnienie (np. Nadmierna planowana / nadmierna fragmentacja tabeli / indeksu, długo działający użytkownik txn blokuje operację „aktualizacji statystyk”)?

Dla celów równoważenia obciążenia zazwyczaj generuję listę zadań (np. Listę tabel, aby zaktualizować statystyki) i umieszczam tę listę w tabeli (tymczasowej / zadrapania).

Struktura tabeli może być modyfikowana zgodnie z Twoimi wymaganiami, np .:

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
)

Następnie rozpoczynam X równoczesnych procesów, aby wykonać rzeczywiste operacje „aktualizacji statystyk”, przy czym każdy proces wykonuje następujące czynności:

• umieść wyłączną blokadę na tasksstole (zapewnia, że ​​żadne zadanie nie zostanie odebrane przez więcej niż jeden proces; powinna być relatywnie krótkotrwałą blokadą)
• znajdź „pierwszy” wiersz, w którym start = NULL(„pierwszy” zostanie określony przez Ciebie, np. uporządkować według priority?)
• zaktualizuj zestaw wierszy start = getdate(), thread = <process_number>
• zatwierdzić aktualizację (i zwolnić blokadę wyłączną)
• zanotuj idi target/commandwartości
• wykonaj żądaną operację przeciwko target(alternatywnie, uruchom command), a po zakończeniu ...
• zaktualizuj za taskspomocąend = getdate() where id = <id>
• powtarzaj powyżej, aż nie będzie więcej zadań do wykonania

Dzięki powyższemu projektowi mam teraz dynamicznie (głównie) zrównoważoną operację.

UWAGI:

• Staram się podać jakąś metodę ustalania priorytetów, aby móc rozpocząć od dłuższych zadań; podczas gdy kilka procesów pracuje nad dłużej działającymi zadaniami, inne procesy mogą przeglądać listę krótszych zadań
• jeśli proces napotka nieplanowane opóźnienie (np. długo działający, blokujący txn użytkownika), inne procesy mogą „nabrać luzu”, kontynuując pobieranie operacji „następnej dostępnej” z tasks
• konstrukcja taskstabeli powinna zapewniać inne korzyści, np. historię czasów wykonywania, które można zarchiwizować do wykorzystania w przyszłości, historię czasów pracy, które można wykorzystać do modyfikacji priorytetów, zapewnienia statusu bieżących operacji itp.
• chociaż „blokada wyłączności” tasksmoże wydawać się nieco nadmierna, pamiętaj, że musimy zaplanować potencjalny problem 2 (lub więcej) procesów próbujących uzyskać nowe zadanie w tym samym czasie , więc musimy zagwarantować zadanie jest przypisany tylko do jednego procesu (i tak, można uzyskać te same wyniki za pomocą komendy „update / select” - zależnie od możliwości języka SQL RDBMS); etap uzyskania nowego „zadania” powinien być szybki, tj. „blokada wyłączności” powinna być krótkotrwała, a w rzeczywistości procesy będą uderzać tasksw dość losowy sposób, więc i tak będzie mało blokować

Osobiście uważam, że ten tasksproces oparty na tabeli jest nieco łatwiejszy do wdrożenia i utrzymania ... w przeciwieństwie do (zwykle) bardziej złożonego procesu próbowania wstępnego przypisania mapowania zadań / procesów ... ymmv.

Oczywiście dla twojego przykładu, nie możesz kazać swoim ciężarówkom wracać do dystrybucji / magazynu dla następnego zamówienia, więc musisz wstępnie przypisać swoje zamówienia do różnych ciężarówek (pamiętając, że UPS / Fedex / itp. Również muszą przypisywanie na podstawie tras dostaw, aby skrócić czas dostawy i zużycie gazu).

Jednak w twoim przykładzie z prawdziwego świata („aktualizacja statystyk”) nie ma powodu, dla którego przypisania zadania / procesu nie mogą być wykonywane dynamicznie, co zapewnia większą szansę na zrównoważenie obciążenia pracą (między procesami i pod względem skrócenia ogólnego czasu działania) .

UWAGA: Rutynowo widzę ludzi (IT), którzy próbują wstępnie przypisać swoje zadania (jako formę równoważenia obciążenia) przed faktycznym uruchomieniem tych zadań, i w każdym przypadku musi on stale dostosowywać proces wstępnego przypisania, aby podjąć biorąc pod uwagę stale zmieniające się problemy dotyczące zadań (np. poziom fragmentacji w tabeli / indeksie, równoczesna aktywność użytkownika itp.)

utwórz i wypełnij tabelę liczb według własnego uznania. Jest to jednorazowe stworzenie.

 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)

Utworzono stół dla ciężarówek

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 )

Stworzyłem jeden OrderSummarystół

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

Sprawdź moją wartość Delta i daj mi znać, jeśli jest niepoprawna

;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 

Możesz sprawdzić wynik CTE1, to wszystko jest możliwe Permutation and Combination of order along with their size.

Jeśli moje podejście jest poprawne do tej pory, potrzebuję pomocy.

Oczekujące zadanie:

filtruj i dziel wynik CTE1na 3 części ( Truck count), tak, że Orderidjest unikalny dla każdej grupy, a każda część T ruckOrderSizejest zbliżona do Delta.