Комментарии 29
SELECT * FROM deals
JOIN customers ON deal.customer_id = customers.id
JOIN managers ON deal.manager_id = managers.idА вот тут только меня смущает, что все данные кастомера и менеджера дублируются 100500 раз? С этим правда ничего не сделать? Может быть, как-нибудь, ну я не знаю, выполнить задачу без джойнов? Ну, что-нибудь типа такого:
SELECT *, customer:{*}, manager:{*} FROM DealА спросил что-то настолько абсурдное, что серьёзные люди не зают что ответить?
Ну... наверное просто для хабра вопрос странноват.
Это как бы даже не основы, а основы основ. Нормализация баз данных, нормальные формы (1НФ, 2НФ, 3НФ, НФБН, 4НФ).
Когда нужна нормализация, а когда наоборот - денормализация.
А, ну да, на Хабре же никто глубже основы реляционной алгебры не копал, про другие модели хранения данных не в курсе, про мультимодельные субд на слышал, чего это я..
Если что, второй пример запроса - это OSQL из OrientDB, в доке которой можно подтянуть и теорию по моделям данных.
Статья про оптимизатор запросов в реляционной СУБД
Лучшая война - та, которая не началась (с) СУНЬ-ЦЗЫ
Ну и определитесь уж, реляционная у вас СУБД или гибридная. И является ли она чем-то прогрессивным, или очередным переизобретением кривого велосипеда, выдающего любые данные в виде одной большой денормализованной таблички с многократным дублированием одних и тех же данных, которые приходится обратно нормализовывать в прикладном коде.
YDB гибридная реляционная СУБД, что означает, что она поддерживает высокие OLTP нагрузки одновременно с тяжелыми OLAP запросами. Авторы YDB в свое время и XML СУБД разрабатывали, и как показывает многолетняя практика, реляционные СУБД отлично справляются со всеми современными вызовами. Предлагаю в комментариях обсуждать статью, а не модели данных для СУБД
Статья о том, как вы героически боретесь с проблемой, которой могло бы и не быть вовсе, используй вы опыт современных СУБД. И достигнуть этого вы можете сравнительно небольшим рефакторингом:
Первичный ключ делаете персистентным автоинкрементом с O(1) поиском.
Вводите тип данных "ссылка на запись в другой таблице".
Модифицируете язык запросов, чтобы вместо каскада из O(log) джойнов использовать O(1) траверсинг по ссылкам.
Модифицируете формат ответа, чтобы возвращать не денормализованную табличку, а множество нормализованных табличек.
Вы описали обычную графовую базу, которая умеет только лукавы. В графовых СУБД оптимизация запросов ничем не проще, чем реляционный и можете почитать работу DuckPGQ где на реляционной базе 10х перебивается Neo4j. При этом есть кейсы где графы действительно полезны, когда например по одному большому графу мы ходим в глубину. Поэтому мы внимательно следим за этой темой и какой-то графовой функционал в формате PGW будем реализовывать в будущем
Я описал тогда уж объектную базу, на основе которой уже можно реализовать графовое апи, но это часто не практично. Ключевое отличие - в объектной базе ссылки легковесные и односторонние, а в графовой они всегда двусторонние и не всегда легковесные. Также обратите внимание, что ни таблички, ни индексы я у вас не забирал - только джойны. Ну а если предлагаете что-то почитать - прилагайте ссылки.
В графовых базах есть как односторонние так и двусторонние ребра, но не суть.
Такие вот легковесные ссылки во первых только на лукапах дают большое преимущество, а у нас полно запросов со значительным сканированием в аналитике. Потом поддерживать такие ссылки на больших объемах данных очень непростое дело и вредит производительности больше чем помогает.
Вот статья о том, как на DuckDB реализовали PGQ и побили Neo4j 10x: https://duckpgq.org/
В графовой базе рёбра бывают направленными и ненаправленными. В обоих случаях они описываются минимум двумя ссылками: прямой и обратной, чтобы по ним можно было ходить в обе стороны. Объектная не имеет такого ограничения.
Поддерживать индекс дешевле, чем делать каждый раз "значительное сканирование". Особенно на больших объёмах. Особенно, когда нужен мониторинг этой аналитики.
Впрочем, приведите пример такого запроса, подумаем вместе, как в нём избавиться не только от джойнов, но и от сканирования.
Это ссылка на сайт, а не на статью.
На сайте есть и ссылки на статьи и имплементация в DuckDB
Поддерживать прямые ссылки приходится используя технику pointer swizzling и на больших объемах и при больших вставлениях это все ужасно работает, поэтому и не используется.
Объектные базы данных были интересны в 90-ых, что-то они очень удобно и хорошо делали, сам пользовался O2 в свое время. Графовые СУБД сейчас что-то интересное показывают, но только на узких сценариях. С графовыми я сам плотно работал, разрабатывая оптимизатор запросов в TigerGraph
Возьмите те же самые аналитические бенчмарки TPCH и TPCDS и попробуйте конкурировать с реляционными базами, а работе DuckPGQ сравнение на графовом бенчмарке
Рука, наверно, отсохнет, если скопипастить прямую ссылку на статью, на которую вы ссылаетесь..
Хз, при чём тут "pointer swizzling", но прямые ссылки реализуются довольно просто и работают весьма быстро - нужно лишь 2 хопа, чтобы по ним перейти. Обновляются в одном месте. А резолвинг внешних идентификаторов, если вы про них, не влияет на стоимость траверсинга по внутренним.
С чем вы там в 90-х работали к теме обсуждения не относится. Мы тут не на собеседовании.
Ну ок, вот, я взял оттуда первый попавшийся селект c 4+3 джойнами и одному планировщику известной стоимостью:
select
s_acctbal,
s_name,
n_name,
p_partkey,
p_mfgr,
s_address,
s_phone,
s_comment
from
part,
supplier,
partsupp,
nation,
region
where
p_partkey = ps_partkey
and s_suppkey = ps_suppkey
and p_size = '[SIZE]'
and p_type like '%[TYPE]'
and s_nationkey = n_nationkey
and n_regionkey = r_regionkey
and r_name = '[REGION]'
and ps_supplycost = (
select
min(ps_supplycost)
from
partsupp,
supplier,
nation,
region
where
p_partkey = ps_partkey
and s_suppkey = ps_suppkey
and s_nationkey = n_nationkey
and n_regionkey = r_regionkey
and r_name = '[REGION]'
)
order by
s_acctbal desc,
n_name,
s_name,
p_partkey;А вот тот же запрос без джойнов с очевидной O(n), где n - общее число предложений искомой детали:
-- O(part.partsup) --
SELECT
part:{mfgr},
supply:{
acctbal,
name,
nation:{name},
address,
phone,
comment
}
FROM (
-- O(log(Part)) --
SELECT partsupp
FROM Part
WHERE (
type BEGINS_FROM $type
) AND (
size = $size
)
)
WHERE (
supplycost = MIN(supplycost)
) AND (
supplier.nation.region = $region
)
Основная проблема оптимизаторов что в оракле что в постгрес для больших таблиц с постоянно меняющимися большими объёмами данных это когда собиралась статистика для выполняющегося запроса.
Я правильно понял, что у вас тоже сбор идет по каким то своим эвристикам с не очень прозрачным итоговым прогнозом по частоте сбора? Ну то есть план может спокойно плавать на одних и тех же запросах в зависимости от того когда собиралась статистика, что там в ней сейчас, и насколько она соответствует текущей ситуации в таблице?
Нет, у нас сбор статистики идет на компакшене, то есть совсем немного запаздывает от вставки.
А ваши колеги, которые пилят ClickHouse - у них нет оптимизации соединений (точнее в документации они написали: "В настоящее время ClickHouse не переставляет соединения").
Точно ли вот это нужно из-за того что человек не справляется на 6 джоинах или это все-таки для того чтобы порог входа сократить до, кхм, определенного уровня когда не знаешь струтуру БД?
Какой самый сложный запрос с JOIN'ами вам доводилось оптимизировать?
Предпочитаю в деталях знать схему данных, их взаимосвязь и пропорции объемов. Для каждого отдельного случая какого-то запроса представлять работу процессора(итератора) запроса, и подставлять ему такой flow, который понятен и более менее оптимален. Если обладать такими знаниями о собственной системе, то вручную составленный запрос дает стабильно идентичную производительность, хорошую или плохую - второстепенно, первостепенно - одинаковую стабильную, можно улучшать свои знания и оптимизировать, в итоге опять получать стабильную производительность. При росте объема данных конечно можем получить падение скорости, но это ожидаемо. А что, если ваш оптимизатор безошибочно сработал по стоимостям и заложенному алгоритму, но сделал итоговую производительность хуже, чем по изначальному запросу? Что, если стоимости динамично меняются, и план запроса в итоге меняется, и в итоге производительность "флакает"? В чем формальное доказательство, что именно написанный Вами алгоритм подбора по стоимостям дает какой-то плюс-минус оптимальный результат? Ведь пока вы его не прогоните на полном объеме данных и не сделаете замер, до этого момента все "догадки", некая стоимость Шрёдингера, простите. Не ради троллинга, правда хотелось бы узнать, как быть уверенным, что оптимизация не сломала изначально хороший запрос?
Изначально хороших запросов в аналитике (когда сложный план, много джоинов и возможны разные варианты доступа к данным) нет. Тот SQL который вы напишете недоопределен - там порядок джоинов фиксирован, но не выбраны алгоритмы и access paths (способы доступа к данным). Поэтому все аналитические СУБД используют стоимостные оптимизаторы.
Конечно, оптимизатор может ошибаться и оптимальность не гарантирована. Если производительность не устраивает после оптимизации и есть подозрение, что можно улучшить план, который сделал оптимизатор, можно посмотреть на EXPLAIN ANALYZE и попробовать подсказать какие-то детали оптимизатору в местах, где видно, что он ошибся. Это делается с помощью хинтов запросов
Тот SQL который вы напишете недоопределен - там порядок джоинов фиксирован, но не выбраны алгоритмы и access paths (способы доступа к данным). Поэтому все аналитические СУБД используют стоимостные оптимизаторы.
А я наброшу. Кажется, что для решения этих проблем стоимостный оптимизатор не обязателен:
Алгоритмы можно выбирать по простым правилам, например: merge при совпадении сортировок, nested loop для кореллированных соединений, а в остальных случаях - hash.
Методы доступа к данным (т.е. выбор индексов) выбираются по предикатам в фильтрах. По принципу «видим подходящий индекс для фильтра - используем, не видим - используем обычную таблицу).
То есть технически можно пойти по пути sqlite и не использовать стоимостную модель. И дальше все в руках авторов запросов, так как правила очень простые. И если автор захочет где-то материализацию и новую сортировку, то он сделает руками нужный cte (а не планировщик будет пытаться переписать суть плана за человека).
Мой опыт говорит, что когда ты пишешь сложные запросы, ты борешься с планировщиком и пытаешься его хакнуть через хинты или разные конструкции в sql. И самый главный страх, что на новой статистике план изменится, планировщик построит ерунду и запрос начнет исполняться очень долго.
Практика показывает, что 99.9% пользователей не готовы и не умеют оптимизировать свои сложные запросы, да и сама задумка SQL - это декларативность, вы пишите что вы хотите от СУБД, а она сама находил лучший план как это обеспечить. Для меняющейся статистики и такого рода страхов есть инструменты, как прикопать конкретный план, который понравился - пока в YDB не реализовано, но скоро сделаем, на подобие как сделано в TiDB.
Если ну очень хочется все самому - можно полностью захинтовать запрос
Стоимостной оптимизатор: сердце гибридной базы данных YDB