Jak wdraża się LIKE?

22

Czy ktoś może wyjaśnić, w jaki sposób operator LIKE jest implementowany w obecnych systemach baz danych (np. MySQL lub Postgres)? lub wskazać mi jakieś odniesienia, które to wyjaśniają?

Naiwnym podejściem byłoby sprawdzanie każdego rekordu, wykonywanie wyrażenia regularnego lub częściowego dopasowania ciągu na polu zainteresowania, ale mam wrażenie (mam nadzieję), że te systemy robią coś mądrzejszego.

Nacięcie
źródło

Odpowiedzi:

19

Nie, właściwie to robią. Teraz, jeśli nie ma wiodącego symbolu wieloznacznego, a pole jest indeksowane, co jest typową sytuacją, aparat bazy danych może zastosować do indeksu wyrażenie regularne. Na przykład, jeśli piszesz

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

baza danych może użyć indeksu, LAST_NAMEaby znaleźć wszystkie wiersze, w których nazwisko zaczyna się na „Cav”. Z drugiej strony, jeśli miałbyś coś takiego

SELECT *
  FROM employees
 WHERE last_name LIKE '%av%'

baza danych musiałaby przeskanować całą tabelę (lub cały indeks) i ocenić wyrażenie pod kątem pełnej LAST_NAMEwartości. Oczywiście to bardzo drogie.

Większość lepszych relacyjnych baz danych posiada funkcje do wyszukiwania pełnotekstowego w bardziej wydajny sposób poprzez tworzenie różnego rodzaju indeksów i katalogów tekstowych, ale nie używają one słowa kluczowego LIKE. Oto na przykład fajny artykuł, który omawia wyszukiwanie pełnotekstowe w PostgreSQL .

Justin Cave
źródło
4
Oracle może używać indeksu nawet z wiodącym procentem. Jeśli wyszukiwane dane reprezentują mały podzbiór wierszy, podpowiedź może zmusić go do użycia indeksu i przyspieszyć wykonanie. Zobacz laurentschneider.com/wordpress/2009/07/... .
Leigh Riffel,
1
„zeskanuj całą tabelę… Oczywiście, to bardzo kosztowne” - to raczej zależy od tabeli;) ps czy zgadzasz się LAST_NAMEbyć kandydatem na (pierwszą kolumnę w) indeks klastrowany? pps w jakim stopniu ta odpowiedź zakłada, że ​​system bazy danych opiera się na ciągłym przechowywaniu na indeksach dysku i B-drzewa?
dniu
26

Oprócz tego, co napisał Justin Cave, od PostgreSQL 9.1 możesz przyspieszyć każde wyszukiwanie za pomocą LIKE( ~~) lub ILIKE( ~~*), a także podstawowych dopasowań wyrażeń regularnych ( ~). Użyj klas operatora dostarczonych przez moduł pg_trgm z indeksem GIN lub GiST, aby przyspieszyć LIKEwyrażenia, które nie są zakotwiczone w lewo. Aby zainstalować rozszerzenie, uruchom raz na bazę danych:

CREATE EXTENSION pg_trgm;

Utwórz indeks formularza

CREATE INDEX tbl_col_gin_trgm_idx ON tbl USING gin (col gin_trgm_ops);

Lub:

CREATE INDEX tbl_col_gist_trgm_idx ON tbl USING gist (col gist_trgm_ops);

Tworzenie i utrzymywanie indeksu GIN lub GiST wiąże się z pewnymi kosztami, ale jeśli twoja tabela nie jest mocno napisana, jest to świetna funkcja dla Ciebie.

Depesz napisał świetny artykuł na swoim blogu o nowej funkcji.

GIN czy GiST?

Te dwa cytaty z podręcznika powinny dostarczyć wskazówek

Wybór między indeksowaniem GiST i GIN zależy od względnej charakterystyki wydajności GiST i GIN, które omówiono w innym miejscu. Zasadniczo indeks GIN jest szybszy w wyszukiwaniu niż indeks GiST, ale wolniej buduje lub aktualizuje; dlatego GIN lepiej nadaje się do danych statycznych, a GiST do często aktualizowanych danych.

Ale w przypadku zapytań typu „najbliższy sąsiad” za pomocą operatora odległości <->:

Można to dość skutecznie zaimplementować za pomocą indeksów GiST, ale nie przez indeksów GIN.

Erwin Brandstetter
źródło
3
Czytając to, zastanawiałem się, czy użyć GIN, czy GiST. Zgodnie z tym, co przeczytałem, indeksy GIN są droższe w utrzymaniu, ale szybsze w wyszukiwaniu, podczas gdy indeks GiST jest tańszy w utrzymaniu, ale wolniejszy w wyszukiwaniu. Oznacza to, że indeksy GIN powinny być generalnie stosowane w relatywnie statycznych danych, podczas gdy indeksy GiST są preferowane w bardziej intensywnie mutujących tabelach.
Colin 't Hart,
1
@ Colin'tHart: To generalnie prawda, ale są wyjątki od reguły. Rozważ dodatek powyżej.
Erwin Brandstetter,
5

Mówiąc o MySQL, pozycja znaku wieloznacznego (%) robi różnicę. Jeśli pierwsza część tekstu jest określona jako where first_name like 'Sta%', wówczas silnik DB przeszuka tylko mniejszy podzbiór słów, wpatrując się w S, następnie w St, a potem Sta itp. Jeśli zrobisz coś takiego where first_name like '%stan%', wtedy i cały skan kolumna będzie wymagana. Możesz także przejrzeć indeksy pełnotekstowe, które również wyszukują w języku naturalnym. Sprawdź dokumenty MySQL tutaj.

StanleyJohns
źródło
1
Dlaczego zacznie szukać „S%”, gdy podłańcuch jest zdefiniowany jako 3 znaki (tzn. Wiemy, że ciąg nie jest „Sr%”)? A może zakładasz, że DB ma drzewo prefiksów nad atrybutami i daje przykład przejścia przez to drzewo?
Nick