Sonntag, 28. Dezember 2014

Kombinierte Indexe richtig definieren

Ganz aktuell habe ich bei einem Kunden ein Problem in einer Abfrage entdeckt, die trotz “korrektem” Index nicht optimal ausgeführt wird. Das Problem war relativ schnell gefunden; die Reihenfolge der Attribute im Index waren nicht korrekt implementiert. Der Artikel beschreibt, wie wichtig bei der Erstellung von Indexen die Berücksichtigung von Abfragemustern ist.

Szenario

Der Kunde setzt ein Online-Bestellsystem ein, das neben einer Kundennummer ([Customer_Id]) das Datum der Bestellung ([OrderDate]) speichert. Für die nachfolgenden Beispiele wird eine einfache Tabellenstruktur mit 100.000 Datensätzen erstellt. Alle 100.000 Aufträge datieren aus dem Jahr 2014. Für die Erstellung der Testdaten habe ich den SQL Data Generator von Red Gate verwendet!

-- Erstellung der Demotabelle
CREATE TABLE dbo.Orders
(
    Id           INT     NOT NULL    IDENTITY (1, 1),
    OrderNo      CHAR(5) NOT NULL,
    Customer_Id  INT     NOT NULL,
    OrderDate    DATE    NOT NULL,
 
    CONSTRAINT pk_Orders_ID PRIMARY KEY CLUSTERED (Id)
);
GO
 
-- Zusammengesetzter Index nach Datum und Kunden-Id
CREATE INDEX ix_Orders_OrderDate ON dbo.Orders
(
    OrderDate,
    Customer_Id
);
GO

Abfrage(n)


Die Tabelle enthält 100.000 Datensätze. Von diesen 100.000 Datensätzen sind ca. 9.000 Datensätze aus dem Januar 2014. Die Abfrage sucht alle Aufträge, die im Januar 2014 getätigt wurden:



SELECT Id, Customer_Id, OrderDate
FROM   dbo.Orders
WHERE  OrderDate BETWEEN '20140101' AND '20140131';

Der zugehörige Ausführungsplan sieht ideal aus und zeigt, dass der zuvor erstellte Index [ix_Orders_OrderDate] verwendet wird um einen INDEX SEEK auf [OrderDate] auszuführen.


EXECUTION_PLAN_01 


Der Ausführungsplan zeigt 8.426 gefundene Datensätze. Das Ergebnis der Operation war vorhersehbar, da [OrderDate] im Index das primäre Indexattribut repräsentiert. In diesem Fall ist es unerheblich, dass [Customer_ID] als Prädikat nicht verwendet wurde.


Diese Abfrage wird vom Benutzer jedoch nicht nur zur Eingrenzung des Bestelldatums angewendet sondern ausschließlich in Verbindung mit einer gültigen Kundennummer ([Customer_Id]). Die Abfrage muss um die Eingrenzung nach der Kundennummer erweitert werden:



SELECT Id, Customer_Id, OrderDate
FROM   dbo.Orders
WHERE  OrderDate BETWEEN '20140101' AND '20140131' AND
       Customer_Id = CAST(5 AS INT);

Der Ausführungsplan der obigen Abfrage lässt erahnen, dass erneut ein INDEX SEEK verwendet wird. Schaut man jedoch auf die Eigenschaften des Abfrageoperators, kann man Anomalien erkennen, die darauf hinweisen, dass der INDEX SEEK nicht “ideal” verwendet wird.


EXECUTION_PLAN_02


Die Abbildung zeigt, dass für das Datum erneut ein SEEK verwendet werden konnte während jedoch die Suche nach der Kundennummer ([Customer_Id]) mit Hilfe eines Filters durchgeführt wird. In diesem Fall spricht man von einem Index Range Scan! Um die Filteroperation sichtbar zu machen, wird Traceflag 9130 als Option verwendet.



SELECT Id, Customer_Id, OrderDate
FROM   dbo.Orders
WHERE  OrderDate BETWEEN '20140101' AND '20140131' AND
       Customer_Id = CAST(5 AS INT)
OPTION (QUERYTRACEON 9130);

