Query optimieren: SELECT ... NOT IN

Hallo!

Ich habe wenig Praxis-Erfahrung mit MySQL (außer ein paar kleinen
Projekten), insbesondere in der Optimierung von Queries, bin aber im
Zuge einer Übung wieder einmal dazugekommen, mich ein wenig mit MySQL
auseinanderzusetzen.

Konkret implementiere ich ein kleines Rezeptebuch (wie gesagt, es ist
eine Übung und keine RL-Applikation). Dabei soll es die Möglichkeit
geben, dass man nach allen Rezepten sucht, für die man die Zutaten
daheim hat.

Der wesentliche Teil meiner Datenbank sieht folgendermaßen aus:

CREATE TABLE recipe (
idRecipe INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
idCategory INTEGER UNSIGNED NOT NULL,
name VARCHAR(100) NULL,
timeToCook TIME NULL,
instruction TEXT NULL,
PRIMARY KEY(idRecipe)
);

CREATE TABLE ingredient_in_recipe (
idRecipe INTEGER UNSIGNED NOT NULL,
idIngredient INTEGER UNSIGNED NOT NULL,
quantity DOUBLE UNSIGNED NOT NULL,
PRIMARY KEY(idRecipe, idIngredient)
);

Dazu existiert noch eine Tabelle ingredient, d.h. ingredient_in_recipe
ist eine m:n-Tabelle (falls das der richtige Ausdruck dafür ist) mit den
Foreign Keys idRecipe und idIngredient.

Mit folgender Query frage ich den Namen der Rezepte ab, die ich nur mit
den Zutaten kochen kann, die ich zuhause habe. "(11, 12, 13)" sind Ids
für Zutaten, die ich zuhause habe (diese Zahlen bekomme ich dynamisch
über ein Skript).

Meine bisherige Query sieht so aus:

SELECT r.name FROM recipe r WHERE r.idRecipe NOT IN
(SELECT iir.idRecipe FROM ingredient_in_recipe iir WHERE
iir.idIngredient NOT IN (11,12,13) GROUP BY iir.idRecipe);

Aus Interesse habe ich mir diese Query mit EXPLAIN angeschaut und
folgendes Resultat erhalten (etwas gekürzt, damit es lesbar bleibt, ich
hoffe, ich unterschlage damit nicht wichtige Informationen):

+----+--------------------+-------+-------+----------------- +---------+
| id | select_type | table | type | possible_keys | key |
+----+--------------------+-------+-------+----------------- +---------+
| 1 | PRIMARY | r | ALL | NULL | NULL |
| 2 | DEPENDENT SUBQUERY | iir | index | ix_idIngredient | PRIMARY |
+----+--------------------+-------+-------+----------------- +---------+

Soweit ich die Ausgabe von EXPLAIN verstehe, schaut die Subquery vom
Laufzeit-Verhalten schon ganz gut aus. Allerdings verstehe ich nicht,
wieso bei type der Query mit der id 1 "ALL" aufscheint, was nach meinem
Verständnis ja das worst-case-scenario ist, noch dazu, wo das Resultat
der Subquery ja mit meinem Primary Key aus recipe verglichen wird.

Warum ist das so? Wie kann man das verbessern? Mir geht es vor allem um
das Verständnis, da ich in Zukunft natürlich von Haus aus "gute" Queries
schreiben möchte.

Ich freue mich über alle Antworten, Meinungen und/oder Verweisen auf
Bücher oder ins Web.

Danke im Voraus,
lg,
Gernot

Re: Query optimieren: SELECT ... NOT IN

Gernot Bauer wrote:

> SELECT r.name FROM recipe r WHERE r.idRecipe NOT IN
> (SELECT iir.idRecipe FROM ingredient_in_recipe iir WHERE
> iir.idIngredient NOT IN (11,12,13) GROUP BY iir.idRecipe);
>
> Aus Interesse habe ich mir diese Query mit EXPLAIN angeschaut und
> folgendes Resultat erhalten (etwas gekürzt, damit es lesbar bleibt, ich
> hoffe, ich unterschlage damit nicht wichtige Informationen):
>
> +----+--------------------+-------+-------+----------------- +---------+
> | id | select_type | table | type | possible_keys | key |
> +----+--------------------+-------+-------+----------------- +---------+
> | 1 | PRIMARY | r | ALL | NULL | NULL |
> | 2 | DEPENDENT SUBQUERY | iir | index | ix_idIngredient | PRIMARY |
> +----+--------------------+-------+-------+----------------- +---------+

Doch, tust Du.

Am besten rufst Du solche Sachen immer mit dem Terminator \G statt mit ;
auf, dann erhältst Du so was wie

*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: r
type: ALL
possible_keys: NULL
key: NULL
key_len: ...
ref: ...
rows: ...
Extra:

> Soweit ich die Ausgabe von EXPLAIN verstehe, schaut die Subquery vom
> Laufzeit-Verhalten schon ganz gut aus. Allerdings verstehe ich nicht,
> wieso bei type der Query mit der id 1 "ALL" aufscheint, was nach meinem
> Verständnis ja das worst-case-scenario ist, noch dazu, wo das Resultat
> der Subquery ja mit meinem Primary Key aus recipe verglichen wird.

Wenn ich jetzt nicht völlig daneben liege, könnte das an dem doppelten
NOT IN liegen, was mir (zumindest vom Gefühl her) recht teuer und
aufwendig vorkommt.

Genaueres könnte man sagen, wenn Du zumindest mal die rows-Informationen
des EXPLAIN dagelassen hättest und evtl. noch Infos, wieviele Rows
insgesamt in den Tabellen sind.

Wenn "sehr viele"[TM] Rows zurückgeliefert werden (gemessen an der
Gesamtzahl in der Tabelle), werden die Indices ignoriert und ein Full
Table Scan gemacht, da dieser ab einer bestimmten Trefferquote billiger
ist.


HTH zumindest ein wenig,


Thomas
--
Jabber-ID: glglgl@amessage.info (keine Email-Adresse!)
Warum Jabber, was ist das und wie geht das?
http://de.wikibooks.org/wiki/Jabber-Kompendium:_Schnelleinst ieg

Re: Query optimieren: SELECT ... NOT IN

Hallo!

Thomas Rachel schrieb:
> Gernot Bauer wrote:
>
>> SELECT r.name FROM recipe r WHERE r.idRecipe NOT IN
>> (SELECT iir.idRecipe FROM ingredient_in_recipe iir WHERE
>> iir.idIngredient NOT IN (11,12,13) GROUP BY iir.idRecipe);

> Am besten rufst Du solche Sachen immer mit dem Terminator \G statt mit ;

Danke, hab ich nicht gekannt. Der Output ist:

*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: r
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 4
Extra: Using where
*************************** 2. row ***************************
id: 2
select_type: DEPENDENT SUBQUERY
table: iir
type: index
possible_keys: NULL
key: PRIMARY
key_len: 8
ref: NULL
rows: 10
Extra: Using where; Using index

"possible_keys" unter 2. row ist NULL (im Gegensatz zu meinem ersten
Posting), da ich einen Index entfernt habe, im OP allerdings das EXPLAIN
mit den "alten" Tabellen durchgeführt habe (die CREATE-Statements sind
aktuell).

> Wenn ich jetzt nicht völlig daneben liege, könnte das an dem doppelten
> NOT IN liegen, was mir (zumindest vom Gefühl her) recht teuer und
> aufwendig vorkommt.
>
> Genaueres könnte man sagen, wenn Du zumindest mal die rows-Informationen
> des EXPLAIN dagelassen hättest und evtl. noch Infos, wieviele Rows
> insgesamt in den Tabellen sind.

Oben ist der EXPLAIN-Output. Dazu noch die Daten aus den beiden Tabellen:

mysql> select * from ingredient_in_recipe;
+----------+--------------+----------+
| idRecipe | idIngredient | quantity |
+----------+--------------+----------+
| 1 | 11 | 2 |
| 1 | 12 | 2 |
| 1 | 13 | 4 |
| 2 | 7 | 400 |
| 2 | 12 | 2 |
| 3 | 1 | 300 |
| 3 | 6 | 600 |
| 4 | 3 | 50 |
| 4 | 4 | 100 |
| 4 | 5 | 4 |
+----------+--------------+----------+
10 rows in set (0.02 sec)

mysql> select idRecipe, name from recipe;
+----------+-------------------+
| idRecipe | name |
+----------+-------------------+
| 1 | Fish soup |
| 2 | Beef with onions |
| 3 | Chicken with rice |
| 4 | Egg cake |
+----------+-------------------+
4 rows in set (0.00 sec)

sowie die Query:

mysql> SELECT r.name FROM recipe r WHERE r.idRecipe NOT IN
-> (SELECT iir.idRecipe FROM ingredient_in_recipe iir WHERE
-> iir.idIngredient NOT IN (11,12,13) GROUP BY iir.idRecipe);
+-----------+
| name |
+-----------+
| Fish soup |
+-----------+
1 row in set (0.00 sec)


Wie im OP erwähnt, ist das nur eine Übung, die ich zu erledigen habe,
wobei das Hauptaugenmerk auch nicht auf der Datenbank liegt. Deshalb
sind nicht viele Informationen in der Datenbank gespeichert.

> Wenn "sehr viele"[TM] Rows zurückgeliefert werden (gemessen an der
> Gesamtzahl in der Tabelle), werden die Indices ignoriert und ein Full
> Table Scan gemacht, da dieser ab einer bestimmten Trefferquote billiger
> ist.

Aha, also hängt das auch von der Beschaffenheit der Daten in der
Datenbank ab, verstehe ich das richtig? Wie kann man die Query besser
formulieren?

> HTH zumindest ein wenig,

Ja, vielen Dank, ein wenig klarer ist mir die Sache jetzt geworden.

