Какова проблема с запросом SELECT N + 1?

SELECT N + 1 обычно упоминается как проблема в обсуждениях объектно-реляционного сопоставления (ORM), и я понимаю, что он что-то делает с необходимостью делать много запросов к базе данных для чего-то, что кажется простым в объектном мире.

У кого-нибудь есть более подробное объяснение проблемы?

Предположим, у вас есть коллекция объектов Car (строки базы данных), и каждый Car имеет коллекцию объектов Wheel (также строк). Другими словами, Car -> Wheel является отношением «один ко многим».

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

 SELECT * FROM Cars; 

И затем для каждого Car :

 SELECT * FROM Wheel WHERE CarId = ? 

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

В качестве альтернативы можно было получить все колеса и выполнить поиск в памяти:

 SELECT * FROM Wheel 

Это уменьшает количество обращений к базе данных с N + 1 до 2. Большинство инструментов ORM предоставляют вам несколько способов предотвратить выбор N + 1.

Ссылка: Java Persistence with Hibernate , глава 13.

 SELECT table1.* , table2.* INNER JOIN table2 ON table2.SomeFkId = table1.SomeId 

Это дает вам набор результатов, в котором дочерние строки в таблице2 вызывают дублирование, возвращая результаты таблицы1 для каждой дочерней строки в таблице2. Маршрутизаторы O / R должны различать экземпляры таблицы1 на основе уникального ключевого поля, а затем использовать все столбцы таблицы2 для заполнения дочерних экземпляров.

 SELECT table1.* SELECT table2.* WHERE SomeFkId = # 

N + 1 – это то, где первый запрос заполняет первичный объект, а второй запрос заполняет все дочерние объекты для каждого из возвращаемых уникальных первичных объектов.

Рассматривать:

 class House { int Id { get; set; } string Address { get; set; } Person[] Inhabitants { get; set; } } class Person { string Name { get; set; } int HouseId { get; set; } } 

и таблицы с аналогичной структурой. Один запрос для адреса «22 Valley St» может вернуться:

 Id Address Name HouseId 1 22 Valley St Dave 1 1 22 Valley St John 1 1 22 Valley St Mike 1 

O / RM должен заполнить экземпляр Home с ID = 1, Address = «22 Valley St», а затем заполнить массив «Жители» экземплярами People для Dave, John и Mike с помощью всего одного запроса.

Запрос N + 1 для одного и того же адреса, использованного выше, приведет к:

 Id Address 1 22 Valley St 

с отдельным запросом типа

 SELECT * FROM Person WHERE HouseId = 1 

и в результате получается отдельный dataset, подобный

 Name HouseId Dave 1 John 1 Mike 1 

и конечный результат будет таким же, как и выше, с единственным запросом.

Преимущества для одного выбора – это то, что вы получаете все данные спереди, которые могут быть тем, чего вы в конечном итоге желаете. Преимущества N + 1 – сложность запросов, и вы можете использовать ленивую загрузку, когда дочерние результирующие наборы загружаются только при первом запросе.

Поставщик с отношением «один ко многим» с продуктом. Один поставщик имеет (поставляет) много продуктов.

 ***** Table: Supplier ***** +-----+-------------------+ | ID | NAME | +-----+-------------------+ | 1 | Supplier Name 1 | | 2 | Supplier Name 2 | | 3 | Supplier Name 3 | | 4 | Supplier Name 4 | +-----+-------------------+ ***** Table: Product ***** +-----+-----------+--------------------+-------+------------+ | ID | NAME | DESCRIPTION | PRICE | SUPPLIERID | +-----+-----------+--------------------+-------+------------+ |1 | Product 1 | Name for Product 1 | 2.0 | 1 | |2 | Product 2 | Name for Product 2 | 22.0 | 1 | |3 | Product 3 | Name for Product 3 | 30.0 | 2 | |4 | Product 4 | Name for Product 4 | 7.0 | 3 | +-----+-----------+--------------------+-------+------------+ 

