Performante Lösung für Duplikaten suche innerhalb eines Zeitfensters

Java-Forum Datenbankprogrammierung
1

Halli Hallo

Da ich aktuell keinen wirklichen brauchbaren Ansatz habe. Welche Möglichkeiten gibt es einer halbwegsperformanten Lösung, in einer DB innerhalb eines gegebenen Zeitfensters alle Duplikate zu suchen?
[table=“width: 500”]

ID
Name
Zeit


1
Martin
0


2
Uwe
1


3
Uwe
2


4
Ede
2


5
Martin
3


6
Uwe
4


7
Ede
5

[/table]
Wenn ich nun in einem Zeitfenster von “1” suche, sollen als Ergebnis die beiden Uwe ausgegeben werden. Wenn ich nun nach einem Zeitfenster von “2” suche, dann entsprechend wieder 2x Uwe und Ede. Bei einem Fenster von “3”, müssten alle Namen in der Ergebnisliste auftauchen

2

Wie wäre es erstmal mit einem Ansatz, bevor man nach einem Performanten Ansatz sucht?

Die Tabelle mit dem Namen Joinen und die Differenz der Zeit berechnen.

Etwas Pseudocode (before, after, oder kleiner größer gleich je nach Datentypen anzupassen)
[SQL]select a.id, b.id, a.name
from tab a, tab b
where a.name = b.name
and a.zeit before b.zeit
and a.zeit + zeitfenster after b.zeit[/SQL]

Wenn man nur eine Liste der Namen möchte

[SQL]select a.name
from tab a, tab b
where a.name = b.name
and a.zeit before b.zeit
and a.zeit + zeitfenster after b.zeit
group by a.name[/SQL]

Ansonsten Frage präzisieren!

3

Ede 2 + 5 scheint nicht höher als 3 zu stehen wie Martin 0 + 3

Fehler oder warum Ede bei 2?

4

[QUOTE=Unregistered]Wie wäre es erstmal mit einem Ansatz, bevor man nach einem Performanten Ansatz sucht?

Die Tabelle mit dem Namen Joinen und die Differenz der Zeit berechnen.

Etwas Pseudocode (before, after, oder kleiner größer gleich je nach Datentypen anzupassen)
[SQL]select a.id, b.id, a.name
from tab a, tab b
where a.name = b.name
and a.zeit before b.zeit
and a.zeit + zeitfenster after b.zeit[/SQL]

Wenn man nur eine Liste der Namen möchte

[SQL]select a.name
from tab a, tab b
where a.name = b.name
and a.zeit before b.zeit
and a.zeit + zeitfenster after b.zeit
group by a.name[/SQL]

Ansonsten Frage präzisieren![/QUOTE]Mein Ansatz wäre gewesen alle Einträge durchzulaufen und sich entsprechende Differenzen der Zeit anzuschauen. Dieser ist aber recht schnell fallengelassen, und die Überlegung ob es eben nicht irgendeine Magic Lösung/Statement oder Anderes dafür gibt.

[QUOTE=SlaterB;122774]Ede 2 + 5 scheint nicht höher als 3 zu stehen wie Martin 0 + 3

Fehler oder warum Ede bei 2?[/QUOTE]Tippfehler. Grundsätzlich sind Zeiten nicht doppelt vergeben, da die entsprechende Spalte den timestamp als long speichert und es entsprechend unwahrscheinlich ist zu einer Zeit doppelte Einträge zu haben

5

Hab das heute mal getestet und der Code oben geht in die richtige Richtung, wobei es wie schon bei meinem Ansatz einfach ewig dauert da irgendwas auszugeben. Bei 130k Datensätzen in der DB etwa 7min wenn man LIMIT auf 5k stellt. Query war dabei folgender:
[SQL]
select data3.id from
(select data1.id, data1.name, data1.time from table1 as data1) as data3
inner join (select data2.id, data2.name, data2.time from table1 as data2) as data4
on data3.name=data4.name
where data3.time < data4.time
and (data3.time+1000) > data4.time[/SQL]

