# Brauche die Datensätze, die beim Join keine Treffer haben



## Tommy57 (12. Dezember 2013)

Hallo,

ich stehe gerade vor einem komplizierten Problem. Ich suche die Ausreißer in einer MySQL-Tabelle (ENGINE=MEMORY). Ein funktionierendes Statement dafür habe ich schon:


```
UPDATE 
    tmp_item_prices
SET valid = 0
WHERE id IN
    (SELECT
        id
    FROM
        (SELECT
            tip1.id,
            COUNT(tip2.price) AS amount
        FROM
            tmp_item_prices tip1
        LEFT OUTER JOIN
            tmp_item_prices tip2
        ON
            tip2.item_id = tip1.item_id
        AND
            tip2.id >= tip1.id-5 AND tip2.id != tip1.id AND tip2.id <= tip1.id+5
        AND
            tip2.price > tip1.price*0.8 AND tip2.price < tip1.price*1.2
        GROUP BY
            tip1.id) subq1
    WHERE
        amount = 0);
```

Die Memory-Tabelle könnte so aussehen:

```
ID    ITEM_ID    PRICE
1     1                120
2     1                90
3     1                135
4     1                144
5     1                124
6     2                645
7     2                660
8     2                610
9     2                550
```

Das Statement oben läuft bei einer Tabelle mit 10.000 Zeilen in wenigen Sekunden durch. Bei einer Tabelle mit 100.000 lädt er schon rund 10 Minuten. Die Memory Tabelle hat mehrere Millionen Zeilen.

Das Statement oben zählt in einem Join die zugehörigen Treffer zu jedem Preis. Das ist ein unglaublicher Rechenprozess. Ich brauche eine Variante, wo er gezielt nur die nimmt, die keine Treffer haben. Die Anzahl der nicht validen Preise beläuft sich auf unter 1% der Daten, deswegen sollten die überschüssigen 99% mit einer geschickten Bedingung verworfen werden.

Gruß, Tommy


EDIT:

Durch eine kleine Änderung braucht er bei 100.000 Datensätzen nur noch 5 Minuten.

Das ist aber leider immer noch viel zu langsam. Hat Jemand eine Idee, wie man da noch mehr rausholen kann?



```
UPDATE 
    tmp_item_prices
SET valid = 0
WHERE id IN
    (SELECT
        id
    FROM
        (SELECT
            tip1.id
        FROM
            tmp_item_prices tip1
        LEFT OUTER JOIN
            tmp_item_prices tip2
        ON
            tip2.item_id = tip1.item_id
        AND
            tip2.id >= tip1.id-5 AND tip2.id != tip1.id AND tip2.id <= tip1.id+5
        AND
            tip2.price > tip1.price*0.8 AND tip2.price < tip1.price*1.2
        WHERE
            tip2.id IS NULL) subq1);  -- Diese WHERE Abfrage erspart mir den COUNT und verwirft somit die validen Ergebnisse
```


----------



## Yaslaw (12. Dezember 2013)

Ich kann nicht nachvollziehen, was du hast und was du willst.

1) Poste doch mal ein Datenbeispiel von tmp_item_prices.

2) Dann Poste noch, was da gefunden werden soll. Ausreisser? Der höchste? der tiefste?

3) Was soll 'tip1.id-5' bewirken

4) Was ist das für eine Memory-Tabelle, welche du hier gepostet hast?


----------



## Tommy57 (12. Dezember 2013)

Hi Yaslaw,

1. die Tabelle oben mit den drei Spalten ID, ITEM_ID und PRICE ist ein Beispiel. 
Jeder Datensatz entspricht einem gekauften Artikel. Die ITEM_ID ist der Artikel.

