Abfrageherausforderung: Erstellen gleichgroßer Buckets basierend auf einer Kennzahl ohne Zeilenanzahl

Ich beschreibe das Problem, indem ich eine feste Anzahl von LKWs mit Bestellungen so gleichmäßig wie möglich belade.

Eingänge:

@TruckCount - the number of empty trucks to fill

Ein Satz:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Ordersbestehen aus einem oder mehreren OrderDetails.

Hier besteht die Herausforderung darin, TruckIdjedem Datensatz ein zuzuweisen .

Eine einzelne Bestellung kann nicht auf mehrere Lkw aufgeteilt werden.

LKWs sollten möglichst gleichmäßig * beladen sein, gemessen an sum(OrderDetailSize).

* Gleichmäßig: Das kleinste erreichbare Delta zwischen dem am wenigsten beladenen und dem am meisten beladenen LKW. Nach dieser Definition ist 1,2,3 gleichmäßiger verteilt als 1,1,4. Wenn es hilft, tun Sie so, als wären Sie ein Statistikalgorithmus, der Histogramme mit gleichmäßiger Höhe erstellt.

Es wird keine maximale LKW-Ladung berücksichtigt. Dies sind magische elastische Lastwagen. Die Anzahl der LKWs ist jedoch festgelegt.

Es gibt offensichtlich eine iterative Lösung: Round-Robin-Zuweisung von Befehlen.

Aber kann es als satzbasierte Logik durchgeführt werden?

Mein Hauptinteresse gilt SQL Server 2014 oder höher. Aber auch Set-basierte Lösungen für andere Plattformen könnten interessant sein.

Das fühlt sich an wie Itzik Ben-Gan Gebiet :)

Meine reale Anwendung verteilt eine Verarbeitungsauslastung auf eine Anzahl von Buckets, die der Anzahl der logischen CPUs entsprechen. Daher hat jeder Eimer keine maximale Größe. Insbesondere Statistik-Updates. Ich dachte nur, dass es mehr Spaß macht, das Problem in Lastwagen zusammenzufassen, um die Herausforderung zu formulieren.

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

Mein erster Gedanke war

select
    <best solution>
from
    <all possible combinations>

Der Teil "Beste Lösung" wird in der Frage definiert - der kleinste Unterschied zwischen den am meisten beladenen und den am wenigsten beladenen Lastwagen. Das andere Stück - alle Kombinationen - ließ mich nachdenken.

Stellen Sie sich eine Situation vor, in der wir drei Aufträge A, B und C sowie drei Lastwagen haben. Die Möglichkeiten sind

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.

Viele davon sind symmetrisch. Die ersten sechs Zeilen unterscheiden sich beispielsweise nur darin, in welchem ​​Lkw jede Bestellung aufgegeben wird. Da die Lastwagen fungibel sind, erzielen diese Arrangements das gleiche Ergebnis. Ich werde das jetzt ignorieren.

Es sind Abfragen zum Erzeugen von Permutationen und Kombinationen bekannt. Diese werden jedoch Anordnungen innerhalb eines einzelnen Eimers erzeugen. Für dieses Problem brauche ich Vereinbarungen über mehrere Eimer.

Betrachtet man die Ausgabe der Standardabfrage "Alle Kombinationen"

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

Ich bemerkte, dass die Ergebnisse dasselbe Muster wie in Tabelle A bildeten. Indem ich den Gesamtsprung machte, jede Spalte als eine Bestellung ^{1 zu betrachten} , die Werte , die besagen, welcher LKW diese Bestellung enthält, und eine Reihe , die eine Anordnung von Bestellungen innerhalb von LKWs darstellt. Die Abfrage wird dann

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.

Erweitern Sie dies, um die vierzehn Befehle in den Beispieldaten abzudecken, und vereinfachen Sie die Namen, die wir erhalten:

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

Ich halte die Zwischenergebnisse der Einfachheit halber in temporären Tabellen.

Nachfolgende Schritte werden viel einfacher, wenn die Daten zuerst UNPIVOTED sind.

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.

Gewichte können durch Hinzufügen zur Tabelle "Bestellungen" eingegeben werden.

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

Die Frage kann nun beantwortet werden, indem die Anordnung (en) gefunden werden, die den geringsten Unterschied zwischen am meisten beladenen und am wenigsten beladenen Lastwagen aufweisen

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

Diskussion

