MySQL Datum fuzzy grouping

Boldar · Verfasst: So 08.02.15 20:39

Hi,
ich arbeite in PHP an einer Mysql5 db. Ich habe nun in etwa folgende Tabelle (Primarykey markiert):

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Date              name  id  blablabla....
01.01.2014 10:37  user1   1  ...    \\  Gruppe 1
01.01.2014 10:37  user2   2  ...    ||  Gruppe 1
01.01.2014 10:38  user3   3  ...    //  Gruppe 1
01.01.2014 11:57  user3   4  ...    \\  Gruppe 2
01.01.2014 11:58  user1   5  ...    //  Gruppe 2
01.01.2014 12:38  user2   6  ...        Gruppe 3
01.01.2014 15:37  user1   7  ...      Gruppe 4
02.01.2014 12:37  user3   8  ...    \\  Gruppe 5
02.01.2014 12:40  user2   9  ...    //  Gruppe 5
03.01.2014 17:23  user2  10  ...      Gruppe 6

Ich möchte nun das Ergebnis der Abfrage nach dem datumsfeld gruppieren (wie gekennzeichnet), und zwar so, dass auch einige Minuten Abstand möglich sind, möchte also folgendes Ergebnis:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Date              name  id  blablabla....
01.01.2014 10:37  user1   1  ...

01.01.2014 11:57  user3   4  ...

01.01.2014 12:38  user2   6  ...

01.01.2014 15:37  user1   7  ...

02.01.2014 12:37  user3   8  ...

03.01.2014 17:23  user2  10  ...

Der Hintergrund sind requests, die reinkommen. Ein bestimmtes Event kann evtl von verschiedenen Benutzern aufgezeichnet werden, und durch Netzwerk-delay kommt das evtl ein paar Minuten später. In der Ausgabeliste soll das aber nur einmal auftauchen. Ich möchte also diejenigen gruppieren, wo sich das Datum höchstens um x minuten Unterscheidet. Der triviale Ansatz mit runden funktioniert hier nicht, weil das ja nicht Abstandsabhängig ist. Wie muss da das statement aussehen?

markieren

Quelltext

1:
2:
3:

SELECT *
FROM table
GROUP BY ??????

lg Boldar

Nersgatt · Verfasst: Mo 09.02.15 07:05

Also mir fällt keine Möglichkeit ein, die nicht das manuelle durchgehen aller Datensätze beinhalten würde.
Von welchen Datenmengen reden wir denn? Wenn man sowas als stored procedure umsetzt, kann dass durchaus trotzdem noch performant sein, wenn das nicht große Datenmengen sind.
Wichtig ist, dass man die Daten vor der Verarbeitung so weit wie möglich filtert, um den Rechenaufwand gering zu halten.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

ene · Verfasst: Mo 09.02.15 12:50

Ähm, ist das nicht einfach nur der früheste jeder Gruppen?

markieren

SQL-Anweisung

1:
2:
3:

SELECT First(datum), ...
FROM Tabelle
GROUP BY Gruppe

_________________
Wir, die guten Willens sind, geführt von Ahnungslosen, Versuchen für die Undankbaren das Unmögliche zu vollbringen.
Wir haben soviel mit so wenig so lange versucht, daß wir jetzt qualifiziert sind, fast alles mit Nichts zu bewerkstelligen.

Boldar · Verfasst: Mo 09.02.15 17:08

Nersgatt hat folgendes geschrieben :

Also mir fällt keine Möglichkeit ein, die nicht das manuelle durchgehen aller Datensätze beinhalten würde.
Von welchen Datenmengen reden wir denn? Wenn man sowas als stored procedure umsetzt, kann dass durchaus trotzdem noch performant sein, wenn das nicht große Datenmengen sind.
Wichtig ist, dass man die Daten vor der Verarbeitung so weit wie möglich filtert, um den Rechenaufwand gering zu halten.

Also im Endeffekt wären dass nach Vorfilterung so maximal 10k Datensätze. Das ist jetzt aber schon sehr viel gerechnet - bisher kamen ungefähr so 800 pro Jahr dazu.
Ich schätze mal, dass zählt noch als "nicht viele"??

ene hat folgendes geschrieben :

Ähm, ist das nicht einfach nur der früheste jeder Gruppen?

markieren

SQL-Anweisung

1:
2:
3:

SELECT First(datum), ...
FROM Tabelle
GROUP BY Gruppe

Das Problem ist die Gruppierung selbst nach ähnlichen Timestamps.