Факторы:

  • Lazy mode для поставщика, установленного в “true” (по умолчанию)

  • Режим выборки, используемый для запросов на Продукт, выбирается

  • Режим Fetch (по умолчанию): Доступ к информации о поставщике

  • Кэширование не играет роли в первый раз

  • Доступ к поставщику

Режим Fetch – выбор Fetch (по умолчанию)

 // It takes Select fetch mode as a default Query query = session.createQuery( "from Product p"); List list = query.list(); // Supplier is being accessed displayProductsListWithSupplierName(results); select ... various field names ... from PRODUCT select ... various field names ... from SUPPLIER where SUPPLIER.id=? select ... various field names ... from SUPPLIER where SUPPLIER.id=? select ... various field names ... from SUPPLIER where SUPPLIER.id=? 

Результат:

  • 1 выберите оператор для продукта
  • N выбор заявлений для поставщика

Это проблема с выбором N + 1!

Я не могу прямо комментировать другие ответы, потому что у меня недостаточно репутации. Но стоит отметить, что проблема по существу возникает только потому, что, исторически, много dbms были довольно плохими, когда речь заходила о обработке объединений (особенно для MySQL – замечательный пример). Таким образом, n + 1, как правило, заметно быстрее, чем соединение. И тогда есть способы улучшить n + 1, но все же без необходимости объединения, к чему относится исходная проблема.

Однако MySQL теперь намного лучше, чем раньше, когда дело доходит до присоединений. Когда я впервые изучил MySQL, я много использовал. Затем я обнаружил, насколько они медленны, и вместо этого переключился на n + 1. Но в последнее время я возвращаюсь к объединению, потому что MySQL теперь намного лучше справляется с ними, чем когда я впервые начал использовать его.

В наши дни простое соединение по правильно индексированному набору таблиц редко является проблемой, с точки зрения производительности. И если это дает удар производительности, то использование указательных подсказок часто решает их.

Это обсуждается здесь одной из разработчиков MySQL:

http://jorgenloland.blogspot.co.uk/2013/02/dbt-3-q3-6-x-performance-in-mysql-5610.html

Итак, резюме: если вы избегали объединений в прошлом из-за ужасающей производительности MySQL с ними, повторите попытку в последних версиях. Вы, вероятно, будете приятно удивлены.

Из-за этой проблемы мы отошли от ORM в Django. В принципе, если вы попытаетесь

 for p in person: print p.car.colour 

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

Простой и очень эффективный подход к этому – это то, что я называю « фальсификацией », что позволяет избежать бессмысленной идеи о том, что результаты запроса из реляционной базы данных должны отображаться обратно к исходным таблицам, из которых состоит запрос.

Шаг 1: Широкий выбор

  select * from people_car_colour; # this is a view or sql function 

Это вернет что-то вроде

  p.id | p.name | p.telno | car.id | car.type | car.colour -----+--------+---------+--------+----------+----------- 2 | jones | 2145 | 77 | ford | red 2 | jones | 2145 | 1012 | toyota | blue 16 | ashby | 124 | 99 | bmw | yellow 

Шаг 2: Objectify

Соедините результаты с создателем общего объекта с аргументом для разделения после третьего элемента. Это означает, что объект «jones» не будет выполняться более одного раза.

Шаг 3: Render

 for p in people: print p.car.colour # no more car queries 

См. Эту веб-страницу для реализации фальсификации для python.

Предположим, что у вас есть КОМПАНИЯ и СОТРУДНИК. КОМПАНИЯ имеет много СОТРУДНИКОВ (т.е. EMPLOYEE имеет поле COMPANY_ID).

