performante Verteilungsstatistik

[molily]

Hallo,

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):

SELECT innerwidth, count(id) as summe FROM hits GROUP BY innerwidth ORDER BY summe DESC

So bekomme ich eine Tabelle, in der drinsteht, wieviele Einträge (summe) es zu der vorkommenden Zahl (innerwidth) gibt.

Dann durchlaufe ich alle Zeilen des Ergebnisses, runde die innerwidth auf die nächste Zehnerstelle auf. Dann lege ich ein Arrayelement mit dieser Zahnerstelle als Index an. In dieses Arrayelement schreibe ich dann die Anzahl der Datensätze (summe) bzw. addiere sie. Z.B. $array[$gerundete_breite] += $hits; (Pseudocode).

Gleichzeitig addiere ich die summe zu einer Totalsumme.

So komme ich z.B. zu einem solchen Array (willkürlich):

400 => 25
620 => 543
830 => 134
1000 => 7854

Daraus lege ich dann einen Array an, in dem die kumultativen Zahlen in Zehnerschritten drinstehen:

400 => 25
410 => 25
...
620 => 568
...
830 => 702
...
1000 => 8556

Daraus kann ich dann Prozentwerte berechnen ausgehend von der Totalsumme (total / total - wert):

400 => 0.9974287050023375409
...
620 => 0.933613838242169238
usw.

Vorteil dieser Methode: Sie ist schnell und kommt mit einer Datenbankabfrage aus.
Nachteil: Ich blicke nicht ganz durch, ob ich meine Berechnungen wirklich aussagen: Soundsoviel Prozent haben eine innerwidth kleiner gleich x.

2.

Ich hole die Summe aller relevanten Zeilen aus der Datenbank.
Ich hole den größten innerwidth-Wert aus der der Datenbank.

Ich laufe von 0 in Zehnerschritten bis zum größten innerwidth-Wert und mache immer wieder:

SELECT count(id) as summe FROM hits WHERE innerwidth <= $Breite;

Das Ergebnis schreibe ich jeweils in einen Array, daraus erstelle ich dann direkt die kumulative Prozent-Statistik.

Vorteil dieser Methode: Sie scheint mir präziser. Ich bekomme andere Werte als bei der anderen. (Ja, seltsam, ich werde das nochmal untersuchen.)
Nachteil: Ich laufe in Zehnerschritten von 0 bis z.B. 2480 und führe immer wieder diese Abfrage aus. Das dauert ewig, sodass ich das Script schonmal gar nicht mehr über HTTP aufrufen kann, sondern nur noch auf der Kommandozeile.

Jetzt suche ich eine Möglichkeit, wie ich das ganze besser lösen kann. Ist es irgendwie möglich, diese Rechnerei die Datenbank-Software übernehmen zu lassen? Ich würde gerne weder eine Pseudo-Summenstatistik abfragen, mit der ich dann noch weiterrechnen noch, noch eine echte Summenstatistik, die hunderte Abfragen benötigt und 130 Sekunden läuft.

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.

Mathias

[Blaubart]

Hallo Mathias.

Nachteil: Ich blicke nicht ganz durch, ob ich meine Berechnungen wirklich aussagen: Soundsoviel Prozent haben eine innerwidth kleiner gleich x.

Das sagen sie auch nicht aus. Das kannst du schon daran erkennen, daß die Prozentwerte mit steigender innerwidth ebenfalls wachsen sollten. Jemand, der 500 Pixel Breite hat, erfüllt damit auch <= 800 Pixel und natürlich auch <= 1000 Pixel.

Ich weiß nicht, womit du die obige Graphik erstellt hast, aber sie scheint mir genau das Gegenteil auszudrücken: x Prozent haben eine Auflösung von y Pixel oder _größer_. Vermutlich ist es auch das, was du eigentlich wissen möchtest. Oder?

Falls ja, würde ich deine zuerst vorgeschlagene Methode benutzen, nur mit der richtigen Rechnung:

Beginne bei der höchsten Auflösung (z.B. 1000 Pixel).
100 * hits_1000 / hits_total ergibt den Prozentwert der Leute, die mit 1000 oder mehr Pixeln Breite registiert wurden.

Abwärts zur nächst tieferen Auflösung (z.B. 990 Pixel).
100 * (hits_1000 + hits_990) / hits_total ergibt den Prozentwert der Leute, die mit 990 oder mehr Pixeln Breite registiert wurden.

usw.

Die Prozentangaben geben natürlich das Verhältnis zur Zahl der Gesamtregistrierten an.

[molily]

Hallo,

Nachteil: Ich blicke nicht ganz durch, ob ich meine Berechnungen wirklich aussagen: Soundsoviel Prozent haben eine innerwidth kleiner gleich x.

Das sagen sie auch nicht aus. Das kannst du schon daran erkennen, daß die Prozentwerte mit steigender innerwidth ebenfalls wachsen sollten.

Ja, stimmt. Den Fehler hab ich schonmal gemacht... Im verlinkten Artikel habe ich (nach Korrektur im Kommentar) geschrieben:

»Diese Diagramme sind so zu lesen: 78,9 Prozent aller Besucher haben eine Viewport-Breite größer als 1000 Pixel, hingegen nur 48,1 Prozent einen Viewport größer als 1040 Pixel.«

