SQL HowTo: Erstellen von Ketten mit Fensterfunktionen

Bei der Analyse von Daten tritt manchmal das Problem auf , „Ketten“ in einer Stichprobe zu unterscheiden, dh geordnete Sequenzen von Datensätzen, für die jeweils eine bestimmte Bedingung erfüllt ist .

Dies kann entweder eine Bedingung für die Daten des Datensatzes selbst oder ein komplexer Ausdruck in Bezug auf einen oder mehrere vorherige Datensätze sein, z. B. die Länge des Intervalls zwischen Abtastungen zum Abschlusszeitpunkt.



Herkömmliche Lösungen bieten verschiedene Optionen für die "Selbstverknüpfung", wenn die Stichprobe eine Verbindung zu sich selbst herstellt, oder für die Verwendung bestimmter Fakten "außerhalb der Daten". Beispielsweise müssen Datensätze einen genau definierten Schritt haben (N + 1, "für jeden Tag", ...). )

Die erste Option führt häufig zu einer quadratischen Komplexität des Algorithmus in Bezug auf die Anzahl der Datensätze, die bei großen Stichproben nicht akzeptabel ist, und die zweite Option kann leicht „auseinanderfallen“, wenn die Quelldaten plötzlich keine Stichproben enthalten.

Diese Aufgabe hilft uns jedoch, Fensterfunktionen in PostgreSQL effektiv zu lösen.

Aufgabe: Das Geld anderer Leute zählen

Stellen Sie sich den einfachsten Fall einer Kette vor, bei dem die Kontinuitätsbedingung durch die Daten des Datensatzes selbst bestimmt wird.

Alle weiteren Vorgänge müssen nicht separat durchgeführt werden. Der Klarheit halber werde ich den Algorithmus jedoch in aufeinanderfolgende Schritte aufteilen und am Ende zeigen, was und wie optimiert werden muss .

Stellen wir uns vor, wir haben eine kleine Bank, die Guthaben auf Kundenkonten in der Tabelle verwaltet. Sobald die Eingangs- und Ausgabentransaktion stattfindet, wird mit diesem Datum auch der Gesamtrechnungsbetrag am Ende des Tages festgelegt.

Nach einem langen Neujahrsurlaub entschied sich die Bank, ihre Kunden zu belohnen - und jede Person, die in diesem Jahr ein Konto eröffnet hat, erhält zusätzlich + 1% des durchschnittlichen täglichen Kontostands für den längsten zusammenhängenden Zeitraum, in dem das Konto nicht „zurückgesetzt“ wurde .

Hier ist es unser Kriterium für die Kontinuität der "Kette". Nun, die Reihenfolge der Daten wird durch die Daten der Salden bestimmt.

Sie brachten uns eine solche CSV und fragten uns, wer und wie viel Großzügigkeit von der Bank bekommen sollte:

date;client;balance 01.01.2020;;150 01.01.2020;;100 02.01.2020;;100 02.01.2020;;150 03.01.2020;;200 05.01.2020;;0 06.01.2020;;50 08.01.2020;;0 08.01.2020;;200 09.01.2020;;0 09.01.2020;;0 10.01.2020;;5 

Beachten Sie nur einige Fakten, die sich in diesen Daten bemerkbar machen:

• 01.01 war ein Feiertag, und die Bank hat nicht funktioniert. Daher hat keiner der Kunden Aufzeichnungen über Änderungen des Kontostands an diesem Tag, aber sie haben Geld auf ihren Konten. Das heißt, "Brute Force" -Algorithmen, die am Tag wiederholt werden, funktionieren nicht normal.
• 04.01 Alice hat keine Operationen durchgeführt, daher gibt es keinen Eintrag. Aber vor dem 05.01 war der Betrag auf ihrem Konto nicht Null - dies muss bei der Analyse berücksichtigt werden.
• Wir führen die Analyse am 01.01.12.01 durch, aber der Kontostand von Alice am Ende dieses Zeitraums ist ungleich Null. Wir berücksichtigen auch die Notwendigkeit, den Zeitraum zu begrenzen.

CSV-to-Table

Der beste Weg, aus CSV zu importieren, ist die Verwendung des COPY-Operators . Aber wir werden versuchen, dies durch reguläre Ausdrücke zum Aufwärmen zu tun:

 CREATE TEMPORARY TABLE tbl AS SELECT to_date(prt[1], 'DD.MM.YYYY') dt , prt[2] client , prt[3]::numeric(32,2) balance FROM ( SELECT regexp_split_to_array(str, ';') prt FROM ( SELECT regexp_split_to_table( $$ date;client;balance 01.01.2020;;150 01.01.2020;;100 02.01.2020;;100 02.01.2020;;150 03.01.2020;;200 05.01.2020;;0 06.01.2020;;50 08.01.2020;;0 08.01.2020;;200 09.01.2020;;0 09.01.2020;;0 10.01.2020;;5 $$ , E'\\n') str ) T WHERE str <> '' OFFSET 1 ) T; 