2. und 3. Hin und wieder sind Preise in der Datenbank, die von den anderen extrem abweichen. Um diese Preise zu ermitteln, ist die Anforderung, jeden Preis eines bestimmten Artikels gegen die 5 vorher und gegen die 5 nachher zu prüfen (deswegen tip1.id-5). Befindet sich innerhalb dieser maximal 10 Datensätze kein anderer Preis innerhalb der Range von 80%-120%, wird dieser Preis als nicht valide gekennzeichnet.

Wichtig ist hier zu wissen, dass es auch eine Preisentwicklung gibt. Heißt 100€ können heute valide sein, aber in 3 Monaten sind sie es schon nicht mehr, weil der Einkaufspreis zum Beispiel in die Höhe geschossen ist.

4. Um das Ganze etwas zu beschleunigen, werden die Daten vorher von einer MYISAM Tabelle in eine Memory-Tabelle zwischen gespeichert, welche sich ja im Arbeitsspeicher befindet. Diese Daten sind bereits vorsortiert und entsprechend gruppiert, so dass man mittels ID und ITEM_ID die Preise nach vorne und hinten prüfen kann, ohne dabei ein Kaufdatum oder so zu überprüfen.


----------



## Yaslaw (12. Dezember 2013)

Kannst du mal ein Script mit der memeory-Tabelle und etw 100 Datensätze zur Verfügung stellen, damit man testen kann?


----------



## Tommy57 (12. Dezember 2013)

Hi Yaslaw,

das wäre die Tabelle:


```
DROP TABLE IF EXISTS `tmp_item_prices`;
CREATE TABLE `tmp_item_prices` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `item_id` int(11) NOT NULL,
  `price` double(8,2) NOT NULL,
  `valid` varchar(45) DEFAULT NULL,
  KEY `id` (`id`)
) ENGINE=MEMORY AUTO_INCREMENT=0 DEFAULT CHARSET=utf8;

INSERT INTO `tmp_item_prices` (`item_id`, `price`) VALUES (1,90),(1,92),(1,83),(1,77),(1,77),(1,84),(1,79),(1,83),(1,81),(1,47),(1,86),(1,89),(1,99),(1,108),(1,116),(1,108),(1,111),(1,112),(1,108),(1,105),(1,100),(1,104),(1,114),(1,118),(1,115),(1,111),(1,102),(1,105),(1,96),(1,96),(1,87),(1,78),(1,69),(1,62),(1,58),(1,60),(1,50),(1,51),(1,47),(1,45),(1,53),(1,47),(1,38),(1,46),(1,39),(1,48),(1,58),(1,65),(1,64),(1,60),(2,451),(2,454),(2,452),(2,442),(2,452),(2,447),(2,449),(2,458),(2,466),(2,465),(2,465),(2,461),(2,455),(2,453),(2,455),(2,449),(2,441),(2,449),(2,449),(2,445),(2,453),(2,463),(2,463),(2,473),(2,476),(2,481),(2,474),(2,475),(2,470),(2,960),(2,466),(2,472),(2,476),(2,469),(2,476),(2,479),(2,478),(2,476),(2,478),(2,474),(2,482),(2,474),(2,477),(2,468),(2,468),(2,462),(2,458),(2,461),(2,452),(2,458);
```

Und mit dieser Abfrage erhälst du die nicht validen IDs:


```
SELECT
            tip1.id
        FROM
            tmp_item_prices tip1
        LEFT OUTER JOIN
            tmp_item_prices tip2
        ON
            tip2.item_id = tip1.item_id
        AND
            tip2.id >= tip1.id-5 AND tip2.id != tip1.id AND tip2.id <= tip1.id+5
        AND
            tip2.price > tip1.price*0.8 AND tip2.price < tip1.price*1.2
        WHERE
            tip2.id IS NULL
```

Durch das setzen eines Indices auf ITEM_ID, wird die Abfrage nochmal um einiges beschleunigt:


```
ALTER TABLE `tmp_item_prices` ADD INDEX ( `item_id` );
```


