Hallo, Radio SQL ist wieder auf Sendung! Heute haben wir eine Lösung für das Problem , das wir in unserer vorherigen Sendung übertragen haben, und haben versprochen, das nächste Mal auszumachen. Und das nächste Mal ist gekommen.
Die Aufgabe löste eine lebhafte Reaktion unter den Humanoiden der Milchstraße aus (und nicht überraschend mit ihrer Arbeitssklaverei, die sie immer noch zum Wohle der Zivilisation respektieren). Leider wurde auf dem dritten Planeten der Start des Spectrum-RG-Weltraumobservatoriums Ende Juli 2019, der RC (Local Chronology), verschoben, mit deren Hilfe die Ausstrahlung dieser Sendung geplant war. Ich musste nach alternativen Übertragungswegen suchen, was zu einer leichten Verzögerung des Signals führte. Aber alles ist gut, das endet gut.
Ich muss sofort sagen, dass es keine Magie in der Analyse der Aufgabe geben wird, es nicht notwendig ist, hier nach Enthüllungen zu suchen oder auf eine besonders effektive (oder besonders in einem anderen Sinne) Implementierung zu warten. Dies ist nur eine Analyseaufgabe. Darin können diejenigen, die nicht wissen, wie sie sich der Lösung solcher Probleme nähern sollen, sehen, wie sie gelöst werden können. Außerdem gibt es hier nichts Schreckliches.
Lassen Sie mich Sie an den Zustand erinnern.Es gibt mehrere Zeitintervalle, die durch das Datum und die Uhrzeit des Beginns und Endes angegeben werden (ein Beispiel in der PostgreSQL-Syntax):
with periods(id, start_time, stop_time) as ( values(1, '2019-03-29 07:00:00'::timestamp, '2019-04-08 14:00:00'::timestamp), (2, '2019-04-10 07:00:00'::timestamp, '2019-04-10 20:00:00'::timestamp), (3, '2019-04-11 12:00:00'::timestamp, '2019-04-12 16:07:12'::timestamp), (4, '2018-12-28 12:00:00'::timestamp, '2019-01-16 16:00:00'::timestamp) )
In einer SQL-Abfrage (c) muss die Dauer jedes Intervalls in Arbeitsstunden berechnet werden. Wir glauben, dass wir wochentags von Montag bis Freitag arbeiten, die Arbeitszeiten sind immer von 10:00 bis 19:00 Uhr. Darüber hinaus gibt es gemäß dem Produktionskalender der Russischen Föderation eine Reihe von offiziellen Feiertagen, die keine Arbeitstage sind, und einige der freien Tage sind im Gegenteil Arbeitstage, da dieselben Feiertage verschoben werden. Eine Verkürzung der Vorferientage ist nicht erforderlich, wir halten sie für vollständig. Da die Feiertage von Jahr zu Jahr variieren, dh durch explizite Auflistung festgelegt werden, beschränken wir uns auf Daten nur von 2018 und 2019. Ich bin sicher, dass die Lösung bei Bedarf leicht ergänzt werden kann.
Es ist erforderlich, eine Spalte mit der Dauer in Arbeitsstunden zu den Anfangsperioden von Perioden hinzuzufügen. Hier ist das Ergebnis:
id | start_time | stop_time | work_hrs
Wir überprüfen die Anfangsdaten nicht auf Richtigkeit, sondern berücksichtigen immer start_time <= stop_time .
Das Ende der Bedingung, das Original ist hier: https://habr.com/en/company/postgrespro/blog/448368/ .
Die Aufgabe verleiht der Tatsache, dass ich bewusst eine gute Hälfte der Bedingung bewusst in beschreibender Form angegeben habe (wie dies im wirklichen Leben der Fall ist), eine leichte Pikantheit, wobei es im Ermessen der technischen Implementierung liegt, wie der Zeitplan festgelegt werden soll. Dies erfordert zum einen einige architektonische Denkfähigkeiten. Andererseits hätte das vorgefertigte Format dieses Zeitplans zu einer Verwendung der Vorlage geführt. Und wenn Sie weglassen, werden Gedanken und Fantasien besser funktionieren. Der Empfang hat sich voll ausgezahlt und mir ermöglicht, auch in den veröffentlichten Lösungen interessante Ansätze zu finden.
Um das ursprüngliche Problem auf diese Weise zu lösen, müssen zwei Unteraufgaben gelöst werden:
- Bestimmen Sie, wie Sie einen Arbeitsplan am kompaktesten festlegen können und ob dies für eine Lösung bequem ist.
- Berechnen Sie tatsächlich die Dauer jeder Quellperiode in Arbeitsstunden gemäß dem Arbeitsplan aus der vorherigen Unteraufgabe.
Und es ist besser, mit der zweiten zu beginnen, um zu verstehen, in welcher Form wir die erste lösen müssen. Lösen Sie dann die erste und kehren Sie erneut zur zweiten zurück, um das Endergebnis zu erhalten.
Wir werden das Ergebnis schrittweise mithilfe der CTE-Syntax erfassen, mit der wir alle erforderlichen Datenbeispiele in separate benannte Unterabfragen einfügen und dann alles miteinander verknüpfen können.
Nun, lass uns gehen.
Berechnen Sie die Dauer in Arbeitsstunden
Um die Dauer jeder Arbeitszeit in der Stirn zu berechnen, müssen Sie die Anfangszeit (grüne Farbe im Diagramm) mit den Intervallen kreuzen, die die Arbeitszeit beschreiben (orange). Die Arbeitszeitintervalle sind montags von 10:00 bis 19:00 Uhr, dienstags von 10:00 bis 19:00 Uhr und so weiter. Das Ergebnis wird blau angezeigt:
Übrigens, um weniger verwirrt zu sein, werde ich die Anfangsperioden weiterhin als Anfangsperioden bezeichnen und Arbeitszeitintervalle aufrufen.
Der Vorgang sollte für jede Anfangsperiode wiederholt werden. Die Anfangsperioden für uns sind bereits auf der Registerkarte Perioden (start_time, stop_time) festgelegt . Wir werden die Arbeitszeiten in Form einer Tabelle darstellen, z. B. Zeitplan (strat_time, stop_time) , in der jeder Arbeitstag vorhanden ist. Das Ergebnis ist ein vollständiges kartesisches Produkt aller anfänglichen Perioden und Intervalle der Arbeitszeit.
Schnittpunkte können auf klassische Weise gezählt werden, wobei alle möglichen Optionen für Schnittintervalle berücksichtigt wurden - wir schneiden Grün mit Orange, das Ergebnis ist blau:
und jeweils den gewünschten Wert für den Anfang und das Ende des Ergebnisses nehmen:
select s.start_time, s.stop_time
Da wir für jede Kreuzung nur eine von vier Optionen haben können, werden alle mit union all zu einer Anfrage zusammengefasst.
Sie können dies auch tun, indem Sie den in PostgreSQL verfügbaren tsrange- Bereichstyp und die dafür bereits verfügbare Schnittmenge verwenden:
select tsrange(s.start_time, s.stop_time) * tsrange(s.start_time, s.stop_time) from periods p, schedule s
Stimmen Sie zu, dass es ein bisschen einfacher ist. Im Allgemeinen gibt es in PostgreSQL eine Menge solcher praktischen Kleinigkeiten, daher ist es sehr schön, Abfragen darüber zu schreiben.
Kalender generieren
Nun zurück zur Unteraufgabe mit dem Arbeitszeitplan.
Wir müssen den Arbeitsplan in Form von Arbeitszeitintervallen von 10:00 bis 19:00 für jeden Arbeitstag erhalten, so etwas wie einen Zeitplan (start_time, stop_time) . Wie wir verstanden haben, wird es zweckmäßig sein, unser Problem zu lösen. Im wirklichen Leben sollte ein solcher Zeitplan gedeckt werden, für zwei Jahre sind es nur etwa 500 Datensätze, aus praktischen Gründen müssen sogar zehn Jahre festgelegt werden - dies sind ein paar anderthalbtausend Datensätze, ein echter Müll für moderne Datenbanken. Wir haben jedoch ein Problem, das in einer Anfrage gelöst werden kann, und die Auflistung der gesamten Tabelle ist nicht sehr praktisch. Versuchen wir es kompakter zu implementieren.
In jedem Fall benötigen wir Feiertage, um sie aus dem Basisplan zu entfernen, und hier ist nur die Auflistung geeignet:
dates_exclude(d) as ( values('2018-01-01'::date),
und zusätzliche Werktage, die hinzugefügt werden müssen:
dates_include(d) as ( values
Die Reihenfolge der Arbeitstage für zwei Jahre kann durch eine spezielle und sehr geeignete Funktion generate_series () generiert werden, die sofort Samstage und Sonntage auf dem Weg wirft:
select d from generate_series( '2018-01-01'::timestamp , '2020-01-01'::timestamp , '1 day'::interval ) as d where extract(dow from d) not in (0,6)
Wir erhalten die Arbeitstage, indem wir alles miteinander verbinden: Wir generieren eine Folge aller Arbeitstage in zwei Jahren, fügen zusätzliche Arbeitstage aus date_include hinzu und entfernen alle zusätzlichen Tage aus date_exclude :
schedule_base as ( select d from generate_series( '2018-01-01'::timestamp , '2020-01-01'::timestamp , '1 day'::interval ) as d where extract(dow from d) not in (0,6)
Und jetzt bekommen wir die Zeitintervalle, die wir brauchen:
schedule(start_time, stop_time) as ( select d + '10:00:00'::time, d + '19:00:00'::time from schedule_base )
Also haben wir den Zeitplan.
Alles zusammenfügen
Jetzt bekommen wir die Kreuzungen:
select p.* , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh from periods p join schedule s on tsrange(p.start_time, p.stop_time) && tsrange(s.start_time, s.stop_time)
Beachten Sie die ON- Verknüpfungsbedingung, sie stimmt nicht mit zwei entsprechenden Datensätzen aus den verknüpften Tabellen überein, es gibt keine solche Entsprechung, aber es wird eine Optimierung eingeführt, die die Arbeitszeitintervalle verkürzt, mit denen sich unsere Anfangsperiode nicht überschneidet. Dies erfolgt mit dem Operator && , der den Schnittpunkt der Bereichsintervalle überprüft. Dadurch werden viele leere Kreuzungen entfernt, um den Augen nicht im Weg zu stehen. Auf der anderen Seite werden jedoch Informationen zu den Anfangsperioden entfernt, die vollständig außerhalb der Geschäftszeiten liegen. Wir bewundern also, dass unser Ansatz funktioniert, und schreiben die Anfrage wie folgt um:
periods_wrk as ( select p.* , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh from periods p , schedule s ) select id, start_time, stop_time , sum(upper(wrkh)-lower(wrkh)) from periods_wrk group by id, start_time, stop_time
In period_wrk zerlegen wir jede Quellperiode in Arbeitsintervalle und betrachten dann ihre Gesamtdauer. Das Ergebnis war ein vollständiges kartesisches Produkt aller Zeiträume und Intervalle, aber es ging kein einziger Zeitraum verloren.
Alles, das Ergebnis wird empfangen. Die NULL- Werte für leere Intervalle haben mir nicht gefallen. Lassen Sie die Abfrage ein Intervall mit der Länge Null besser anzeigen. Wickeln Sie die Menge in coalesce () :
select id, start_time, stop_time , coalesce(sum(upper(wrkh)-lower(wrkh)), '0 sec'::interval) from periods_wrk group by id, start_time, stop_time
Alles zusammen ergibt das Endergebnis:
with periods(id, start_time, stop_time) as ( values(1, '2019-03-29 07:00:00'::timestamp, '2019-04-08 14:00:00'::timestamp) , (2, '2019-04-10 07:00:00'::timestamp, '2019-04-10 20:00:00'::timestamp) , (3, '2019-04-11 12:00:00'::timestamp, '2019-04-12 16:00:00'::timestamp) , (4, '2018-12-28 12:00:00'::timestamp, '2019-01-16 16:00:00'::timestamp) ), dates_exclude(d) as ( values('2018-01-01'::date),
Hurra! .. Dies könnte abgeschlossen sein, aber der Vollständigkeit halber werden wir einige verwandte Themen betrachten.
Weiterentwicklung des Themas
Verkürzte Vorferientage, Mittagspausen, unterschiedliche Zeitpläne für verschiedene Wochentage ... Im Prinzip ist alles klar, Sie müssen die Definition des Zeitplans festlegen, geben Sie nur ein paar Beispiele.
So können Sie je nach Wochentag unterschiedliche Start- und Endzeiten eines Arbeitstages einstellen:
select d + case extract(dow from d) when 1 then '10:00:00'::time
Wenn Sie die Mittagspausen von 13:00 bis 14:00 Uhr berücksichtigen müssen, führen Sie anstelle eines Intervalls pro Tag zwei Schritte aus:
select d + '10:00:00'::time , d + '13:00:00'::time from schedule_base union all select d + '14:00:00'::time , d + '19:00:00'::time from schedule_base
Gut und so weiter.
Leistung
Ich werde ein paar Worte zur Leistung sagen, da es immer Fragen dazu gibt. Ich werde noch nicht viel kauen, dies ist ein Abschnitt mit einem Sternchen.
Im Allgemeinen ist eine vorzeitige Optimierung böse. Nach meiner langjährigen Beobachtung ist die Lesbarkeit des Codes der wichtigste Vorteil. Wenn der Code gut gelesen ist, ist es einfacher zu warten und zu entwickeln. Gut lesbarer Code erfordert implizit sowohl eine gute Lösungsarchitektur, korrekte Kommentare als auch gute Variablennamen, Kompaktheit ohne Beeinträchtigung der Lesbarkeit usw., dh alles, wofür der Code als gut bezeichnet wird.
Daher ist die Anfrage immer so lesbar wie möglich geschrieben, und wir beginnen genau dann mit der Optimierung, wenn sich herausstellt, dass die Leistung nicht ausreicht. Darüber hinaus werden wir es genau dort optimieren, wo die Leistung nicht ausreicht und genau so weit, dass es ausreicht. Wenn Sie Ihre eigene Zeit schätzen und etwas zu tun haben.
Es ist jedoch richtig, keine unnötige Arbeit in der Anfrage zu leisten. Sie sollten immer versuchen, dies zu berücksichtigen.
Auf dieser Grundlage werden wir sofort eine Optimierung in die Abfrage aufnehmen - lassen Sie jede Quellperiode nur mit den Arbeitszeitintervallen schneiden, mit denen sie gemeinsame Punkte hat (anstelle einer langen klassischen Bedingung an den Bereichsgrenzen ist es bequemer, den integrierten Operator && für den Typ tsrange zu verwenden). Diese Optimierung ist bereits in der Anfrage enthalten, hat jedoch dazu geführt, dass die anfänglichen Zeiträume, die vollständig außerhalb der Arbeitszeit lagen, aus den Ergebnissen verschwunden sind.
Bringen Sie diese Optimierung zurück. Verwenden Sie dazu LEFT JOIN , um alle Datensätze aus der Periodentabelle zu speichern. Jetzt sieht die Unterabfrage period_wrk folgendermaßen aus:
, periods_wrk as ( select p.* , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh from periods p left join schedule s on tsrange(p.start_time, p.stop_time) && tsrange(s.start_time, s.stop_time))
Die Analyse der Anfrage zeigt, dass sich die Zeit für die Testdaten um etwa die Hälfte verringert hat. Da die Laufzeit davon abhängt, was der Server zur gleichen Zeit tat, nahm ich einige Messungen vor und gab ein „typisches“ Ergebnis, nicht das größte, nicht das kleinste, aus der Mitte.
Alte Abfrage:
explain (analyse) with periods(id, start_time, stop_time) as ( ... QUERY PLAN
Neu:
explain (analyse) with periods(id, start_time, stop_time) as ( ... QUERY PLAN
Das Wichtigste ist jedoch, dass eine solche Anforderung auch besser skaliert wird und weniger Serverressourcen erfordert, da das gesamte kartesische Produkt sehr schnell wächst.
Und hier würde ich mit Optimierungen aufhören. Als ich dieses Problem für mich selbst löste, hatte ich selbst in einer viel schrecklicheren Form dieser Anfrage genug Leistung, aber es bestand wirklich kein Grund zur Optimierung. Um einmal im Quartal einen Bericht über meine Daten zu erhalten, kann ich weitere zehn Sekunden warten. Die zusätzliche Stunde, die für die Optimierung unter solchen Bedingungen aufgewendet wird, wird sich niemals auszahlen.
Es stellt sich jedoch als uninteressant heraus. Lassen Sie uns noch darüber nachdenken, wie sich Ereignisse entwickeln könnten, wenn eine Optimierung der Ausführungszeit wirklich erforderlich wäre. Zum Beispiel möchten wir diesen Parameter in Echtzeit für jeden unserer Datensätze in der Datenbank überwachen, dh für jedes Niesen wird eine solche Anforderung aufgerufen. Nun, oder überlegen Sie sich Ihren eigenen Grund, warum Sie optimieren müssen.
Das erste, was mir in den Sinn kommt, ist, einmal zu zählen und eine Tabelle mit Arbeitsintervallen in die Datenbank aufzunehmen. Es kann Kontraindikationen geben: Wenn die Datenbank nicht geändert werden kann oder Schwierigkeiten bei der Unterstützung relevanter Daten in einer solchen Tabelle zu erwarten sind. Dann müssen Sie die Generierung der Arbeitszeit „on the fly“ in der Anfrage selbst belassen, da dies keine sehr schwere Unterabfrage ist.
Der nächste und leistungsstärkste (aber nicht immer anwendbare) Ansatz ist die algorithmische Optimierung. Einige dieser Ansätze wurden bereits in den Kommentaren zum Artikel mit dem Zustand des Problems vorgestellt.
Ich mag dieses am meisten. Wenn Sie eine Tabelle mit allen (nicht nur Arbeitstagen) des Kalenders erstellen und die kumulierte Summe der Arbeitsstunden pro Tag aus einer bestimmten „Erschaffung der Welt“ berechnen, können Sie die Anzahl der Arbeitsstunden zwischen zwei Daten mit einer Subtraktionsoperation ermitteln. Es bleibt nur, die Arbeitszeiten für den ersten und letzten Tag korrekt zu berücksichtigen - und Sie sind fertig. Folgendes habe ich bei diesem Ansatz erreicht:
schedule_base(d, is_working) as ( select '2018-01-01'::date, 0 union all select d+1, case when extract(dow from d+1) not in (0,6) and d+1 <> all('{2019-01-01,2019-01-02,2019-01-03,2019-01-04,2019-01-07,2019-01-08,2019-03-08,2019-05-01,2019-05-02,2019-05-03,2019-05-09,2019-05-10,2019-06-12,2019-11-04,2018-01-01,2018-01-02,2018-01-03,2018-01-04,2018-01-05,2018-01-08,2018-02-23,2018-03-08,2018-03-09,2018-04-30,2018-05-01,2018-05-02,2018-05-09,2018-06-11,2018-06-12,2018-11-05,2018-12-31}') or d+1 = any('{2018-04-28,2018-06-09,2018-12-29}') then 1 else 0 end from schedule_base where d < '2020-01-01' ), schedule(d, is_working, work_hours) as ( select d, is_working , sum(is_working*'9 hours'::interval) over (order by d range between unbounded preceding and current row) from schedule_base ) select p.* , s2.work_hours - s1.work_hours + ('19:00:00'::time - least(greatest(p.start_time::time, '10:00:00'::time), '19:00:00'::time)) * s1.is_working - ('19:00:00'::time - least(greatest(p.stop_time::time, '10:00:00'::time), '19:00:00'::time)) * s2.is_working as wrk from periods p, schedule s1, schedule s2 where s1.d = p.start_time::date and s2.d = p.stop_time::date
Ich werde kurz erklären, was hier passiert. In der Unterabfrage Schedule_base generieren wir alle Tage des Kalenders für zwei Jahre und bestimmen an jedem Tag das Vorzeichen, ob der Arbeitstag (= 1) oder nicht (= 0). Darüber hinaus betrachten wir in der Zeitplan- Unterabfrage die Fensterfunktion als die kumulierte Gesamtzahl der Arbeitsstunden ab dem 01.01.2018. Es wäre möglich, alles in einer Unterabfrage zu erledigen, aber es würde sich als umständlicher herausstellen, was die Lesbarkeit beeinträchtigen würde. In der Hauptanfrage berücksichtigen wir dann die Differenz zwischen der Anzahl der Arbeitsstunden am Ende und am Anfang des Zeitraums und berücksichtigen, etwas blumig, die Arbeitszeit für den ersten und letzten Tag des Zeitraums. Floridität ist mit der Verschiebung der Zeit vor dem Beginn des Arbeitstages auf den Beginn und der Zeit nach dem Ende des Arbeitstages auf das Ende verbunden. Wenn der Teil der Anforderung mit Shedule_Base und Zeitplan in eine separate vorberechnete Tabelle entfernt wird (wie zuvor vorgeschlagen), wird die Anforderung zu einer völlig trivialen.
Vergleichen wir die Ausführung an einer größeren Stichprobe, um die durchgeführte Optimierung besser darzustellen. Für vier Zeiträume ab der Aufgabenbedingung wird mehr Zeit für die Erstellung eines Arbeitsplans aufgewendet.
Ich habe ungefähr dreitausend Perioden gebraucht. Ich werde nur die oberste zusammenfassende Zeile in EXPLAIN geben, typische Werte sind wie folgt.
Ursprüngliche Option:
GroupAggregate (cost=265790.95..296098.23 rows=144320 width=36) (actual time=656.654..894.383 rows=2898 loops=1) ...
Optimiert:
Hash Join (cost=45.01..127.52 rows=70 width=36) (actual time=1.620..5.385 rows=2898 loops=1) ...
Der Zeitgewinn betrug einige Größenordnungen. Mit der Zunahme der Anzahl der Perioden und ihrer Länge in Jahren wird sich der Abstand nur vergrößern.
Alles schien in Ordnung zu sein, aber warum habe ich nach einer solchen Optimierung die erste Version der Anfrage für mich belassen, bis ihre Leistung ausreichte? Ja, da die optimierte Version zweifellos schneller ist, aber viel mehr Zeit benötigt, um zu verstehen, wie sie funktioniert, dh die Lesbarkeit hat sich verschlechtert. Das heißt, wenn ich die Anfrage das nächste Mal unter meinen geänderten Bedingungen neu schreiben muss, muss ich (oder nicht ich) viel mehr Zeit damit verbringen, zu verstehen, wie die Anfrage funktioniert.
Das ist alles für heute, halten Sie die Tentakel warm und ich verabschiede mich von Ihnen bis zur nächsten Veröffentlichung von Radio SQL.