Ausführunsplan / SQL Optimizer

[tsteinmaurer]

Neben dem Ausführungsplan wären auch noch IO Statistiken in Form von Indexed vs. Non-Indexed Reads auf den Tabellen interessant.

Regel Nummer 1 beim Performance testen ist das Ganze mit einer repräsentativen Datenmenge zu machen. Füll dir die Tabellen mal mit einem Datengenerator an und dann schau mal, ob sich hier was ändert.

Thomas

[Namenloser]

Zitat von exilant:

@Namenloser: Ja. Auf Feld STATUS gibt es einen Index. Warum das aber dazu führen sollte dass der Index für den PK in v2fertigartikel nicht benutzt wird ist mir nicht klar.

Weil der Nutzen des Index beim Join, soweit ich weiß, hauptsächlich darin besteht, dass durch ihn beide Relationen bezüglich der Verknüpfungs-Spalte sortiert sind. Dadurch kann man einen recht effizienten Merge-Join durchführen.

Folgende Tabellen als Beispiel:

Code:

Tabelle X    Tabelle Y
 A B          A C
---------    ---------
 1 42         2 0
 2 27         3 1
 3 40         4 2
 5 38         5 3
 7 39         7 4
 9 41         9 5

Beide Tabellen haben einen Index auf Spalte A (aufsteigend sortiert), und die Abfrage ist select A, B, C from X join Y on X.A = Y.A .

Man geht nach folgendem Pseudocode vor:

Code:

CursorX := Zeiger auf erste Zeile von Tabelle X.
CursorY := Zeiger auf erste Zeile von Tabelle Y.

while (not CursorX.EOF and not CursorY.EOF) do
begin
  if CursorX.A = CursorY.A then
    Elemente von CursorX und CursorY konkatenieren und Zeile ausgeben
  else if CursorX.A > CursorY.A then
    CursorY eine Zeile weiter nach unten bewegen
  else if CursorX.A < CursorY.A then
    CursorX eine Zeile weiter nach unten bewegen
end;

(Zur Vereinfachung gehe ich hier mal davon aus, dass A in beiden Tabellen unique ist. Man kann den Algorithmus aber auch für nicht-unique Fälle verallgemeinern).

Das ist ein recht effizienter Join-Algorithmus, allerdings nur dann wirklich effizient, wenn die es für die Eingabemengen schon sortiert sind. Im obigen Beispiel ist das der Fall dank des Index.

Wenn die Abfrage jetzt aber stattdessen wäre select A, B, C from X join Y on X.A = Y.A where X.B in (42, 27, 38, 39) und auf B ein Index liegt, dann kann es sein, dass der Optimizer sich entscheidet erst mal nach der Bedingung zu filtern und dabei den Index auf B zu nutzen.

Zwischenergebnis:

Code:

Tabelle X'   Tabelle Y
 A B          A C
---------    ---------
 2 27         2 0
 5 38         3 1
 7 39         4 2
 1 42         5 3
              7 4
              9 5

Da der Index auf B benutzt wurde, sind die Zeilen von X' nun möglicherweise in einer anderen Reihenfolge und nicht mehr nach A sortiert. Folglich kann der Join nun nicht mehr so effizient mit dem Merge-Join-Algorithmus durchgeführt werden. Man könnte jetzt natürlich X' einfach noch mal extra nach A sortieren, aber möglicherweise ist es effizienter, gleich einen ganz anderen Join-Algorithmus zu verwenden, z.B. Hash-Join. Dabei nützt einem dann allerdings auch der Index auf Tabelle Y nichts mehr, weshalb er nicht benutzt wird.


Ist aber nur geraten, ich hab keine Ahnung, was der Optimizer intern macht und was für Algorithmen er verwendet.

[Dejan Vu]

Dann brauch ich aber keinen B+ Baum. Ich habe das so umgesetzt:

Code:

CursorX auf 1.Zeile
while not CursorX.EOF do
  if CursorY.FindFirst(CursorX.A) then
    repeat
      Output CursorX.joined(CursorY);
    until not CursorY.FindNext(CursorX.A);
    CursorX.GotoNext

Wobei CursorX meist auf die Tabelle zeigt, die kleiner ist bzw. bei der alle 'A'-Werte insgesamt schneller zu lesen sind (z.B. weil die Tabelle kleiner ist, oder ein Index vorliegt oder beides oder oder oder).

Der Optimizer wird diese Strategie verwenden, wenn er für das Suchen des korrespondierenden Eintrags eine schnelle B*-Suche verwenden kann (fast O(1)) und Indexe für beide Tabellen auf 'A' vorhanden sind und die Tabelle 'X' nicht all zu viele unterschiedliche 'A' besitzt. Im Extremfall ist die eine Tabelle nur 1 Zeile lang, dann habe ich den korrespondierenden Eintrag aus der anderen Tabelle in O(1) gefunden. Bei deiner Version ist das O(n).

Es kann allerdings sein, das 'dein' Scan schneller ist. Z.B. wenn beide Tabellen in etwa gleich groß sind und es viele unterschiedliche 'A' in beiden Tabelle gibt. Es wird bestimmt Heuristiken geben, die ausrechnen, wann welche Schleife verwendet wird (der 'Optimizer'). Wozu sind denn sonst die Indexstatistiken gut?

Dein Algorithmus bricht blöderweise ab, wenn ein Schlüssel 'A' in X größer ist als der größte in Y (wenn also CursorY.EOF = true) ist. Aber ich weiß, wie Du das meinst. Blöd ist der jedenfalls nicht, der Algo.

[hoika]