Es gibt sehr viele Probleme damit. Erstens ist es ein Brute-Force-Algorithmus. Die Anzahl der Zeilen in den Arbeitstabellen ist in Bezug auf die Anzahl der Lastkraftwagen und Aufträge exponentiell. Die Anzahl der Zeilen in #Arrangements ist (Anzahl der Lastwagen) ^ (Anzahl der Bestellungen). Dies wird nicht gut skalieren.

Zweitens ist in den SQL-Abfragen die Anzahl der Bestellungen eingebettet. Der einzige Weg, dies zu umgehen, ist die Verwendung von dynamischem SQL, das seine eigenen Probleme hat. Wenn die Anzahl der Bestellungen in Tausenden liegt, kann es vorkommen, dass die generierte SQL zu lang wird.

Drittens ist die Redundanz in den Vereinbarungen. Dadurch werden die Zwischentabellen aufgebläht und die Laufzeit erheblich erhöht.

Viertens lassen viele Zeilen in #Arrangements einen oder mehrere Lastwagen leer. Dies kann unmöglich die optimale Konfiguration sein. Es wäre einfach, diese Zeilen bei der Erstellung herauszufiltern. Ich habe beschlossen, dies nicht zu tun, um den Code einfacher und fokussierter zu halten.

Auf der anderen Seite können negative Gewichte verarbeitet werden, falls Ihr Unternehmen jemals mit dem Versand gefüllter Heliumballons beginnen sollte!

Gedanken

Wenn es eine Möglichkeit gäbe, #FilledTrucks direkt aus der Liste der LKWs und Aufträge zu übernehmen, wären die schlimmsten dieser Bedenken meines Erachtens beherrschbar. Leider stolperte meine Vorstellungskraft über diese Hürde. Ich hoffe, dass ein zukünftiger Mitwirkender das liefern kann, was mir entgangen ist.

¹ Sie sagen, dass sich alle Artikel für eine Bestellung auf demselben LKW befinden müssen. Dies bedeutet, dass das Zuweisungsatom der Auftrag und nicht der Auftragsdetail ist. Ich habe diese aus Ihren Testdaten so generiert:

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

Es macht jedoch keinen Unterschied, ob wir die betreffenden Artikel mit "Bestellung" oder "BestellDetail" kennzeichnen, die Lösung bleibt gleich.

Ein Blick auf Ihre Anforderungen aus der realen Welt (von denen ich annehme, dass es sich um den Versuch handelt, Ihre Arbeitslast über eine Reihe von CPUs zu verteilen) ...

Gibt es einen Grund, warum Sie Prozesse bestimmten Buckets / CPUs vorab zuweisen müssen? [Der Versuch, Ihre tatsächlichen Anforderungen zu verstehen ]

Woher wissen Sie, wie lange ein bestimmter Vorgang in Anspruch nehmen wird, wenn Sie ein Beispiel für die Aktualisierung von Statistiken verwenden? Was passiert, wenn eine bestimmte Operation in eine unerwartete Verzögerung gerät (z. B. mehr als geplante / übermäßige Fragmentierung von Tabelle / Index, lang andauernder Benutzer txn blockiert eine 'Statistikaktualisierungs'-Operation)?

Zu Lastenausgleichszwecken generiere ich normalerweise die Liste der Aufgaben (z. B. Liste der Tabellen, deren Statistiken aktualisiert werden sollen) und platziere diese Liste in einer (temporären / temporären) Tabelle.

Die Struktur der Tabelle kann nach Ihren Wünschen angepasst werden, zB:

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
)

Als nächstes starte ich X gleichzeitige Prozesse, um die eigentlichen "Statistiken aktualisieren" -Operationen auszuführen, wobei jeder Prozess Folgendes ausführt:

• Setzen Sie eine exklusive Sperre auf den tasksTisch (stellt sicher, dass keine Aufgabe von mehr als einem Prozess übernommen wird; sollte eine relativ kurzlebige Sperre sein)
• 'first' row where finden start = NULL('first' würde von dir bestimmt, zB order by priority?)
• Zeilengruppe aktualisieren start = getdate(), thread = <process_number>
• Update festschreiben (und exklusive Sperre aufheben)
• notiere idund target/commandwerte
• targetFühren Sie die gewünschte Operation gegen (alternativ ausführen command) und wenn Sie fertig sind ...
• aktualisiere tasksmitend = getdate() where id = <id>
• Wiederholen Sie den Vorgang, bis keine weiteren Aufgaben mehr ausgeführt werden müssen

