Как реализуется LIKE?

22

Кто-нибудь может объяснить, как оператор LIKE реализован в современных системах баз данных (например, MySQL или Postgres)? или указать мне на некоторые ссылки, которые объясняют это?

Наивным подходом было бы проверять каждую запись, выполняя регулярное выражение или частичное совпадение строк в интересующей области, но у меня есть чувство (надежда), что эти системы делают что-то умнее.

Ник
источник

Ответы:

19

Нет, это в значительной степени то, что они делают. Теперь, если нет подстановочного знака в начале, и поле индексируется, что является обычной ситуацией, ядро ​​базы данных может применять регулярное выражение к индексу. Так, например, если вы пишете

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

база данных может использовать индекс, LAST_NAMEчтобы найти все строки, где фамилия начинается с «Cav». С другой стороны, если у вас было что-то вроде

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

база данных должна будет сканировать всю таблицу (или весь индекс) и сравнивать выражение с полным LAST_NAMEзначением. Очевидно, это очень дорого.

Большинство лучших реляционных баз данных имеют возможности для более полнотекстового поиска более эффективным способом, создавая различные виды индексов и текстовых каталогов, но они не используют ключевое слово LIKE. Например, вот хорошая статья, которая обсуждает полнотекстовый поиск в PostgreSQL .

Джастин Кейв
источник
4
Oracle может использовать индекс даже с опережающим процентом. Если искомые данные представляют небольшое подмножество строк, то подсказка может заставить его использовать индекс и ускорить выполнение. См. Laurentschneider.com/wordpress/2009/07/… .
Ли Риффель
1
«Сканирование всей таблицы ... Очевидно, это очень дорого» - это скорее зависит от таблицы;) ps Вы согласны LAST_NAMEбыть кандидатом (первый столбец в) кластерного индекса? pps, в какой степени этот ответ предполагает, что система баз данных основана на непрерывном хранении на дисковых и B-древовидных индексах?
1
26

В дополнение к тому, что написал Джастин Кейв, начиная с PostgreSQL 9.1, вы можете ускорить любой поиск с помощью LIKE( ~~) или ILIKE( ~~*), а также базовых совпадений с регулярными выражениями ( ~). Используйте классы операторов, предоставляемые модулем pg_trgm с индексом GIN или GiST, чтобы ускорить LIKEвыражения, которые не привязаны слева. Чтобы установить расширение, запустите один раз для каждой базы данных:

CREATE EXTENSION pg_trgm;

Создайте индекс формы

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

Или:

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

Создание и ведение индекса GIN или GiST сопряжено с определенными затратами, но если ваша таблица написана не сильно, это отличная возможность для вас.

Депес написал отличную статью в своем блоге о новой функции.

Джин или ГИСТ?

Эти две цитаты из руководства должны служить руководством

Выбор между индексами GiST и GIN зависит от относительных характеристик производительности GiST и GIN, которые обсуждаются в другом месте. Как правило, поиск по индексу GIN выполняется быстрее, чем по индексу GiST, но его создание или обновление происходит медленнее; поэтому GIN лучше подходит для статических данных, а GiST для часто обновляемых данных.

Но для запросов типа «ближайший сосед» с использованием оператора расстояния <->:

Это может быть реализовано довольно эффективно с помощью индексов GiST, но не с помощью индексов GIN.

Эрвин Брандштеттер
источник
3
Читая это, я задавался вопросом, использовать ли GIN или GiST. Согласно тому, что я прочитал, индексы GIN обходятся дороже, но их поиск выполняется быстрее, тогда как индекс GiST обходится дешевле, но поиск медленнее. Это означает, что индексы GIN обычно следует использовать для относительно статических данных, в то время как индексы GiST предпочтительнее для таблиц с более сильным изменением.
Colin 't Hart
1
@ Colin'tHart: Это обычно так, но есть исключения из правил. Рассмотрите дополнение выше.
Эрвин Брандштеттер
5

Говоря о MySQL, положение символа подстановки (%) имеет значение. Если первая часть текста указана как where first_name like 'Sta%', то механизм БД будет искать только меньшее подмножество слов, начинающихся с S, затем переходящих в St, затем в Sta и т. Д. Если вы делаете что-то подобное where first_name like '%stan%', то и полное сканирование столбец будет обязательным. Вы также можете просмотреть полнотекстовые индексы, которые также выполняют поиск на естественном языке. Проверьте документы MySQL здесь.

StanleyJohns
источник
1
Зачем начинать поиск с «S%», если подстрока определена в 3 символа (т.е. мы знаем, что строка не «Sr%»)? Или вы предполагали, что у БД есть дерево префиксов над атрибутами и предоставили пример обхода этого дерева?
Ник