Większość projektów, w których brałem udział posiadało funkcjonalność wyszukiwania tekstowego. We wszystkich z nich było to zrealizowane klauzulą `LIKE` w SQL. Często ten element aplikacji stawał się wąskim gardłem i redukował responsywność aplikacji. Kiedy serwery dalej płoną, opiszę tutaj po pokrótce kilka alternatyw dla tego rozwiązania.

Oczywiście `LIKE` nie zawsze musi być niewydajny. Kiedy to rozwiązanie może sprawiać problemy? 

Oczywiście przy skanie i analizie całej tabeli/indexu z kolumną tekstową oraz dlatego, że LIKE porównuje input znak po znaku z wartościami w kolumnie, co przy długich tekstach będzie czasochłonne. Jeśli nasza kolumna może posiadać index nieklastrowany, czyli nie jest typu np. `VARCHAR(MAX)` to niektóre rodzaje zapytań nie będą generować skanu. Na przykład:

1. `LIKE ‘something%’` wygeneruje seek przy istniejącym indeksie
2. `LIKE ‘so%thing’` wygeneruje seek przy istniejącym indeksie
3. `LIKE ‘%something’` wygeneruje skan zawsze
4. `LIKE ‘%something%’` wygeneruje skan zawsze

Opcja pierwsza będzie opcją najwydajniejszą, natomiast czwarta najbardziej zasobożerną. Opcję trzecią możemy zamienić na opcję pierwszą za pomocą `COMPUTED COLUMN` i klauzuli `REVERSE`. Mogłoby to wyglądać tak:

ALTER TABLE myTable ADD mycolumn_reversed AS REVERSE(mycolumn)
-- Dodajemy computed kolumn którą będzie wygenerowana 
-- na podstawie naszej kolumny my column

CREATE NONCLUSTERED INDEX IX_REVERSED ON myTable (mycolumn_reversed ASC) 
INCLUDE (mycolumn)
-- Dodajemy indeks na nowej kolumnie który zawiera także mycolumn

Następnie odpytując naszą odwróconą kolumnę musimy także odwrócić nasz input:

SELECT mycolumn FROM mytable WHERE mycolumn_reversed LIKE 'gnihtemos%'
 -- odwrócony something

Co do opcji czwartej – tutaj musimy pójść na jakiś kompromis. Jak zwykle, idealne rozwiązania nie istnieją. Przede wszystkim to zależy od przypadku użycia.

Przypadek 1.

Jeśli w naszej kolumnie jest dłuższy tekst typu opis produktu lub jakiś kawałek html’a, to czy naprawdę użytkownik dostanie jakąś wartość biznesową, gdy w opisie produktu będzie mógł wyszukać np. trzy znaki w środku tego opisu? Czy ktoś, kto nie chce spalić nam serwera będzie szukał w opisie produktu takich niekompletnych wyrazów?

`WHERE DESCRIPTION LIKE %mth%`

Rozwiązaniem może być zdecydowanie się na szukanie w naszym indeksie tylko (prawie) pełnych wyrazów i zdań. Pomóc w tym może wyszukiwanie pełnotekstowe – `FULL TEXT SEARCH`.

Przypadek 2.

Z drugiej strony, gdy posiadamy np. kolumnę z numerem części samochodowej, który wygląda np. tak: `JM1GJ1U59F1220909`. Doświadczeni warsztatowcy chcą wyszukiwać po fragmentach numeru części. Jeśli tych części będzie odpowiednio dużo, może to doprowadzić do problemów.  Problem ten może zostać rozwiązany dzięki podzieleniu naszego tekstu na tzw. n-gramy. W skrócie n-gramy są częściami wyrazu o określonej długości. Generowanie ich można sobie wyobrazić poprzez przechodzenie okienka o określonej długości przesuwającym się po naszym wyrazie. Dla frazy “Programista VisualBasic” 4-literowe n-gramy (four-grams) mogłyby wyglądać tak:

[prog,rogr,ogra,gram,rami,amis,mist,ista,visu,isua,sual,ualb,alba,lbas,basi,asic]

