Alle aktuellen Web Suchmaschinen haben nur ein Eingabefeld für die Suchkriterien und liefern immer ein Ergebnis, egal was man eingibt.
Das macht uns Entwicklern nun das Leben schwer, denn mittlerweile erwarten die Endanwender dieses auch in Line-of-Business (LOB) Anwendungen, z.B. bei der Suche nach einer Adresse oder eines Artikels. Wie man eine vergleichbare Funktion mit dem MS SQL Servers implementieren kann soll dieser Artikel zeigen.

Table of Contents


Einführung

Die Build-In Funktion Volltextindex des Microsoft SQL Server bietet eine einfache Möglichkeit, ganze Worte des Datenbestandes zu indizieren, sowie dieses flexibel und performant abzufragen. Es gibt nur ein paar Einschränkungen, die dazu führen, dass es nicht ganz für eine Websuche ähnliche Funktionalität geeignet ist.
  • keine Suffixsuche möglich wie *Teilbegriff
  • keine Schreibfehlertoleranz bezüglich Suchbegriff und/oder Daten
  • nur bedingte Indizierung von Satztrennzeichen und anderen Noise Words
    Eine Alternative ist es, eine eigene Indizierung zu implementieren und zwar in diesem Fall den sogenannten N-Gram-Index.
    Bei einem N-Gram Index werden immer alle N aufeinander folgende Buchstaben als Einheit (Fragment) gewertet und diese indiziert, wobei N ein beliebiger numerischer Wert von 1-x sein kann.
    Ein Beispiel mit "Hello World" und einem 3-Gram ergibt die Einheiten
    "HEL", "ELL", "LLO", "LO ", "O W", " WO", "WOR", "ORL", "RLD"

    Normalisierung

    Ziel ist es eine fehlertolerante und Akzent-Insensitive Suche von Adressen zu implementieren, dafür muss man die Datenbasis für den N-Gram Index entsprechend normalisiert bereitstellen. Das setzt ein paar Überlegungen vorab voraus.

    Umlaute

    Deutsche Umlaute wie Ü kann man durch UE ersetzen, so finden man mit dem Suchbegriff "Müller" auch den Namen "Mueller".
    In anderen Sprachen gibt es Sonderzeichen, die dem lateinischen Alphabet entstammen und Kennzeichen für die Betonung enthalten, wie das polnische Ł. Solche Zeichen kann man auch ersetzen.

    Satztrennzeichen

    Beim Volltextindex werden Satztrennzeichen als Wortende gewertet und nicht mit indiziert. Es gibt aber durchaus Firmen- und Produktnamen, die ein Satztrennzeichen beinhalten und somit sollten dies e in einem gewissen Rahmen mit suchbar sein. Hier muss man nach Datenbestand entscheiden, ob die Satztrennzeichen beibehalten oder ersetzt werden sollen.
    In diesem Beispiel werden zur Vereinfachung alle Satztrennzeichen durch ein einziges Zeichen ersetzt. So bleibt der Textaufbau erhalten, aber es wird zur Indizierung und Suche nur ein Zeichen verwendet.

    Sonderzeichen

    Auch hier muss man nach Datenbestand entscheiden, ob man Sonderzeichen ersetzt oder nicht. Gutes Beispiel ist das @ Zeichen bei E-Mail Adressen; möchte man gezielt nur nach der E-Mail Adresse suchen können oder soll nach den Teilen der E-Mail Adresse auch in anderen Datenbereich gesucht werden.

    Damit sind in diesem Beispiel nur
  • Ziffern
  • Lateinische Großbuchstaben
  • Ausrufezeichen ! als allgemeiner Ersatz für alle Satztrennzeichen
  • Doppelkreuz # als allgemeiner Ersatz für alle anderen Sonderzeichen als Zeichen für den normalisierten Text zugelassen.
    Um die Liste der zulässigen Zeichen zentral pflegen zu können, wird eine Funktion angelegt, die diese zurück liefert; globale Variablen gibt es im MS SQL Server nicht.
    CREATE FUNCTION dbo.fnGetNGramValidChars()
        RETURNS nvarchar(39)
    AS
    BEGIN
        -- Approved Signs for N-Gram Index
        -- Western capital letters + Space
        -- Digits
        -- Delimiter sign: !
        -- Special character sign: #
        RETURN N'ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789!#';
     
    END;

    Alle anderen Zeichen werden entsprechend ersetzt. Dazu wird eine weitere Funktion erstellt, die den übergebenen Text entsprechend normalisiert, sie wird später sowohl für die Indizierung der Daten als auch für die Normalisierung des Suchbegriffes genutzt.
    Hier die gekürzte Version:
    CREATE FUNCTION dbo.fnNormalizeDatastring
        (@string nvarchar(max))
        RETURNS nvarchar(max)
    AS
    BEGIN
        -- Get all valid characters
        DECLARE @validChars nvarchar(50) = (SELECT dbo.dbo.fnGetNGramValidChars() AS Result);
        -- Only capital characters
        SET @string = UPPER(@string);
        -- Replace umlauts
        SET @string = REPLACE(@string, N'Ä', N'AE');
        SET @string = REPLACE(@string, N'Æ', N'AE');
        -- usw. ...
     
        -- Registered Marks
        SET @string = REPLACE(@string, N'℅', N'C#O');
        SET @string = REPLACE(@string, N'™', N'TM');
        -- usw. ...
     
        -- Replace delimiter by !
        SET @string = REPLACE(@string, N'.', N'!');
        SET @string = REPLACE(@string, N',', N'!');
        -- usw. ...
     
        -- Replace special characeters by hash mark.
        SET @string = REPLACE(@string, N'+', N'#');
        SET @string = REPLACE(@string, N'-', N'#');
        -- usw. ...
     
        -- Replace all other invalid characters by space.
        DECLARE @loop int = 1;
        DECLARE @len int = LEN(@string);
        DECLARE @invalidChar nchar(1);
     
        WHILE @loop <= @len
        BEGIN
            SET @invalidChar = SUBSTRING(@string, @loop, 1);
            IF CHARINDEX(@invalidChar, @validChars) <= 0
            BEGIN
                SET @string = REPLACE(@string, @invalidChar, N' ');
            END;
     
            SET @loop = @loop + 1;
        END;
     
        -- Remove multiple spaces
        DECLARE @goOn tinyint = 1;
        DECLARE @oldLen int;
     
        WHILE @goOn <> 0
        BEGIN
            SET @oldLen = LEN(@string);
            SET @string = REPLACE(@string, N'    ', N' ');
            SET @string = REPLACE(@string, N'  ', N' ');
     
            IF @oldLen = LEN(@string)
            BEGIN
                SET @goOn = 0;
            END;
        END;
     
        RETURN @string;
    END;

    Anmerkung: Solche aufwendigen String Operationen sind im SQL Server sehr teuer. Denkbar wäre zur Optimierung eine Implementierung als CLR Assembly.

    Indexerstellung

    Der Index kann einfach über die Anzahl der erlaubten Zeichen, die Position des Zeichens und dem N-Gram Wert errechnet.

    Für das Fragment "BDHZ" errechnet sich der Index-Wert beispielhaft so über (Position ist 0-based)
    B = Position 1 * (39^0) = 1
    D = Position 4 * (39^1) = 156
    H = Position 7 * (39^2) = 10.647
    Z = Position 25 * (39^3) = 1.482.975
    Summe = 1.493.779 abzgl. Integer Untergrenze -2.147.483.648 => Indexwert -2.145.989.869

    Nehmen wir als Beispiel eine 4-Gram Index mit den oben definierten 39 Zeichen, da können 39^4 = 2.313.441 Zeichenkombinationen (Fragmente) entstehen.
    Lassen wir auch negative Werte zu, reicht der Wertebereich des int Datentypen bis zum 6-Gram Index bequem aus.

    Die Anzahl möglicher Indexwerte je N-Gram:
    2-Gram = 39^2 = 1.521 => smallint
    3-Gram = 39^3 = 59.319 => smallint
    4-Gram = 39^4 = 2.313.441 => int
    5-Gram = 39^5 = 90.224.199 => int
    6-Gram = 39^6 = 3.518.743.761 => int
    7-Gram = 39^7 = 137.231.006.679 => bigint

    Die Berechnungsfunktion in T-SQL sieht wie folgt aus, wobei davon ausgegangen wird, dass das Fragment normalisiert übergeben wird.
    CREATE FUNCTION dbo.fnCalculate4GramIndex
        (@fragment nchar(4))
        RETURNS int
    AS
    BEGIN
        -- Get all valid characters
        DECLARE @validChars varchar(50) = (SELECT dbo.fnGetNGramValidChars() AS Result);
        DECLARE @size int = (SELECT LEN(@validChars) AS size);
     
        DECLARE @id int = -2147483648;
        -- Calculate position of each char
        DECLARE @pos1 int = CHARINDEX(SUBSTRING(@fragment, 1, 1), @validChars);
        DECLARE @pos2 int = CHARINDEX(SUBSTRING(@fragment, 2, 1), @validChars);
        DECLARE @pos3 int = CHARINDEX(SUBSTRING(@fragment, 3, 1), @validChars);
        DECLARE @pos4 int = CHARINDEX(SUBSTRING(@fragment, 4, 1), @validChars);
     
        SET @id = @id + (@pos1 - 1) +
                        (@pos2 - 1) * @size +
                        (@pos3 - 1) * POWER(@size, 2) +
                        (@pos4 - 1) * POWER(@size, 3);
     
        RETURN @id;
    END;
    Um nun alle Index-Werte für einen ganzen Text zu erzeugen, wird eine Table Valued Function (TVF) angelegt, die den Text in die Fragmente zerlegt, die Werte errechnet und das Ergebnis als eine Tabelle zurück liefert.
    CREATE FUNCTION dbo.fnBuildIndex4Gram
        (@string nvarchar(max))
        RETURNS @ids TABLE (id int)
    AS
    BEGIN
        SET @string = (SELECT dbo.fnNormalizeDatastring(@string));
        DECLARE @pos int = 1;
        DECLARE @len int = LEN(@string) - 4;
     
        IF @len <= 0
            RETURN;
     
        WHILE @pos <= @len
        BEGIN
            INSERT INTO @ids (id)
            SELECT dbo.fnCalculate4GramIndex(SUBSTRING(@string, @pos, 4));
     
            SET @pos = @pos + 1;
        END
     
        RETURN;
    END;
     
    -- Small test:
    SELECT *
    FROM dbo.fnBuildIndex4Gram(N'Hello World') AS IDX;

    Funktioniert soweit.

    Als Beispiel für die Indizierung dienen die Adress-Daten im Schema "Person" aus der Datenbank AdventureWorks.
    Um alle relevanten Daten in einem Feld zu erhalten, inkl. der 0-n Telefonnummern, wird eine View angelegt, die die Daten bereitstellt. Diese View hat zudem den Vorteil, dass man die Daten jederzeit erweitern kann, ohne weitere Logiken und Prozessschritte anpassen zu müssen.
    CREATE VIEW Person.vAddressIndexData
    AS
        SELECT ADR.AddressID,
               ADR.AddressLine1 + N' ' +
               ISNULL(ADR.AddressLine2 + N' ', N'') +
               ADR.City + N' ' +
               ADR.PostalCode +  N' ' +
               SPR.StateProvinceCode + N' ' +
               SPR.Name + N' ' +
               CR.Name + N' ' +
               ISNULL(PER.Title + N' ', N'') +
               ISNULL(PER.FirstName + N' ', N'') +
               ISNULL(PER.MiddleName + N' ', N'') +
               ISNULL(PER.LastName + N' ', N'') +
               ISNULL(PER.Suffix + N' ', N'') +
               ISNULL(EA.EmailAddress + N' ', N'') +
               ISNULL((SELECT CAST((SELECT (SELECT PHO.PhoneNumber + ','
                                     FROM Person.PersonPhone AS PHO
                                     WHERE PHO.BusinessEntityID = PER.BusinessEntityID
                                     FOR XML PATH (''), Type
                                   ) AS ColCSV
                                  ) AS nvarchar(MAX))) + N' ', N'')
               AS IndexData
        FROM Person.Address AS ADR
             INNER JOIN
             Person.StateProvince AS SPR
                 ON ADR.StateProvinceID = SPR.StateProvinceID
             INNER JOIN
             Person.CountryRegion AS CR
                 ON SPR.CountryRegionCode = CR.CountryRegionCode
             LEFT JOIN
             Person.BusinessEntityAddress AS BEA
                 ON ADR.AddressID = BEA.AddressID
             LEFT JOIN
             Person.Person AS PER
                 ON BEA.BusinessEntityID = PER.BusinessEntityID
             LEFT JOIN
             Person.EmailAddress AS EA
                 ON PER.BusinessEntityID = EA.BusinessEntityID
                    AND PER.EmailPromotion = EA.EmailAddressID;
    Anmerkung: Die View ist nur als Beispiel gedacht, auf Sinn und Korrektheit wurde hier nicht sonderlich geachtet.

    Als nächstes brauchen wir zum Speichern der Indexwerte eine Tabelle. Benötigt wird der Primary Key des Datensatzes, hier die AddressId, und der N-Gram Indexwert. Da ein Fragment/Indexwert je Datensatz mehrfach vorkommen kann, ist ein Feld für die Häufigkeit vorgesehen statt jeden Indexwert einzeln zu speichern; was natürlich auch ging.
    CREATE TABLE dbo.Gram4Index(
        AddressId int NOT NULL,
        ID_4Gram int NOT NULL,
        Occurrence smallint NOT NULL,
        CONSTRAINT PK_Gram4Index PRIMARY KEY CLUSTERED
        (
            AddressId ASC,
            ID_4Gram ASC
        )
    );

    Anmerkung: Die Vermischung von verschiedenen Schemas wie hier ist normalerweise nicht sinnvoll.
    Bei der späteren Suchfunktion wird direkt nur der Indexwert benötigt, dazu ist der Primary Key nicht so geeignet, deswegen wird ein weiterer Index angelegt, der selektiver ist. Um unnötige Key Lookups auf die AddressId und Occurrence in der Basis Tabelle zu vermeiden, werden die Felder als Include mit aufgenommen.
    CREATE NONCLUSTERED INDEX IDX_Gram4Index_Search
        ON dbo.Gram4Index
           (ID_4Gram)
        INCLUDE (AddressId, Occurrence);
     
    -- Some additional statistics.
     
    CREATE STATISTICS [STAT_Gram4Index_AddressId]
        ON [dbo].[Gram4Index]
           ([AddressId]);
     
    CREATE STATISTICS [STAT_Gram4Index_Occurrence]
        ON [dbo].[Gram4Index]
           ([Occurrence]);
     
    CREATE STATISTICS [STAT_Gram4Index_AddressId_Occurrence]
        ON [dbo].[Gram4Index]
           (AddressId, [Occurrence]);

    Wie es sich gehört sollte das Füllen der Index-Wert zentral über ein Stored Procedure erfolgen, die dann aus anderen SP's oder Triggern heraus aufgerufen werden kann.
    Die folgende SP erfüllt diesen Zweck, sie löscht zunächst die alte Index-Werte und fügt die Neuen in die Index Tabelle ein; erwartet wird nur der PK AddressId als Parameter.
    CREATE PROCEDURE dbo.spUpdate4Gram
        @addressId int
    AS
    BEGIN
        SET NOCOUNT ON;
     
        -- Delete old index data
        DELETE FROM dbo.Gram4Index
        WHERE AddressId  = @addressId;
     
        -- Re-create Index for the Address.
        INSERT INTO dbo.Gram4Index
           (AddressId, ID_4Gram, Occurrence)
        SELECT ADR.AddressId, NG.ID AS ID_NGram4, COUNT(*) AS Occurrence
        FROM Person.vAddressIndexData AS ADR
             CROSS APPLY
             dbo.fnBuildIndex4Gram(ADR.IndexData) AS NG
        WHERE ADR.AddressId = @addressId
        GROUP BY ADR.AddressId, NG.ID;
    END;

    Da wir mit der AdventureWorks eine bestehende Datenbank mit vorhandenen Daten haben, brauchen wir zusätzlich noch eine Routine, die Initial die vorhandenen Daten indiziert. Dazu arbeitet man per Cursor alle vorhandenen Adressen ab.
    SET NOCOUNT ON;
    DECLARE @addressId int;
    DECLARE addresses CURSOR LOCAL FOR
        SELECT AddressId
        FROM Person.Address;
     
    OPEN addresses;
     
    FETCH NEXT FROM addresses INTO @addressId;
    WHILE (@@FETCH_STATUS = 0)
    BEGIN
        EXEC dbo.spUpdate4Gram @addressId;
        FETCH NEXT FROM addresses INTO @addressId;
    END;
     
    CLOSE addresses;
    DEALLOCATE addresses;
     
    PRINT N'Finished';

    Speicherbedarf für den Index

    Jeder Index benötigt zusätzlichen Speicherplatz, das ist bei diesem N-Gram Index natürlich nicht anders.
    Bei einem N-Gram Index wird für einen Text der Länge x dann (x - n) Fragmente gebildet. Je Fragment wird
  • AddressId = int = 4 Byte
  • ID_4Gram = int = 4 Byte
  • Occurrence = smallint = 2 Byte
  • Primary Key = 8 Byte
  • Suchindex = 10 Byte gespeichert, in der Summe alo 28 Bytes je Fragment. Hat ein Text 1.000 Zeichen, kommen bei einem 4-Gram Index also 996 * 28 Bytes = 27.888 Bytes zustande. Im Vergleich benötigt ein einfacher Index auf ein NVarChar Feld 2 Bytes je Zeichen, hier als 2.000 Bytes. Der N-Gram Index ist also ~14-mal so groß und somit vom Speicherplatz her sehr teuer.
    In diesem konkreten Fall werden 30,4 MB für die Daten und 21 MB für die Indizes benötigt, Gesamt also 51,4 MB.

    Anmerkung: Die Größenberechnung ist stark vereinfacht, die genauere Berechnung kann man in der MSDN nachlesen: Schätzen der Größe einer Tabelle

    Suchlogik

    Geeignete Suchtreffer sind nun die Adressen, die möglichst viele der gleichen Indexwerte aufweisen wie im Suchstring. Je weniger Indexwerte übereinstimmen, desto weniger stimmt die Adresse mit dem Suchtext überein.
    Im Gegensatz zu einem normalen Index ist die Reihenfolge einzelner Begriff im Suchtext wie auch in den Daten nahezu unerheblich.
    Andererseits können natürlich Fragmente aus dem Suchtext auch in völlig anderen Kombinationen in den Daten vorkommen.
    Für die Suche wird zunächst der gesamte Suchtext mittels der Funktion dbo.fnBuildIndex4Gram wie zuvor in die einzelnen Indexwerte zerlegt, diese mit den gespeicherten Indexwerten gejoint und nun die Übereinstimmungen gezählt, genauer gesagt wird die Summe über "Occurrence" gebildet und so häufige im Text vorkommende, übereinstimmende Indexwerte stärker gewichtet.
    Über den Parameter @factor kann gesteuert werden, wieviele Indexwerte prozentual übereinstimmen müssen, um als Suchergebnis zu gelten. Der Parameter kann Werte zwischen 0.0 und 1.0 haben, je größer der Wert, desto genauer ist das Suchergebis. Verringert man den Faktor, werden auch ungenaue Ergebnisse zurück geliefert, z.B. auch welche mit Schreibfehler.
    CREATE PROCEDURE dbo.spSearch4Gram
        (@search nvarchar(4000),
         @factor decimal(9, 4)
        )
    AS
    BEGIN
        SET NOCOUNT ON;
        DECLARE @len int;
     
        -- Normalize search string.
        SET @search = (SELECT dbo.fnNormalizeDatastring(@search));
        SET @len = (LEN(@search) - 4) * @factor;
        IF @len <= 0
            SET @len = 1;
     
        -- Weighted 4-Gram index search
        ;WITH idx AS
            (SELECT GR4.AddressId, SUM(GR4.Occurrence) AS Weigth
             FROM dbo.fnBuildIndex4Gram(@search) AS BIG
                  INNER JOIN
                  dbo.Gram4Index AS GR4
                      ON GR4.ID_4Gram = BIG.id
             GROUP BY GR4.AddressId
             HAVING SUM(GR4.Occurrence) > @len
            )
        SELECT ADR.AddressID,
               ADR.AddressLine1,
               ADR.City,
               ADR.City,
               idx.Weigth
        FROM Person.Address AS ADR WITH (NOLOCK)
             INNER JOIN
             idx
                 ON ADR.AddressID = idx.AddressId
        ORDER BY idx.weigth DESC;
    END;
     
    -- Test cases
     
    -- Umlaut search => "Buergermeister" as result
    EXEC dbo.spSearch4Gram N'Saarland Bürgermeister', 0.8;
    -- and counter wise
    EXEC dbo.spSearch4Gram N'rotthaeuser germany saarbruecken', 0.8;
     
    -- City name and telephon number without area code.
    EXEC dbo.spSearch4Gram N'Springfield -555-0181', 0.7;
     
    -- Typeo: "Bery" instead "Berry"
    EXEC dbo.spSearch4Gram N'Bery court', 0.6;
     
    -- Some part terms
    EXEC dbo.spSearch4Gram N'West gloria California 91791', 0.75;
     
    -- Long search text
    EXEC dbo.spSearch4Gram N'5157 Washington 98027 lane marywood Issaquah', 0.8;
     
    -- Large result set
    EXEC dbo.spSearch4Gram N'Washington', 0.8;

    Zusammenfassung

    Der N-Gram Index ist leicht mit Standard Transact-SQL zu implementieren und kann einfach an Besonderheiten des jeweiligen Datenbestandes und der gewünschten Suchlogik angepasst werden.
    Die Suchfunktion ist sehr performant und die Genauigkeit oder Toleranz gegenüber Schreibfehlern kann über einen Parameter individuell gesteuert werden sowie über die Wahl des N Wertes.
    Diese Vorteile erkauft man sich dafür mit einem hohen Speicherbedarf für die Indexwerte.

    Wie bei jeder Lösung kann man auch bei dieser noch Optimierungspotential finden, z.B. die Verwendung eines Column Store Indexes, was aber dann den Einsatz auf die Enterprise Edition einschränkt.

    Andere Sprachen

    SQL Server: Implementation of N-Gram Search Index

    Weblinks

    https://de.wikipedia.org/wiki/N-Gramm
    https://en.wikipedia.org/wiki/N-gram