Dies ist eine „unehrliche“ Methode in dem Sinne, dass sie nicht richtig verdaut wird, z. B. indem ein Separator im Körper eines Feldes abgeschirmt wird. Aber für die meisten einfachen Anwendungen - geeignet.

Schritt 1: Korrigieren Sie den Anwendungszustand

In unserem Fall ist die Kettenkontinuitätsbedingung ein Gleichgewicht ungleich Null. Wir zeigen es der Übersichtlichkeit halber als separates Feld an, in chronologischer Reihenfolge nach Kunden:

 SELECT * , balance > 0 cond FROM tbl ORDER BY client, dt; 

 dt | client | balance | cond ------------------------------------ 2020-01-01 |  | 150.00 | t 2020-01-02 |  | 100.00 | t 2020-01-03 |  | 200.00 | t 2020-01-05 |  | 0.00 | f 2020-01-06 |  | 50.00 | t 2020-01-08 |  | 0.00 | f 2020-01-09 |  | 0.00 | f 2020-01-10 |  | 5.00 | t 2020-01-01 |  | 100.00 | t 2020-01-02 |  | 150.00 | t 2020-01-08 |  | 200.00 | t 2020-01-09 |  | 0.00 | f 

Schritt 2: Berechnen Sie das Fehlen

Beachten Sie, dass sich der Betrag von Bob nicht von 02.01 auf 08.01 geändert hat. Und je nach den Bedingungen des Problems müssen wir den durchschnittlichen Tagesrest berechnen - das heißt, wir benötigen Informationen über diese „fehlenden“ Tage. Oder zumindest die Anzahl der Tage, an denen der Wert gleich blieb:

 coalesce(lead(dt) OVER(PARTITION BY client ORDER BY dt), '2020-01-12') - dt days 

 dt | client | balance | cond | days ------------------------------------------- 2020-01-01 |  | 150.00 | t | 1 2020-01-02 |  | 100.00 | t | 1 2020-01-03 |  | 200.00 | t | 2 2020-01-05 |  | 0.00 | f | 1 2020-01-06 |  | 50.00 | t | 2 2020-01-08 |  | 0.00 | f | 1 2020-01-09 |  | 0.00 | f | 1 2020-01-10 |  | 5.00 | t | 2 2020-01-01 |  | 100.00 | t | 1 2020-01-02 |  | 150.00 | t | 6 2020-01-08 |  | 200.00 | t | 1 2020-01-09 |  | 0.00 | f | 3 

Mit der Funktion lead () Fenster haben wir das Datum aus dem nächsten Datensatz in der angegebenen Reihenfolge gelernt und durch Zusammenführen das Intervall für den letzten Datensatz begrenzt. Gleichzeitig verwendeten sie die nützliche Eigenschaft, dass die Differenz zweier Daten in PostgreSQL eine ganze Zahl von Tagen zwischen ihnen zurückgibt .

Als beinahe kostenlosen Bonus erhielten wir alle gleichen Informationen für Datensätze mit einem Saldo von Null. Wenn es jedoch viele Zeilen mit einer nicht erfüllten Bedingung gibt, die uns nicht interessieren, ist es sinnvoll , solche Berechnungen unter CASE durchzuführen, um Serverressourcen zu sparen.

Schritt 3: Finden Sie die Haltepunkte

Der Anfang jeder Kette, an der wir interessiert sind, ist der Punkt, an dem sich der Wert der zuvor berechneten Bedingung relativ zum vorherigen Datensatz ändert. Wir werden die Funktion lag () verwenden, um solche Punkte zu finden:

 lag(cond) OVER(PARTITION BY client ORDER BY dt) IS DISTINCT FROM cond chain_start 

 dt | client | balance | cond | days | chain_start --------------------------------------------------------- 2020-01-01 |  | 150.00 | t | 1 | t 2020-01-02 |  | 100.00 | t | 1 | f 2020-01-03 |  | 200.00 | t | 2 | f 2020-01-05 |  | 0.00 | f | 1 | t 2020-01-06 |  | 50.00 | t | 2 | t 2020-01-08 |  | 0.00 | f | 1 | t 2020-01-09 |  | 0.00 | f | 1 | f 2020-01-10 |  | 5.00 | t | 2 | t 2020-01-01 |  | 100.00 | t | 1 | t 2020-01-02 |  | 150.00 | t | 6 | f 2020-01-08 |  | 200.00 | t | 1 | f 2020-01-09 |  | 0.00 | f | 3 | t 

