LINUX.ORG.RU

SQL движок с ноля

 , , ,


0

2

Я уже упоминал, что делаю SQL-движок с нуля. Модель исполнения построена на базе моего компилятора Qumir (https://qumir.dev).

Пайплайн выглядит так:

SQL parser -> AST -> logical plan -> optimization passes -> physical plan -> Qumir kernels -> execution graph

Поскольку движок построен на Qumir, появилась возможность практически из коробки встраивать функции на языке Кумир в SQL-запросы через CREATE FUNCTION.

Пощупать можно тут: https://db.qumir.dev

А теперь просто цифры бенчмарков на M5 Pro (измеряется только processing, без фазы llvm):

Clickbench:

Queryqdb (s)DuckDB (s)ClickHouse (s)qdb ÷ DuckDBqdb ÷ ClickHouse
q00.0130.0400.1300.33×0.10×
q10.0160.0500.1200.32×0.13×
q20.0460.0700.1300.65×0.35×
q30.0390.0700.1300.56×0.30×
q40.1750.1600.2001.09×0.87×
q50.2170.2300.2500.94×0.87×
q60.0230.0900.1200.26×0.19×
q70.0110.0500.1200.22×0.09×
q80.2640.2000.2801.32×0.94×
q90.3240.2700.3301.20×0.98×
q100.1130.1000.2001.13×0.57×
q110.1350.1100.2101.23×0.64×
q120.2620.2300.2701.14×0.97×
q130.5000.3600.3701.39×1.35×
q140.2410.2600.3400.93×0.71×
q150.2100.1900.2001.11×1.05×
q160.3830.4300.5000.89×0.77×
q170.3780.3500.2901.08×1.30×
q180.6490.6800.8500.96×0.76×
q190.0810.0500.1201.62×0.68×
q200.3880.4100.5800.95×0.67×
q210.4360.3500.6501.24×0.67×
q220.7680.6200.9601.24×0.80×
q230.4920.5300.6800.93×0.72×
q240.1480.2000.3200.74×0.46×
q250.1250.1700.2300.73×0.54×
q260.1490.2100.3300.71×0.45×
q270.3610.3400.6301.06×0.57×
q280.8843.5600.6800.25×1.30×
q290.0320.0600.1300.53×0.24×
q300.2330.2800.4300.83×0.54×
q310.2610.3100.4700.84×0.55×
q320.7180.7800.8700.92×0.82×
q331.0570.8800.9001.20×1.17×
q341.0650.9200.9001.16×1.18×
q350.1890.2500.1800.76×1.05×
q360.0340.1000.1300.34×0.26×
q370.0250.0900.1200.28×0.21×
q380.0270.0700.1100.39×0.25×
q390.0720.1400.1500.51×0.48×
q400.0110.0600.1200.18×0.09×
q410.0140.0600.1200.23×0.12×
q420.0080.0600.1000.13×0.08×
total11.57714.4414.950.80×0.77×

TPCH-100

Queryqdb (s)DuckDB (s)DataFusion (s)ClickHouse (s)qdb ÷ DuckDBqdb ÷ DataFusionqdb ÷ ClickHouse
q11.5422.2001.653.300.70×0.93×0.47×
q20.5520.4200.560.771.31×0.99×0.72×
q31.6831.3901.1930.181.21×1.41×0.06×
q41.0820.9300.591.101.16×1.83×0.98×
q52.5121.4501.8754.381.73×1.34×0.05×
q60.5910.8700.651.430.68×0.91×0.41×
q71.7861.3503.084.051.32×0.58×0.44×
q81.3281.5701.68110.260.85×0.79×0.01×
q92.9633.0903.23120.440.96×0.92×0.02×
q102.1231.7701.743.881.20×1.22×0.55×
q110.2720.2600.420.651.05×0.65×0.42×
q121.3831.0900.923.421.27×1.50×0.40×
q133.1982.1901.753.021.46×1.83×1.06×
q140.7831.1300.781.660.69×1.00×0.47×
q150.6961.0800.713.070.64×0.98×0.23×
q160.5540.4600.410.521.20×1.35×1.07×
q170.9981.2803.762.140.78×0.27×0.47×
q182.0402.30029.721.930.89×0.07×1.06×
q191.9561.6101.002.851.21×1.96×0.69×
q200.8481.1601.151.860.73×0.74×0.46×
q213.4093.8905.468.740.88×0.62×0.39×
q220.5440.6100.360.590.89×1.51×0.92×
total32.84332.1062.680360.2401.02×0.52×0.09×

TPCDS-100

Queryqdb (s)DuckDB (s)qdb ÷ DuckDB
q10.1430.2000.72×
q20.9650.5201.86×
q30.4700.4301.09×
q46.8763.5601.93×
q52.0611.2001.72×
q60.3710.6100.61×
q70.9810.8501.15×
q83.7510.6405.86×
q94.0483.2501.25×
q100.5560.4101.36×
q114.0452.1601.87×
q120.1560.1800.87×
q131.6791.8000.93×
q1411.7757.7201.53×
q150.2730.2201.24×
q160.7690.1505.13×
q170.9200.7701.19×
q180.8950.3602.49×
q190.7180.7300.98×
q200.2070.1101.88×
q210.3940.0804.92×
q224.2972.0702.08×
q2318.16412.701.43×
q241.3991.9900.70×
q251.1260.9401.20×
q260.5340.2002.67×
q270.9870.8401.17×
q283.8962.9801.31×
q290.8530.9600.89×
q300.2270.1701.34×
q310.9440.7401.28×
q320.3710.0904.12×
q330.9200.6801.35×
q340.7460.6701.11×
q350.7300.8100.90×
q360.9251.0200.91×
q370.3620.1402.59×
q381.4680.8001.84×
q391.3430.3304.07×
q400.8100.2004.05×
q410.0700.0401.75×
q420.5050.4501.12×
q430.6950.5301.31×
q441.6011.1401.40×
q450.2290.2900.79×
q461.3851.3701.01×
q472.6141.1702.23×
q481.2901.2401.04×
q491.4621.2901.13×
q500.6610.7800.85×
q513.1082.9101.07×
q520.5200.4701.11×
q530.5380.4801.12×
q540.7540.6301.20×
q550.4490.4700.96×
q560.8970.6901.30×
q571.0690.3602.97×
q580.6940.5901.18×
q591.7911.3701.31×
q600.9960.7401.35×
q611.2450.09013.83×
q620.4560.2102.17×
q630.5400.4801.13×
q644.3482.4001.81×
q651.7460.8801.98×
q660.8550.4701.82×
q6738.70011.693.31×
q681.2821.5200.84×
q690.5480.4401.25×
q702.1480.7103.02×
q711.0030.8401.19×
q721.5111.1201.35×
q730.6150.6600.93×
q742.7731.8401.51×
q752.8391.8201.56×
q760.9401.0600.89×
q771.3511.1001.23×
q7811.6223.0703.79×
q791.5081.4701.03×
q804.3031.8702.30×
q810.2780.1701.64×
q820.4610.2401.92×
q830.0800.1200.67×
q840.1210.1300.93×
q850.4660.8300.56×
q860.2390.2001.19×
q872.1010.9102.31×
q883.5022.6901.30×
q890.7980.5601.43×
q900.2070.1301.59×
q910.0860.1200.72×
q920.2300.2201.05×
q930.5991.3600.44×
q940.3920.3601.09×
q9514.0492.6305.34×
q960.4230.3801.11×
q973.3810.9903.42×
q980.5530.5501.01×
q990.8930.2403.72×
total212.676117.861.80×
★★★★★

Последнее исправление: Reset (всего исправлений: 1)

Я думаю, у всех вопрос - а зачем вы пытаетесь развить язык Кумир? Ведь этот язык построен на основе школьного алгоритмического языка, который предназначен для исполнения людьми, а не компьютерами.

anonymous
()
Ответ на: комментарий от anonymous

Я думаю, у всех вопрос - а зачем вы пытаетесь развить язык Кумир?

Я его не развиваю. Язык Кумир фиксирован. Трансляция у меня выглядит так кумир -> s-expr -> qumir-ir -> [llvm or qumir-bytecode]. Для sql сразу в s-expr минуя кумир фазу, так как s-expr гораздо богаче.

Reset ★★★★★
() автор топика
Ответ на: комментарий от firkax

Что такое q1 q2 итд?

Номера запросов. Каждый бенчмарк содержит набор фиксированных запросов.

И учтена ли как-то в бенчмарках высокая параллельная нагрузка?

Учтена. Используется везде 18 потоков. distributed (меж-нодовое) исполнение у меня в процессе разработки, оно будет скоро.

Reset ★★★★★
() автор топика

встраивать функции на языке Кумир в

использовать Трава

алг ВластелинSQL
нач
  . если впереди стена
  . . то
  . . . апстену
  . . иначе
  . . . дунуть
  . все
кон
aol ★★★★★
()
Ответ на: комментарий от aol

Вот так можно:

https://db.qumir.dev/?s=l0L9-G2ofAXg

CREATE MODULE orbital
LANGUAGE kumir
AS $$
алг вещ orbit_perihelion_au(вещ a, e)
нач
    знач := a * (1.0 - e)
кон

алг вещ orbit_aphelion_au(вещ a, e)
нач
    знач := a * (1.0 + e)
кон

алг вещ orbit_period_days(вещ a)
нач
    | Третий закон Кеплера для гелиоцентрической орбиты, a в а.е.
    знач := 365.2568983 * sqrt(a * a * a)
кон

алг вещ orbit_mean_motion_deg_day(вещ a)
нач
    знач := 360.0 / orbit_period_days(a)
кон

алг лог orbit_is_neo(вещ a, e)
нач
    знач := orbit_perihelion_au(a, e) < 1.3
кон
$$;

SELECT
    a.designation,
    t.timestamp AS timestamp,
    a.m + orbit_mean_motion_deg_day(a.a) * (t.timestamp - a.epoch) AS mean_anomaly,
    orbit_perihelion_au(a.a, a.e) AS perihelion_au,
    orbit_aphelion_au(a.a, a.e) AS aphelion_au
FROM unnumbered_asteroids a
CROSS JOIN timestamps t
WHERE
    orbit_is_neo(a.a, a.e)
    AND a.e < 0.1
    AND t.timestamp >= 61564
    AND t.timestamp < 61565
LIMIT 10;
Reset ★★★★★
() автор топика

Жалко что синтаксис языка программирования на русском не располагает к программированию, а только к матерщине

superuser ★★★★☆
()

В целом крайне любопытное занятие, как по мне.

Сугубо из любопытства: скажите, есть ли какие то намётки на практическое применение? Или это пока фор фан?

AndreyKl ★★★★★
()
Последнее исправление: AndreyKl (всего исправлений: 1)
Ответ на: комментарий от stave

Да. От бд тут только SQL движок :) Мне (пока) не очень интересно делать storage и слой транзакций. Если будут желающие то я приму коммиты.

Reset ★★★★★
() автор топика
Ответ на: комментарий от Reset

Parquet - де-факто стандарт колоночного хранения в Big Data и табличной аналитике, а не универсальный стандарт аналитических данных.

steemandlinux ★★★★★
()
Ответ на: комментарий от Reset

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

Хотя если внутрь гидру засунуть то хз.

ya-betmen ★★★★★
()
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от ya-betmen

Вот в том то и дело, что луше в твою балалайку кинуть пгбенч и посмотреть чего она может.Хотя если внутрь гидру засунуть то хз.

OLTP out of scope

Reset ★★★★★
() автор топика

Сломал своими таблицами всю верстку на телефоне.

anonymous
()

Может лучше сразу на ЯОС? Кумир нежизнеспособный совсем язык, в нём жёстко не хватает структур данных. Для реализации SQL-движка они нужны. При всём уважении к памяти акад.Ершова, мы сейчас живём в другое время. У меня там даже эрзац-лисп с эрзац-прологом где-то были, надо покопать.

den73 ★★★★★
()
Последнее исправление: den73 (всего исправлений: 2)
Ответ на: комментарий от den73

Кумир это один из фронтов. Внутри там очень богатый язык. Вот например https://github.com/QumirLabs/qumirdb/blob/master/qdb/kernel/aggregation/aggregation_hashtable_generic.oz

Reset ★★★★★
() автор топика
Последнее исправление: Reset (всего исправлений: 1)

с ноля

с нуля

Нет тут доверия к указателям.

anonymous
()
Ответ на: комментарий от den73

При всём уважении к памяти акад.Ершова, мы сейчас живём в другое время.

А.П.Ершов не придумывал Кумир. Кумир придумали совсем другие люди, не знавшие Ершова даже. Кумир основан на школьном алгоритмическом языке, который не является языком программирования, он не приспособлен для исполнения на компьютере, а только головой человека. Ершов придумал язык программирования Рапира, и там есть и модули, и записи, и кортежи/массивы, и множества, и строки. Изучайте классиков.

anonymous
()
Ответ на: комментарий от anonymous

Такая концепция, как отображение и «объект на куче со ссылочной семантикой присваивания», прекрасно помещается в голове человека. Это она в компьютере хуже помещается. Неясно, зачем нужен этот язык сегодня. Как хороший первый язык годится Scratch - там сразу параллельность, причём в наглядной форме. Если я ошибся и зря приписал Ершову ШАЯ, то прошу прощения.

den73 ★★★★★
()
Последнее исправление: den73 (всего исправлений: 1)
Ответ на: комментарий от den73

Это мой собственный язык. Каждая открывающая скобка это ast нода. Удобно как писать текст так и строить программу из программы. Язык в процессе развития

Reset ★★★★★
() автор топика
Ответ на: комментарий от Reset

Понятно, только одно печалит - это llvm. Я отстал от поезда и попал в криокамеру, а сборка мусора есть в llvm вообще и в твоём языке в частности?

den73 ★★★★★
()
Ответ на: комментарий от den73

У меня нет сборки мусора до тех пор пока она мне не нужна. У меня сейчас два бэкенда это llvm и байт-код для моей vm. Я буду экспериментировать с еще одним так как время компиляции llvm меня совсем не устраивает

Reset ★★★★★
() автор топика
Последнее исправление: Reset (всего исправлений: 1)
Ответ на: комментарий от den73

Кстати для sql не нужен gc. Я используют трекер памяти в thread local и если что то не почистилось явно то оно почистится при завершении запроса. Все максимально просто

Reset ★★★★★
() автор топика
Ответ на: комментарий от Reset

Ну, если считать gc - фичей, а delete() - её отсутствием, то может быть и не нужен. А если считать gc одной фичей, а delete() - другой фичей, то с тем же успехом и delete() для sql не нужен - сборки мусора вполне достаточно. И высказывание про «в языке не будет gc, пока он не понадобится», можно также перевернуть и сказать «в языке не будет delete() пока он не понадобится». А в языке, который я ковырял, есть и то, и другое, правда, лучше им вместе не встречаться.

den73 ★★★★★
()
Последнее исправление: den73 (всего исправлений: 3)
Ответ на: комментарий от den73

А в Кумире, кстати, нет ни того не другого. Хотя можно реализовать динамическую память через строки переменной длины (наверное; дипсик говорит, что есть строки произвольной, до технических пределов, длины). Строки иммутабельные, поэтому для записи нужно резать и клеить. Ирония здесь в том, что когда в Дельфи сделали иммутабельные строки, то понадобился сборщик мусора. И это «жжжж» неспроста.

den73 ★★★★★
()
Последнее исправление: den73 (всего исправлений: 1)
Ответ на: комментарий от Reset

Поздравляю, ты изобрёл ранне-пхпшную модель памяти.

А вообще, насчёт «само почистится» - не везде, надо ж ещё кеши хранить. А так же иметь какую-то стратегию какой их низ выкидывать когда нужно новое туда доложить.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Я ничего не изобретал, все sql движки по такой схеме работают. Кеши это отдельная тема.

Вот например в ydb этот BindAllocator делает ровно тоже самое: https://github.com/ydb-platform/ydb/blob/f5af00bb6bf12d8da6160946f4c76f60ab95df55/yql/essentials/minikql/mkql_node.h#L453

Reset ★★★★★
() автор топика
Последнее исправление: Reset (всего исправлений: 1)

эти увлекательнейшие и очень занимательные таблицы восхищают.

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

max_lapshin ★★★★★
()
Ответ на: комментарий от max_lapshin

Я делаю компилируемый движок. Таких движков не много на самом деле. Компиляция дает скорость (видно на тесте clickbench), но оптимизатор плана еще не достаточно хорош, поэтому есть отставание от duckdb в tpcds вдвое. Tpcds содержит очень сложные запросы с кучей джойнов и коррелированных подзапросов. Декорреляттор у меня сейчас работает на эвристиках, поэтому не может все правильно сделать. Я буду его переписывать по статьям Ноймана.

Reset ★★★★★
() автор топика
Ответ на: комментарий от Reset

Но кстати отставание от duckdb в tpcds это не так плохо на самом деле. Многие движки вообще не в состоянии этот бенчмарк пройти. Например, clickhouse и dataFusion не проходят. Postgres строит ужасающие планы и бенчмарк за разумное время отработать не может.

Reset ★★★★★
() автор топика
Ответ на: комментарий от zurg

генерация:

#!/bin/sh
mkdir -p "$1"
duckdb -c "COPY (
  SELECT DATE '2000-01-01' + CAST(i AS INTEGER) AS date,
         CAST(random() < 0.7 AS INTEGER) AS value
  FROM range(${2:-1000000}) t(i) ORDER BY date
) TO '$1/t.parquet' (FORMAT parquet)"
./gen.sh data20 20
parquet cat data20/t.parquet
{"date": 10957, "value": 1}
{"date": 10958, "value": 1}
{"date": 10959, "value": 1}
{"date": 10960, "value": 0}
{"date": 10961, "value": 0}
{"date": 10962, "value": 1}
{"date": 10963, "value": 1}
{"date": 10964, "value": 1}
{"date": 10965, "value": 1}
{"date": 10966, "value": 1}
{"date": 10967, "value": 1}
{"date": 10968, "value": 1}
{"date": 10969, "value": 1}
{"date": 10970, "value": 1}
{"date": 10971, "value": 1}
{"date": 10972, "value": 0}
{"date": 10973, "value": 1}
{"date": 10974, "value": 1}
{"date": 10975, "value": 1}
{"date": 10976, "value": 1}

процессинг:

qdb --data data <<'SQL'
SELECT "date", value,
       CASE WHEN value = 1 THEN fwd + bwd - 1 ELSE 0 END AS n
FROM (
  SELECT "date", value,
         sum(value) OVER (PARTITION BY grp ORDER BY "date")      AS fwd,
         sum(value) OVER (PARTITION BY grp ORDER BY "date" DESC) AS bwd
  FROM (
    SELECT "date", value,
           sum(1 - value) OVER (ORDER BY "date") AS grp
    FROM t
  ) a
) b
ORDER BY "date";
SQL
date  | value | n 
------+-------+---
10957 |     1 |  3
10958 |     1 |  3
10959 |     1 |  3
10960 |     0 |  0
10961 |     0 |  0
10962 |     1 | 10
10963 |     1 | 10
10964 |     1 | 10
10965 |     1 | 10
10966 |     1 | 10
10967 |     1 | 10
10968 |     1 | 10
10969 |     1 | 10
10970 |     1 | 10
10971 |     1 | 10
10972 |     0 |  0
10973 |     1 |  4
10974 |     1 |  4
10975 |     1 |  4
10976 |     1 |  4
Returned 20 rows in 0.00164283 seconds
Reset ★★★★★
() автор топика

Я уже упоминал, что делаю SQL-движок с нуля.

Откуда у тебя такое желание заниматься тем, что никому не нужно и вряд ли будет нужно когда-либо? Я ещё могу понять, что на работе по найму задачи однообразные и поэтому человек может захотеть сделать что-нибудь эдакое в свободное от работы время, но зачем делать ерунду-то? Не лучше ли направить силы на полезное людям дело? Если сам придумать ничего толкового не можешь, то нужно объединяться с людьми, которые чувствуют людей и знают что именно делать и как, чтобы усилия пошли впрок и себе и людям.

/Энтузиаст/

anonymous
()
  • Markdown
Пустая строка (два раза Enter) начинает новый абзац. Знак '>' в начале абзаца выделяет абзац курсивом цитирования.
Внимание: прочитайте описание разметки Markdown.
Используйте Ctrl-Enter для размещения комментария