Запрос, который съел базу

В конце первой части я пообещал поиск пути: «Как добраться из пункта А в пункт Б?» — максимум с двумя пересадками и коротким пешим переходом между остановками, если так быстрее, чем ждать. На сервере он уже был — «написано это, как ты уже догадался, ещё одним рекурсивным запросом», — а приложение его пока не вызывало.

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

Ходьба — тоже маршрут

Сеть из первой части — это остановки и рёбра: «маршрут A едет от C/ Mayor до Petanca за минуту сорок». Но чтобы спланировать поездку, приходится ещё и ходить пешком: от того места, где ты сейчас, до остановки, от одной остановки до другой, чтобы сменить маршрут, и от последней остановки до того места, куда тебе надо.

Первый и последний начинаются или заканчиваются не на остановке, так что их считает пешеходный роутер. А вот средний — это фокус. Небольшой SQL-скрипт перебирает все пары остановок меньше чем в 500 метрах друг от друга, между которыми ещё нет ребра, и соединяет их ребром на маршруте под названием walk():

SELECT a, b, 'walk()' AS line,
       PRINTF("%g", ROUND(distance * 3600 / 3)) || 's' AS duration -- 3 km/h walking speed with "obstacles" (e.g. traffic lights)
FROM ( … the distance between two stops, as great-circle maths in SQL … )

Три километра в час — это вроде бы медленно, пока не вспомнишь про светофоры, кольца и августовское солнце. А дальше пеший переход — просто ещё одно ребро со своей длительностью, и поиску незачем отличать его от автобусного. Пеших рёбер в таблице больше, чем автобусных: на сентябрь около шестисот против четырёхсот.

Запрос

Поиск пути — это двоюродный брат запроса из первой части, который считал время прибытия, только с амбициями. Он начинает с одной остановки, идёт по рёбрам и запоминает, где уже побывал. Здесь он слегка урезан, но это та самая версия, которая работала до сегодняшнего дня:

WITH RECURSIVE dfs(station_id, path, path_lines, current_line, depth, line_changed, stations_on_current_line) AS (
  SELECT e.`from`, CAST(e.`from` AS TEXT), CAST(e.`line` AS TEXT), e.`line`, 0, 0, 1
  FROM route_edges e WHERE e.`from` = {:from}
  UNION ALL
  SELECT e.`to`,
         dfs.path || CASE WHEN e.`line` != dfs.current_line THEN ';switch()' ELSE '' END || ';' || e.`to`,
         …,
         e.`line`, dfs.depth + 1,
         CASE WHEN e.`line` = dfs.current_line THEN dfs.line_changed ELSE dfs.line_changed + 1 END,
         CASE WHEN e.`line` = dfs.current_line THEN dfs.stations_on_current_line + 1 ELSE 1 END
  FROM dfs JOIN route_edges e ON e.`from` = dfs.station_id
  WHERE dfs.depth < {:depth}
    AND instr(dfs.path, e.`to`) = 0
    AND (e.`line` = dfs.current_line
         OR (dfs.line_changed < 2 AND dfs.stations_on_current_line >= 2))
)
SELECT station_id, path_lines, depth, path FROM dfs
WHERE station_id = {:to} AND stations_on_current_line >= 2
ORDER BY depth, <number of lines> LIMIT {:limit};

Каждая строка — это недостроенный путь: список пройденных остановок в виде текста, задействованные маршруты и число пересадок. Все правила сидят в WHERE:

• Никогда не заезжать на одну остановку дважды. instr(path, stop) = 0 — это поиск подстроки в пути. Топорно: стоит пути проехать panorama-2, как panorama тоже считается пройденной. Но в основном работает.
• Не больше двух пересадок.
• Перед пересадкой проехать хотя бы две остановки. Без этого правила поиск с радостью садится в автобус на одну остановку, чтобы на следующей пересесть.

Поиск не знает и того, до какой остановки ты пойдёшь пешком. Он берёт три ближайшие к тебе остановки и три ближайшие к тому месту, куда ты едешь: девять пар. Для каждой пары он запрашивает пути глубиной до 5 рёбер. Если набирается меньше четырёх вариантов, он пробует 10, потом 15 и так вплоть до 50.

