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

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

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

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

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

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

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

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

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

В дополнение к тому, что написал Джастин Кейв, начиная с 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.

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