Kann man hier eventuell mehr Zeit sparen wenn man die Unterabfragen in irgendeiner weiße vorher ausführt/abfragt, so dass die Menge in der zu suchenden Daten schon verkleinert wird?
Eine weitere Möglichkeit wäre, sich immer nur eine Handvoll Datensätze ausgeben zu lassen, aus dieser Liste sich die letzte ID zu merken, und den nächsten Block nach dieser ID starten lassen.

6

versprichst du dir von deiner Variante etwas gegenüber
[sql]select data3.id from
table1 as data3
inner join table1 as data4
on data3.name=data4.name
where data3.time < data4.time
and (data3.time+1000) > data4.time[/sql]
oder ähnlich?
macht das bei der Laufzeit einen Unterschied?

da du am Ende nicht die Daten als Ergebnis herausholst scheinen mit die Verkürzungen unnötig,
intern wird hoffentlich eh nicht zu sehr auf alle Datenfelder geschaut

hast du einen DB-Index auf Namen, dazu robuste Kenntnisse?
ohne vielleicht in der Tat innerhalb der DB aufgeschmissen (obwohl es doch möglich erscheinen sollte…, ach ich weiß auch nicht),
mit sollte bei 130k Elementen nicht so viel los sein

wieviele Gleiche je Gruppe ist wohl auch wichtig, bzw. wieviel verschiedene Namen, was hast du da ungefähr?

ich habe gerade eine Tabelle mit 230k Elementen getestet,
Query select count(*) from table t1, table t2 where t1.id = t2.id läuft in wenigen Sekunden mit gleicher Anzahl

