Immer wieder kommt es vor, dass trotz guter Indexierung ein Index nicht optimal genutzt werden kann, da die Suchmuster eine optimale Verwendung eines Index verhindern. Eher durch Zufall bin ich auf einen interessanten Artikel von Fabricio Lima gestoßen, der eine – wie ich finde – interessante Lösung präsentiert, um sogenannte “Wildcard-Suchen” zu optimieren. Hierbei macht er sich den Umstand zu Nutze, dass der CPU-Anteil bei Verwendung von SQL Sortierungen deutlich reduziert wird und somit Abfragen mit Wildcards schneller ausgeführt werden.

Inhaltsverzeichnis

Grundlagen der Sortierung

Eine Grundfunktion innerhalb von Datenbanken ist die Festlegung von Sortierungen für die Daten. Eine Sortierung gibt die Bitmuster an, die die jeweiligen Zeichen in einem Datensatz darstellen. Sortierungen legen außerdem die Regeln fest, nach denen Daten sortiert und verglichen werden. SQL Server unterstützt das Speichern von Daten mit unterschiedlichen Sortierungen in einer Datenbank. Bei Nicht-Unicode-Spalten gibt die Sortierungseinstellung die Codepage für die Daten und die Zeichen an, die dargestellt werden können. Bei der Auswahl von Sortierungen kann zwischen SQL-Sortierungen und Windows-Sortierungen ausgewählt werden. Bei der Verwendung einer WINDOWS-Sortierung werden Nicht-Unicode-Spalten mit dem gleichen Algorithmus verarbeitet, wie Unicode-Spalten. Bei der Verwendung von SQL-Sortierungen wird ein anderes Verfahren für Nicht-Unicode-Spalten verwendet. Basis für diese Vergleiche sind interne “Sortierungen”.

Testumgebung

Für die Durchführung der Tests wird eine Datenbank mit der WINDOWS-Sortierung [Latin1_General_CI_AS] erstellt. Diese Sortierung berücksichtigt keine Groß- und Kleinschreibung und kann für die Speicherung von Nicht-Unicodedaten (ASCII) und Unicodedaten verwendet werden.

Datenbank

-- Create the database with a unicode collation
CREATE DATABASE [demo_db]
ON PRIMARY
(
    NAME        = N'demo_db',
    FILENAME    = N'S:\MSSQL13.SQL_2016\MSSQL\DATA\demo_db.mdf',
    SIZE        = 500MB,
    FILEGROWTH  = 0MB
)
LOG ON
(
    NAME        = N'demo_log',
    FILENAME    = N'S:\MSSQL13.SQL_2016\MSSQL\DATA\demo_db.ldf',
    SIZE        = 500MB,
    FILEGROWTH  = 0MB
)
COLLATE Latin1_General_CI_AS;

Testtabelle

In der Datenbank wird eine Tabelle angelegt, die eine Spalte verwendet, in der ausschließlich Nicht-Unicodedaten gespeichert werden (VARCHAR, CHAR)

SELECT  message_id,
        language_id,
        severity,
        is_event_logged,
        CAST(text AS VARCHAR(2048)) A [text]
INTO    dbo.messages
FROM    sys.messages;

Die Tabelle enthält ungefähr 280.000 Datensätze (Microsoft SQL Server 2016). Das Attribut ist das einzige Textattribut.

Stored Procedure

Für die Ausführung der Abfragen – insbesondere für Lastvergleiche – wird eine Gespeicherte Prozedur verwendet, die ein Suchmuster als Parameter erwartet. Weiterhin wird durch eine Variable gesteuert, ob die Standardsortierung der Datenbank oder eine SQL-Sortierung verwendet werden soll.

CREATE PROC dbo.GetMessages
    @SearchString      VARCHAR(20),
    @use_sql_collation BIT = 0
AS
BEGIN
    SET NOCOUNT ON;
 
    IF @use_sql_collation = 0
        SELECT * FROM dbo.messages
        WHERE  text LIKE @SearchString;
    ELSE
        SELECT * FROM dbo.messages
        WHERE  text COLLATE SQL_Latin1_General_CP1_CI_AS LIKE @SearchString;
 
    SET NOCOUNT OFF;
END