EXECUTION_PLAN_03


Wie der Ausführungsplan zeigt, müssen zunächst erneut 8.426 Datensätze aus dem Datumszeitraum gesucht werden. Diese Datenmenge wird evaluiert um sie anschließend mit Hilfe eines Filters auf die – in diesem Beispiel – verbliebenen 20 Datensätze zu reduzieren. Microsoft SQL Server muss also 8.426 Datensätze überprüfen, um alle Datensätze mit der Kundennummer 5 zu filtern! Microsoft SQL Server geht bei der Suche nach den Datensätzen wie folgt vor:



|--Index Seek(OBJECT:([demo_db].[dbo].[Orders].[ix_Orders_OrderDate]),
SEEK:
(
   ([demo_db].[dbo].[Orders].[OrderDate], [demo_db].[dbo].[Orders].[Customer_Id]) >= (CONVERT_IMPLICIT(date,[@1], 0), [@3]) AND
   ([demo_db].[dbo].[Orders].[OrderDate], [demo_db].[dbo].[Orders].[Customer_Id]) <= (CONVERT_IMPLICIT(date,[@2], 0), [@3])
),
WHERE:([demo_db].[dbo].[Orders].[Customer_Id]=[@3]) ORDERED FORWARD)

Es ist zu erkennen, dass für die Suche nach den Datumswerten ein – optimaler – INDEX SEEK verwendet wird. Jedoch muss für die Suche nach der Kundennummer eine WHERE-Klausel verwendet werden, die im Ausführungsplan als FILTER-Operator gekennzeichnet ist. Ursächlich für dieses Verhalten ist die Verwendung von >=, <=, BETWEEN.


Microsoft SQL Server kann für die Kombination [OrderDate] und [Customer_Id] nicht auf Statistiken zurück greifen. Microsoft SQL Server speichert im Histogramm ausschließlich die Werte des ersten Attributs eines Index.



DBCC SHOW_STATISTICS('dbo.Orders', 'ix_Orders_OrderDate') WITH HISTOGRAM;
DBCC SHOW_STATISTICS_HISTOGRAM_01

Dadurch bedingt werden zunächst alle Datumswerte aus der Datenmenge extrahiert die nachträglich auf der Kundennummer ([Customer_Id]) gefiltert werden.


Warum INDEX SEEK + FILTER?


Warum kann Microsoft SQL Server nicht idealer Weise bereits beim INDEX SEEK über [OrderDate] das Attribut [Customer_Id] berücksichtigen? Dieser Umstand ist der generellen Struktur eines Index geschuldet. Ein Index ist in einer B-TREE Struktur organisiert. Hierbei wird der Indexbaum immer von einem Root-Knoten bis zu einem Leaf-Knoten durchsucht, um die angeforderten Daten zu finden. Um die Indexstruktur abzubilden, wird die DMF [sys].[dm_db_database_page_allocation] verwendet:



-- Show the index structure of the index ix_Orders_OrderDate
SELECT  page_type_desc,
        page_level,
        allocated_page_page_id,
        previous_page_page_id,
        next_page_page_id
FROM    sys.dm_db_database_page_allocations
(
    DB_ID(),
    OBJECT_ID('dbo.Orders', 'U'),
    3,
    NULL,
    'DETAILED'
) AS DDDPA
WHERE   is_allocated = 1
ORDER BY
    page_type DESC,
    page_level DESC,
    previous_page_page_id ASC;

Die Abbildung zeigt, wie von der Root Page (11.208) abwärts die Leaf-Ebene für alle Daten des Januar 2014 durchsucht wird.


INDEX_RANGE_SCAN_01


Entscheidend für die Arbeit der Query Engine ist, dass der Index erst nach [OrderDate] und anschließend nach [Customer_Id] sortiert ist. Microsoft SQL Server kann nicht in einem Prozessschritt sowohl Datum als auch Kundennummer mit einem effektiven SEEK erkennen. Vielmehr müssen erst alle Bestellungen von Januar 2014 ermittelt werden und anschließend kann die Ergebnismenge nach der entsprechenden Kundennummer “gefiltert” werden!