Query select count(*) from table t1, table t2 where t1.attribut1 = t2.attribut2
für ein Attribut mit 6000 verschiedenen Werten (select count(distinct(t1.attribut1) from table t1)
läuft mit Count-Ergebnis 28 Mio. in 40 sec, das ist bereits recht lahm,
ich glaube da ist Index drauf, aber ich habe da selber nicht so genaue Kenntnisse,

je weniger verschiedene Werte, desto langsamer meine Test-Query, wie sieht es bei dir hinsichtlich Name aus?

7

mit einer oracle-DB ginge es so:

[SQL]select a.name
from tab a
where a.zeit <= :max_zeit
group by a.name
having count (a.id) > 1[/SQL]

bye
TT

8

  1. SlaterB dürfte das selbe machen wie das von TO.

  2. TT macht etwas anderes.

  3. Sucht z.B. nach Events die innerhalb von 7 Tagen Stattfanden.

  4. Sucht nach Events die in einer bestimmten Kalenderwoche stattfanden?

Im Gegensatz zu 2 verschiebt sich das Fenster bei 1 ausgehend vom ersten Auftreten oder sehe ich hier etwas nicht?
:max_zeit wird ja von aussen gesetzt.

Es kommt jetzt darauf an was der TO möchte.

Ein Problem bei 1. ist, wenn z.B. 10 Events in einem Fenster stattfinden. Dann bekommt man hier 9 + 8 + 7 +…+ 1 Ergebnisse.

Dies lässt sich aber durch ein Group by reduzieren.

Es stellt sich halt nun die Frage ob man wirklich so viele Ergebnisse möchte und ob man mit der entstehenden Komplexität umgehen kann?

[SQL]select data3.id from
table1 as data3
where Exists (select *
from table1 as data4
data3.time < data4.time
and (data3.time+1000) > data4.time)[/SQL]

Damit würde man bei 10 Events in einem Zeitfenster nur die 9 Entsprechenden Ergebnisse bekommen.
Abhängig von der DB und deren Optimierungen kann das mit einem Subselect auch schnell laufen.

9

Select a,b,count(*) from Tabelle group by …having…

Bei dir hält als Aggregat Funktion max(Zeit)-min(Zeit)

10

[QUOTE=SlaterB]

hast du einen DB-Index auf Namen, dazu robuste Kenntnisse?
ohne vielleicht in der Tat innerhalb der DB aufgeschmissen (obwohl es doch möglich erscheinen sollte…, ach ich weiß auch nicht),
mit sollte bei 130k Elementen nicht so viel los sein

wieviele Gleiche je Gruppe ist wohl auch wichtig, bzw. wieviel verschiedene Namen, was hast du da ungefähr?

ich habe gerade eine Tabelle mit 230k Elementen getestet,
Query select count(*) from table t1, table t2 where t1.id = t2.id läuft in wenigen Sekunden mit gleicher Anzahl

Query select count(*) from table t1, table t2 where t1.attribut1 = t2.attribut2
für ein Attribut mit 6000 verschiedenen Werten (select count(distinct(t1.attribut1) from table t1)
läuft mit Count-Ergebnis 28 Mio. in 40 sec, das ist bereits recht lahm,
ich glaube da ist Index drauf, aber ich habe da selber nicht so genaue Kenntnisse,

je weniger verschiedene Werte, desto langsamer meine Test-Query, wie sieht es bei dir hinsichtlich Name aus?[/QUOTE]Index ist auf dem Namen drauf, ja. Was intern das DBMS macht, müsste ich ebenso erst rausfinden. Verwendet wird aber H2.
In der TestDB sind es aktuell ~500. In der eigentlich verwendeten sind das bei ähnlicher Anzahl vermutlich eher 100k unterschiedliche.

[QUOTE=Timothy_Truckle;122979]mit einer oracle-DB ginge es so:

[SQL]select a.name
from tab a
where a.zeit <= :max_zeit
group by a.name
having count (a.id) > 1[/SQL]

bye
TT[/QUOTE]Schau ich mal wie das in H2 bzw HQL geht.

[QUOTE=Unregistered;122981]1. SlaterB dürfte das selbe machen wie das von TO.

  1. TT macht etwas anderes.

  2. Sucht z.B. nach Events die innerhalb von 7 Tagen Stattfanden.

  3. Sucht nach Events die in einer bestimmten Kalenderwoche stattfanden?

Im Gegensatz zu 2 verschiebt sich das Fenster bei 1 ausgehend vom ersten Auftreten oder sehe ich hier etwas nicht?
:max_zeit wird ja von aussen gesetzt.

Es kommt jetzt darauf an was der TO möchte.

Ein Problem bei 1. ist, wenn z.B. 10 Events in einem Fenster stattfinden. Dann bekommt man hier 9 + 8 + 7 +…+ 1 Ergebnisse.

Dies lässt sich aber durch ein Group by reduzieren.

Es stellt sich halt nun die Frage ob man wirklich so viele Ergebnisse möchte und ob man mit der entstehenden Komplexität umgehen kann?

[SQL]select data3.id from
table1 as data3
where Exists (select *
from table1 as data4
data3.time < data4.time
and (data3.time+1000) > data4.time)[/SQL]

Damit würde man bei 10 Events in einem Zeitfenster nur die 9 Entsprechenden Ergebnisse bekommen.
Abhängig von der DB und deren Optimierungen kann das mit einem Subselect auch schnell laufen.[/QUOTE]
Was ich möchte: Eine Person durchläuft eine Lichtschranke. Nun gibt es zu dieser Person einen Namen und einen Zeitstempel. Ich möchte nun für ein gegebenes Intervall, bspw. 1Sek, die Personen wissen die mehrfach durch die Lichtschranke gegangen sind. Beispielsweise wenn sie den “Eingang” benutzen und sofort umdrehen und den “Ausgang” benutzen, ist Person A zweimal in 1Sek gelistet. Dadurch kann man annehmen das die Person sofort umgedreht ist.

Den Ansatz schau uch mir auch mal an. Thx

11

Java-Berechnungen auf den Daten wären wohl die schnellsten,
da bisher noch nicht angesprochen: strukturell ungeeignet oder nur aus Interesse bei SQL geblieben oder noch gar nicht an DB-Fremde Berechnungen gedacht?

mithalten kann die DB vielleicht nur mit einen GROUP BY, wenn es jetzt nur eine Funktion wie LOWEST_DIFFERENCE() gäbe,
sind solche Funktionen selber zu ergänzen und käme das für dich in Frage?
reines SQL ist das ja auch nicht

die Datenmenge durch Einschränkung der Zeit zu verkleinern mag auch noch helfen, hierzu Verteilung bekannt?
wieviele der 130k Datensätzen fallen durchschnittlich auf 1 Sekunde?
man müsste überlappend abfragen, erst von Sekunde 0 bis 2, dann von 1 bis 3, dann 2 bis 4 usw.,
oder enger aber dafür öfter, 0 bis 1.3, 0.3 bis 1.6 usw.

12

Gedacht schon. Aber ich bin erstmal davon ausgegangen, dass das DBMS schneller ist als wenn ich das “per Hand” in Java baue. Die Annahme die darauf beruht ist, das es unvorteilhaft ist sich alle Daten zu holen um sie dann weiterzuverarbeiten und uU zu merken das die Ergegnisliste leer ist. Dass das DBMS diese Aufgabe in irgendeiner weiße “besser” macht als ich das per Hand könnte.
Wenn man das so baut müsste man sich eine Teilergebnismenge holen, diese auf die Zeit prüfen und dann uU den ganzen Datensatz nachladen und zwischenspeichern/ausgeben.

Verteilungen sind nicht bekannt, nein. Aber die Zeitdifferenz ist als ziemlich klein anzunehmen. Maximal 2Sekunden.

13

was ist denn mit den 130k Daten, wie sind dort die Zeiten?
aber wenn wie vorher gesagt nur 500 statt evtl. auch 100k verschiedene Namen, dann klingt das ja wirklich nicht besonders vertrauenserweckend, sondern nur nach Zufalls-Testdaten

grundsätzlich wären viele Informationen drumherum interessant,
wie viele Daten welcher Art, wie viele Updates, wie viele Auswertungen

bei ständigen neuen Daten auch ständig nachprüfen?
wenn vielleicht nur Neuerungen der letzten Sekunden interessieren scheint es wenig hilfreich auf anwachsende Datenbestände von Tagen auszuwerten,

auch nützt es für einen bestimmten Namen nicht viel, den aktuell neuen Besuch mit allen 30 vorherigen ewig alten im Kreuzprodukt zu prüfen,

die Querys a la inner join table1 as data4 on data3.name=data4.name where data3.time < data4.time and (data3.time+1000) > data4.time
sind wohl schon die besten möglichen falls bei GROUP BY nichts geht, vielleicht noch eingeschränkt auf festes Min/Max der times, nur aktuelle Sekunden betrachten,
sollten bei überschaubaren Datenmengen auch gar nicht so langsam sein, schwer genauer zu beurteilen,
aber müssen dennoch jedes Mal von 0 anfangen, immer noch vermeidbar aufwendig

echte Programmierlogik könnte in so einem Bereich viel mehr erreichen,
besonders bei Begleitung eines Datenbestand mit laufenden Updates im Vorteil, da Vorwissen aufgebaut,
nicht den gesamten Datenbestand neu zu prüfen, auch nicht in Bereichen manches doppelt auszuwerden,

zu jedem Namen eine Datenecke, alte Einträge verfallen mit der Zeit bzw. überhaupt nur Zeitstempel, der letzte vorherige, zu merken,
falls mit der Zeit zu viele Namen, dann beizeiten aufräumen, alle alten löschen usw.

mit SQL schon bei einer Sache Schwierigkeiten, mit Programmlogik könnten sofort noch zig andere Dinge dazugebaut werden,
etwa Zählung wie oft denn auf diese Weise schnell wieder gegangen, wie viele Besuche überhaupt in einem bestimmten Zeitraum mit welchen sonstigen Verweildauern,
Speicherung alle Verweildauern zur schnellen Auswertung verschiedener Grenzen („wie sieht das ganze bei 5 sec aus?“),
Dinge zu denen an weiteres SQL noch weitaus länger oder überhaupt nicht mehr zu knabbern wäre

die höheren Daten, etwa weg von Einzelschranken hin zu Einträgen mit ‚Name, Begin, Ende, Dauer‘ könnten freilich auch wieder als Zwischenwerte in die DB,
um darauf dann ganz anders mit SQL ranzugehen,
es ist vor allem der erste Schritt, direkte Nachfolger zu finden, der Probleme macht…

14

Ich würde eher vermuten, dass eine Javalösung deutlich schneller ist. Das hängt aber auch davon ab, wie die Datenverbindung zwischen Javaclient und Datenbank ist.

Begründung: die Datenbank müsste einen Join auf der selben Tabelle machen. Das geschieht mit quadratischem Aufwand. Zumindest sehe ich keine Möglichkeit, die Größe des Joins zu reduzieren.

Eine Lösung in Java wäre von linearer (ggf. n log n) Zeitkomplexität, die Sortierung der Einträge der Tabelle wäre dank Index auch in linearer Zeit durchführbar.

Du müsstest dir dafür die Tabelle sortiert nach Zeitpunkt zurückgeben lassen. Danach gehst du in einer einfachen Schleife alle Einträge durch und merkst dir alle Namen in einer Liste. Sobald du einen Eintrag verarbeitest, musst du alle Einträge aus dieser Liste löschen, die älter sind als der aktuelle minus das gewünschte Intervall. Wenn der Name des aktuell verarbeiteten Eintrages danach noch in der Liste steht, gibst du ihn aus. Danach fügst du den Eintrag der Liste hinzu.

Edit: ich habe @SlaterB s Beitrag gerade erst zuende gelesen - der von ihm beschriebene Ansatz entspricht dem hier.

15

die Datenverbindung dürfte nur von geringer Bedeutung sein, für Übertragung der Anfrage und der Ergebnisse,
bei Millionen Ergebnissen nicht zu verachten, bei meist wenigen wie count(*)-Testanfragen dagegen kaum beteiligt

ob der Join schnell ist oder nicht klärt sich nur DB-intern, und das ist eine der überschaubar vielen Hauptaufgaben der DB, sollte da schon was können…,
bei eindeutigen Ids + evtl. Index macht ein normaler Join über Fremdschlüssel usw. ja auch niemanden Bange,

hier nun etwas mehr Einträge mit je gleichen Namen/ Attribut-Wert,
ein ziemlich allgemeines Thema,
da sollte es eigentlich Standard-Wissen geben, was noch unter Normalbedingungen effektiv auszuwerten ist…

100k Einträge, 500 verschiedene Werte = jeder Wert 200x -> 500x * 200^2 = 20 Mio. Paare = 200facher Aufwand gegenüber einmaligen Durchlauf der Tabelle?
falls ein Index auf das Attribut auch vorhanden ist und genutzt wird…

GROUP BY wäre wie gesagt dem einmaligen Durchlauf näher,
da sollte die DB doch nun wirklich vergleichbare Mittel haben, gleiches zusammenzusammeln,

fehlt nur noch etwas um aus dem GROUP BY auch Informationen zu gewinnen,
ohne neue Funktion sehe ich nichts mächtig genuges (falls das ein Wort ist),

16

Eine Lösung die mir noch einfällt ist, den time stamp zu klassifizieren. Also nicht millisekunden sondern z.B. 3 Sekunden genau abzulegen. Dann reicht eine Abfrage mit Group by und having, da die Einträge nun den selben time stamp bekommen.
Nachteil ist das Grenzfälle untergehen könnten.

17

Sorry, jetzt verstehe erst: du willst dann alle Einträge x, für die es ein Paar (x,y) mit einem Abstand <3 gibt

=> ich vermute mal stark, das ist tatsächlich O(n^2), mit einem einfachen Durchlauf ist da nicht viel zu machen

also eher
[SQL]
select id, name from table t1 where exists (select * from table t2 where t2.zeit between t1.zeit and t1+zeit + zeitfenster)
[/SQL]

18

könnte man auch berechnen statt speichern zu müssen, reicht leider nicht völlig

falls PostgreSQL oder andere unterstützende DB zur Verfügung, dann geht vielleicht Window Functions wie gerade gelesen mit Lag:

[sql]select distinct(name) from (
select name, time, lag(time) OVER (PARTITION BY name ORDER BY time) as prev from tab )
where time - prev < 1000
[/sql]
wobei über Performance dabei noch nichts gesagt ist

PostgreSQL: Documentation: 9.4: Window Functions
PostgreSQL: Documentation: 9.4: Window Functions

sql server - SQL Query to group items by time, but only if near each other? - Stack Overflow

19

Das ganze durch Java Code zu jagen ist in der Tat deutlich schneller. Aus der Tabelle werden ID/Name/Zeit abgefragt in einer Map gespeichert. Key ist dabei der Name und Value ein Objekt welches ID/Zeit beinhaltet. Danach wird die Map durchgelaufen und die entsprechenden Listen angepasst, so dass am Ende nur noch die Einträge vorhanden sind wo mindestens 1x der geforderte Zeitabstand unterschritten wurde.

		
		double count = DBDAO.count(currentProject);
		int resultSize = 500000;
		double pages = Math.ceil(count / resultSize);
		
		long lastUsedID = -1L;
                DuplicateTableModel tableModel= ((DuplicateTableModel)duplicateTable.getModel())
		while(pages != 0){
			lastUsedID++;
			Map listOfRecords = DBDAO.getRecordIDAndTimeWithPaging(lastUsedID, resultSize, currentProject);
			List <IDAndTimePart> listToCheck;
			Set<IDAndTimePart> set;
			DuplicateTableRow row;
			
			for(Entry <String, List <IDAndTimePart>> object : listOfRecords.entrySet()){
				listToCheck = object.getValue();
				set = findDuplicates(listToCheck, timeRange);
				if(set.size() > 1){
					for(IDAndTimePart part : set){
						row = new DuplicateTableRow(object.getKey(), part.getId());
						tableModel.addRow(row);
						if(part.getId() > lastUsedID)
							lastUsedID = part.getId();
					}
                                }
				if(set.size() == 1){
				        long id = set.iterator().next().getId();
					if(id > lastUsedID)
						lastUsedID = id;
					
				}
			}	
			pages--;
		}
		
		tableModel.updateModel();
		
	}

private Set<IDAndTimePart> findDuplicates(List<IDAndTimePart> inputList, long timeRange){
		Set<IDAndTimePart> duplicates = new HashSet <IDAndTimePart>();
		IDAndTimePart currentPart;
		
		if(inputList.size() == 1)
			return duplicates;
		
		for(int i=0; i<inputList.size()-1; i++){
			currentPart = inputList.get(i);
			if((currentPart.getTime() + timeRange) > inputList.get(i+1).getTime()){
				duplicates.add(currentPart);
				duplicates.add(inputList.get(i+1));
			}
		}
		
		return duplicates;
	}

Dass das so extrem schneller ist, hätt ich am Ende nicht erwartet. Zumindest aber tut es erstmal was es soll in akzeotabler Zeit. Bei ersten Tests mit der DB, in ~1.5Sek. Wie sich das bei mehr Daten und “Realdaten” ausgeht, muss ich noch testen.

20

was planst du bei der lastUsedId?
wieso etwas (nur) von den Doppelten dazu holen?
wenn keine Doppelten, dann die Id der letzten Anfrage +1, wobei pages trotzdem gnadenlos sinkt?

bei nicht lückenlos vergebenen Ids ist ein Filter darauf vielleicht nicht trivial,
deins sieht aber gewiss nicht praktikabel aus

siehe evtl. auch
http://forum.byte-welt.net/java-forum-das-java-welt-kompetenz-zentrum-wir-wissen-und-helfen-/datenbankprogrammierung/16649-setfirstresultstartid-vs-id-startid.html

wenn du getrennte Auswertungen machst, dann besser um 1x timeRange überlagernd abfragen,
sonst ist Zeitstempel xyz400 in der einen Query und xyz900 in der nächsten, völlig getrennt,
dabei eigentlich ein Doppelter für range = 1000

Zeit ist vielleicht generell ein guter Filter, leicht einzuteilen, eindeutig abzufragen, range-Problem gleich mit zu lösen
aber möglich dass dann mal wenige, mal viele Einträge in einem bestimmten Zeitraum liegen

ohne Überlappung würe wie schon öfter angesprochen helfen, die alten Daten etwas merken, zumindest den letzten Zeitstempel je Key/ Name