Mit dem obigen Design habe ich jetzt einen dynamisch (größtenteils) ausgeglichenen Betrieb.

ANMERKUNGEN:

• Ich versuche, eine Art Priorisierungsmethode bereitzustellen, damit ich die länger laufenden Aufgaben im Vorfeld starten kann. Während ein paar Prozesse an den länger laufenden Aufgaben arbeiten, können die anderen Prozesse die Liste der kürzer laufenden Aufgaben durchgehen
• Wenn ein Prozess auf eine ungeplante Verzögerung stößt (z. B. eine lange Laufzeit, die den Benutzer txn blockiert), können andere Prozesse die Lücke schließen, indem sie den nächsten verfügbaren Vorgang fortsetzen tasks
• Das Design der tasksTabelle sollte weitere Vorteile bieten, z. B. einen Verlauf von Laufzeiten, die Sie zur späteren Bezugnahme archivieren können, einen Verlauf von Laufzeiten, mit denen Prioritäten geändert werden können, einen Status aktueller Vorgänge usw
• während die auf ‚exklusive Sperre‘ tasksübermäßigen ein wenig erscheinen mag, bedenken wir haben für das potenzielle Problem Plan von 2 (oder mehr) Prozessen versuchen , eine neue Aufgabe zu erhalten exakt zur selben Zeit , so dass wir eine Aufgabe gewährleisten , müssen ist nur einem Prozess zugeordnet (und ja, Sie können die gleichen Ergebnisse mit einer kombinierten 'update / select'-Anweisung erzielen - abhängig von den SQL-Sprachfähigkeiten Ihres RDBMS). Der Schritt des Erhaltens einer neuen "Aufgabe" sollte schnell sein, dh die "exklusive Sperre" sollte von kurzer Dauer sein und in Wirklichkeit werden die Prozesse tasksin einer ziemlich zufälligen Weise ablaufen, so dass sowieso wenig blockiert wird

Persönlich finde ich diesen taskstabellengesteuerten Prozess ein bisschen einfacher zu implementieren und zu warten ... im Gegensatz zu einem (normalerweise) komplexeren Prozess, bei dem versucht wird, Aufgaben- / Prozesszuordnungen vorab zuzuweisen ... ymmv.

Offensichtlich für Ihr Make glauben Beispiel Sie nicht Ihre Lastwagen geht zurück auf die Verteilung / Lager für den nächsten Auftrag haben, so dass Sie benötigen , Ihre Aufträge zu verschiedenen Lkw vorbelegen ( wenn man bedenkt, dass UPS / Fedex / etc haben auch anhand der Lieferwege zuordnen, um Lieferzeiten und Gasverbrauch zu reduzieren).

In Ihrem Beispiel aus der realen Welt ("Aktualisierung der Statistiken") gibt es jedoch keinen Grund, warum die Aufgaben- / Prozesszuweisungen nicht dynamisch ausgeführt werden können, wodurch eine bessere Chance für die Verteilung der Arbeitslast (über den gesamten Prozessor und im Hinblick auf die Reduzierung der Gesamtlaufzeit) gewährleistet wird. .

HINWEIS: Ich routinemäßig sehen (IT) versuchen , die Leute ihre Aufgaben zur Vorbelegung (als eine Form der Load - Balancing) , bevor sie tatsächlich Aufgaben der ausgeführt wird , und in jedem Fall er / sie endet mit bis zu ständig die Vorbelegung Prozess optimieren zu nehmen Berücksichtigung ständig wechselnder Aufgabenbereiche (z. B. Fragmentierungsgrad in Tabelle / Index, gleichzeitige Benutzeraktivität usw.).

Erstellen und füllen Sie die Nummerntabelle nach Ihren Wünschen. Dies ist nur eine einmalige Erstellung.

 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)

Erstellt LKW-Tabelle

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 )

Ich habe eine OrderSummaryTabelle erstellt

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

Bitte überprüfen Sie meinen Delta-Wert und teilen Sie mir mit, ob er falsch ist

;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 

Sie können das Ergebnis von CTE1 überprüfen, es hat alles möglich Permutation and Combination of order along with their size.

Wenn mein Ansatz bis hier richtig ist, dann brauche ich jemanden, der mir hilft.

Ausstehende Aufgabe:

filter and Divide result von CTE1in bis 3 part ( Truck count), so dass Orderides für jede Gruppe einzigartig ist und jeder Teil T ruckOrderSizein der Nähe von Delta liegt.