Почему n+1 выбирает шаблон медленно?
Я не очень разбираюсь в базах данных и только что прочитал о проблеме "n+1 selects". Мой дополнительный вопрос: если база данных находится на том же компьютере, что и моя программа, кэширована в ОЗУ и правильно проиндексирована, почему шаблон запроса n + 1 работает медленно?
В качестве примера возьмем код из принятого ответа:
SELECT * FROM Cars;
/* for each car */
SELECT * FROM Wheel WHERE CarId = ?
С моей ментальной моделью кэша базы данных каждый из SELECT * FROM Wheel WHERE CarId = ? запросы должны требовать:
- 1 поиск, чтобы добраться до таблицы "Колесо" (один хэш-карта
get()) - 1 поиск, чтобы добраться до списка k колес с указанным
CarId(еще один хэш-картаget()) - k поисков, чтобы получить ряды колес для каждого совпадающего колеса (k разыменований указателя)
Даже если мы умножим это на небольшой постоянный коэффициент для дополнительных издержек из-за внутренней структуры памяти, это все равно должно быть незаметно быстрым. Является ли межпроцессное взаимодействие узким местом?
Редактировать: я только что нашел эту статью через Hacker News: после выбора заявления через Postgres Internals. - HN обсуждение темы.
Изменить 2: чтобы уточнить, я предполагаю N быть большим. Нетривиальные накладные расходы добавят заметную задержку, тогда да. Я спрашиваю, почему накладные расходы в первую очередь нетривиальны для настройки, описанной выше.
4 ответа
Вы правы в том, что избегание выбора n+1 менее важно в описываемом вами сценарии. Если база данных находится на удаленном компьютере, задержки связи> 1 мс являются общими, то есть процессор будет тратить миллионы тактов на ожидание сети.
Если мы находимся на одной машине, задержка связи на несколько порядков меньше, но синхронная связь с другим процессом обязательно включает переключение контекста, которое обычно стоит> 0,01 мс ( источник), что составляет десятки тысяч тактовых циклов.
Кроме того, как инструмент ORM, так и база данных будут иметь некоторые накладные расходы на запрос.
В заключение, избегание n+1 выбора гораздо менее важно, если база данных является локальной, но все равно имеет значение, если n большое.
Предполагая, что база данных находится на той же машине, что и моя программа
Никогда не предполагай это. Думать об особых случаях, подобных этому, никогда не бывает хорошей идеей. Вполне вероятно, что ваши данные будут расти, и вам нужно будет разместить базу данных на другом сервере. Или вам понадобится избыточность, которая включает (как вы уже догадались) другой сервер. Или для безопасности, вы можете не захотеть, чтобы ваш сервер приложений находился в той же коробке, что и БД.
почему шаблон запроса n+1 медленный?
Вы не думаете, что это медленно, потому что ваша ментальная модель производительности, вероятно, совершенно неверна.
1) ОЗУ ужасно медленно. Ваш ЦП тратит около 200-400 циклов ЦП каждый раз, когда ему нужно что-то прочитать из ОЗУ. У процессоров есть много хитростей, чтобы скрыть это (кэши, конвейерная обработка, гиперпоточность)
2) Чтение из ОЗУ не является "произвольным доступом". Это как жесткий диск: последовательное чтение быстрее. См. Эту статью о том, как доступ к ОЗУ в правильном порядке на 76,6% быстрее http://lwn.net/Articles/255364/ (Прочтите всю статью, если вы хотите узнать, насколько ужасно сложна ОЗУ на самом деле.)
Кэш процессора
В вашем случае "N+1 запрос" "цикл" для каждого N включает много мегабайт кода (на клиенте и на сервере), включая и отключая кэши на каждой итерации, а также переключатели контекста (которые обычно в любом случае сбрасывают кэши).
Случай "1 запрос", вероятно, включает в себя один замкнутый цикл на сервере (поиск и копирование каждой строки), затем один замкнутый цикл на клиенте (чтение каждой строки). Если эти циклы достаточно малы, они могут выполняться в 10-100 раз быстрее из кеша.
ОЗУ последовательного доступа
В случае "1 запроса" все данные из БД будут считаны в один линейный буфер, и он будет отправлен клиенту, который будет читать его линейно. Нет случайного доступа во время передачи данных.
Случай "N+1 запрос" будет распределять и отменять выделение ОЗУ N раз, что (по разным причинам) может не совпадать с физическим битом ОЗУ.
Различные другие причины
Сетевой подсистеме нужно только читать один или два заголовка TCP вместо N.
Ваша БД должна проанализировать только один запрос вместо N.
Когда вы добавляете нескольких пользователей, "локальность / последовательный доступ" становится еще более фрагментированным в случае N + 1, но остается довольно хорошим в случае 1 запроса.
Множество других приемов, которые использует процессор (например, прогнозирование ветвлений), лучше работают с узкими циклами.
Смотрите: http://blogs.msdn.com/b/oldnewthing/archive/2014/06/13/10533875.aspx
Наличие базы данных на локальной машине уменьшает проблему; тем не менее, большинство приложений и баз данных будут находиться на разных компьютерах, где каждая передача в оба конца занимает не менее пары миллисекунд.
База данных также потребует много проверок блокировок и блокировок для каждого отдельного запроса. Переключатели контекста уже упоминались meriton. Если вы не используете окружающую транзакцию, она также должна создавать неявные транзакции для каждого запроса. Некоторые издержки синтаксического анализа запроса все еще существуют, даже с параметризованным, подготовленным запросом или запомненным равенством строк (с параметрами).
Если база данных заполнится, время запроса может увеличиться по сравнению с почти пустой базой в начале.
Если ваша база данных будет использоваться другим приложением, вы, скорее всего, столкнетесь с ней: даже если ваше приложение работает, другие могут замедляться или даже получать все больше сбоев, таких как тайм-ауты и взаимоблокировки.
Также рассмотрите возможность иметь более двух уровней данных. Представьте себе три уровня: блоги, записи, комментарии, со 100 блогами, каждый с 10 записями и 10 комментариями к каждой записи (в среднем). Это SELECT 1+N+(NxM) ситуация. Для получения записей в блоге потребуется 100 запросов и еще 1000 для получения всех комментариев. Некоторые более сложные данные, и вы столкнетесь с 10000 или даже 100000.
Конечно, плохое программирование может работать в некоторых случаях и в некоторой степени. Если база данных всегда будет на одной и той же машине, никто ее не использует, а количество машин никогда не превышает 100, даже очень неоптимальной программы может быть достаточно. Но остерегайтесь того дня, когда изменится любое из этих предварительных условий: рефакторинг всего этого займет у вас гораздо больше времени, чем правильное выполнение в начале. И, вероятно, вы сначала попробуете другие обходные пути: еще несколько предложений IF, кэш памяти и тому подобное, которые помогают в начале, но еще больше портят ваш код. В конце концов, вы можете оказаться в положении "никогда не трогайте работающую систему", когда производительность системы становится все менее и менее приемлемой, но рефакторинг слишком рискован и намного сложнее, чем изменение правильного кода.
Кроме того, хороший ORM предлагает вам способы обойти N+1: (N)Hibernate, например, позволяет вам указать размер пакета (объединение многих SELECT * FROM Wheels WHERE CarId=? запросы в один SELECT * FROM Wheels WHERE CarId IN (?, ?, ..., ?)) или использовать подвыбор (например: SELECT * FROM Wheels WHERE CarId IN (SELECT Id FROM Cars)).
Самый простой способ избежать N + 1 - это объединение, с недостатком, состоящим в том, что каждая строка автомобиля умножается на количество колес, и несколько элементов ребенка / внука, вероятно, заканчиваются огромным декартовым произведением результатов объединения.
Затраты все еще существуют, даже если база данных находится на том же компьютере, кэширована в ОЗУ и правильно проиндексирована. Размер этих издержек будет зависеть от того, какую СУБД вы используете, на каком компьютере она работает, количество пользователей, конфигурацию СУБД (уровень изоляции, ...) и так далее.
При получении N строк вы можете оплатить эту стоимость один раз или N раз. Даже небольшая стоимость может стать заметной, если N достаточно велико.
Однажды кто-то может захотеть поместить базу данных на отдельную машину или использовать другую базу данных. Это часто случается в деловом мире (чтобы соответствовать некоторому стандарту ISO, чтобы сократить расходы, сменить поставщиков, ...)
Поэтому иногда полезно планировать ситуации, когда база данных работает не слишком быстро.
Все это очень сильно зависит от того, для чего предназначено программное обеспечение. Избегать "проблемы выбора n+1" не всегда необходимо, это просто правило, чтобы избежать часто встречающейся ошибки.