EDIT: Die nicht validen Preise sind hier zufällig auch gleichzeitig der MIN und MAX. Das trifft nur ganz selten zu. Häufiger ist z.B., dass ein Preis ins falsche Jahr eingetragen wurde, wo er 2012 rund 80€ gekostet hat und 2013 rund 150€ würde dieser Wert dann rausspringen.


----------



## Yaslaw (12. Dezember 2013)

Beschränkt brauchbar. Am grossen beabsichtigten Preisbruch mit derselben item_id geht es nicht.


```
SELECT
	p1.*,
	-- Durchschnitt der +/- 5 Datensätze
	@avgp:=(SELECT	AVG(p2.price)
	FROM tmp_item_prices p2
	WHERE p2.id BETWEEN p1.id-3 AND p1.id+3
			AND p2.item_id = p1.item_id
	) AS avgp,
	-- Abweichung des Preises zum Durchschnitt in %
	@percent:=100 - (@avgp/p1.price*100) AS percent,
	-- Flag obs ein Ausreisser ist
	ABS(@percent) > 5 invalid
FROM tmp_item_prices p1
```
Ergibt mit der obigen Tabelle

```
| id | item_id | price | avgp          | percent                | invalid |
|  1 |       1 |   120 | 122.250000000 |  -1.875000000000000000 | 0       |
|  2 |       1 |    90 | 122.600000000 | -36.222222222222222200 | 1       |
|  3 |       1 |   135 | 122.600000000 |   9.185185185185185200 | 1       |
|  4 |       1 |   144 | 122.600000000 |  14.861111111111111200 | 1       |
|  5 |       1 |   124 | 123.250000000 |   0.604838709677419400 | 0       |
|  6 |       2 |   645 | 616.250000000 |   4.457364341085271400 | 0       |
|  7 |       2 |   660 | 616.250000000 |   6.628787878787878800 | 1       |
|  8 |       2 |   610 | 616.250000000 |  -1.024590163934426200 | 0       |
|  9 |       2 |   550 | 616.250000000 | -12.045454545454545400 | 1       |
```


----------



## Tommy57 (12. Dezember 2013)

Also die Idee ist klasse. Aber du benutzt ja jetzt den Durchschnitt der insgesamt 11 Preise. Ich soll es so machen, dass ich jeden Preis gegen die anderen prüfe. Ich hatte noch überlegt, dass ich den MIN aller umliegenden höheren Preise und den MAX aller umliegenden niedrigeren Preise nehme. 

Ich glaube aber nicht, dass das Statement dann schneller wird. Also für die komplette Tabelle liegen wir aktuell bei 90 Minuten.

EDIT: Ich werde deine Variante gleich mal auf der großen Datenbank testen. Mal sehen, wie schnell das durchläuft. ^^


----------



## Yaslaw (12. Dezember 2013)

Das Problem. Du findest mit deiner Variante 2 Ausreisser innerhalb von 5 ids nicht
Mit meiner ev. auch nicht, das der andere Ausreisser ebenfalls in den Durchschnitt zählt

100
101
103
70
100
103
108
60
100
101
102

Bei der Prüfung der 70 findet er die 60 - ergo kein Ausreisser
Beid er Prüfung der 60 findet er die 70 - ergo kein Ausreisser

Wenn man die Zahlen aber so betrachtet, sind es Ausreisser.


----------



## Tommy57 (12. Dezember 2013)

Ja, das ist ein Problem, da hast du recht. Aber der Kunde sagt, wir haben so viele Datensätze, die Wahrscheinlichkeit, dass sicher innerhalb von einem so kleinen Zeitraum 2 Fehler einschleichen ist eher unwahrscheinlich.

Kurz zu deinem Statement. Wenn wir Ausreißer nach oben 70%-140% zulassen, müsste es dann heißen:

```
ABS(@PerCent) > 40 OR ABS(@PerCent) < -30 invalid
```


----------



## Yaslaw (12. Dezember 2013)