В некоторых конфигурациях O / R, когда у вас есть сопоставленный объект компании и доступ к его объектам Employee, инструмент O / R сделает один выбор для каждого сотрудника, но если вы просто делаете что-то в прямом SQL, вы можете select * from employees where company_id = XX . Таким образом, N (# сотрудников) плюс 1 (компания)

Так работали начальные версии EJB Entity Beans. Я считаю, что такие вещи, как Hibernate, покончили с этим, но я не уверен. Большинство инструментов обычно include информацию о своей страtagsи для сопоставления.

Вот хорошее описание проблемы – http://www.realsolve.co.uk/site/tech/hib-tip-pitfall.php?name=why-lazy

Теперь, когда вы понимаете проблему, ее обычно можно избежать, выполнив выбор извлечения в вашем запросе. Это в основном заставляет выборку ленивого загруженного объекта, поэтому данные извлекаются в одном запросе вместо n + 1 запросов. Надеюсь это поможет.

Проверьте сообщение Ayende на тему: Борьба с проблемой выбора N + 1 в NHibernate

В принципе, при использовании ORM, например, NHibernate или EntityFramework, если у вас есть отношение «один ко многим» (мастер-деталь) и вы хотите перечислить все данные на каждой основной записи, вам необходимо сделать запросы N + 1 запросов к базы данных, «N» – это количество основных записей: 1 запрос для получения всех основных записей и N запросов, по одному на основную запись, для получения всех деталей на основную запись.

Больше запросов к запросу базы данных -> больше времени ожидания -> снижение производительности приложения / базы данных.

Однако у ORM есть варианты, чтобы избежать этой проблемы, главным образом используя «соединения».

По-моему, статья, написанная в Hibernate Pitfall: почему отношения должны быть ленивыми , прямо противоположна реальной проблеме N + 1.

Если вам нужны правильные объяснения, обратитесь к Hibernate – Глава 19: Повышение производительности – Страtagsи получения

Выбор выборки (по умолчанию) чрезвычайно уязвим для N + 1, который выбирает проблемы, поэтому мы можем захотеть включить сборку ссылок

Поставляемая ссылка имеет очень простой пример проблемы n + 1. Если вы примените его к Hibernate, это в основном говорит об одном и том же. Когда вы запрашиваете объект, объект загружается, но любые ассоциации (если они не настроены иначе) будут загружены лениво. Следовательно, один запрос для корневых объектов и другой запрос для загрузки ассоциаций для каждого из них. 100 возвращенных объектов означает один начальный запрос, а затем 100 дополнительных запросов для получения связи для каждого, n + 1.

http://pramatr.com/2009/02/05/sql-n-1-selects-explained/

Гораздо быстрее выдать 1 запрос, который возвращает 100 результатов, чем выдавать 100 запросов, каждый из которых возвращает результат 1.

Проблема с запросом N + 1 возникает, когда вы забываете получить ассоциацию, а затем вам нужно получить к ней доступ:

 List comments = entityManager.createQuery( "select pc " + "from PostComment pc " + "where pc.review = :review", PostComment.class) .setParameter("review", review) .getResultList(); LOGGER.info("Loaded {} comments", comments.size()); for(PostComment comment : comments) { LOGGER.info("The post title is '{}'", comment.getPost().getTitle()); } 

Что генерирует следующие операторы SQL:

 SELECT pc.id AS id1_1_, pc.post_id AS post_id3_1_, pc.review AS review2_1_ FROM post_comment pc WHERE pc.review = 'Excellent!' INFO - Loaded 3 comments SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 1 INFO - The post title is 'Post nr. 1' SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 2 INFO - The post title is 'Post nr. 2' SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 3 INFO - The post title is 'Post nr. 3' 

Во-первых, Hibernate выполняет запрос JPQL, и выбирается список объектов PostComment .

Затем для каждого PostComment связанное свойство post используется для создания сообщения журнала, содержащего заголовок Post .

Поскольку ассоциация post не инициализирована, Hibernate должен получить объект Post с вторичным запросом, а для N объектов PostComment будет выполнено еще N запросов (следовательно, проблема с запросом N + 1).

Во-первых, вам нужно надлежащее ведение журнала и мониторинг SQL, чтобы вы могли выявить эту проблему.

Во-вторых, эту проблему лучше всего улавливать интеграционными тестами. Вы можете использовать автоматическое утверждение JUnit для проверки ожидаемого количества сгенерированных операторов SQL . Проект db-unit уже предоставляет эту функциональность, и это с открытым исходным кодом.

Когда вы идентифицировали проблему с запросом N + 1, вам нужно использовать JOIN FETCH, чтобы дочерние ассоциации извлекались в одном запросе вместо N. Если вам нужно получить несколько дочерних ассоциаций, лучше получить одну коллекцию в исходном запросе, а вторую – с вторичным SQL-запросом.

Один миллионер имеет N автомобилей. Вы хотите получить все (4) колеса.

Один (1) запрос загружает все автомобили, но для каждого (N) автомобиля отправляется отдельный запрос для загрузки колес.

Расходы:

Предположим, что индексы вписываются в ram.

1 + N parsing запроса и строгание + поиск индекса И 1 + N + (N * 4) доступ к пластине для загрузки полезной нагрузки.

Предположим, что индексы не вписываются в ram.

Дополнительные затраты в наихудшем случае 1 + N пластины доступа для загрузки индекса.

Резюме

Шея бутылки – доступ к пластине (около 70 раз в секунду произвольный доступ на hdd). Желающий выбор соединения также будет обращаться к пластине 1 + N + (N * 4) раз для полезной нагрузки. Поэтому, если индексы вписываются в ram – не проблема, это достаточно быстро, потому что задействованы только операции ram.

Вопрос, как и другие, более элегантно, заключается в том, что у вас есть декартово произведение столбцов OneToMany или вы выбираете N + 1. Или возможные гигантские результаты или чаты с базой данных, соответственно.

Я удивлен, что это не упоминается, но это то, как я столкнулся с этой проблемой … Я делаю полу-временную таблицу идентификаторов . Я также делаю это, когда у вас есть ограничение предложения IN () .

Это не работает для всех случаев (возможно, даже не для большинства), но оно работает особенно хорошо, если у вас много дочерних объектов, так что декартово устройство выйдет из-под контроля (то есть много колонок OneToMany число результатов будет умножение столбцов) и его больше похожее на пакетное задание.

Сначала вы вставляете идентификаторы родительских объектов как пакетные в таблицу идентификаторов. Этот batch_id – это то, что мы создаем в нашем приложении и поддерживаем.

 INSERT INTO temp_ids (product_id, batch_id) (SELECT p.product_id, ? FROM product p ORDER BY p.product_id LIMIT ? OFFSET ?); 

Теперь для каждого столбца OneToMany вы просто выполняете SELECT в таблице идентификаторов INNER JOIN в дочерней таблице с WHERE batch_id= (или наоборот). Вы просто хотите удостовериться, что вы заказываете по столбцу id, поскольку это упростит объединение столбцов результатов (в противном случае вам понадобится HashMap / Table для всего набора результатов, который может быть не так уж и плох).

Затем вы просто периодически чистите таблицу идентификаторов.

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

Теперь количество запросов, которые вы делаете, – это количество столбцов OneToMany.

Проблема выбора N + 1 – это боль, и имеет смысл обнаруживать такие случаи в модульных тестах. Я разработал небольшую библиотеку для проверки количества запросов, выполняемых данным тестовым методом или просто произвольным блоком кода – JDBC Sniffer

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

 @Rule public final QueryCounter queryCounter = new QueryCounter(); @Expectation(atMost = 3) @Test public void testInvokingDatabase() { // your JDBC or JPA code } 

Возьмите пример Мэтта Солнита, представьте, что вы определяете связь между автомобилем и колесами как LAZY, и вам нужны поля Wheels. Это означает, что после первого выбора, hibernate будет делать «Выберите * из колес, где car_id =: id» ДЛЯ КАЖДОГО автомобиля.

Это делает первый выбор и более 1 выбирается каждым N-автомобилем, поэтому он называется проблемой n + 1.

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

Но обратите внимание, если много раз вы не получаете доступ к связанным колесам, лучше сохранить LAZY или изменить тип выборки с помощью критериев.

Давайте будем гением компьютера.