Hallo,

reduzier mal deine Query schrittweise

select
v2ps.par,
v2ps.v2fertigartikel,
v2fertigartikel.artikelbezeichnung
from v2ps
inner join v2fertigartikel on (v2ps.v2fertigartikel=v2fertigartikel.id)
where v2ps.status in ('U','A')


select
v2ps.par,
v2ps.v2fertigartikel,
v2fertigartikel.artikelbezeichnung
from v2ps
inner join v2fertigartikel on (v2ps.v2fertigartikel=v2fertigartikel.id)
// das fliegt erst mal raus where v2ps.status in ('U','A')

Vielleicht mag er das IN nicht ?

Das ginge ja auch über OR.

Von welcher FB-2.5-Version reden wir eigentlich ?


Heiko

[Namenloser]

Zitat von Dejan Vu:

Dein Algorithmus bricht blöderweise ab, wenn ein Schlüssel 'A' in X größer ist als der größte in Y (wenn also CursorY.EOF = true) ist.

Dann gibt es ja auch keine weiteren Datensätze mehr, für die die Join-Bedingung noch erfüllt sein könnte. X und Y sind ja beide sortiert; d.h. man einen Schlüssel A in X erreicht, der größer ist als alle Schlüssel in Y, dann wären alle nachfolgenden Schlüssel von X erst recht größer als alle Schlüssel in Y (und folglich nicht gleich).

Aber du hast natürlich recht, dass die beste Strategie immer von den Daten selbst abhängt. Es kann daher eben z.B. auch schneller sein, einen stumpfen Table-Scan durchzuführen als den Index zu benutzen, weil konsekutives Lesen schneller ist als Random-Access.

[Dejan Vu]

(abbrechen) Autsch, ja. Stimmt.

[exilant]

Zunächst mal vielen Dank für die vielen Antworten.
Zunächst @tsteinmaurer:

Klar. Man sollte mit einer Datenmenge testen die dem worst-case nahekommt. Das werde ich auch tun.
Aber zunächst mal folgendes:

Die Statistik indexed vs. natural reads habe ich mir angesehen und verstehe nicht wirklich was da vor sich geht.
Situation ist wie beschrieben folgende:

v2ps -> Betriebsaufträge, 241.954 Datensätze
v2ps.v2fertigartikel = integer not NULL,

v2fertigartikel -> wie der Name sagt: Artikelstammdaten, 7.782 Datensätze
v2fertigartikel.id = integer, natürlich NOT NULL da PK

Die Abfrage wie gehabt:

select v2ps.par, v2ps.v2fertigartikel, v2fertigartikel.artikelbezeichnung
from v2ps
inner join v2fertigartikel on (v2ps.v2fertigartikel=v2fertigartikel.id)
where v2ps.status in ('U','A')

Ausgabe des Plans (IBExpert)
PLAN JOIN (V2FERTIGARTIKEL NATURAL, V2PS INDEX (V2PS_IDX3))

Statistik:
NonIndexed Reads (v2fertigartikel): 7.782 !!!!!
Indexed Reads (v2ps): 241.934 !!!

Der vom Plan verwendete Index V2PS_IDX3 indexiert die Felder (V2FERTIGARTIKEL,V2FARBE), ist also völlig unbrauchbar im Kontext der Abfrage.
Entweder spinnt die Ausgabe des IBExpert oder der Optimizer erzeugt seinen Plan nach sehr esoterischen Kriterien.

@hoika

Das Query reduziert habe ich. Ebenfalls das IN durch ein OR ersetzt. Es ändert genau garnichts.
Ich bin echt verwundert.

[exilant]

Zum Pseudocode: Vielleicht bin ich da zu naiv, aber in den alten Zeiten in denen man noch selbst mit Indexen 'rumhantierte hätte meine Lösung wie folgt ausgesehen:


foreach status in menge
seek status in v2psindex
while v2psindex.staus = status;
seek v2ps.v2fertigartikel in v2fertigartikelindex
ergebnismenge.add ( v2ps.par, v2fertigartikel.artikelbezeichnung)
next in V2PsIndex;
end
end


Ergibt (Anzahl gesuchter Stati) Suchevorgänge im Index von v2ps, in meinem Fall genau zwei.
Dann noch (Anzahl gefundener passender stati ) Suchvorgänge im Index v2fertigartikel. In meinem Besispiel wären das 864.
Beide Tabellen verfügen über genau die Indexe die benötigt werden die Abfrage optimal auszuführen

Grüße,
Martin

[Dejan Vu]

Zitat von exilant:

Der vom Plan verwendete Index V2PS_IDX3 indexiert die Felder (V2FERTIGARTIKEL,V2FARBE), ist also völlig unbrauchbar im Kontext der Abfrage.

Wieso? V2FERTIGARTIKEL wird doch im JOIN verwendet.

[exilant]

Zitat von Dejan Vu:

Zitat von exilant:

Der vom Plan verwendete Index V2PS_IDX3 indexiert die Felder (V2FERTIGARTIKEL,V2FARBE), ist also völlig unbrauchbar im Kontext der Abfrage.

Wieso? V2FERTIGARTIKEL wird doch im JOIN verwendet.

v2ps_idx3 ist ein Index der Tabelle v2ps. Wozu ich ich im Kontext der Anfrage diesen Index benötigen sollte
beleibt unklar. Die Indexierten Felder V2FERIGARTIKEL und V2FARBE sind kein Kriterium für die erwartete Ergebnismenge aus v2ps. Hier bilden die Sätze mit den gesuchten Stati das gewünschte Ergebnis.