> Thomas

lg,
Gernot

Re: Query optimieren: SELECT ... NOT IN

Gernot Bauer schrieb:
> Hallo!
>
> Thomas Rachel schrieb:
>> Gernot Bauer wrote:
>>
>>> SELECT r.name FROM recipe r WHERE r.idRecipe NOT IN
>>> (SELECT iir.idRecipe FROM ingredient_in_recipe iir WHERE
>>> iir.idIngredient NOT IN (11,12,13) GROUP BY iir.idRecipe);
>
>> Am besten rufst Du solche Sachen immer mit dem Terminator \G statt mit ;
>
> Danke, hab ich nicht gekannt. Der Output ist:
>
> *************************** 1. row ***************************
> id: 1
> select_type: PRIMARY
> table: r
> type: ALL
> possible_keys: NULL
> key: NULL
> key_len: NULL
> ref: NULL
> rows: 4
> Extra: Using where

Es geht also um exakt vier Zeilen. Wozu sollte man da einen Index
bemühen? Das lohnt nicht, da ist die direkte Lektüre der Tabelle
schneller, zumal die vermutlich auf einen Rutsch ins RAM passt.

> Aha, also hängt das auch von der Beschaffenheit der Daten in der
> Datenbank ab, verstehe ich das richtig? Wie kann man die Query besser
> formulieren?
>

Ja, natürlich. Hast Du eigentlich mal im Handbuch nachgelesen
(dev.mysql.com/doc)? Dort gibt es einen länglichen Abschnitt zum Thema
"Wann MySQL Indizes nutzt".

Re: Query optimieren: SELECT ... NOT IN

Hallo!

Christian Kirsch schrieb:
>
> Es geht also um exakt vier Zeilen. Wozu sollte man da einen Index
> bemühen? Das lohnt nicht, da ist die direkte Lektüre der Tabelle
> schneller, zumal die vermutlich auf einen Rutsch ins RAM passt.

Klingt natürlich logisch. Bisher habe ich gedacht, dass die Ausführung
der Queries unabhängig ist von der Anzahl der Daten, die darin sind, das
war wohl eine große Fehlannahme.

Ich schau mal, was passiert, wenn ich die Datenbank mit vielen
Datensätzen befülle.

> Ja, natürlich. Hast Du eigentlich mal im Handbuch nachgelesen
> (dev.mysql.com/doc)? Dort gibt es einen länglichen Abschnitt zum Thema
> "Wann MySQL Indizes nutzt".

Das Handbuch kenne ich, diesen Abschnitt habe ich aber übersehen. Ich
werde alles noch einmal genauer durchlesen, dann steigt mein Verständis
von der Materie hoffentlich ein bisschen.

Vielen Dank für deine Hilfe,

lg,
Gernot

Re: Query optimieren: SELECT ... NOT IN

On 20.05.2007 23:10, Gernot Bauer wrote:
> Hallo!
>
> Christian Kirsch schrieb:
>> Es geht also um exakt vier Zeilen. Wozu sollte man da einen Index
>> bemühen? Das lohnt nicht, da ist die direkte Lektüre der Tabelle
>> schneller, zumal die vermutlich auf einen Rutsch ins RAM passt.
>
> Klingt natürlich logisch. Bisher habe ich gedacht, dass die Ausführung
> der Queries unabhängig ist von der Anzahl der Daten, die darin sind, das
> war wohl eine große Fehlannahme.
>
> Ich schau mal, was passiert, wenn ich die Datenbank mit vielen
> Datensätzen befülle.
>
>> Ja, natürlich. Hast Du eigentlich mal im Handbuch nachgelesen
>> (dev.mysql.com/doc)? Dort gibt es einen länglichen Abschnitt zum Thema
>> "Wann MySQL Indizes nutzt".
>
> Das Handbuch kenne ich, diesen Abschnitt habe ich aber übersehen. Ich
> werde alles noch einmal genauer durchlesen, dann steigt mein Verständis
> von der Materie hoffentlich ein bisschen.

Das doppelte NOT INT wird dich umbringen. Ein positiver Join ist viel
effizienter - bei NOT IN kann die DB keinen Index verwenden
(Hausaufgabe: warum?). Versuch's mal mit

SELECT r.name
FROM recipe r
WHERE r.idRecipe IN
(SELECT iir.idRecipe
FROM ingredient_in_recipe iir
WHERE iir.idIngredient IN (11,12,13))

SELECT r.name
FROM recipe r,
(SELECT DISTINCT iir.idRecipe
FROM ingredient_in_recipe iir
WHERE iir.idIngredient IN (11,12,13)) ri
WHERE r.idRecipe = r1.idRecipe

SELECT r.name
FROM recipe r,
(SELECT iir.idRecipe
FROM ingredient_in_recipe iir
WHERE iir.idIngredient IN (11,12,13)
GROUP BY iir.idRecipe) ri
WHERE r.idRecipe = r1.idRecipe

Ciao

robert