Wenn ich richtig sehe, stimmt diese Beschreibung auch. Danke für die Auffrischung, ich hatte das wieder komplett vergessen... ;)

Ich weiß nicht, womit du die obige Graphik erstellt hast

Mit dem besagten Algorithmus. ;)

aber sie scheint mir genau das Gegenteil auszudrücken: x Prozent haben eine Auflösung von y Pixel oder _größer_. Vermutlich ist es auch das, was du eigentlich wissen möchtest. Oder?

Ja, das will ich.

Ich habe z.B. eine Site, deren Layout einen Viewport von 1000px voraussetzt. Jetzt will ich wissen, wieviele Leute einen so breiten Viewport oder einen breiteren haben. Anders herum: Bei wieviel Prozent ist die Site zu breit für den Viewport (das sollte durch Umkehrung des Prozentwertes ersichtlich werden).

Leider habe ich durch das Umkehren der Statistik von viewport <= x nur ein viewport > x im Diagramm. Deshalb ist die ursprüngliche Beschreibung richtig, aber ich hätte lieber >= gewusst.

Beginne bei der höchsten Auflösung (z.B. 1000 Pixel).
100 * hits_1000 / hits_total ergibt den Prozentwert der Leute, die mit 1000 oder mehr Pixeln Breite registiert wurden.

Abwärts zur nächst tieferen Auflösung (z.B. 990 Pixel).
100 * (hits_1000 + hits_990) / hits_total ergibt den Prozentwert der Leute, die mit 990 oder mehr Pixeln Breite registiert wurden.

usw.

Danke, so habe ich es jetzt implementiert und es liefert auch die korrekten Zahlen (ich kann es ja mit Methode 2 nachprüfen).

Die Zahlen weichen nicht groß von denen meines bisherigen Algorithmus ab. Bzw. die Abweichungen sind logisch klar auf den Unterschied zwischen <= und >= zurückzuführen. Bsp.

Gesamtheit: 62756

Alter Algorithmus:
12972 haben <= 1000px
Demnach haben 49784 > 1000px, das sind 79,3294665052% der Gesamtheit

Neuer Algorithmus:
49882 haben >= 1000px
Das sind 79,4856268723% der Gesamtheit

SELECT count(id) as summe FROM hits WHERE innerwidth = 1000 (AND ...)
ergibt: 98

62756 - 49882 = 12874
(gesamt minus x>=1000 = 12874)

12972 - 98 = 12874
(x<=1000 minus 98 = 12874)

Insofern stimmen die Aussagen des ursprünglichen Diagramms zwar (wenn ich mich nicht irre), aber jetzt kann ich sinnigeres Diagramm im Hinblick auf meine Fragestellung erstellen.

Danke für die Erklärungen!

Mathias

[Auge]

Hallo

In MySQL gibt es BETWEEN. Ich vermute mal, dass es das so oder ähnlich auch in PostgreSQL gibt.

SELECT ... WHERE innerwidth BETWEEN 200 AND 400;

Tschö, Auge

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

[Vinzenz Mai]

Hallo Ingrid,

wie ich selbst einmal schrieb, ist es keine gute Idee, Namen nachträglich zu ändern. Es ist schön zu sehen, dass meine Tabelle "ergebnis" bei meinen Tests "temptest" hieß ...

Weiterhin habe ich die Intervallbreite einer Variablen zugewiesen, damit diese sich leichter anpassen lässt. Derzeit ist zu bedenken, dass die Intervallbreite auch im View auftaucht. Wenn View und Funktion durch eine weitere Funktion erstellt würden, könnte man die Intervallbreite über einen Übergabeparameter steuern, das wäre eine erste Verbesserung.

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  
    schritt   bigint;  -- Schrittweite  
    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  
    -- Schrittweite setzen  
    schritt := 10;  
    -- Leere die Ergebnistabelle  
    TRUNCATE ergebnis;  
    -- Ermittle den Startwert  
    beginn  := schritt * MIN(cast(CEIL(cast(innerwidth as real)/schritt) 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 ergebnis (abschnitt, summe, total)  
                VALUES (aktuell, k_summe, gesamt);  
            -- nächstes Intervall  
            aktuell := aktuell + schritt;  
        END LOOP;  
        -- verarbeite aktuellen Datensatz  
        -- Berechne die kumulierte Summe neu  
        k_summe := k_summe + datensatz.summe;  
  
        -- Schreibe den Datensatz weg  
        INSERT INTO ergebnis (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) + schritt;  
        -- Am Ende ist grundsätzlich ein besetztes Intervall :-)  
    END LOOP;  
  
    RETURN 1;  
END;  
$$ LANGUAGE plpgsql;

Freundliche Grüße

Vinzenz

[molily]

Hallo,

vielen Dank erst einmal für die Arbeit. Ich weiß bisher zwar, dass es Views und Funktionen gibt, aber mehr auch nicht. ;) Ich werde mich da mal anhand deiner Beispiele einarbeiten und mich dann noch einmal melden, wenn ich noch Fragen habe. Das sieht alles sehr vielversprechend aus.

Mathias