Edit: Ich hab leider keine Idee, wie man das mit stored Procedures am besten löst. Hat da jemand einen Ansatz?

Xion · Verfasst: Mo 09.02.15 21:51

Ganz naiv würde ich so vorgehen:

markieren

SQL-Anweisung

1:
2:
3:

SELECT * 
FROM (SELECT *, TRUNCATE(Datum/1000) AS LowResolutionDate FROM Tabelle) 
GROUP BY (LowResolutionDate)

Je größer du den markierten Wert machst, desto größer die Gruppen. Klar, das kann dann auch ungünstige Zuordnungen bilden oder Gruppen trennen, die gerade ungünstig liegen.

Wenn du die Gruppen ordentlich bilden willst, dann hast du im wesentlichen ein Graphenproblem. Jeder Eintrag in deiner Tabelle entspricht einem Knoten im Graphen, die Differenz der Zeiten die Länge der Kante zwischen diesen. Die Anfrage würde dann lauten: "Finde zu jedem Eintrag alle die Einträge, die einen Abstand kleiner x haben". Diese bilden dann eine Gruppe.
Prinzipiell bin ich zuversichtlich, dass das mit SQL geht, indem du eine rekursive Anfrage benutzt. Leider ist mir gerade entfallen, wie das mit der Rekursion in SQL ausgesehen hat...etwas erstaunt bin ich, dass alle Funde bei Google behaupten, Rekursion in MYSQL ginge nicht. Ich weiß aber genau, dass ich das schon als SQL gesehen und ausgeführt habe.

PS: hier gibts Rekursion in SQL:
technet.microsoft.co...%28v=sql.105%29.aspx

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Xion · Verfasst: Mo 09.02.15 22:02

Etwas abgewandelt würde ich prinzipiell so vorgehen:

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

WITH GroupExtraction(GroupID, MemberID, Datum)
AS
(
    SELECT id AS GroupID, id AS MemberID, datum
    FROM Tabelle AS accumulationTable

    UNION ALL

    SELECT accumulationTable.GroupID, recursion.id, datum
    FROM Tabelle AS recursion
    WHERE ABS(accumulationTable.datum - recursion.datum)<1000
)

SELECT table.*
FROM Tabelle, 
     SELECT DISTINCT * FROM GroupExtraction
GROUP BY GroupID

So ungefähr zumindest als grobe Marschrichtung.

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Xion · Verfasst: Di 10.02.15 01:08

Hab nach etwas Pause gerade nochmal mir das Problem angeschaut. Im vorherigen Posting sind auf jeden Fall noch einige Fehler/Probleme.

Es folgt daher ein sauberer, wohlüberlegter Ansatz

So würden wir alle Gruppenmitglieder für die Gruppe zum Zeitpunkt "VorgabeDatum" finden:

markieren

SQL-Anweisung

1:
2:
3:

SELECT * 
FROM Tabelle 
WHERE ABS(Datum-VorgabeDatum)<1000

Das müssen wir ja nur für alle Einträge machen. Also:

markieren

SQL-Anweisung

1:
2:
3:
4:

SELECT t1.*, t2.id AS PartnerID
FROM Tabelle t1, Tabelle t2
WHERE ( ABS(t1.Datum-t2.Datum)<1000 )
AND (t1.id < t2.id)

Die letzte Zeile (das AND) vermindert die Anzahl der Paare, die wir bekommen. Also nicht (2,1) und (1,2), sondern eben nur (1,2). Das heißt: 1 und 2 liegen in einer Gruppe.

Nun ist es aber so: 1 und 2 können in einer Gruppe liegen, 2 und 3 auch, aber der zeitliche Abstand von 1 und 3 kann zu groß sein. Trotzdem möchten wir aber, dass 1 2 und 3 in einer Gruppe liegen. Ich nehme zumindest an, wir möchten das, sonst bräuchten wir keine Rekursion

Wenn wir das so möchten, brauchen wir jetzt die Rekursion.

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

WITH PartnerTable(ID, PartnerID)
AS
(
    SELECT t1.id AS ID, t2.id AS PartnerID
    FROM Tabelle t1, Tabelle t2
    WHERE ( ABS(t1.Datum-t2.Datum)<1000 )
    AND (t1.id <= t2.id) 
)

WITH GroupExtraction(ID, PartnerID)
AS
(
    SELECT id, PartnerID
    FROM PartnerTable AS accumulationTable

    UNION ALL

    SELECT accumulationTable.PartnerID, recursion.ID
    FROM PartnerTable AS recursion
    WHERE (recursion.PartnerID = accumulationTable.id)
)