Bei der Auswahl der geeigneten SQL-Sortierung wurde darauf geachtet, dass – um unterschiedliche Ergebnisse zu vermeiden – gleiche Einstellungen für Groß- und Kleinschreibung sowie die Berücksichtigung von Akzenten verwendet wurden!

Testszenario

Für eine möglichst präzise Auswertung der Laufzeiten wird vor der Ausführung der Prozedur mit unterschiedlichen Parameterwerten die Ausgabe der Ausführungszeiten aktiviert!

SET STATISTICS TIME ON;
GO

EXEC dbo.GetMessages @SearchString = '%error%', @use_sql_collation = 0;
GO
PRINT '===================================================================';
GO
EXEC dbo.GetMessages @SearchString = '%error%', @use_sql_collation = 1;
GO
 
SET STATISTICS TIME OFF;

Bei der ersten Ausführung wird die WINDOWS-Sortierung verwendet, die für die Datenbank als Standardsortierung definiert wurde (Latin1_General_CI_AS). Beim zweiten Aufruf wird die Verwendung der SQL-Sortierung (siehe Code in Prozedur) forciert. Der Unterschied in den Laufzeiten ist beeindruckend.

Für die Ausführung der Abfrage unter Verwendung der WINDOWS Sortierung benötigt Microsoft SQL Server (13.0.1772.0) auf einem Laptop mit 16 GB RAM und 4 Cores ca. 5 Mal länger als bei Verwendung einer SQL-Server-Sortierung. Die nachfolgende Abbildung zeigt die Ausführung der Prozedur mit 10 Clients unter Verwendung der WINDOWS-Sortierung und anschließender Ausführung mit der SQL-Server Sortierung.

Die mit Hilfe von PerfMon aufgezeichneten CPU-Auslastungen zeigen im Zeitraum der ersten 15 Sekunden (Blau) eine permanente Prozessorauslastung während der Ausführung der Prozedur unter Verwendung der WINDOWS-Sortierung. Die anschließend erneut von 10 Prozessen ausgeführte Prozedur unter Verwendung der SQL-Server Sortierung zeigt ebenfalls einen hohen – aber kurzen – Konsum von Prozessorzeiten. Dieses Verhalten spiegelt sich auch in der Ausführungszeit wider:

15,491 Sekunden für Ausführung von 10 Clients mit WINDOWS-Sortierung
2,570 Sekunden für Ausführung von 10 Clients mit SQL-Server-Sortierung

Grund für dieses Verhalten

Bei der Verwendung von WINDOWS-Sortierungen wird der Vergleich von Nicht-Unicode-Spalten mit den gleichen Algorithmen durchgeführt wie der Vergleich von Unicode-Spalten. Bei der Verwendung von SQL-Server Sortierungen wird eine andere Vergleichssemantik für Nicht-Unicode-Spalten verwendet, die auf einer einfacheren Sortierordnung basiert. Sortierregeln für Unicode-Spalten sind komplexer als Regeln für Nicht-Unicode-Spalten. Die Komplexität wird bereits durch den erweiterten Zeichensatz begründet. Nicht-Unicode-Spalten kennen nur den ASCII-Zeichensatz mit 255 unterschiedlichen Zeichen!

Zusammenfassend gilt:

Wenn Nicht-Unicode-Spalten in Microsoft SQL Server mit einer WINDOWS-Sortierung verwendet werden, unterliegen die Vergleichsregeln / Sortierungsregeln IMMER den Regeln für Unicodedaten
Wenn Nicht-Unicode-Spalten in Microsoft SQL Server mit einer SQL-Server Sortierung verwendet werden, unterliegen die Vergleichsregeln / Sortierungsregeln den – einfacheren – Regeln für Nicht-Unicode-Spalten

Der Unterschied wird spürbar bei rozessorgebundenen Operationen bedingt durch den Overhead bei den Vergleichsoperationen und/oder Textmanipulationen. Mehr Details zu diesem Thema finden sich in dem von Microsoft veröffentlichten Artikel “Comparing SQL Collations to WINDOWS Collations”.

Besonderheiten

Die Lösung hat ihren Charme – aber es gilt: “There is no lunch for free!”. Den Prozessorvorteil erkauft man sich möglicherweise mit höheren Speicherzuteilungen wenn explizit mit einer angegebenen Sortierung (COLLATE) gearbeitet wird. Die nachfolgenden Beispiele zeigen, wie sich die Abfragen in Bezug auf ihre Schätzungen und den damit verbundenen Speicherzuteilungen verhalten.

