О сайтах и не о сайтах

MySQL vs файлы. Скорость поиска строки по подстроке.

На днях задался вопросом целесообразности хранение строковых данных в БД вместо файлов с точки зрения скорости поиска.

Хотя, конечно, вопрос правильней поставить так — чем быстрее осуществлять поиск в массиве строк, средствами языка программирования (в данном случае php) или средствами РСУБД (MySQL)? А сравнение «MySQL vs файлы» только для наглядности, ведь данные в базах тоже хранятся в файлах (а в чем же еще?) и используется все та же файловая система.

Решил провести небольшой тест. Сгенерировал 100к строк вида

MP0bWDXN1AxhI9yCZiGpKUZObSBOSrFv6vxTYkxPLUXjUmLJui
Z53PK4xcJgteCqAZ9p9w5LhTU15wBqFrlz6VtuX3Bg83xzSwOS
Tjt0seSoBkE6BPvyBPSoJjvHcS6VfLDYlXPD1ySsImp91Lxsrg

Каждая строка при генерации писалась одновременно в файл (*.txt) и в четыре таблицы — таблицу типа MyISAM, тип данных «text», таблицу MyISAM, тип данных «varchar(100)», таблицу InnoDB, тип данных «text» и таблицу InnoDB, тип данных «varchar(100)».

При генерации 100к строк из каждой тысячной строки из середины копировалось 10 символов, которые писались в отдельный файл. Таким образом получилось 100 подстрок, по которым и осуществляется поиск полной строки в файле и базе данных.

Суть теста заключается в следующем — берем первую подстроку, ищем ее вхождение в строках, сохраненных в файле и БД, потом берем вторую подстроку и так далее сто раз. При каждом поиске засекаем время, необходимое для нахождения строки по ее подстроке, потом вычисляем среднее и сравниваем.

Поиск при хранении строк в текстовом файле осуществлялся четырьмя способами:

1. При каждом поиске (которых всего, как говорилось выше, сто) происходит чтение файла в массив функцией file(), потом осуществляется проход по получившемуся массиву конструкцией foreach(), где ищется вхождение подстроки в строку строковой функцией strpos().

2. Аналогично, только для поиска подстроки вместо строковой функции используются регулярные выражения, функция preg_match().

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

Поиск по каждой из четырех созданных таблиц осуществлялся восемью способами:

1. Открытие соединения с БД. Поиск подстроки с использованием в SQL запросе операции сравнения LIKE. Закрытие соединения.

2. Открытие соединения с БД. Поиск подстроки с использованием в SQL запросе операции сравнения REGEXP. Закрытие соединения.

Третий и четвертый способы аналогичны предыдущим двум, но в них не учитывается время, необходимое на открытие и закрытие соединения с БД. Точнее, соединение с БД не закрывается до тех пор, пока не будут выполнены все сто запросов.

И 5-8 способы повторяют 1-4, но только в настройках MySQL отключается кэширование запросов (по умолчанию кэширование осуществляется). При использовании кэширования, поиск фактически происходит не по базе данных, а по кэшу (запрос хэшируется и ищется в кэше, если совпадения найдены - результат запроса возвращается из кэша, а сам запрос не делается).

Ниже представлена таблица с полученными в ходе теста данными.

Хранение данных Способ поиска Учет времени на чтение файла или открытие/закрытие соединения с БД Среднее время поиска, с
Файл, *.txt Строковые функции, strpos() Да 0.252027
Файл, *.txt Регулярные выражения, preg_match() Да 0.334894
Файл, *.txt Строковые функции, strpos() Нет 0.129508
Файл, *.txt Регулярные выражения, preg_match() Нет 0.303539
БД, MyISAM, text, без кэширования запросов Операция сравнения like "%pattern%" Да 0.202112
БД, InnoDB, text, без кэширования запросов Операция сравнения like "%pattern%" Да 0.335769
 БД, MyISAM, varchar(100) , без кэширования запросов Операция сравнения like "%pattern%" Да 0.194496