Reihenfolge der Attribute in Index


Immer wieder wird empfohlen, einen Index nach der Kardinalität seiner Attribute zu erstellen; diese Aussage ist nur bedingt richtig – wie das obige Bespiel beeindruckend zeigt. Kardinalität allein kann nicht das Kriterium sein, nach dem ein Index erstellt wird; es gilt auch die Abfragen selbst zu analysieren. Wenn – wie im vorliegenden Beispiel – ein Index sehr häufig für Mengenoperationen verwendet wird, kann die gewählte Indexstrategie schnell zu einem Bumerang werden. Für das aktuelle Szenario wurde der Index wie folgt umgebaut:



CREATE INDEX ix_Orders_OrderDate ON dbo.Orders (Customer_Id, OrderDate) WITH DROP_EXISTING;

Wir die gleiche Abfrage erneut ausgeführt, reduziert sich das IO um über 90%, da der Index ix_Orders_OrderDate wesentlich effektiver verwendet werden kann:



SELECT Id, Customer_Id, OrderDate
FROM   dbo.Orders
WHERE  OrderDate BETWEEN '20140101' AND '20140131' AND
       Customer_Id = CAST(5 AS INT)
OPTION (QUERYTRACEON 9130);
EXECUTION_PLAN_04

Die Details des Ausführungsplans offenbaren, dass sowohl nach der Kundennummer als auch nach dem Auftragsdatum mit Hilfe eines INDEX SEEK gesucht werden kann. Die Ursache hierfür liegt in der – neuen – Struktur des Indexes.


INDEX_RANGE_SCAN_02


Die neue Struktur des Indexes wird durch die Kundennummer ([Customer_Id]) kontrolliert. Da der Index aus [Customer_Id] und [OrderDate] besteht, wird das zweite Attribut ([OrderDate]) ebenfalls im Index sortiert. Wird – wie in der Beispielabfrage – nach einem Kunden mit der Customer_Id = 5 gesucht, kann der Query Optimizer einen optimalen INDEX SEEK verwenden, da er lediglich einen Indexwert betrifft. Die gleiche Operation kann nun auch für das Auftragsdatum verwendet werden, da dieses Attribut im Index vorhanden und sortiert ist. Die Query Engine KANN beim INDEX SEEK das Datum während des Zugriffs prüfen. Ist die obere Grenze des zu filternden Auftragsdatums erreicht, kann die Query Engine die Arbeit beenden; es kann keine weiteren Aufträge mit einem Bestelldatum im Januar geben, die nach dem 31.01.2014 getätigt wurden!


Zusammenfassung


Die richte Zusammenstellung / Komposition eines Index hängt nicht immer von starren Regeln ab. Vielmehr muss immer wieder der eigentliche Workload im Fokus stehen. Wenn – wie das obige Beispiel recht deutlich zeigt – stur nach “Vorgabe” implementiert wird, ergeben sich daraus hervorragende Optimierungsmöglichkeiten, die für Überraschungen sorgen können.


Herzlichen Dank fürs Lesen!


PS: Dieses Problem wie auch viele andere werde ich auf der SQL Konferenz 2015 in Darmstadt demonstrieren, analysieren und mit Lösungswegen präsentieren. Die SQL Konferenz findet in 2015 das zweite Mal mit einer beeindruckenden Themen- und Sprechervielfalt rund um SQL Server statt nachdem bereits die Premiere in 2014 ein voller Erfolg war.


Seien es Fragen zu diesem Artikel oder aber auch generelle Fragen zur Indexierung oder zur Database Storage – bitte nicht zögern, mich einfach anzusprechen. Ich freue mich über jeden Gedankenaustausch!

Kommentare :

  1. hallo Uwe
    in der letzten Grafik sind die Spalten auf Page 11932 etwas durcheinander gekommen.

    AntwortenLöschen
  2. Aaargh - jetzt habe ich es (nach fast einer Minute) endlich auch gesehen.
    Vielen Dank für den Hinweis und das sorgfältige Lesen!
    Wird asap geändert!

    AntwortenLöschen