SELECT table.*
FROM Tabelle,  
      (
           SELECT MIN(ID) AS GroupIdentifier, PartnerID AS MyID
           FROM GroupExtraction 
           GROUP BY PartnerID
      ) AS GroupIDTable
WHERE Tabelle.id = MyID
GROUP BY GroupIdentifier

Kleines Beispiel:
1 ist zeitlich nahe 2
2 ist zeitlich nahe 3
(1 und 3 liegen zu weit auseinander)
4 ist zeitlich nahe 5
5 ist zeitlich nahe 6
6 ist zeitlich nahe 4

PartnerTable ist dann:
(1,1) (1,2) (2,2) (2,3) (3,3) (4,4) (4,5) (4,6) (5,5) (5,6) (6,6)

GroupExtraction sieht dann so aus:
1. Schritt: (1,1) (1,2) (2,2) (2,3) (3,3) (4,4) (4,5) (4,6) (5,5) (5,6) (6,6)
2. Schritt: + (1,3)
3. Schritt: -

GroupIDTable sieht dann so aus:
(1,1) (1,2) (1,3) (4,4) (4,5) (4,6)

Und wir haben für jede ID jeweils als GruppenID das kleinste Gruppenmitglied. Sollte passen. Spannend ist nur die Frage, ob MySQL das kann und wie es auf die Rekursion reagiert, wann es also abbricht, da der Code ständig neue Duplikate einfügt. Dem könnte man aber evtl begegnen, indem man die Rekursionsstufen mitzählt.

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

WITH PartnerTable(ID, PartnerID)
AS
(
    SELECT t1.id AS ID, t2.id AS PartnerID
    FROM Tabelle t1, Tabelle t2
    WHERE ( ABS(t1.Datum-t2.Datum)<1000 )
    AND (t1.id <= t2.id) 
)

WITH GroupExtraction(ID, PartnerID,Level)
AS
(
    SELECT id, PartnerID, 0 AS LEVEL
    FROM PartnerTable AS accumulationTable

    UNION ALL

    SELECT accumulationTable.PartnerID, recursion.ID, accumulationTable.Level+1
    FROM PartnerTable AS recursion
    WHERE (recursion.PartnerID = accumulationTable.id)
    AND (accumulationTable.Level = (SELECT MAX(Level) FROM accumulationTable))
)

SELECT table.*
FROM Tabelle,  
      (
           SELECT MIN(ID) AS GroupIdentifier, PartnerID AS MyID
           FROM GroupExtraction 
           GROUP BY PartnerID
      ) AS GroupIDTable
WHERE Tabelle.id = MyID
GROUP BY GroupIdentifier

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Boldar · Verfasst: Di 10.02.15 12:07

Ok, Danke für die ausführliche Antwort. Ich glaube, ich habe dass ganze sogar einigermaßen verstanden. Aber: es scheint so, als ob MYSQL kein WITH unterstützt (die Doku ist da irgendwie unklar), bzw. mit temporären tabellen keine Rekursion?. Also wohl doch stored procedures. Muss ich wohl noch ein bischen rumbasteln.

Edit:
Konkret gesagt versuche ich jetzt folgendes:
Zunächst

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

DROP FUNCTION IF EXISTS `enum_battles`//

CREATE FUNCTION `enum_battles`(
  p_timestamp1 timestamp, p_i1 INT,
  p_timestamp2 timestamp, p_id2 INT, delta INT, p_inc INT
) RETURNS INT
BEGIN
  DECLARE abs_true INT DEFAULT 0;
  SET abs_true := ABS(p_timestamp1-p_timestamp2);
  SET p_inc := p_inc + abs_true;
  SET @oldtimestamp := p_timestamp2;
  SET @oldid := p_id2;
  RETURN (p_inc);
END //

und dann

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:

SET @inc:=0//
SET @oldid := 0//
SET @oldtimestamp := 0//

SELECT battles.id as pid, battles.timestamp as ptimestamp, @newtimestamp := battles.timestamp, @newid := battles.id, @inc := enum_battles(@oldtimestamp, @oldid, @newtimestamp,  @newid, 600000, @inc)
FROM battles
WHERE (battles.clanid = 500028261 AND battles.serverid = 1)
ORDER BY battles.timestamp
LIMIT 0, 100 //