Nop, dann ohne ABS() und mit BETWEEN

```
NOT @PerCent BETWEEN -30 AND +40 AS invalid
```

Nachtrag:
Ändere bei deiner Version auch auf BETWEEN
Und setze einen Index auf id + item_id


----------



## Tommy57 (12. Dezember 2013)

Ich sehe gerade ein Problem bei deinem Statement.

Wenn ein Preis mal total aus der Reihe springt, weil er einfach 100 mal größer ist als die umliegenden Preise, würden bei deinem Statement alle umliegenden Preise invalide sein.


----------



## Yaslaw (12. Dezember 2013)

Jepp.

Darum probier mal deine Variante mit den Anpassungen von meinem Nachtrag


> Nachtrag:
> Ändere bei deiner Version auch auf BETWEEN
> Und setze einen Index auf id + item_id


----------



## Tommy57 (12. Dezember 2013)

Kann es zufällig sein, dass MySQL irgendwie Daten zusätzlich cached. Ich mache bei jedem Durchlauf ein Truncate auf die Tabelle und nehme 100.000 Datensätze. Normale Ergebnisse lagen immer im Minuten Bereich. Auf einmal kriege ich hier ein Ergebnis mit 4 Sekunden, was ich aber vorher schon getestet hatte und bei rund 5 Minuten lag!?


----------



## Yaslaw (12. Dezember 2013)

Immer die gleichen Datensätze?

Und mein Index ist ein anderer als derjenige, den du gepostet hast.

Schau dir mal den Explain-Plan vom SQL an.


----------



## Tommy57 (12. Dezember 2013)

> Und setze einen Index auf id + item_id



ID ist doch ein Primary. Bringt das was, da ein Index mit ITEM_ID drauf zu setzen? Ich teste das gleich mal...




> Immer die gleichen Datensätze?



Ja, müsste so sein. Mache beim Import einfach ein LIMIT 100000


EDIT:
Also es findet ein Truncate auf die Tabelle statt und dann werden die Daten aus anderen Tabellen geholt und da rein geschoben. Da gehe ich hin und hole dann nur 10.000 oder 100.000 oder so...


EDIT2:
Der neue Index hat keinen Vorteil gebracht.


----------



## Tommy57 (12. Dezember 2013)

Also die aktuelle Variante benötigt nur noch knapp 50 Minuten. Die alte Variante hatte 90 Minuten gebraucht. Das ist soweit schon mal okay.

Noch vllt zwei kurze Fragen:

1. Was ist besser?
Die ITEMs in einer foreach Schleife zu prüfen, was die Tabelle immer nur kurz locken würden oder ein komplette Überprüfung, was die Tabelle glaube ich auch über die komplette Dauer blockiert. Die Memory-Tabelle dient nur als Zwischentabelle. Da finden eigentlich keine anderen Prozesse statt.

2. Was ist performanter, wenn ich in einer foreach Schleife einzelne ITEM_IDs prüfe? 
Einen direkten JOIN über die ganze Tabelle machen und im ON mit der ITEM_ID verknüpfen oder den JOIN auf eine Subquery setzen, die die gesuchte ITEM_ID vorselektiert.


----------



## Tommy57 (12. Dezember 2013)

So, in einer foreach Schleife wird jede ITEM_ID geprüft mittels Script und einfacher if-Abfrage. Die nicht validen Preise werden mittels UPDATE auf nicht valide gesetzt. Der Spaß dauert, warum auch immer, nur eine Minute. Das Ergebnis sieht korrekt aus und der Query-Cache ist deaktiviert. Es ist mir ein absolutes Rätsel, da vor zwei Tagen diese Variante mit 90 Minuten mich zum Optimieren getrieben hat. In den zwei Tagen ist nicht viel passiert, bis auf der Indice, der da zu gekommen ist. 

Wie auch immer. Die Lösung ist super. Und danke für die Hilfe.

Gruß, Tommy


----------

