Абстракции это замечательные вещи. Взгляните на Rails : мы можем достичь огромного количества функциональности при сравнительно небольшом количестве написанного кода. Например, мне не нужно много знать о том, как реализована моя база данных, чтобы быстро начать работу.
Недостатком этого уровня изоляции от основной функциональности является то, что разработчики не учатся всему, что им, возможно, следует. Только на прошлой неделе мне удалось устранить неполадки с медленным запросом, удалив индекс, потому что кто-то в этом ряду не понимал количество элементов или работу индекса. Не могли бы вы реализовать базу данных самостоятельно? Давайте углубимся в другую технологию, которую мы считаем само собой разумеющимся!
Как работают индексы?
Мы ожидаем относительно быстрое время поиска при запросах к базе данных. Если бы вы реализовывали функцию для извлечения каждого значения между двумя числами, у вас может возникнуть соблазн проверить каждое значение, чтобы увидеть, соответствует ли оно критерию, но это было бы чрезмерно неэффективно для больших наборов данных, так как оно выполняется за линейное время ( O(n) Вам нужен способ хранить записи в указанном порядке, чтобы ускорить время доступа. Структура, подобная Binary Search Tree (BST), делает именно это, гарантируя, что любая данная запись больше, чем все записи в его левом поддереве, но ниже, чем все элементы в ее правом поддереве. Это сокращает время поиска до гораздо более значительного O(log n)
BST подводит нас к тому, что нам редко требуется конкретная запись. Скорее мы хотим, чтобы все записи соответствовали определенному критерию. Наивным решением было бы проверить каждую запись снова, что возвращает нас обратно к линейному времени, или O(n) Нам нужен способ хранить все записи по порядку, обходить этот список и затем останавливаться при выполнении условия (в данном случае это верхняя граница нашего запроса). Структурой данных, хорошо подходящей для этой задачи, является дерево B + , которое сокращает время доступа до O(m + log n)
Исследуя эту статью, я был поражен неэффективностью этого подхода. Скорее всего, все, что требуется, — это быстрая индексация упорядоченного списка — задача, хорошо подходящая для преступно недостаточно используемой и малоизвестной структуры данных, списка пропусков . Оказывается, что, хотя B + Trees обычно требует больше ресурсов процессора, чем эквивалентные операции в других структурах данных, они превосходно справляются с гораздо меньшим количеством операций переноса с диска на память, что является естественным узким местом. Этот пост в блоге Google дает некоторое представление о том, почему это так. Кроме того, деревья B + также эффективны в наихудшем случае — огромный фактор, когда наборы данных больше.
Почему слишком много индексов — плохая идея?
Представим себе удаление строки в нашей базе данных. Это означает, что нам также необходимо удалить соответствующий узел в дереве B +. Вы не можете просто удалить узел, потому что мы полагаемся на упорядоченный характер структуры данных, что означает, что нам нужно сохранить порядок в дополнение к обеспечению того, чтобы общая высота дерева была настолько низкой, насколько это возможно. Для борьбы с этим наш механизм базы данных будет использовать интеллектуальные методы вставки и удаления, но они потребуют логарифмического ( O(log n) Важно то, что любое поле, к которому вы применяете индекс, должно перебалансировать дерево при каждом выполнении операции вставки или удаления.
Считается, что поле с несколькими возможными вариантами (например, логическое, трилиновое и т. Д.) Имеет низкую мощность. Вот отличная статья IBM, которая предостерегает от ловушек индексации полей с низким количеством элементов, но суть в том, что вам следует избегать этого. Однако, как это ни странно, я сократил количество запросов на 80% раньше, просто индексируя столбцы True / False и, как всегда, профиль профиля!
Query Parser
Давайте возьмем стандартный запрос и проследим его путь:
SELECT id, email, admin, credits FROM users WHERE credits > 2 + 3;
Таким образом, синтаксический анализатор преобразует ваш текст в дерево разбора:
>>> SELECT email, admin, credits FROM users WHERE credits > 2 + 3
LOG: parse tree:
DETAIL: {QUERY
:commandType 1
:querySource 0
:canSetTag true
:utilityStmt <>
:resultRelation 0
:hasAggs false
:hasWindowFuncs false
:hasSubLinks false
:hasDistinctOn false
:hasRecursive false
:hasModifyingCTE false
:hasForUpdate false
:hasRowSecurity false
:cteList <>
:rtable (
{RTE
:alias <>
:eref
{ALIAS
:aliasname users
:colnames ("id" "created_at" "updated_at" "email" "encrypted_password
" "confirmation_token" "remember_token" "admin" "" "credits")
}
:rtekind 0
:relid 27043
:relkind r
:tablesample <>
:lateral false
:inh true
:inFromCl true
:requiredPerms 2
:checkAsUser 0
:selectedCols (b 12 16 18)
:insertedCols (b)
:updatedCols (b)
:securityQuals <>
Time: 0.001s
Для тех, кто играет дома, я использую превосходный pgcli с Postgres и следующие две настройки:
SET client_min_messages=debug1;
SET debug_print_parse=on;
Вернуться к парсеру запросов. Во время этого процесса он проверяет, что ваш ввод является законным. Ключевые слова в неправильном порядке? Опечатка? Это парсер запросов, который возвращает вам ошибку (обратите внимание на WHRE
SELECT email, admin, credits FROM users WHRE credits > 2 + 3;
syntax error at or near "credits"
Затем анализатор запросов проверяет метаданные базы данных: существует ли ваша таблица? Столбец существует? Возможна ли операция, которую вы собираетесь выполнить? У вас есть авторизация через систему разрешений базы данных?
SELECT email, admin, credits FROM users WHERE credits > 'Ostrich';
invalid input syntax for integer: "Ostrich"
Если все выглядит хорошо, то анализатор запросов передает дерево к следующему шагу.
Query Rewriter
После успешного построения нашего дерева пришло время оптимизировать его. Программа составления запросов берет наше дерево и применяет к нему список правил. Например, если вы поместили DISTINCTDISTINCT Целочисленные вычисления заменяются константой (2 + 3 в нашем примере заменяется на 5 здесь). Здесь есть множество других правил, но конечной целью является обеспечение того, чтобы тактовые циклы, возникающие при выполнении запроса, были сведены к минимуму.
Конечным результатом является план запроса, теоретически это сильно оптимизированный и эффективный запрос SQL. Но как движок БД узнает, какие соединения наиболее эффективны и так далее? Для этого нам нужно сделать быстрый обход…
Статистика
Хороший движок базы данных будет собирать статистику. Это будут такие вещи, как количество записей в таблице, количество различных значений в столбце, минимальные / максимальные значения и т. Д. Это относится к процессу оптимизации запросов, и поэтому ваши запросы выполняются быстро. Например, если вы пытаетесь объединить таблицу с миллионом строк в одну с сотней, будет гораздо быстрее объединить таблицу с меньшим количеством записей. На самом деле это гораздо глубже, чем вычисление гистограмм, содержащих информацию, такую как квантили и стандартное отклонение, но вы поняли идею.
Нет ничего менее подходящего для быстрых запросов, чем ошибочная статистика. Если оптимизатор запросов считает, что существует 200 записей, а их фактически 200 миллионов, и на этой основе вычисляет гистограммы и статистику, это может быть разницей между минутами и часами для выполнения запроса. По этой причине важно периодически запускать статистический сбор.
Query Executor
Наконец, пришло время выполнить наш запрос! Диспетчер запросов проверяет, имеет ли он достаточные ресурсы (память и процессор), и, если разрешено, начинает выполнение. Сначала он проверит кэш данных в памяти (запоминается намного быстрее, чем диск) и запустит менеджер кэша для предварительной выборки следующего необходимого фрагмента данных, как указано в плане запроса. Он будет отбрасывать данные, которые больше не требуются, и вы можете проверить, хорошо ли это работает, взглянув на то, что называется коэффициентом попадания в буфер / кэш . Около 99% — это то, к чему вы стремитесь.
Если бы это была операция записи / обновления / удаления, ваш Transaction Manager включился бы здесь, чтобы защитить вашу целостность данных, но, поскольку мы просто делаем простое чтение, все, что осталось, — это чтобы клиентский менеджер базы данных возвратил красиво выгруженный ответ клиенту.
Завершение
Есть много отличных ресурсов для лучшего понимания баз данных, и многое я не рассмотрел здесь. Но мы надеемся, что этого будет достаточно, чтобы вы могли начать понимать, что искать при профилировании. По крайней мере, вы можете дважды подумать, прежде чем слепо добавлять индекс!