БД, InnoDB, varchar(100), без кэширования запросов Операция сравнения like "%pattern%" Да 0.261031
БД, MyISAM, text, без кэширования запросов Операция сравнения regexp ".*pattern.*" Да 1.074974
БД, InnoDB, text, без кэширования запросов Операция сравнения regexp ".*pattern.*" Да 1.225922
БД, MyISAM, varchar(100), без кэширования запросов Операция сравнения regexp ".*pattern.*" Да 1.070542
БД, InnoDB, varchar(100), без кэширования запросов Операция сравнения regexp ".*pattern.*" Да 1.143679
БД, MyISAM, text, без кэширования запросов Операция сравнения like "%pattern%" Нет 0.190953
БД, InnoDB, text, без кэширования запросов Операция сравнения like "%pattern%" Нет 0.333155
БД, MyISAM, varchar(100), без кэширования запросов Операция сравнения like "%pattern%" Нет 0.189853
БД, InnoDB, varchar(100), без кэширования запросов Операция сравнения like "%pattern%" Нет 0.262696
БД, MyISAM, text, без кэширования запросов Операция сравнения regexp ".*pattern.*" Нет 1.070554
БД, InnoDB, text, без кэширования запросов Операция сравнения regexp ".*pattern.*" Нет 1.231657
БД, MyISAM, varchar(100), без кэширования запросов Операция сравнения regexp ".*pattern.*" Нет 1.063102
БД, InnoDB, varchar(100), без кэширования запросов Операция сравнения regexp ".*pattern.*" Нет 1.139206
БД, MyISAM, text, кэширование запросов Операция сравнения like "%pattern%" Да 0.000332
БД, InnoDB, text, кэширование запросов Операция сравнения like "%pattern%" Да 0.000357
 БД, MyISAM, varchar(100) , кэширование запросов Операция сравнения like "%pattern%" Да 0.000294
БД, InnoDB, varchar(100), кэширование запросов Операция сравнения like "%pattern%" Да 0.000377
БД, MyISAM, text, кэширование запросов Операция сравнения regexp ".*pattern.*" Да 0.000332
БД, InnoDB, text, кэширование запросов Операция сравнения regexp ".*pattern.*" Да 0.000349
БД, MyISAM, varchar(100), кэширование запросов Операция сравнения regexp ".*pattern.*" Да 0.000335
БД, InnoDB, varchar(100), кэширование запросов Операция сравнения regexp ".*pattern.*" Да 0.000365
БД, MyISAM, text, кэширование запросов Операция сравнения like "%pattern%" Нет 0.000071
БД, InnoDB, text, кэширование запросов Операция сравнения like "%pattern%" Нет 0.000126
БД, MyISAM, varchar(100), кэширование запросов Операция сравнения like "%pattern%" Нет 0.000071
БД, InnoDB, varchar(100), кэширование запросов Операция сравнения like "%pattern%" Нет 0.000108
БД, MyISAM, text, кэширование запросов Операция сравнения regexp ".*pattern.*" Нет 0.000072
БД, InnoDB, text, кэширование запросов Операция сравнения regexp ".*pattern.*" Нет 0.000070
БД, MyISAM, varchar(100), кэширование запросов Операция сравнения regexp ".*pattern.*" Нет 0.000071
БД, InnoDB, varchar(100), кэширование запросов Операция сравнения regexp ".*pattern.*" Нет 0.000109

Исходя из полученных данных, можно сделать несколько выводов, банальных и не очень.

Открытие или закрытие какого-то ресурса (будь то файл или соединение с БД) — очень времязатратная процедура. Оформлять кусок кода в функцию, где что-то открывается, пишется, закрывается, и потом эту функцию вызывать несколько раз в разных местах программы или даже в цикле — неправильное решение с точки зрения производительности.

Строковые функции работают быстрее, чем регулярные выражения. Поэтому то, что можно сделать строковыми функциями, надо делать именно строковыми функциями, а не регулярками.

Скорость поиска строковых данных в таблицах типа MyISAM быстрее, чем в таблицах типа InnoDB. Поэтому если при выборе таблицы того или иного типа основным критерием является скорость чтения и не требуется каких-то специфичных свойств (механизм транзакций, работа с внешними ключами), то использовать следует MyISAM.

Скорость поиска по данным типа text и varchar при использовании таблиц типа MyISAM примерно сопоставима. При использовании же таблиц типа InnoDB, скорость поиска по данным text осуществляется медленнее, чем по данным типа varchar.

Поиск с использованием в SQL запросах операции сравнения «REGEXP» работает в разы медленнее, чем с использованием операции сравнения «LIKE». Что еще раз подтверждает тот факт, что регулярными выражениями надо пользоваться только при отсутствии альтернатив.

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

Вывод из сравнения можно сделать такой: без учета времени на открытие файла/соединение с БД, поиск средствами php по данным, находящимся в оперативной памяти, осуществляется в среднем в два раза быстрее, чем средствами MySQL по данным, находящимся в БД. Однако MySQL имеет систему кэширования запросов, поэтому если требуется регулярно обращаться к одним и тем же данным и делать одинаковые выборки, то выигрыш в скорости при использовании баз данных становится весьма значительным.

Комментарии

*Такая скорость работы БД связана видимо с тем, что select запросы кэшируются и поиска при повторных идентичных запросах по сути не происходит, это я к сожалению забыл учесть. Хорошо хоть через пять часов после написания поста начал догадываться, что ну не может поиск по 100к строкам осуществляться за 0.00007 с. и что-то тут нечисто=) Завтра покурю мануалы, потестю еще и пофиксю пост.

А если искать не обходом массива в цикле, а загружая все данные в одну строку?

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

Пост дополнен. Добавлены результаты теста скорости поиска по базе данных с отключенным кэшированием. Выводы переписаны.

PS
Тормоз, потестил предложенный тобой вариант - получилось в среднем в 30 раз быстрее. Но это в моем конкретном "сферическом" случае, когда я знаю длину строк, длину подстрок и позицию вхождения подстроки в строку. В реальности же я не буду знать ни первого, ни второго, ни третьего. Поэтому после нахождения позиции вхождения подстроки в строку мне придется еще слева/справа искать символы-разделители. А это дополнительное время, плюс слишком сложно и непонятно для частого использования. Хотя если выигрыш во времени существенен, то почему бы и нет. Но надо сначала потестить все это основательно, может на днях займусь. А вообще, раньше я всегда стороной обходил всякие книги по алгоритмам (коих достаточно много), как оказалось - зря. Алгоритмы везде=)

Алгоритмы действительно везде :) И не только в программировании.
Спасибо, интересные тесты.

Сравни select с MySQl(MyISAM) & MongoDB

К своему стыду, ничем кроме как MySQL до сих пор не доводилось пользоваться. Но как только - так сразу.

Не помешали бы примеры запросов, которые вы применяли в 2010 году. :)

Скорее всего что-то простое, видa

SELECT %column% FROM %table% WHERE %column% LIKE %pattern%

Но в целом пост ни о чем, конечно, насколько я сейчас понимаю.

Если используется LIKE - тогда на колонку имеет смысл повесить индекс, и искать уже по бинарному дереву, время поиска будет минимальным. Делал один заказ, где надо было быстро находить нужную строку LIKE-ом по БД из миллиона+ записей для одной АПИшки, индекс решил все проблемы.

Если нужен полнотекстовый - то копать куда-нибудь в сторону Apache Solr, например. Или в сторону индексации текста за пределами логики БД. Есть один Друпал сайт, там прикручен полнотекстовый по десяткам тысяч материалов. Обошелся полностью встроенным функционалом самого Друпала, там он "из коробки" может создавать индекс по текстовым массивам. Скорость ответа не измерял, так как там по сути внутренний поиск по сайту, сотые и десятые доли секунды ну совсем не играют роли.

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

Добавить комментарий

Содержимое данного поля является приватным и не предназначено для показа.