(Die Delimiter habe ich auf // gestellt)

Das klappt auch soweit - allerdings bleibt @oldtimestamp immer 0. Versuche ja in der Funktion mit

markieren

SQL-Anweisung

1:	SET @oldtimestamp := p_timestamp2;

@oldtimestamp so zu setzen, dass der quasi immer 1 hinterherhängt. Das klappt aber irgendwie nicht -evtl. falscher Scope? Aber Variablen sollten doch für die ganze Session gültig bleiben?
lg Boldar

Einloggen, um Attachments anzusehen!

Boldar · Verfasst: Di 10.02.15 15:55

Ok, Ich habs jetzt einigermaßen, aber extrem unperformant:
zunächst

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

DROP FUNCTION IF EXISTS `enum_battles`//

CREATE FUNCTION `enum_battles`(
  p_timestamp timestamp, delta INT, p_inc INT
) RETURNS INT
BEGIN
  DECLARE abs_true INT DEFAULT 0;
  DECLARE oldtimestamp TIMESTAMP DEFAULT 0;
  SELECT MAX(battles.timestamp) FROM battles WHERE (battles.timestamp<p_timestamp) INTO oldtimestamp;
  SET abs_true := IF(ABS(p_timestamp-oldtimestamp)<delta,0,2);
  SET p_inc := p_inc + abs_true;
  RETURN (p_inc);
END //

Und dann

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

SET @inc:=0//
SELECT tmp.pid, tmp.ptimestamp, tmp.pmap as `map`, tmp.fc
FROM
  (
  SELECT GROUP_CONCAT(tmpbt.id) as pid, GROUP_CONCAT(fc) as fc, MIN(tmpbt.timestamp) as ptimestamp, @pnewtimestamp := tmpbt.timestamp, @pnewid := tmpbt.id, @inc := enum_battles(@pnewtimestamp, 600000, @inc) as grouper, `map` as pmap
  FROM
    (
    SELECT 
      *
    FROM
      battles
    WHERE (battles.clanid = 500028261 AND battles.serverid = 1)
    ORDER BY battles.timestamp
    ) as tmpbt
  GROUP BY grouper, pmap
  ) as tmp
  //

Ich gehe halt in der Funktion jedesmal die Tabelle neu durch, um das nächstkleinere zu finden. Leider habe ich gerade noch keine hinreichend großen Testdaten, aber die Performance geht vermutlich in den Keller bei entsprechend vielen Zeilen.

Narses · Verfasst: Di 10.02.15 22:08

Moin!

Mal ein Denk-Vorschlag:

Wie wäre es denn mit der Idee direkt beim Einfügen neuer Datensätze mit so einer Art "Schleppzeiger" (z.B. den "Startzeitpunkt" einer Gruppe) zu arbeiten? Also vor dem Einfügen eines neuen Datensatzes ermitteln, ob er in die "letzte" Gruppe gehört oder eine "neue aufmacht"? :idea:

Zumindest aber die Gruppen-ID in den Datensatz schreiben (ggfs. bei einem zyklischen Update, 0 Uhr oder so)? Dann entfällt das aufwändige on-the-fly gruppieren.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

Nersgatt · Verfasst: Mi 11.02.15 06:49

Die Idee finde ich gut.
Allerdings lässt sich dann der Abstand zwischen den Buchungen, die zu einer neuen Gruppe führen, nicht mehr individuell entscheiden. Man muss sich vorher auf einen passenden Abstand einstellen. Eine Änderung des Abstands würde eine komplette Neuberechnung des Schleppzeigers (tolles Wort

) bedeuten.
Wenn der Abstand aber fix definiert ist, ist das eine wirklich gute Idee.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

Boldar · Verfasst: Di 03.03.15 08:40

Narses hat folgendes geschrieben :

Moin!

Mal ein Denk-Vorschlag:

Wie wäre es denn mit der Idee direkt beim Einfügen neuer Datensätze mit so einer Art "Schleppzeiger" (z.B. den "Startzeitpunkt" einer Gruppe) zu arbeiten? Also vor dem Einfügen eines neuen Datensatzes ermitteln, ob er in die "letzte" Gruppe gehört oder eine "neue aufmacht"? :idea:

Zumindest aber die Gruppen-ID in den Datensatz schreiben (ggfs. bei einem zyklischen Update, 0 Uhr oder so)? Dann entfällt das aufwändige on-the-fly gruppieren.

cu
Narses

Das ist eine sehr gute Idee, aber mir zu unflexibel. Ich muss möglicherweise die Abstände anpassen, bevor das richtig läuft.
Ich habe gerade noch folgendes Problem:
Ich arbeite mit einer stored Funktion, die mir eine Art Gruppen-ID gibt:+

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

CREATE FUNCTION `enum_battles`(p_timestamp timestamp, p_id INT, delta INT, p_inc INT, p_clanid INT, p_serverid INT) RETURNS INT NOT DETERMINISTIC
BEGIN
  DECLARE abs_true INT DEFAULT 0;                                              #variablen initialisieren
  DECLARE oldtimestamp TIMESTAMP DEFAULT 0;
  SELECT MAX(battles.timestamp) FROM battles WHERE ((battles.timestamp<=p_timestamp) AND (battles.id!=p_id) AND (battles.clanid=p_clanid) AND (battles.serverid=p_serverid))INTO oldtimestamp;  #Hole den nächstkleineren Timestamp
  SET @oldts := p_timestamp;                                  #testausgabe
  SET abs_true := IF(ABS(UNIX_TIMESTAMP(p_timestamp)-UNIX_TIMESTAMP(oldtimestamp))<delta,0,1);     #prüfen, wie gross der Abstand ist
  SET p_inc := p_inc + abs_true;                              #gruppenid erhöhen, falls der Abstand zu groß war
  RETURN (p_inc);
END

Und habe dann folgendes Statement:

markieren

SQL-Anweisung

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

    SELECT tmp.pid, tmp.maxid, tmp.fc, tmp.pmap as `map`, tmp.ptimestamp, tmp.grouper, oldts
    FROM
      (
      SELECT GROUP_CONCAT(tmpbt.id) as pid, MAX(tmpbt.id) as maxid, GROUP_CONCAT(fc) as fc, GROUP_CONCAT(tmpbt.timestamp) as ptimestamp, @pnewid := tmpbt.id, @inc := enum_battles(tmpbt.timestamp, tmpbt.id, 400, @inc, ?, ?) as grouper, `map` as pmap, @oldts as oldts
      FROM
        (
        SELECT 
          *
        FROM
          battles
        WHERE (battles.clanid = ? AND battles.serverid = ? AND battles.battletype=10)
        ORDER BY battles.timestamp ASC
        ) as tmpbt
      GROUP BY grouper
      ) as tmp

Jedoch funktioniert das nicht wie gewünscht. Ich habe dann bemerkt, dass es nur für die neuesten Daten funktioniert - also nur die werden gruppiert. Dann habe ich testweise die markierten Zeilen eingefügt, und es scheint so, als ob beim Aufruf der Funktion nicht immer der Timestamp der jeweiligen Reihe übergeben wird, sondern immer der gleiche - @oldts ist jedesmal (also für jede Reihe im Ergebnis) "2015-03-03 08:07:19", und um dieses eine Datum wird auch eine Gruppe gebildet. Ich bin da ein bischen ratlos, warum das so ist? Irgendwie wird der parameter nicht für jede Reihe übergeben.
Oder habe ich stored functions irgendwie mißverstanden?
lg Boldar

Boldar · Verfasst: Sa 07.03.15 15:08

push?

Boldar · Verfasst: Sa 14.03.15 17:51

push?

Xion · Verfasst: Sa 14.03.15 19:15

Es scheint mir ein Scope-Problem zu sein, aber ich bin mir nicht sicher. Allerdings wäre es irgendwie seltsam, wenn es so funktioniert, wie du es beschreibst, da es ja mehrere aufrufende Stellen geben kann. Vergleiche das auch zu Delphi, du kannst nicht in die lokalen Variablen einer aufrufenden Prozedur schreiben.

Probiers mal so:

markieren

SQL-Anweisung

1:	CREATE FUNCTION `enum_battles`(p_timestamp timestamp, p_id INT, delta INT, p_inc INT, p_clanid INT, p_serverid INT, OUT oldts timestamp) RETURNS INT NOT DETERMINISTIC

und der Aufruf

markieren

SQL-Anweisung

1:	enum_battles(tmpbt.timestamp, tmpbt.id, 400, @inc, ?, ?, @oldts)

Kenne mich allerdings überhaupt garnicht mit stored procedures aus

Vergleiche auch:

dev.mysql.com/doc/re...reate-procedure.html hat folgendes geschrieben:

markieren

SQL-Anweisung

1:
2:
3:
4:

CREATE PROCEDURE simpleproc (OUT param1 INT)
 BEGIN
   SELECT COUNT(*) INTO param1 FROM t;
 END

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme