Wie erhalte ich das Aggregat einer Fensterfunktion in Postgres?

11

Ich habe eine Tabelle mit zwei Spalten mit Permutationen / Kombinationen von ganzzahligen Arrays und eine dritte Spalte mit einem Wert wie folgt:

CREATE TABLE foo
(
  perm integer[] NOT NULL,
  combo integer[] NOT NULL,
  value numeric NOT NULL DEFAULT 0
);
INSERT INTO foo
VALUES
( '{3,1,2}', '{1,2,3}', '1.1400' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '1.2680' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '1.2680' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '1.2680' ),
( '{3,1,2}', '{1,2,3}', '0.9280' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '1.2680' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,1,2}', '{1,2,3}', '1.2680' ),
( '{3,1,2}', '{1,2,3}', '0' ),
( '{3,2,1}', '{1,2,3}', '0' ),
( '{3,2,1}', '{1,2,3}', '0.8000' )

Ich möchte den Durchschnitt und die Standardabweichung für jede Permutation sowie für jede Kombination herausfinden. Ich kann das mit dieser Abfrage machen:

SELECT
  f1.perm,
  f2.combo,
  f1.perm_average_value,
  f2.combo_average_value,
  f1.perm_stddev,
  f2.combo_stddev,
  f1.perm_count,
  f2.combo_count
FROM
(
  SELECT
    perm,
    combo,
    avg( value ) AS perm_average_value,
    stddev_pop( value ) AS perm_stddev,
    count( * ) AS perm_count
  FROM foo
  GROUP BY perm, combo
) AS f1
JOIN
(
  SELECT
    combo,
    avg( value ) AS combo_average_value,
    stddev_pop( value ) AS combo_stddev,
    count( * ) AS combo_count
  FROM foo
  GROUP BY combo
) AS f2 ON ( f1.combo = f2.combo );

Diese Abfrage kann jedoch ziemlich langsam werden, wenn ich viele Daten habe, da die "foo" -Tabelle (die in Wirklichkeit aus 14 Partitionen mit jeweils ungefähr 4 Millionen Zeilen besteht) zweimal gescannt werden muss.

Kürzlich habe ich erfahren, dass Postgres "Fensterfunktionen" unterstützt, was im Grunde wie ein GROUP BY für eine bestimmte Spalte ist. Ich habe meine Abfrage so geändert, dass sie Folgendes verwendet:

SELECT
  perm,
  combo,
  avg( value ) as perm_average_value,
  avg( avg( value ) ) over w_combo AS combo_average_value,
  stddev_pop( value ) as perm_stddev,
  stddev_pop( avg( value ) ) over w_combo as combo_stddev,
  count( * ) as perm_count,
  sum( count( * ) ) over w_combo AS combo_count
FROM foo
GROUP BY perm, combo
WINDOW w_combo AS ( PARTITION BY combo );

Während dies für die Spalte "combo_count" funktioniert, sind die Spalten "combo_average_value" und "combo_stddev" nicht mehr korrekt. Es scheint, dass der Durchschnitt für jede Permutation genommen und dann für jede Kombination ein zweites Mal gemittelt wird, was falsch ist.

Wie kann ich das beheben? Können Fensterfunktionen hier überhaupt als Optimierung verwendet werden?

Scott Small
quelle
Angenommene aktuelle Version Postgres 9.2? Fensterfunktionen kamen mit 8.4.
Erwin Brandstetter
Entschuldigung, ich habe vergessen anzugeben. Ja, ich verwende die neueste Version, Postgres 9.2.4.
Scott Small

Antworten:

9

Sie können Fensterfunktionen für das Ergebnis von Aggregatfunktionen in einer einzelnen Abfrageebene haben.

Dies alles würde nach ein paar Änderungen gut funktionieren - außer dass es für die Standardabweichung nach dem mathematischen Prinzip fehlschlägt . Die beteiligten Berechnungen sind nicht linear, daher können Sie Standardabweichungen von Teilpopulationen nicht einfach kombinieren.

SELECT perm
      ,combo
      ,avg(value)                 AS perm_average_value
      ,sum(avg(value) * count(*)) OVER w_combo /
       sum(count(*)) OVER w_combo AS combo_average_value
      ,stddev_pop(value)          AS perm_stddev
      ,0                          AS combo_stddev  -- doesn't work!
      ,count(*)                   AS perm_count
      ,sum(count(*)) OVER w_combo AS combo_count
FROM   foo
GROUP  BY perm, combo
WINDOW w_combo  AS (PARTITION BY combo);

Denn combo_average_valuedu würdest diesen Ausdruck brauchen

sum(avg(value) * count(*)) OVER w_combo / sum(count(*)) OVER w_combo

Da brauchst du einen gewichteten Durchschnitt. (Der Durchschnitt einer Gruppe mit 10 Mitgliedern wiegt mehr als der Durchschnitt einer Gruppe mit nur 2 Mitgliedern!)

