performante Verteilungsstatistik

[Vinzenz Mai]

Hallo Mathias,

In http://aktuell.de.selfhtml.org/weblog/aufloesung-viewport habe ich ein Script beschrieben, dass mithilfe von JavaScript Viewport-Breiten in eine PostgreSQL-Datenbank einträgt.

Ich habe also beliebige Zahlen zwischen 0 und ichweißnichtwieviel in der Datenbank. Daraus will ich letztlich eine solche Statistik erstellen:
http://aktuell.de.selfhtml.org/weblog/files/2006-04-viewport-gesamt-ausschnitt.png
Das ist so zu lesen: 78,9% aller Zahlen sind unter oder gleich 1000.

Jetzt frage ich mich, wie ich die Zahlen für eine solche Statistik performant berechne mit möglichst wenig Datenbankaufwand.

Zwei Methoden habe ich gefunden:

1. Ich mache (vereinfacht):

[...]

Vorteil dieser Methode: Sie ist schnell und kommt mit einer Datenbankabfrage aus.
Nachteil: Ich blicke nicht ganz durch,

ich auch nicht :-)

ob ich meine Berechnungen wirklich aussagen: Soundsoviel Prozent haben eine innerwidth kleiner gleich x.

Diese Vorgehensweise bietet bestimmt den Ansatz, um mit möglichst geringem Aufwand zum Ergebnis zu kommen.

Gibts da irgendwelche eleganten Möglichkeiten? Vielleicht eine SQL-Query die mir annähernd direkt meine gewünschte Statistik ausgibt? Ich bin völlig PostgreSQL-unerfahren und ansonsten kenne ich auch nur MySQL oberflächlich.

Aus Deiner Problemstellung geht für mich eindeutig hervor, dass Du eine Funktion benötigst. Schließlich können sich die Einträge für die minimale und maximale Viewportbreite im Laufe der Zeit ändern. Ich habe dieses Problem dazu genutzt, meine ersten Schritte in PL/pgSQL zu machen. Das Ergebnis sollte sich nutzen lassen.

Alles in allem benutze ich einen[1] View, eine zusätzliche Tabelle und eine Funktion. Anschließend kann das Ergebnis mit einer einfachen Abfrage ermittelt werden. Ich bitte zu berücksichtigen, dass es meine erste Funktion ist, die ich mit PL/pgSQL erstellt habe, sicherlich gehört noch einiges an Fehlerbehandlung dazu, wahrscheinlich sind auch einige Casts nicht unbedingt erforderlich.

Ausgangspunkt ist die Tabelle "test" mit den Spalten
    id,          (SERIAL)
    innerwidth   (INTEGER)
in der die auszuwertenden Daten gespeichert sind.

Mit

CREATE VIEW gruppierung AS  
    SELECT  
        CAST(10*CEIL(CAST(innerwidth AS real)/10) AS int) AS abschnitt,  
        COUNT(id) AS summe  
    FROM test  
    GROUP BY abschnitt;  

erstelle ich einen View, der mir die Treffer in den 10-er-Intervallen anzeigt. Die Casts sind erforderlich, da ansonsten eine Division ohne Rest erfolgt - und somit das Ergebnis nicht das gewünschte ist.

Meine Ergebnistabelle "ergebnis" enthält folgende Spalten
    abschnitt  -- die Intervalle
    wert       -- die Treffer im Intervall
    summe      -- die kumulierte Summe
    total      -- die Gesamtzahl der Einträge

CREATE TABLE ergebnis (  
    abschnitt int,  
    wert      int DEFAULT NULL,  
    summe     int,  
    total     int);

Im nächsten Schritt wird eine Funktion erstellt, die die Ergebnistabelle mit den kumulierten Daten füllt - und nicht besetzte Intervalle einfügt.

CREATE FUNCTION aktualisiere_ergebnis() RETURNS bigint AS $$  
DECLARE  
    beginn    bigint;  -- Startwert der Intervalle  
    gesamt    bigint;  -- Gesamtzahl der Datensätze  
    aktuell   bigint;  -- aktuelles Intervall  
    k_summe   bigint;  -- kumulierte Summe  
    datensatz RECORD;  -- aktueller Datensatz  
BEGIN  
     -- Leere die Ergebnistabelle  
    TRUNCATE ergebnis;  
    -- Ermittle den Startwert  
    beginn  := 10 * MIN(cast(CEIL(cast(innerwidth as real)/10) as int)) FROM test;  
    -- Ermittle die Gesamtzahl der Datensätze  
    gesamt  := COUNT(*) FROM test;  
    -- Setze die Startwerte  
    aktuell := beginn;  
    k_summe := 0;  
  
    -- Durchlaufe alle Datensätze  
    FOR datensatz IN SELECT abschnitt, summe FROM gruppierung ORDER BY abschnitt LOOP  
        -- Falls Intervalle nicht besetzt sind, müssen sie eingetragen werden  
        WHILE cast(aktuell as int) < cast(datensatz.abschnitt as int) LOOP  
            INSERT INTO temptest (abschnitt, summe, total)  
                VALUES (aktuell, k_summe, gesamt);  
            -- nächstes Intervall, Schrittweite ist 10  
            aktuell := aktuell + 10;  
        END LOOP;  
        -- verarbeite aktuellen Datensatz  
        -- Berechne die kumulierte Summe neu  
        k_summe := k_summe + datensatz.summe;  
  
        -- Schreibe den Datensatz weg  
        INSERT INTO temptest (abschnitt, wert, summe, total) VALUES (datensatz.abschnitt, datensatz.summe, k_summe, gesamt);  
        -- setze das nächste Intervall (sonst gibt es Doppeleinträge)  
        aktuell := cast(datensatz.abschnitt as int) + 10;  
        -- Am Ende ist grundsätzlich ein besetztes Intervall :-)  
    END LOOP;  
  
    RETURN 1;  
END;  
$$ LANGUAGE plpgsql;

Nach diesen Vorarbeiten ist für die Auswertung nur noch folgendes zu tun:

1. Aufruf der Funktion

SELECT aktualisiere_ergebnis()

2. Abfragen der Werte

SELECT  
    abschnitt,  
    summe,  
    ROUND(100 * CAST(total - summe AS numeric) / total, 1) AS anteil  
FROM ergebnis  
ORDER BY abschnitt

Die Funktion aktualisiere_ergebnis() - nach meinen rudimentären Messungen (10000, 100000 und 1000000 Datensätze) - arbeitet mit O(N), auf meinem Testsystem bei 1 Million Datensätzen im einstelligen Sekundenbereich. Laut PostreSQL-Doku wird für COUNT(*) ein kompletter Tablescan benötigt, so dass sich hier nicht viel optimieren lässt :-(

Das Abfragen der Werte erfolgt in konstanter Zeit (es sei denn, die Anzahl der zu betrachtenden Intervalle stiege deutlich an - was doch eher unwahrscheinlich ist), die Ausführungszeit dieser Abfrage ist vernachlässigbar.

Freundliche Grüße

Vinzenz

[1] Mein Sprachempfinden sagt mir, dass es sich bei View um ein Maskulinum handelt, weder "die View" (da "die Sicht") noch "das View" hört sich meiner Meinung nach richtig an. Ich halte zudem nichts davon, diesen Begriff zu übersetzen.