Durch die Verwendung des Operators IS DISTINCT FROM anstelle von <> konnten die Probleme beim Vergleich mit NULL für die ersten Datensätze für jeden Client vermieden werden. Dementsprechend sind alle Zeilen, in denen der Wert TRUE der Anfang einer neuen Kette und FALSE deren Fortsetzung ist.

Schritt 4: Verknüpfen Sie die Links

Um Daten innerhalb jeder einzelnen Kette zu gruppieren, ist es am einfachsten, allen Datensätzen denselben Bezeichner zuzuweisen. Die Seriennummer der Kette selbst ist dafür perfekt. Und es ist genau gleich der Anzahl der "Anfänge" von Ketten , die höher in der Stichprobe gefunden wurden.

Sie können entweder durch die "Fenster" -Summe der Bool-Werte ({boolean} :: integer) oder durch Zählen der Anzahl der Datensätze berechnet werden, die mit der Bedingung count (*) FILTER (WHERE {boolean} übereinstimmen. Wir werden die zweite Option verwenden:

 count(*) FILTER(WHERE chain_start) OVER(PARTITION BY client ORDER BY dt) grpid 

 dt | client | balance | cond | days | chain_start | grpid ----------------------------------------------------------------- 2020-01-01 |  | 150.00 | t | 1 | t | 1 2020-01-02 |  | 100.00 | t | 1 | f | 1 2020-01-03 |  | 200.00 | t | 2 | f | 1 2020-01-06 |  | 50.00 | t | 2 | t | 2 2020-01-10 |  | 5.00 | t | 2 | t | 3 2020-01-01 |  | 100.00 | t | 1 | t | 1 2020-01-02 |  | 150.00 | t | 6 | f | 1 2020-01-08 |  | 200.00 | t | 1 | f | 1 

In diesem Schritt kennen wir bereits die Länge aller Glieder in jeder Kette. Wir brauchen keine "uninteressanten" Datensätze mehr. Filtern Sie sie einfach heraus.

Schritt 5: Ketten setzen

Um den Durchschnitt aller Tage in einer Kette zu berechnen, benötigen wir die Gesamtzahl der Tage und den "integralen" Saldo:

 SELECT client , min(dt) chain_dt , sum(days * balance) balance , sum(days) days FROM ... GROUP BY 1, grpid ORDER BY 1, grpid; 

 client | chain_dt | balance | days -------------------------------------  | 2020-01-01 | 650.00 | 4  | 2020-01-06 | 100.00 | 2  | 2020-01-10 | 10.00 | 2  | 2020-01-01 | 1200.00 | 8 

Schritt 6: Suchen Sie nach Applied Highs

Mit DISTINCT ON hinterlassen wir für jeden Kunden einen einzigen Datensatz (mit einem Höchstwert von Tagen):

 SELECT DISTINCT ON(client) * FROM ... ORDER BY client, days DESC; 

 client | chain_dt | balance | days -------------------------------------  | 2020-01-01 | 650.00 | 4  | 2020-01-01 | 1200.00 | 8 

Eigentlich ist das alles, alles was noch übrig ist ...

Wir kombinieren und optimieren

Hier haben wir die ersten drei Schritte zusammengefasst und optimiert:

• Die LATERAL-Unterabfrage ermöglichte es uns, ein zusätzliches Feld zu berechnen, ohne die Auswahl unnötig zu durchlaufen, und es sofort in der Funktion zu verwenden
• Das Entfernen einer allgemeinen Definition unter WINDOW hilft PostgreSQL dabei, nicht doppelt zu sortieren, um ein „Fenster“ zu bilden und beide Funktionen in einem WindowAgg-Knoten zu berechnen
• Die Berechnung der Lazy- Funktion unter CASE reduziert die Anzahl der ausgeführten Operationen

In ähnlicher Weise haben wir die folgenden beiden Schritte kombiniert. Die Reihenfolge des „Fensters“ für die Berechnung der Aggregate (Client, Grpid) und der Eindeutigkeit (Client, Summe (Tage)) stimmte jedoch nicht überein. Daher befinden sich im letzten Block noch zwei Sortierknoten - vor WindowAgg und vor Unique.


[siehe EXPLAIN.TENSOR.RU]

Ich stelle fest, dass beim Nummerieren von Ketten zuerst die WHERE-Bedingung erfüllt wird , sodass sich die von der Fensterfunktion generierten Zahlen als sequenziell herausstellen.