Das funktioniert :

SELECT DISTINCT ON (perm, combo)
       perm
      ,combo
      ,avg(value)        OVER wpc AS perm_average_value
      ,avg(value)        OVER wc  AS combo_average_value
      ,stddev_pop(value) OVER wpc AS perm_stddev
      ,stddev_pop(value) OVER wc  AS combo_stddev
      ,count(*)          OVER wpc AS perm_count
      ,count(*)          OVER wc  AS combo_count
FROM   foo
WINDOW wc  AS (PARTITION BY combo)
      ,wpc AS (PARTITION BY perm, combo);

Ich verwende hier zwei verschiedene Fenster und reduziere die Zeilen, mit DISTINCTdenen auch nach Fensterfunktionen angewendet wird.

Aber ich bezweifle ernsthaft, dass es schneller sein wird als Ihre ursprüngliche Anfrage. Ich bin mir ziemlich sicher, dass es nicht so ist.

Bessere Leistung bei geändertem Tabellenlayout

Arrays haben einen Overhead von 24 Bytes (geringfügige Abweichungen je nach Typ). Außerdem scheinen Sie einige Elemente pro Array und viele Wiederholungen zu haben. Für eine große Tabelle wie Ihre würde es sich lohnen, das Schema zu normalisieren . Beispiellayout:

CREATE TABLE combo ( 
  combo_id serial PRIMARY KEY
 ,combo    int[] NOT NULL
);

CREATE TABLE perm ( 
  perm_id  serial PRIMARY KEY
 ,perm     int[] NOT NULL
);

CREATE TABLE value (
  perm_id  int REFERENCES perm(perm_id)
 ,combo_id int REFERENCES combo(combo_id)
 ,value numeric NOT NULL DEFAULT 0
);

Wenn Sie keine referenzielle Integrität benötigen, können Sie die Fremdschlüsseleinschränkungen weglassen.

Die Verbindung zu combo_idkönnte auch in die Tabelle eingefügt werden perm, aber in diesem Szenario würde ich sie valuefür eine bessere Leistung speichern (leicht de-normalisiert) .

Dies würde zu einer Zeilengröße von 32 Bytes führen (Tupel-Header + Auffüllen: 24 Bytes, 2 x int (8 Byte), kein Auffüllen) plus der unbekannten Größe Ihrer numericSpalte. (Wenn Sie keine extreme Präzision benötigen, reicht möglicherweise auch eine double precisionoder sogar eine realSpalte aus.)

Weitere Informationen zum physischen Speicher finden Sie in dieser Antwort zu SO oder hier:
Konfigurieren von PostgreSQL für die Leseleistung

Wie auch immer, das ist nur ein Bruchteil dessen, was Sie jetzt haben, und würde Ihre Anfrage allein aufgrund der Größe viel schneller machen. Das Gruppieren und Sortieren nach einfachen ganzen Zahlen ist auch viel schneller.

Sie würden zunächst in einer Unterabfrage Aggregat und dann beitreten permund combofür die beste Leistung.

Erwin Brandstetter
quelle
Vielen Dank für die klare und prägnante Antwort. Sie haben Recht, es scheint, dass es keine Möglichkeit gibt, die Standardabweichung einer Teilmengenpopulation auf diese Weise zu ermitteln. Davon abgesehen gefällt mir die Einfachheit Ihrer Lösung. Durch das Eliminieren von GROUP BY wird die resultierende Abfrage viel lesbarer. Wie Sie vermutet haben, ist die Leistung leider unterdurchschnittlich. Ich musste die Abfrage beenden, nachdem ich über 30 Minuten gelaufen war.
Scott Small
@ScottSmall: Sie könnten etwas für die Leistung tun ... siehe Update zur Antwort.
Erwin Brandstetter
Um meine Frage zu vereinfachen, habe ich die foonicht relevanten Spalten aus der Tabelle entfernt . In der Realität gibt es mehrere weitere Spalten, die von dieser Abfrage nicht verwendet werden. Daher bin ich nicht davon überzeugt, dass die Normalisierung der Permutationen und Kombinationen für diesen speziellen Anwendungsfall einen erheblichen Geschwindigkeitsschub bedeuten würde.
Scott Small
Darüber hinaus stammen die ganzzahligen Werte, aus denen jede Permutation und Kombination besteht, aus einer anderen Tabelle in der Datenbank. Das Vorgenerieren dieser Daten ist rechenintensiv. Die maximale Länge einer Dauerwelle / Kombination beträgt 5, jedoch wachsen 5Pn und 5Cn für große Werte von n (derzeit etwa 1000, aber täglich wachsend) ziemlich groß. Die Optimierung ist jedoch die Frage eines anderen Tages. Nochmals vielen Dank für all Ihre Hilfe Erwin.
Scott Small