Плейсхолдеры вроде {:from} — это синтаксис PocketBase, как и {{route_edges}}, который выше я для простоты написал обычным route_edges. На нашем сервере их подставляет сам PocketBase, а в Worker то же самое делают несколько строчек кода, так что наши файлы с запросами работают и там, и там. Я этим, признаться, гордился. Сам поиск пути, правда, так никогда и не запускался нигде, кроме Worker.

Всё работало. Потом мы натравили на него приложение

Впервые запрос появился в октябре 2024 года — как файл, который я запускал руками, — а в ноябре получил эндпоинт в коммите под названием «navigation alpha». Приложение его ни разу не вызвало.

В августе наш Flutter-разработчик превратил его в полноценный метод API, который начинает с двух точек на карте, а не с двух id остановок. В октябре к нему подключили экран навигации, который за лето собрали на моковых данных, и дев-сборки начали задавать настоящие вопросы — из настоящих мест в настоящие места. Проблемы начались на той же неделе:

• Конец октября. Первая оптимизация: прежде чем пересесть, путь должен проехать хотя бы две остановки. Для людей правило разумное, а поиск оно заметно сужает.
• Конец ноября. Метод получил маршрут в продовом API, и через день у D1 уже заканчивалась память. Каждый поиск отправлял все девять пар остановок разом. Починили это тем, что стали отправлять их по одной, а рядом оставили комментарий с нашей тогдашней версией происходящего: «искать пути ПОСЛЕДОВАТЕЛЬНО, чтобы не ловить от D1 ошибки нехватки памяти из-за слишком большого числа одновременных рекурсивных CTE-запросов».
• 1 декабря. Гипотеза: память съедает сама рекурсия, которая уходит вглубь по одной ветке за другой. Поэтому появилась версия запроса с поиском в ширину и комментарием сверху: «Подход BFS: итеративные запросы вместо рекурсивного CTE. Так мы избегаем взрывного роста памяти при глубокой рекурсии». Тот же коммит расширил поиск до четырёх ближайших остановок с каждого конца — шестнадцать пар — и ограничил глубину тридцатью. Ничего заметного всё это не изменило.

D1 — это SQLite на стороне Cloudflare, и ограничения там такие, каких у ноутбука нет: на запрос даётся 30 секунд, а памяти куда меньше, чем у ноутбука, — сколько именно, Cloudflare не говорит. На маленькой сети и для короткой поездки наш запрос чувствовал себя нормально. Через весь город на глубину в десять рёбер — уже нет.

С сегодняшнего дня граф живёт в Worker

Так что сегодня мы перестали спрашивать у SQL.

Остановки и рёбра теперь складываются в снапшот — protobuf-файл в R2. Когда файл впервые нужен Worker, тот загружает его в graphology, строит из него простую табличку — какая остановка куда ведёт — и держит её в памяти до конца своей жизни. Сам поиск — это цикл со стеком: берёшь путь, продлеваешь его по каждому разрешённому ребру и кладёшь то, что вышло, обратно на стек. Правила — те же три, что были в SQL. А D1 по-прежнему отвечает на дешёвые вопросы вроде «какие остановки рядом с этой точкой» и «когда следующий автобус», и отвечает за миллисекунды.

Судя по новым логам производительности, поиск теперь занимает 0,00 мс. Я решил им верить.

Урок, который я из этого выношу: SQL был правильным инструментом, чтобы «сложить срез вектора», и неправильным, чтобы «перечислить все способы добраться отсюда туда». Тысяча рёбер — крошечная таблица, а запрос, который помещается на один экран, — крошечный запрос. А вот число путей крошечным не назовёшь.

Что дальше

• Ночная джоба, которая пересобирает снапшот из базы, чтобы никому не приходилось об этом помнить.
• Автобусы в настоящем роутинг-движке. Пешеходную навигацию нам уже даёт Valhalla — роутинг-движок, который мы хостим сами. Общественный транспорт он тоже умеет, если скормить ему GTFS-файл: стандартный формат расписаний, который для Торревьехи, насколько мы знаем, никто не публикует.