SELECT *
FROM   dbo.messages
WHERE  text LIKE '%error%'
ORDER BY
       text
OPTION
(
    QUERYTRACEON 2363,
    QUERYTRACEON 3604
);

Die Abfrage verwendet – um eine Speicherzuteilung zu erzwingen – eine ORDER BY-Klausel. Der Ausführungsplan für die Abfrage unter Verwendung der WINDOWS-Sortierung sieht wie folgt aus:

Microsoft SQL Server schätzt, dass ~4.000 Datensätze zurückgeliefert werden. Für die Sortierung wird ein Speicherbedarf für den Sort-Operator von 6,5 MB berechnet. Bei der Berechnung der zu erwartenden Datensätze kann Microsoft SQL Server nicht auf das Histogramm des Statistikobjekts selbst zugreifen. Wenn ein Statistikobjekt für eine Textspalte (char, varchar, nchar, nvarchar, varchar(max), nvarchar(max), text, oder ntext) erstellt wird, werden Statistiken über Zusammenfassungen von Zeichenfolgen (string summary statistics) erstellt, um die Kardinalitätsschätzungen für Abfrageprädikate, die den LIKE-Operator verwenden, zu verbessern. Zusammenfassungen von Zeichenfolgen werden getrennt vom Histogramm gespeichert! Ein Blick in die Ausgabe des “Estimation Process” zeigt, wie Microsoft SQL Server die geschätzte Anzahl von Datensätzen berechnet.

Die Kalkulation der geschätzten Zeilen basiert auf Statistiken über die Zusammenfassung von Zeichenfolgen. Microsoft SQL Server verwendet einen “Trie” für die Evaluierung der Daten. Ein Trie oder Präfixbaum ist eine Datenstruktur, die in der Informatik zum Suchen nach Zeichenketten verwendet wird. Die Selektivität ergibt sich aus den “string summary statistics”.

Anders jedoch sieht es jedoch aus, wenn explizit eine Sortierung für das Prädikat angegeben wird.

SELECT *
FROM   dbo.messages
WHERE  text COLLATE SQL_Latin1_General_CP1_CI_AS LIKE '%error%'
ORDER BY
    text COLLATE SQL_Latin1_General_CP1_CI_AS
OPTION
(
    QUERYTRACEON 2363,
    QUERYTRACEON 3604
);

Der zugehörige Ausführungsplan zeigt erhebliche Abweichungen vom vorherigen Beispiel.

Die Kalkulation der geschätzten Zeilen ergibt ein höheres Ergebnis. Dieses Ergebnis wirkt sich auf die Speicherzuteilung aus. Braucht die erste Abfrage lediglich 6,5 MB hat sich die Speicherzuteilung bei der Verwendung einer expliziten Sortierung um den Faktor 10 erhöht. Diese Erhöhung basiert auf den höheren Schätzungen für die Anzahl der zurückzuliefernden Datensätze. Auch hier hilft ein Blick auf den “Estimation Process”.

Konnte Microsoft SQL Server ohne die explizite Angabe einer Sortierung noch auf “string summary statistics” zugreifen, ist das mit der Verwendung einer expliziten Sortierung nicht mehr möglich. Die Sortierung sorgt dafür, dass sich die Schätzung ähnlich einer “non-sargable” Abfrage verhält. Für die Suche der betreffenden Datenzeilen müssen zunächst die Werte in der Textspalte in die angegebenen Sortierung konvertiert werden, bevor sie ausgewertet werden können.
In diesem Fall kann Microsoft SQL Server kein Histogramm (und somit auch keine string summary statistics) verwenden sondern wendet einen festen Filterwert (CSelCalcFixedFilter) für die Berechnung der auszugebenden Datensätze. Aus diesem Faktor ergibt sich die Anzahl der zu liefernden Datensätze: 278.696 * 0,09 = 25.082,6. Der “Vorteil” des geringeren CPU-Verbrauchs geht mit einem – möglichen – höheren Konsum des Speichers einher.

Herzlichen Dank fürs Lesen!

Optimierung von LIKE-Suche