Spacja została tutaj pominięta, ale równie dobrze mogłaby być zawarta. Powyższe four-gramy będą przechowywane w sposób następujący:

ngram	rowId
prog	1
rogr	1
ogra	1

…

rowId to identyfikator wiersza w naszej pierwotnej tabeli. Teraz nasz częściowy tekst, po którym chcemy wyszukiwać np. %visual% zostanie także podzielony na four-gramy. Będzie się to prezentować następująco:

[visu,isua,sual]

Następnie przeszukujemy naszą kolumnę z n-gramami powyższymi n-gramami wygenerowanymi z częściowego tekstu. Wiersze, które zawierają wszystkie n-gramy będą ocenione za najbardziej spełniające wyszukiwanie. To rozwiązanie zwiększy ilość przechowywanych danych, ale wyszukiwanie po nich będzie dużo bardziej wydajne głównie dlatego, że na takiej kolumnie możemy założyć indeks oraz będziemy szukać dokładnej frazy (n-gramu), a nie częściowej z wildcardem %. Niestety, w SQL’u musimy także pamiętać o dobraniu n-gramów tak, aby posiadały one w miarę unikalne wartości, inaczej to też może prowadzić do problemów wydajnościowych (aby indeks był jak najbardziej selektywny). SQL Server nie posiada wbudowanego mechanizmu n-gramów, a jego własna implementacja nie jest trywialna. Przykład znajduje się np. tutaj. Zajmijmy się teraz wyszukiwaniem pełnotekstowym.

 

SQL SERVER FULL TEXT SEARCH

Jeśli myślimy o indeksach w relacyjnej bazie danych to przychodzą nam do głowy głównie dwa rodzaje: klastrowany i nieklastrowany. W związku z tym, że tych indeksów nie możemy założyć na kolumnie VARCHAR(MAX) na przeciw przychodzi nam indeks typu full text. W procesie indeksowania tekst dzielony jest na tzw. tokeny. Dla przykładu zdanie “What is domain driven design?” w indeksie może być przechowywane tak:

Keyword	ColId	DocId	Occurrence
domain	1	1	1
driven	1	1	1
design	1	1	1

…

Taki podział może być skonfigurowany w zależności od języka. Dla przykładu – może nie zawierać tak zwanych noise/stop words, czyli słów które w wyszukiwaniu pełnotekstowym mogą być bezużyteczne, tj. “what”, “a”, “and”, “is” w języku angielskim oraz znaków specjalnych takich jak kropki, przecinki, myślniki itp. Powyższa tabela przedstawia strukturę nazywaną odwróconym indeksem (inverted index). Jak skonfigurować i używać tego indeksu napisano już dobrze tutaj i tutaj. W skrócie FULL TEXT SEARCH udostępnia nam dwa predykaty tj. CONTAINS i FREETEXT oraz dwie funkcje tj.CONTAINSTABLE i FREETEXTABLE. Funkcje od predykatów różnią się tym, że predykaty zwracają wartość bool true/false, natomiast funkcje zwracają dwie kolumny KEY i RANK.  KEY to klucz identyfikujący wiersz w kolumnie z indeksem, natomiast RANK to liczba reprezentująca dopasowanie wyszukiwania do danego wiersza. Im wartość jest wyższa, tym dopasowanie jest lepsze. CONTAINS / CONTAINSTABLE służy do bardziej dokładnego wyszukiwania wyrazów, natomiast FREETEXT /FREETEXTABLEszuka bardziej znaczenia i synonimów i nie jest już tak dokładny.

Przykładowo wyszukiwanie słowa “VisualBasic” może wyglądać tak:

SELECT Title FROM [Stackoverflow3].[dbo].[Posts]
WHERE CONTAINS(Title,'VisualBasic')

Możemy także wyszukiwać zdań w naszej tabeli:

 SELECT ID,FULLTXT.[RANK] AS [RANK],Title, Body FROM [Stackoverflow3].[dbo].[Posts] 
 INNER JOIN
            (SELECT [KEY],[RANK]
             FROM CONTAINSTABLE([Stackoverflow3].[dbo].[Posts],[Title],'"What is domain driven design?"',10)) as FULLTXT 
	     ON ID = FULLTXT.[KEY]

