Зависит от смысла, вкладываемого в термин "обход 2D лабиринта".
Если про удобство реализуемости таких алгоритмов на SQL, то можно посмотреть варианты прошлогодних решений: раз, два, три. Если же про вычислительную эффективность, то сравнивать сложно - один мелкий шаг в алгоритме может его замедлить на порядок.
Просто в качестве примера: день 4 (читайте завтра пост) я сначала попробовал решить "втупую" переведя вход в двумерный массив - и за 20 минут запрос не досчитался.
Мне кажется, вы так и не поняли основную идею моей статьи, хотя она присутствует в первом же абзаце - что агрегаты-по-соединению можно заменить на функции от массива без всяких соединений.
А оба приведенные здесь плана отбрасывают примерно в 6 раз больше записей соединения, чем выдают полезных.
Так LATERAL подразумевает неявный вызов JOIN согласно документации?
В случае возврата из LATERAL единственной записи, в плане видно, что узлов соединений (Nested Loop, ... Join) не появляется. Вот если их хотя бы две, как вот тут, то приходится тратиться и на соединение.
Если немного развить тему, то можно "агрегацию" оконными функциями внести внутрь скобок:
SELECT
cli.id
, first_value dt
FROM
cli
, LATERAL (
SELECT
first_value(dt) OVER w
, nth_value(dt, 2) OVER w
FROM
doc
WHERE
cli = cli.id
WINDOW w AS(ORDER BY cli, dt DESC ROWS UNBOUNDED PRECEDING)
ORDER BY
cli, dt DESC
LIMIT 2
) doc
WHERE
cli.name LIKE '!%' AND
nth_value IS NOT NULL;
Но результат все равно чуть хуже из-за необходимости фильтрации "первых" записей при соединении:
Безусловно, если делать JOIN по уже заведомо ограниченной парой записей выборке, то агрегатные функции и группировка становятся гораздо менее неэффективными. Но издержки на соединение и группировку никуда не исчезают.
Если закинете планы на explain, будут более наглядно видны затраты на каждом из узлов. Разницу в последних примерах я отношу к погрешности измерений - у меня до 10% разброс между замерами получался, но в статью брал минимально достигнутые.
При отсутствии параллельных узлов операции плана выполняются последовательно. Или речь о нескольких одновременно запущенных запросах? Но это не влияет же на распределение user/system.
Но, в условиях высокой нагрузки и параллельности - разница в производительности на порядки.
Параллельность тут вообще не при чем. Ни в одном из моих планов она даже не пыталась использоваться.
Вывод: В тесте "MAX" CPU интенсивнее используется приложением, тогда как в "ARRAY" выше нагрузка на ядро.
Тут все достаточно очевидно - при агрегации доминируют затраты на JOIN, производимые как раз в usertime. При его отсутствии, за счет уменьшения общего времени, увеличивается доля чтений данных в systime.
Программа пишется для решения определенных задач за конкретные деньги.
ФОТ программистов легко конвертируется в затраты на "железо" и обратно. Грубо, чем проще написать программу, тем менее эффективно (долго, дорого) она будет выполняться. Иногда ради эффективности можно многим пожертвовать.
В традиционных бизнес-системах документы по клиентам имеют тенденцию повторяться неоднократно (счета ежемесячно, договора ежегодно, отгрузки постоянным клиентам, ...).
Можно вот так, и даже будет использоваться Run Condition:
WITH pre AS (
SELECT
cli.id
, dt
, row_number() OVER (PARTITION BY cli.id ORDER BY doc.dt DESC) rn
FROM
cli
JOIN
doc
ON doc.cli = cli.id
WHERE
cli.name LIKE '!%'
)
SELECT
id
, max(dt) OVER (PARTITION BY id) dt
FROM
pre
WHERE
rn = 2;
Имеется в виду "не хватает подходящего". Там на картинке в узле Index Scan rows=1, Rows Removed by Filter: 48668 - то есть мы вычитали тучу лишних записей ради одной нужной.
Еще с 9.1 требует не всегда. В какой-то из более поздних версий определение доступных к возврату столбцов было заменено на что-то типа "однозначно функционально вычислимые".
Тут, конечно, без плана исходного запроса добрая половина оптимизаций выглядит сделанной непонятно зачем, но попробуем зайти на задачу с точки зрения алгоритмов и прикладной логики.
Сформулируем условие: "Вывести TOP-50 активных (is_active = true) пользователей, у кого наберется хотя бы по 10K оборота, лидирующих по сумме (amount) отгрузок (status = 'completed') заказов, созданных (created_at) с 01.01.2023."
Из базовой прикладной логики можно предположить, что большинство пользователей, отгружавших на диапазоне последних 3 лет, будут активными и по сей день (и чем этот интервал меньше, тем больше вероятность, что все отгружавшие - активны).
По этой причине эффективнее сразу "схлопнуть" все заказы интервала по пользователю.
Потом подтягиваем активных пользователей к полученной выборке и не забываем посортировать снова после JOIN.
Как-то примерно так:
SELECT
u.id
, u.name
, o.order_count
, o.total_amount
FROM
(
SELECT
user_id
, count(id) order_count
, sum(amount) total_amount
FROM
orders
WHERE
status = 'completed' AND
created_at >= '2023-01-01'
GROUP BY
user_id
HAVING
total_amount > 10000
ORDER BY
total_amount DESC
LIMIT 50
) o
JOIN
users u
ON (u.id, u.is_active) = (o.user_id, TRUE)
ORDER BY
total_amount DESC;
И только после этого имеет смысл прикидывать, какие из индексов нам реально пригодятся тут:
CREATE INDEX ON orders(created_at) WHERE status = 'completed';
CREATE INDEX ON users(id) WHERE is_active = true;
Понятно, что индекс orders(user_id, created_at) тоже может быть полезен, но или не для этой задачи, или если разных пользователей у нас всего десяток-полтора.
Если входная строка конкретно такая, то она невалидна согласно условию 4-й задачи - пробелы после двух последних запятых. Поэтому "ничего" - как раз корректный ответ, по условию.
А если их (пробелы) убрать, то запрос выдаст DC43.
WITH gameparty AS (
SELECT
*
, parts[1] code
, regexp_split_to_array(parts[1], '') chars
, parts[2]::integer b
, parts[3]::integer c
FROM
regexp_split_to_table(upper(current_setting('bulls.gameparty')), ',')
WITH ORDINALITY T(step, n)
, regexp_match(step, '^([0-9A-F]{4}) (\d)B(\d)C$') parts -- заодно и формат проверяем
)
SELECT
xcode code
FROM
generate_series(0xFFFF, 0, -1) i -- нужен максимальный код, так что сразу генерим реверсивно (до первого подходящего, благодаря LIMIT)
, lpad(upper(to_hex(i)), 4, '0') xcode
, regexp_split_to_array(xcode, '') secret
, LATERAL (
SELECT
bool_and((b, c) = (xb, xc - xb)) chk -- совпадение быков/коров во всех ходах
FROM
gameparty
, LATERAL (
SELECT
count(*) FILTER(WHERE x = y) xb
FROM
unnest(chars, secret) T(x, y)
) b
, LATERAL (
SELECT
count(*) FILTER(WHERE x = ANY(secret)) xc
FROM
unnest(chars) T(x)
) c
) T
WHERE
NOT EXISTS ( -- при корректности кодов в исходнике
SELECT
NULL
FROM
gameparty
WHERE
code IS NULL OR
code ~ '(.).*\1'
LIMIT 1
) AND
xcode !~ '(.).*\1' AND -- отсекаем коды с повторными символами
chk -- оставляем только удовлетворившие всем ходам
LIMIT 1;
Зависит от смысла, вкладываемого в термин "обход 2D лабиринта".
Если про удобство реализуемости таких алгоритмов на SQL, то можно посмотреть варианты прошлогодних решений: раз, два, три. Если же про вычислительную эффективность, то сравнивать сложно - один мелкий шаг в алгоритме может его замедлить на порядок.
Просто в качестве примера: день 4 (читайте завтра пост) я сначала попробовал решить "втупую" переведя вход в двумерный массив - и за 20 минут запрос не досчитался.
Мне кажется, вы так и не поняли основную идею моей статьи, хотя она присутствует в первом же абзаце - что агрегаты-по-соединению можно заменить на функции от массива без всяких соединений.
А оба приведенные здесь плана отбрасывают примерно в 6 раз больше записей соединения, чем выдают полезных.
В случае возврата из
LATERALединственной записи, в плане видно, что узлов соединений (Nested Loop, ... Join) не появляется. Вот если их хотя бы две, как вот тут, то приходится тратиться и на соединение.Если немного развить тему, то можно "агрегацию" оконными функциями внести внутрь скобок:
Но результат все равно чуть хуже из-за необходимости фильтрации "первых" записей при соединении:
Безусловно, если делать JOIN по уже заведомо ограниченной парой записей выборке, то агрегатные функции и группировка становятся гораздо менее неэффективными. Но издержки на соединение и группировку никуда не исчезают.
Если закинете планы на explain, будут более наглядно видны затраты на каждом из узлов. Разницу в последних примерах я отношу к погрешности измерений - у меня до 10% разброс между замерами получался, но в статью брал минимально достигнутые.
При отсутствии параллельных узлов операции плана выполняются последовательно. Или речь о нескольких одновременно запущенных запросах? Но это не влияет же на распределение user/system.
Параллельность тут вообще не при чем. Ни в одном из моих планов она даже не пыталась использоваться.
Тут все достаточно очевидно - при агрегации доминируют затраты на JOIN, производимые как раз в usertime. При его отсутствии, за счет уменьшения общего времени, увеличивается доля чтений данных в systime.
LIMIT 2 - это чтобы нашлась вторая запись, если она есть - чтобы проверить условие задачи "документов по нему несколько".
Программа пишется для решения определенных задач за конкретные деньги.
ФОТ программистов легко конвертируется в затраты на "железо" и обратно. Грубо, чем проще написать программу, тем менее эффективно (долго, дорого) она будет выполняться. Иногда ради эффективности можно многим пожертвовать.
CTE не пишется на диск (
temp buffers), пока влезает в work_memв PG массивы нумеруются с 1, а не с 0
В традиционных бизнес-системах документы по клиентам имеют тенденцию повторяться неоднократно (счета ежемесячно, договора ежегодно, отгрузки постоянным клиентам, ...).
"Не считает" или "не читает"?
Можно вот так, и даже будет использоваться
Run Condition:Только медленнее в 1.5 раза от исходного:
Даже на PG16 это не работает, не говоря о более ранних версиях:
Ну и параллелиться
WindowAggпока не умеет.Кроме того, подсчет номера записи в выборке все-таки требует иметь эту выборку (полный JOIN) "под ногами" - то есть грабли ровно те же.
Имеется в виду "не хватает подходящего". Там на картинке в узле Index Scan rows=1, Rows Removed by Filter: 48668 - то есть мы вычитали тучу лишних записей ради одной нужной.
https://www.postgresql.org/docs/release/9.1.0/
Еще с 9.1 требует не всегда. В какой-то из более поздних версий определение доступных к возврату столбцов было заменено на что-то типа "однозначно функционально вычислимые".
Причина еще может крыться в привычке писать как в моем примере ниже:
JOIN users u ON (u.id, u.is_active) = (o.user_id, TRUE)vs.
JOIN users u ON u.id = o.user_id AND u.is_active10M - это еще маловато для секционирования, пожалуй. Да и агрегаты тут явно избыточны, если итоговый запрос пока уложился в 120ms.
Тут, конечно, без плана исходного запроса добрая половина оптимизаций выглядит сделанной непонятно зачем, но попробуем зайти на задачу с точки зрения алгоритмов и прикладной логики.
Сформулируем условие: "Вывести TOP-50 активных (
is_active = true) пользователей, у кого наберется хотя бы по 10K оборота, лидирующих по сумме (amount) отгрузок (status = 'completed') заказов, созданных (created_at) с 01.01.2023."Из базовой прикладной логики можно предположить, что большинство пользователей, отгружавших на диапазоне последних 3 лет, будут активными и по сей день (и чем этот интервал меньше, тем больше вероятность, что все отгружавшие - активны).
По этой причине эффективнее сразу "схлопнуть" все заказы интервала по пользователю.
Потом подтягиваем активных пользователей к полученной выборке и не забываем посортировать снова после JOIN.
Как-то примерно так:
И только после этого имеет смысл прикидывать, какие из индексов нам реально пригодятся тут:
Понятно, что индекс
orders(user_id, created_at)тоже может быть полезен, но или не для этой задачи, или если разных пользователей у нас всего десяток-полтора.Если входная строка конкретно такая, то она невалидна согласно условию 4-й задачи - пробелы после двух последних запятых. Поэтому "ничего" - как раз корректный ответ, по условию.
А если их (пробелы) убрать, то запрос выдаст
DC43.5-я задача на основе предыдущего варианта: