Дата публикации: 11-12-2022

Что я узнал за 10 дней Advent Of Code на SQLite

sqlite.jpg

Advent Of Code - популярный набор задачек по программированию в формате адвент-календаря. В этом году я решил порешать его на SQL, чтобы подтянуть свои знания этого языка. Формат задач по программированию - нетипичное применение SQLite и я сумел разобраться с фичами и столкнулся с особенностями SQLite, которые раньше почти не трогал. Я совсем не DBA, так что от каких-то “заметок” можно прибить себя фейспалмом. Смело пиши в комменты, где я не прав.

Заметка 1. SQLite отлично работает для решений “навыброс”

До решения AoC я работал в основном с Postgres с несложными аналитическими запросами, а sqlite использовал как часть утилиты textql для того чтобы трогать csv-шки. Кстати, sqlite я изучал по курсу на Stepik и он мне очень понравился. Когда я выбирал на чём решать AoC, я решил использовать sqlite а не postges, потому что её не нужно разворачивать и у неё есть удобный cli и инструменты работы с текстовым вводом. И это действительно было удобно.

Заметка 2. В SQLite нет циклов

Я, конечно, знал, что в SQL буква S ни разу не означает Standard. Но разница в диалектах иногда уж очень большая. Например, для меня было сюрпризом, что в SQLite нет поддержки циклов. А без этого весьма тяжело было поначалу решать AoC задачки, потому что большая часть из них состоит в том, чтобы правильно спарсить инструкции и выполнить их.

Заметка 3. Зато в SQLite есть рекурсивные Common Table Expressions

В итоге для решения AoC одной из самых полезных фич оказались Common Table Expressions. Ими можно и инструкции спарсить, и на подстроки ввод разбить и потом эти же инструкции и выполнить. В обычном мире RCTE используют для запросов иерархичных данных. Классическим примером будет такой код

select * from folders;
-- +------+--------+
-- |  id  | parent |
-- +------+--------+
-- | root |        |
-- | a    | root   |
-- | b    | root   |
-- | c    | a      |
-- | d    | b      |
-- | e    | c      |
-- +------+--------+
with recursive path as(
  select id, id as path from folders
  where parent is null

  union all

  select folders.id, path.path || '/' || folders.id from path -- recursive call
  join folders on parent = path.id
) select * from path;
-- +------+------------+
-- |  id  |    path    |
-- +------+------------+
-- | root | root       |
-- | a    | root/a     |
-- | b    | root/b     |
-- | c    | root/a/c   |
-- | d    | root/b/d   |
-- | e    | root/a/c/e |
-- +------+------------+

Но так как в SQLite нет циклов, а итерироваться по набору данных как-то нужно, RCTE я использовал почти в каждой задаче, вне зависимости от того, были ли там иерархичные данные или нет. Сейчас покажу несколько примеров.

Пример 1. Разбить строку на подстроки

В шестой день была простая задача, которая бы на Kotlin решалась в одну строку при помощи цепочки из операторов из стандартной библиотеки. Нужно было найти первую позицию скользящего окна в 4 символа, в которой все символы различаются. Но для того, чтобы это сделать, нужно превратить строку в таблицу с рядами вида (character, index). Тут нам на помощь может прийти RCTE.

select * from inp;
-- +-------------------------------+
-- |              inp              |
-- +-------------------------------+
-- | sgrrrrwcrxlqqgppfgfnngsgcgngr |
-- +-------------------------------+
with recursive parsed as (
     -- Выбираем первый символ и первый индекс
     select substr(inp, 1, 1) as ch, 1 as index from inp
     union all
     -- Выбираем последующие символы, увеличивая индекс на единицу
     select substr(inp, index+1, 1) as ch,
            index + 1 as index
     from parsed, inp
     -- Чтобы не улететь в бесконечную рекурсию, останавливаемся когда индекс выходит за границы строки
     where index < length(inp)
) select * from parsed
-- +--------+-----+
-- | window | pos |
-- +--------+-----+
-- | s      | 1   |
-- | g      | 2   |
-- | r      | 3   |
-- | r      | 4   |
-- | r      | 5   |
-- | r      | 6   |
-- | w      | 7   |
-- | c      | 8   |
-- | r      | 9   |
-- | x      | 10  |
-- | l      | 11  |
-- | q      | 12  |
-- | q      | 13  |
-- | g      | 14  |
-- | p      | 15  |
-- | p      | 16  |
-- | f      | 17  |
-- | g      | 18  |
-- | f      | 19  |
-- | n      | 20  |
-- | n      | 21  |
-- | g      | 22  |
-- | s      | 23  |
-- | g      | 24  |
-- | c      | 25  |
-- | g      | 26  |
-- | n      | 27  |
-- | g      | 28  |
-- | r      | 29  |
-- +--------+-----+

В RCTE в SQLite рекурсия немного своеобразная. Если бы на Kotlin я писал, начиная от общего случая и приводя базовые потом, то здесь приходится сначала давать базовый случай и “наращивать” данные поверх него. Вот пример рекурсивного решения на Kotlin:

fun explode(str: String, chars: List<Char> = emptyList()) : List<Char> = when (str.isEmpty) {
    true -> chars
    else -> explode(str.substringAfter(0), chars.plus(str[0]))
}

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

Пример 2. RCTE позволяют выполнять инструкции ’по шагам’

Так как в RCTE мы в каждом ряду храним какой-то стейт, его можно итеративно изменять, используя некоторый набор инструкций как вход. К примеру, в 9 день была задача, в которой конец верёвки перемещался по двумерному полю по инструкциям в виде букв ’U’, ’D’, ’L’, ’R’. Небольшим CTE можно получить из набора инструкций таблицу с координатами верёвки на каждом шаге.

select * from instructions;
-- +-----------+----+
-- | direction | n  |
-- +-----------+----+
-- | R         | 1  |
-- | U         | 2  |
-- | D         | 3  |
-- | U         | 4  |
-- | R         | 5  |
-- | R         | 6  |
-- | D         | 7  |
-- | D         | 8  |
-- | R         | 9  |
-- | R         | 10 |
-- | D         | 11 |
-- | D         | 12 |
-- | R         | 13 |
-- | U         | 14 |
-- +-----------+----+
solution as(
    -- Задаём начальные позиции как 0,0 и текущий шаг как 1
    select 0 as hi, 0 as hj, 1 as step
    union all
    select
        -- "изменяем" состояние, основываясь на предыдущем шаге
        case direction
            when 'U' then hi + 1
            when 'D' then hi - 1
            else hi
        end as hi,
        case direction
            when 'R' then hj + 1
            when 'L' then hj - 1
            else hj
        end as hj,
        -- инкрементируем шаг
        step + 1 as step
    from solution
    -- джойним нашу таблицу с инструкциями, чтобы знать что делать дальше
    join instructions on n = step
) select * from solution
-- +----+----+------+
-- | hi | hj | step |
-- +----+----+------+
-- | 0  | 0  | 1    |
-- | 0  | 1  | 2    |
-- | 1  | 1  | 3    |
-- | 0  | 1  | 4    |
-- | 1  | 1  | 5    |
-- | 1  | 2  | 6    |
-- | 1  | 3  | 7    |
-- | 0  | 3  | 8    |
-- | -1 | 3  | 9    |
-- | -1 | 4  | 10   |
-- | -1 | 5  | 11   |
-- | -2 | 5  | 12   |
-- | -3 | 5  | 13   |
-- | -3 | 6  | 14   |
-- | -2 | 6  | 15   |
-- +----+----+------+

В коде выше для каждого шага join возвращает новую инструкцию из таблицы, пока они не закончатся. Таким образом можно на SQL решать задачи, в которых требуется итерация. Прямо как деоптимизация хвостовой рекурсии руками.

Заметка 4. Window functions это прикольно, но не всегда возможно

Оконные функции - мощный инструмент чтобы просматривать рядом выше или рядом ниже. Или как-нибудь узнать порядковый номер ряда в нашем окне или в таблице в целом. Например пронумеровать ряды можно простым селектом по пустому окну.

select *, row_number() over () from my_table

Иногда они гиперполезны. Например первая задача восьмого дня решается четырьмя оконными функциями и селектом по ним.

select *,
    max(val) over (partition by i order by j rows between unbounded preceding and current row EXCLUDE CURRENT ROW) as rank_i,
    max(val) over (partition by i order by j rows between current row and unbounded following EXCLUDE CURRENT ROW) as rank_i_rev,
    max(val) over (partition by j order by i rows between unbounded preceding and current row EXCLUDE CURRENT ROW) as rank_j,
    max(val) over (partition by j order by i rows between current row and unbounded following EXCLUDE CURRENT ROW) as rank_j_rev
from parsed

Этот набор функций позволяет “просмотреть” наиболее высокие деревья по вертикали и горизонтали, исключая наши. Очень круто, но не всегда работает.

Подводный камень 1. Оконные функции не поддерживают distinct

Задачу из шестого дня выше можно было бы решить элегантно используя window functions, написав что-то вроде такого sql

select count(distinct *) over (order by index between current row and 4 following) from parsed

Но SQLite бодро встретит тебя сообщением о том, что в оконных функциях distinct не поддерживается и иди-ка ты сам группируй символы по четыре и делай там свой count(distict *).

Подводный камень 2. Оконные функции нельзя использовать в where.

Допустим, мы захотели селектнуть каждый второй ряд. Мы не можем просто взять и написать

select * from my_table where row_number() over () % 2 = 0

SQLite плюнет в тебя ошибкой про то что в where использовать оконные функции нельзя. Только в select и order by, а всё остальное - будь добр используй CTE.

with temp as(select *, row_number() over () as rn from my_table)
select * from my_table where rn % 2 = 0

Подводный камень 3. Я не нашёл способа переиспользовать больше одного окна

В SQLite можно вынести определение окна как window <имя> as

select row_number() over w, lead() over w from my_table
window w as (partition by x order by y)

Но сделать больше одной такой конструкции нельзя. Поэтому если у тебя больше одного повторяющегося окна, приходится его копипастить.

Заметка 5. В SQLite есть поддержка JSON

Честно говоря, после того как узнал что в SQLite, в отличие от Postgres, нет поддержки for loops и массивов, я не надеялся на поддержку JSON. Но она есть, причём весьма неплохая. Можно как получать элементы по JSONpath, так и добавлять их и даже раскладывать json-объекты и массивы в таблицы и обратно при помощи jsoneach и jsonaggregate. Можно даже работой с json массивами заменить отсутствие настоящих массивов, но по индексу придётся брать при помощи json path.

select * from numbers;
-- +---+
-- | x |
-- +---+
-- | 1 |
-- | 2 |
-- | 3 |
-- +---+

-- Можем собрать всё в json array агрегатной функцией
select json_group_array(x) as json from numbers;
-- +---------+
-- |  json   |
-- +---------+
-- | [1,2,3] |
-- +---------+

-- Можем обращаться по индексу через json path
select json_extract(json, '$[0]') as num from jsonified;
-- +-----+
-- | num |
-- +-----+
-- | 1   |
-- +-----+

-- И, наконец, можем разложить json массив обратно в с
select json_each.value as x from json_each(jsonified);
-- +---+
-- | x |
-- +---+
-- | 1 |
-- | 2 |
-- | 3 |
-- +---+

Заметка 6. SQL - язык времён COBOL

Меня хватило на 10 дней Advent Of Code на SQL. И не потому что следующие задачи нельзя решить на SQL. Несмотря SQL очень неповоротливый язык, который слишком пытается быть похожим на английский язык. Чего только стоит синтаксис оконных функций. Писать на нём не очень приятно, он постоянно просит от тебя каких то церемоний типа убрать лишнюю запятую после того как переписал запрос или сделать ещё один select чтобы не повторять агрегатную функцию второй раз. К этому всему добавляется разница в диалектах разных баз данных. Честно говоря, не понимаю, почему до сих пор не придумали какой-нибудь байткод для движков запросов и нормальный фронтенд к нему. Почему тысячи человеколет направлены на оптимизацию не самого приятного для работы языка.

Каждый язык под свою задачу?

Ты скажешь, что я дурачок и просто забиваю молотком шурупы. Но такие ли уж это разные задачи? Почему доставать данные из хранилища я должен одним языком, а обрабатывать их - другим? Любой веб работает как пайплайн из select-map-render. Почему не придумали до сих пор способов писать всё на одном языке программирования? Причём не просто запихнуть ORM, а дать возможность именно что задавать вопросы к хранилищу. LINQ подобрался к этому ближе всего, но недостаточно.Планирую в будущем поизучать другие языки запросов для реляционных данных, такие как EdgeQL и различные имплементации Datalog. Ещё видел язык Flix, который имеет Datalog как часть языка, попробую и его. Обязательно напишу пост, если найду что-то удобнее SQL, а пока AoC дорешаю на чём нибудь другом.

Подпишись и обсуждай в Telegram