Проблема N+1 запросов
Проблема N + 1 возникает, когда фреймворк доступа к данным выполняет N дополнительных SQL‑запросов для получения тех же данных, которые можно получить при выполнении одного SQL‑запроса.
В качестве примера возьмем БД состоящую из двух таблиц:
users — список пользователей. У каждого пользователя может быть несколько профилей
profiles — список профилей пользователя. У каждого профиля может быть указан редактор (пользователь, который последним редактировал профиль)
Структура БД
Данные в таблицах БД
Необходимо выбрать пользователей с идентификаторами [1,2,3], к каждому из них выбрать список профилей и к каждому профилю выбрать имя редактора.
Решение в "лоб".
$users = [];
foreach ([1, 2, 3] as $id) {
// Выбрать информацию о пользователе
$user = db()->select('users')->cond('id', '=', $id)->get();
// Выбрать список профилей пользователя
$user['profiles'] = db()->select('profiles')->cond('user_id', '=', $id)->get();
// Выбрать имена редакторов
$user['profiles'] = array_map(function ($profile) {
if ($profile['editor_id'] == 0) {
// Нет редактора
$profile['editor'] = '';
} else {
// Выберем имя редактора
$profile['editor'] = db()->select('users', 'name')->cond('user_id', '=', $profile['editor_id'])->first();
}
}, $user['profiles']);
// Добавить в список пользователей
$users[] = $user;
}
Данное решение генерирует целых 8 SQL запросов (в более рациональном варианте можно список пользователей выбрать через in() и сократить количество запросов до 6, но для примера специально взят именно такой вариант).
Группировка вызовов в "лоб"
Проблему можно решить c помощью группировки вызовов.
Пример выбора списка пользователей с группировкой вызовов
// Буфер для накапливания идентификаторов пользователей
// и хранения результатов выполнения SQL запроса
class Buffer
{
// Список идентификаторов пользователей
static public array|false $users;
// Список идентификаторов пользователей
static public array $ids;
// Сбросить буфер в начальное состояние
static public function reset()
{
self::$users = false;
self::$ids = [];
}
}
// Функция для получения информации о пользователе
// Точнее для получения обещания получить информацию о пользователе
function getUser(int $id): Promise
{
Buffer::$ids[] = $id;
return new Promise(function ($resolve) use ($id) {
// Если запрос ещё не выполнялся
if (Buffer::$users === false) {
// Выбрать информацию о пользователях
$rows = db()->select('users')->in('id', Buffer::$ids)->get();
// Группировать по пользователям
Buffer::$users = [];
foreach ($rows as $row) {
Buffer::$users[$row['id']] = $row;
}
}
// Вернуть информацию по пользователю
$resolve(Buffer::$users[$id]);
});
}
// Сбросить буфер в начальное состояние
Buffer::reset();
// Выбрать информацию о пользователях
// Для этого создадим обещание для каждого пользователя
// и дождемся их завершения
Promise::all([
getUser(1),
getUser(2),
getUser(3),
])->then(function ($users) {
// Получили список пользователей
// ...
});
Данный подход позволяет сократить количество SQL запросов с 3 до 1 ( выбирается только информация о пользователях без профилей и их редакторов! ). Но я не зря не стал приводить пример всех выборок по данному методу, так как решение получается громоздким из-за необходимости создавать отдельный буфер для каждого запроса.
Суть же данного метода весьма простая:
Необходимо накапливать переданные в функцию значения
В функцию выполнения обещания необходимо передавать все накопленные параметры, запрос один раз, а затем использовать выбранные значения для возврата данных по каждому вызову.
Группировка вызовов с использованием своего объекта группировки
Заменим обещание (Promise) на свою реализацию группировки (Batching).
Batching - объект группировки
//-- Объект группировки
class Batching
{
// Создает объект группировки и добавляет его в event loop
static public function create(\Closure $cb, ...$args): static;
// Создает объект группировки который ожидает выполнения списка объектов группировки
static public function all(array $batchings): static;
// Указывает функцию, в которую будет предан результат выполнения группировки
public function then(\Closure $cb): static;
}
Класс Batching служит для создания объекта группировки. Созданный объект содержит метод then в котором необходимо указать функцию для возврата значения. Отличие от обещания (Promise) в том, что в функцию выполнения передается не функция $resolve, а объект группы Batch. Этот объект содержит все накопленные значения параметров и используется для установки для каждого набора параметров.
Batch - объект группы
//-- Группа
class Batch
{
// Получить список уникальных значений параметра номер $nArgs
// Позволяет получать накопленные значения
public function unique(...$nArgs);
// Устанавливаем результат для каждого вызова
// В функцию обратного вызова передаются параметры для каждого вызова
// и необходимо вернуть значение для каждого набора параметров
public function setResult(\Closure $cb);
}
Пример на основе Batching
//-- Выбрать информацию о пользователях
Batching::all([
getUserForId(1),
getUserForId(2),
getUserForId(3)
])->then(function (array $users) {
// Получили список пользователей
// с профилями и редакторами
// ...
});
//-- Функция получения информации о пользователе
function getUserForId(int $id): Batching
{
return Batching::create(function (Batch $batch) {
// Выбираем список пользователей
$users = db()->select('users')->in('id', $batch>unique(0));
// Создадим список обещаний для выбора списка профилей для каждого пользователя
$promises = [];
foreach ($users as $user) {
$promises[] = getProfilesForUserId($user['id']);
}
return Batching::all($promises)->then(function ($profilesForUsers) use ($batch, $users) {
// Устанавливаем поле профилей для каждого пользователя и группируем по id пользователя
$userById = [];
foreach ($users as $index => $user) {
$user['profiles'] = $profilesForUsers[$index];
$userById[$user['id']] = $user;
}
// Устанавливаем результат для каждого вызова
$batch->setResult(function ($id) use ($userById) {
return $userById[$id];
});
});
}, $id);
}
//-- Функция получения списка профилей для пользователя
function getProfilesForUserId(int $user_id): Batching
{
return Batching::create(
function (Batch $batch) {
// Выбираем из БД список профилей для каждого идентификатора пользователя
$profiles = db()->select('profiles')->in('user_id', $batch->unique(0));
// Создадим список обещаний для выбора информации по имени пользователя редактора профиля
$promises = [];
foreach ($profiles as $profile) {
$promises[] = getUserNameForId($profile['editor_id']);
}
return Batching::all($promises)->then(function ($namesForUsers) use ($batch, $profiles) {
// Устанавливаем поле профилей для каждого пользователя и группируем по id пользователя
$profilesByUserId = [];
foreach ($profiles as $index => $profile) {
// Установить имя редактора
$profile['editor'] = $namesForUsers[$index];
// Группировать профили по пользователю
if (array_keys($profile['user_id'], $profilesByUserId)) {
$profilesByUserId[$profile['user_id']] = [];
}
$profilesByUserId[$profile['user_id']][] = $profile;
}
// Устанавливаем результат для каждого вызова
$batch->setResult(function ($user_id) use ($profilesByUserId) {
return $profilesByUserId[$user_id] ?? [];
});
});
},
$user_id
);
}
//-- Функция получения имени пользователя
function getUserNameForId(int $id): Batching
{
return Batching::create(function (Batch $batch) {
// Выбираем список пользователей
$users = db()->select('users')->in('id', $batch->unique(0));
// Группируем имена по идентификатору
$nameById = [];
foreach ($users as $user) {
$nameById[$user['id']] = $user['name'];
}
// Устанавливаем результат для каждого вызова
$batch->setResult(function ($id) use ($nameById) {
return $nameById[$id] ?? '-';
});
}, $id);
}
В результате выполнения примера на основе Batching будет выполнено 3 запроса вместо 8.
Есть три вызова с тремя идентификаторами пользователя: 1, 2, 3.
Функция Batching::create группирует эти вызовы и сгруппированный результат передаётся в функцию обработки объекта группировки. Объект Batch $batch содержит эти сгруппированные аргументы. Происходит выполнение запроса. После этого функцией $batch->setResult устанавливается результат для каждого вызова Batching::create. Т.е. хотя функция группировки в которую передаётся объект Batch $batch выполняется только один раз, но она должна установить результат для каждого вызова.
Фактически функция Batching::create группирует аргументы и создаёт объект Batch $batch, который использует функция выполнения группировки. А затем функция $batch->setResult разделяет результат обратно по вызовам.
Асинхронная группировка => синхронный PHP
PHP и многие фреймворки у нас синхронные. Поэтому необходимо асинхронные вызовы возвращать в синхронный код. Для этого необходимо запустить следующую функцию
// Запустить event loop и получить результат
$users = Batching::run(function (Batch $batch) {
Batching::all([
getUserForId(1),
getUserForId(2),
getUserForId(3)
])->then(function (array $users) use ($batch) {
// Устанавливаем результат для вызова
// Именно он будет возвращен из функции Batching::run
$batch->setResult(function () use ($users) {
return $users;
});
});
});
Кэширование
Возможно вы заметили что информацию по пользователю 2 выбирается два раза. Для того чтобы этого избежать можно использовать кэширование результата запроса. Напишем функцию, которая выбирает данные из таблицы users
и кэширует результат.
Функция чтения данных из users с использованием КЭШа
//-- Получить список пользователей
function getUserUseCache(array $ids)
{
$ret = [];
$idsSelect = [];
// Проверить: а может какие-то данные есть в КЭШе?
foreach ($ids as $id) {
$key = 'user.' . $id;
// Если данные есть
if (cache()->has($key)) {
// то прочитать данные из КЭШа
$ret[] = cache()->get($key);
} else {
// иначе добавить идентификатор в список для выборки из БД
$idsSelect[] = $id;
}
}
if (!empty($idsSelect)) {
// Выполнить запрос в БД
$users = db()->select('users')->in('id', $idsSelect);
// Сохранить результат в КЕШ
foreach ($users as $user) {
$key = 'user.' . $id;
cache()->put($key, $user);
// Добавить выбранные данные к результату
$ret[] = $user;
}
}
return $ret;
}
Эта функция не уменьшит количество запросов, но уменьшит количество выбираемых из БД данных.
В самом простом вариант можно кэшировать значения в памяти текущего скрипта. Для более сложного варианта и кэширования в REDIS или файловой системе необходимо предусмотреть сброс значения КЭШ‑а при изменении объекта. Как вариант, можно указывать время жизни, по прошествии которого значение в КЭШ‑е должно быть заново выбрано из БД.
Для удобства функция может иметь параметр использовать КЭШ или нет. В этом случае можно, при необходимости, читать значение без использования КЭШ‑а. К примеру принудительное чтение из БД необходимо перед записью изменений в таблицу БД чтобы получить текущее актуальное состояние записи.
Если есть данные которые редко меняются (к примеру текст статьи), то кэширование сильно снизит нагрузку на сервер БД.
Приоритизация
Ещё одна возможность снизить количество запросов к БД — это приоритизация группы вызовов. К примеру в event loop осталось две группы A и B, каждая из которых выполняет один запрос. При этом группа B при исполнении генерирует ещё объекты группы A. В этом случае важно в какой последовательности будут выполняться группы A и B.
Если сначала A, а потом B, то будет три SQL запроса.
SQL запрос в A
SQL запрос в B
SQL запрос в A
т. е. запросы вида A будут выполнены дважды, так как после выполнения B будут сгенерированы новые объекты A.
А если сначала B, а затем A, то SQL запроса будет всего два:
SQL запрос в B
SQL запрос в A
т. е. запросы из B добавятся в группу A и будут выполнены за один проход.
Объекты группировки, которые не генерируют новые объекты группировки, необходимо выполнять последними. Но пока не ясно насколько это актуально в реальной ситуации и как указывать приоритеты: вручную или автоматически. Как вариант ручного указания можно использовать такой код:
return Batching::create(Batching::LOW, function (Batch $batch) {
// ...
}, $id);
Т.е. первым параметром указывать приоритет. Если не указан, то = Batching::NORMAL
Послесловие
Изначально хотел сделать эту статью в виде поста, но размер оказался сильно больше.
Вроде идея лежит на поверхности, но не нашёл никакой реализации. Единственное упоминание встретил тут (Solving N+1 Problem). Но там это встроено в graphql-php. А вот в виде отдельного проекта ничего не нашёл. Либо не по тем ключевым словам искал, либо тут есть какой-то серьезный недостаток который я просто не увидел.
Так что буду рад если мне на этот недостаток укажут. В общем покритикуют идею перед тем как я начну её реализовывать.
UPDATE: Подсказали куда смотреть. Исправил названия в соответствии с правильными ключевыми словами, по которым нужно искать реализации алгоритма. Grouping=>Batching, Group=>Batch
Комментарии (10)
Anvano
17.07.2023 05:46+5На что только не идут люди, лишь бы не дать базе данных сделать её основную работу, для которой она была написана.
Вы уверены, что всё вышеописанное будет оптимальнее банального джойна внутри БД ?
shasoftX Автор
17.07.2023 05:46Конечно join будут оптимальнее. Но его придется писать руками для каждого случая. Ленивую загрузку в ORM не просто так придумали.
FanatPHP
17.07.2023 05:46Вы хотели сказать активную или жадную (eager) загрузку. А точнее, в данном случае речь идет не о конкретной реализации загрузки связанных сущностей, а о самой идее их получения автоматом. То есть ответ получается короче, "ORM не просто так придумали".
mcferden
17.07.2023 05:46join будет оптимальнее, если связь 1 к 1, а если на одну строку приходится 100 связанных, то придется по сети гонять дублированные данные, и тут же их отбросывать в приложении.
oracle_schwerpunkte
17.07.2023 05:46А здесь не понял. Что мешает отбрасывать их на уровне запроса? Заодно и план запроса улучшится, возможно, получится задействовать индексы и т.д.
mcferden
17.07.2023 05:46Предположим, что я хочу достать всех пользователей, и по каждому список профилей, которые он редактировал. Если я сделаю join в лоб, то данные из таблицы пользователей продублируются на каждый профиль.
У меня два варианта — агрегировать профили в запросе в какой-нибудь json (но это уже сложнее "банального джойна"), или тащить результат как есть в приложение и убирать дубликаты там.
LordDarklight
17.07.2023 05:46Данная схема будет работать только в случае если клиент готов сначала порционно сообщить всё что он хочет получить из БД - а потом подучить результат (как один пакет для единого получателя, так и в виде набора пакетов, с асинхронными подписчиками).
Иначе - очень сложно понять - а сколько же будет послано мелких запросов, и с какого момента надо начинать их группировать в общее ожидание. Да и само ожидание может быть очень не эффективным, особенно когда такие мелкие запросы связаны с интерактивной работой (что чаще всего и бывает). Тут тогда в реализации нужно сначала начинать асинхронное параллельное выполнение 1-2-х первых запросов, а уже следом ставить остальные однотипные запросы в очередь, и накапливать их по времени пока не выполнятся первые запросы (можно подождать ещё столько же - если накопление идёт раза в 2 быстрее, чем исполнение) и только затем запускать следующую порцию.
Но ни первой ни второй логики я в приведённой реализации не увидел.
И это не говоря ещё о кешировании - ведь такие запросы обычно часто ещё и повторяются и эффективно кешировать их результаты.
И тут проблема - если полагаться на СУБД - то при группировке запросов они для СУБД будут единым запросом - и именно его результат будет кэширован средствами СУБД - но если потом будут сформированы новые группы с частичным пересечением или вложением в ранее полученные - то для СУБД это будут новыми запросами и кеш не будет задействован. Да, безусловно, в СУБД есть ещё и кеширование физических элементов (например, страниц данных) в памяти (ну или вся СУБД In memory) - но это уже явно никак особенно сильно не скажется на приведённых в статье оптимизациях.
Эффективнее - это кешировать на стадии ОRM обработки и группировки запросов - но тут задача становится сложнее - ведь нужно правильно декомпозировать исходные запросы, идентифицировать ключ обращения к данным и формировать/получать по нему кеш, а потом ещё и обратно объединять результаты взятые из кеша и полученные из СУБД. И это всё очень не просто.
А если ещё и более глубоко подойти к анализу не совсем тривиальных условий - когда есть какая-то общая часть, а есть меняющаяся - то такое тоже надо определять и кешировать запрос по общей части, а по тривиальной уже делать фильтрацию по кэшированным (и "проиндексированным") в памяти ORM данным.
И при этом ещё надо следить за расходом памяти такого кеша - т.к. может не зря изначально запросы шли более узкими порциями друг за другом - может всё дело в больших объёмах самих порций, так и более общей выборки (без доп. условий).
В общем, такая постановка задачи только на первый взгляд кажется простой - а на деле тут скрыто много подводных камней и нюансов - для достижения реальной пользы от такой доп. обработки запросов внутри посредника (ORM)
shasoftX Автор
17.07.2023 05:46На самом деле при данной схеме понятно когда нужно начинать выполнять - когда мы дошли до точки ожидания результата (до начала event loop). Т.е. вот у нас есть код:
// Запустить event loop и получить результат $users = Batching::run(function (Batch $batch) { Batching::all([ getUserForId(1), getUserForId(2), getUserForId(3) ])->then(function (array $users) use ($batch) { // Устанавливаем результат для вызова // Именно он будет возвращен из функции Batching::run $batch->setResult(function () use ($users) { return $users; }); }); });
Замыкание выполнилось, в нем в event loop добавились задачи группировки. Их будет три штуки (так как три вызова функции getUserForId). И вот тут будут созданы три задачи
//-- Функция получения информации о пользователе function getUserForId(int $id): Batching { return Batching::create(function (Batch $batch) {...} }
После этого запустится event loop. Он объединит все эти задачи в один пакет, вызовет замыкание, которое в свою очередь добавит четыре задачи (три вызова функции getProfilesForUserId + Batching::all). Т.е. стандартный event loop и выполнением задач, отличие в том, что задачи группируются перед тем как отправится на выполнение.
Если нужно выполнить 1-2 запроса, то выполняем их в отдельном Batching::run(..), результат отправляем куда на нужно, а затем запускаем следующие задание.
Кэширование тут делается на стадии данных, которые возвращаются. т.е. если вы возвращаете строки, полученные из БД, то будут они кэшироваться. Вернете объекты ORM - закэшируются эти объекты.для достижения реальной пользы от такой доп. обработки запросов внутри посредника (ORM)
На самом деле тут как раз нет привязки к ORM или базе данных. Можно использовать API вообще без использование БД. К примеру требуется выгрузить файлы на FTP. Делаем вызовы, затем в пакетной обработке группируем по FTP серверам и производим загрузку. Если у нас несколько файлов для одного сервера, то будет установлено только одно соединение и через него все файлы загрузятся.
nogoody
Можете посмотреть dataloader в graphql https://github.com/graphql/dataloader
Есть куча реализаций на разных языках, в том числе на php
shasoftX Автор
Благодарю. Нашёл несколько реализаций. Как раз то что нужно
https://github.com/overblog/dataloader-php
https://github.2u2.cc/lordthorzonus/php-dataloader
Как я понял при беглом просмотре, там загрузка идет только по одному ключевому полю.