To zapytanie zwróci 10 najlepiej dopasowanych tematów na StackOverflow:

Powyższa tabela posiada ponad 40 mln wierszy pełnych tekstu. Powyższe zapytanie wykonywało się 43 ms na moim laptopie.

Przed wyszukiwaniem SQL Server zamieni nasze zdanie “What is domain driven design?” na tokeny/słowa. W jaki sposób zostanie to zrobione możemy sprawdzić poprzez systemową funkcje `SYS.DM_FTS_PARSER`.

SELECT display_term, special_term FROM SYS.DM_FTS_PARSER('"What is domain driven design?"', 1033, 0, 0)
--1033 to id języka angielskiego

 

 

FULL TEXT INDEX umożliwia wyszukiwanie z użyciem znaku wildcard

 FROM CONTAINSTABLE([Stackoverflow3].[dbo].[Posts],[Title],'"drive*"',10))

Niestety znak wildcard możemy umieścić tylko na końcu wyrazu/frazy. Jeśli chcemy umieścić go z przodu, możemy zastosować sztuczkę, którą opisałem wcześniej.

Wyszukiwanie pełnotekstowe w SQL Serverze posiada jeszcze wiele innych funkcjonalności, tj. synonimy, oznaczanie słów jako ważniejsze w danym wyszukiwaniu, operatory logiczne oraz wyszukiwanie fleksyjne. Co ciekawe, wyszukiwanie fleksyjne wspiera język polski. Możemy do tego użyć CONTAINS, jak i FREETEXT

... WHERE CONTAINS(txt,'FORMSOF(INFLECTIONAL, "programista)')
-- FREETEXT wyszukuje fleksyjnie domyślnie
... WHERE FREETEXT(txt,'programista')

 

Powyższe predykaty przefiltrują wiersze zawierające fleksyjne formy wyrazu “programista”. Możemy sprawdzić, jakie słowa wygeneruje to wyszukiwanie:

SELECT display_term FROM SYS.DM_FTS_PARSER('FORMSOF(INFLECTIONAL, programista)', 1045, 0, 0)
-- 1045 id języka polskiego

 

 

 

Jak widać, FULL TEXT INDEX ma sporo zalet i może pomóc rozwiązać niektóre nasze problemy, ale posiada też wady. Na przykład wyszukiwanie zdań z użyciem wildcard nie ignoruje “słów szumów” – noise words, co powoduje, że takie wyszukiwanie staje się bezużyteczne. Posłużę się przykładem:

... FROM SYS.DM_FTS_PARSER('"What is domain driven design"', 1033, 0, 0)

... FROM SYS.DM_FTS_PARSER('"What is domain driven de*"', 1033, 0, 0)

Pierwsze zapytanie oznaczy słowa “What” oraz “is” jako noise words, zaś drugie jako exact match.

Spowoduje to, że zapytanie z wildcardnie zwróci żadnych wyników, ponieważ podczas procesu indeksowania słowa “what” oraz “is” nie są indeksowane. Wyszukiwanie zdań z wildcard dodaje ten wildcard do każdego słowa, czyli dla wyszukiwania `local wine*`, FULL TEXT SEARCH znajdzie zdania: local winery, ale i także `locally wined and dined`, co może być mylące.

Drugą wadą jest także to, że mamy bardzo mały wpływ na to, jak nasze słowa będą indeksowane. Na przykład: przy indeksowaniu kodu HTML być może chcielibyśmy wyciąć wszystkie jego znaczniki i indeksować czysty tekst. W tym rozwiązaniu nie ma na to łatwej drogi i wymagałoby to dodatkowego nakładu pracy.

 

Podsumowanie

Opisałem tutaj w skrócie, jakie alternatywy dla zasobożernej klauzuli LIKE możemy zastosować w SQL Serwerze. Myślę, że warto je przetestować. Oczywiście to zależy, czy powyższe rozwiązania rozwiążą nasze problemy. Jeśli nie, to w następnej części tego artykułu pójdziemy trochę dalej w kierunku rozwiązania dedykowanego dla tego rodzaju problemów – bazie Elasticsearch.