Ivan Grishaev

Ivan Grishaev's blog

Writing on programming, education, books and negotiations.

Home About Open Source Bookshelf RSS
Clojure Postgres Emacs Python Programming Interview Video
Книга «Clojure на производстве»
Книга «Clojure на производстве», второй том

  • Совет дня №38

    ,

    Иногда бизнес-логику проще выразить на SQL – нравится вам это или нет. При этом окружающие теряют лицо: кричат “боже, хранимки!” и ведут себя недостойно. Бояться тут нечего, а истерика — от незнания.

    Я не говорю, что нужно писать хранимки. Речь о том, чтобы поручить базе ту работу, что делает ваш Питон или Джава. Часто SQL выигрывает: он короче, точнее, не требует многих обращений к базе.

    Нюанс в том, что меняется парадигма мышления. Когда вы пишете на SQL, то должны думать реляционно. Если писать хранимки императивно как на Питоне, это будет ужасно.

    Давайте вспомним пример, который я описывал в статье про рейтинг пользователей. Постановка такая: у пользователей есть история начисления баллов. Также есть глобальный рейтинг. Как только пользователю начисляются баллы, он видит их в истории. Одновременно меняется его позиция в рейтинге.

    На какой-нибудь питонячей ORM это выглядит так:

    user_id = 51315
points = 100

points_entry = UserPoints.create(user_id=user_id, points=points)
points_entry.save()

rating_entry = UserRating.get_or_create(user_id=user_id)
rating_entry.points += points
rating_entry.save()

    Сперва мы добавили запись в историю баллов. Затем выбрали или создали запись в глобальном рейтинге. Прибавили баллы, записали. Все это нужно делать в транзакции, иначе есть риск потерять баллы (по аналогии с задачей про семейную пару и терминал).

    Предположим, руководитель сказал: “ребят, переносим логику в БД”, но не удосужился объяснить, что это значит. Окей, программист пишет процедуру на plpgsql:

    create procedure add_points(int user_id, int points)
begin
  create_points_history(user_id, points);
  rating_entry = get_user_rating_by_user_id(user_id);
  if (rating_entry is NULL) then
    insert_user_rating(user_id, points);
  else
    update_user_rating(user_id, points);
  endif;
end;

    Эта процедура – построчная калька с Питона. Далее пишутся функции get_user_rating_by_user_id, get_user_rating_by_user_id и другие. Получается два экрана SQL, который трудно понять и поддерживать. Запросов по-прежнему много. Один раз увидев такое, разработчик получает душевную травму. При слове “хранимки” у него начинается истерика.

    Проблема в том, что автор процедуры использует SQL не по назначению. Он пишет на нем императивно, а SQL создан для операций над отношениями. Прочитайте еще раз: SQL создан для операций над отношениями. Единица операции — таблица. Если ваш SQL полон функций get_user_by_id, get_profile_by_id, то это ошибка. Копаешь граблями – получишь заведомо плохой результат. Нельзя пересаживать программиста с императивного Питона на SQL. Пока мозги не перестроились, хорошего результата не ждите.

    Достойное решение на SQL выглядит примерно так:

    with update_history as (
  insert into user_history (user_id, points)
  values ($1, $2)
)
insert into user_rating(user_id, points)
  values ($1, $2)
  on conflict user_id do update
  set points += excluded.points
  returning user_id, points

    Здесь все просто: часть update_history добавляет запись в историю баллов. Основная часть пытается вставить пользователя и баллы в рейтинг, а если пользователь уже есть в нем, прибавляет баллы. Запрос возвращает пользователя и новую сумму баллов.

    Этот запрос выполняется транзакционно, обе части видят один снимок данных. Подчеркну: совершенно незачем выносить его в хранимку. Достаточно хранить запрос в проекте и вызывать его. Хранимки нет, но работа делегируется базе.

    Итого: не пишите хранимки только затем, чтобы они были. Думайте о том, как делегировать работу базе, а не писать бороду SQL-функций. Если вы работаете с базой, мыслите реляционно. Экраны императивного SQL говорят о том, что вы делаете что-то не так.

  • Совет дня №37

    ,

    Совет №36 оканчивался фразой:

    Мне известны для случая, когда от внешних ключей отказываются добровольно.

    О них и поговорим.

    Первый случай, когда ослабление ключей допустимо – это GDPR и схожие требования. Например, пользователь оставил заявку на удаление учетки и связанных данных. Удалять их в лоб долго и трудно: пользователь – это центральная сущность, на которую завязано все. Каскадный DELETE, во-первых, крайне медленный, а во-вторых, может задеть данные, которые нужно оставить.

    Кроме пользователя, бывают и другие сущности, которые нужно экстренно удалить, но мешают внешние связи. В этом случае сперва удаляют внешние ключи при помощи drop constraint. Например, ниже удаляется внешний ключ user_id в профилях:

    alter table profiles drop constraint fk_user_id

    Далее удаляется целевая сущность — пользователь. В дальнейших запросах используется внутреннее соединение, чтобы отсечь записи, которые ссылаются в никуда. Например, если мы выбрали профили по особому критерию, то пользователи цепляются не LEFT, а обычным JOIN. Это гарантирует, что в выборке не будет “висюков”:

    select * from profiles p
where p.open_to_work
join users u on p.user_id = u.id

    Позже “висюки” подчищаются запросом по расписанию. Заметим, что внутренний JOIN в целом работает лучше, чем левый и правый аналоги. Он быстрее и отсекает больше данных. Как правило, LEFT JOIN означает, что в базе что-то не так.

    Сказанное выше звучит костыльно, но увы — это жизнь. Так было в одном стартапе: он выходил на очередной раунд инвестирования, и сказали: по такому-то закону нужно удалить учетку пользователя по запросу в короткое время. Таких пользователей было немного, буквально пять или шесть, но обилие внешних ссылок все усложняло. Получалось огромное дерево таблиц, которое нужно было очистить в особом порядке. Руководители стартапа не хотели тратить время и деньги на такую ерунду. Поэтому внешние ключи удалили и снесли записи обычным DELETE. Схема базы пострадала, зато с задачей справились быстро.

    Внешние ключи нужны – без них легко испортить данные. Но в редких случаях выгодно их ослабить – только никому об этом не говорить.

  • Совет дня №36

    ,

    Перечитав прошлый совет, я понял, что он нуждается в технической демке. Быстренько покажу, на что влияет индекс внешнего ключа.

    Уточнение: будет много планов. Поскольку они длинные, их трудно записать в Телеграме в понятном виде. Здесь только фрагменты, а в конце – ссылка на гист.

    Итак, делаем две таблицы, пользователей и профили:

    create table users (
    id serial primary key
);

create table profiles (
    id serial primary key,
    user_id integer not null references users(id)
);

    Вставим миллион пользователей:

    insert into users
select x
from generate_series(1, 999999) as seq(x);

    Профилей тоже миллион, но есть нюанс. Я не хочу, чтобы n-ая строка профиля ссылалась на n-ую строку пользователя. Это слишком хорошо и не отражает действительности. Поэтому первый профиль ссылается на последнего пользователя, второй – на предпоследнего и так далее. Другими словами, максимально усложним базе жизнь в плане соединений:

    insert into profiles
select x, 1000000 - x
from generate_series(1, 999999) as seq(x);

    Проверим, что в таблицах:

    table users limit 100;

    ┌─────┐
│ id  │
├─────┤
│   1 │
│   2 │
│   3 │
│   4 │
│   5 │
│   6 │
│   7 │
│   8 │
│   9 │
│  10 │

    table profiles limit 100;

    ┌─────┬─────────┐
│ id  │ user_id │
├─────┼─────────┤
│   1 │  999999 │
│   2 │  999998 │
│   3 │  999997 │
│   4 │  999996 │
│   5 │  999995 │
│   6 │  999994 │
│   7 │  999993 │
│   8 │  999992 │
│   9 │  999991 │

    Индекса на user_id пока что нет. Что будет, если выбрать профили ста определенных пользователей? Посмотрим план:

    explain
select * from profiles
where user_id between 450000 and 450100;

    Gather  (cost=1000.00..11684.39 rows=94 width=8)
Workers Planned: 2
Parallel Seq Scan on profiles
  (cost=0.00..10674.99 rows=39 width=8)
Filter: ((user_id >= 450000) AND (user_id <= 450100))

    Видим, что было полное сканирование профилей. При этом Postgres сделал это параллельно в два процесса (Parallel Seq Scan, Workers =2), а потом объединил результат (шаг Gather). Итоговая стоимость довольно высокая (11684).

    Предположим, я делаю отчет по всем пользователям и профилям: тупо соединяю две таблицы джоином:

    explain
select *
from users u, profiles p
where u.id = p.user_id;

    Hash Join  (cost=30831.98..59602.98 rows=999999 width=12)
Hash Cond: (p.user_id = u.id)
Seq Scan on profiles p
  (cost=0.00..14424.99 rows=999999 width=8)
Hash  (cost=14424.99..14424.99 rows=999999 width=4)
Seq Scan on users u
   (cost=0.00..14424.99 rows=999999 width=4)

    То, что был seq scan по таблице users, это нормально – мы выбираем все записи. Однако по таблице profiles тоже был full scan, при этом стоимость хэширования огромна (cost=14424.99..14424.99). Финальный обход хэшей тоже дорогой: 59602.98

    Другой пример: предположим, мы выбрали малую часть пользователей и нужно присоединить им профили. Для этого рассмотрим запрос:

    explain
with some_users as (
    select * from users
    where id between 450000 and 450100
)
select *
from some_users sm
join profiles p on sm.id = p.user_id;

    Считаем, что выборка some_users даст всего 100 пользователей. В реальности мы бы фильтровали по городу или другому признаку, но поскольку у нас только id, остается по нему.

    Gather  (cost=1007.61..10702.82 rows=98 width=12)
Workers Planned: 2
Hash Join  (cost=7.61..9693.02 rows=41 width=12)
Hash Cond: (p.user_id = users.id)
Parallel Seq Scan on profiles p
  (cost=0.00..8591.66 rows=416666 width=8)
Hash  (cost=6.39..6.39 rows=98 width=4)
Index Only Scan using users_pkey on users
  (cost=0.42..6.39 rows=98 width=4)
Index Cond: ((id >= 450000) AND (id <= 450100))

    Этот план говорит о следующем: выборка some_users сработала моментально, но дальше все плохо. Чтобы найти профили, Postgres опять зарядил два параллельных потока с объединением. Итоговая стоимость (10702.82) высокая.

    Добавим индекс на поле user_id и посмотрим, как все изменится:

    create unique index idx_profiles_user_id_u
on profiles using btree (user_id);

analyze profiles;

    Простой пример: найти профили по диапазону пользователей:

    explain
select * from profiles
where user_id between 450000 and 450100;

    Index Scan using idx_profiles_user_id_u on profiles
  (cost=0.42..10.37 rows=97 width=8)
Index Cond: ((user_id >= 450000) AND (user_id <= 450100))

    Очевидно, стоимость копеечная.

    Далее: имея узкую выборку пользователей (например, по городу), присоединить им профили:

    explain
with some_users as (
    select * from users
    where id between 450000 and 450100
)
select *
from some_users sm
join profiles p on sm.id = p.user_id;

    Nested Loop
  (cost=0.85..825.75 rows=98 width=12)
Index Only Scan using users_pkey on users
  (cost=0.42..6.39 rows=98 width=4)
Index Cond: ((id >= 450000) AND (id <= 450100))
Index Scan using idx_profiles_user_id_u on profiles p  (cost=0.42..8.36 rows=1 width=8)
Index Cond: (user_id = users.id)

    Было два прохода по индексам, итоговые данные соединены вложенным циклом (Nested Loop). Сложность такого соединения квадратична, но на малых объемах выигрывает. Стоимость 825 – низкая.

    И наконец, узрите истинную мощь Merge Join – соединения слиянием. Повторим запрос, в котором мы соединяем две таблицы без каких-либо фильтров:

    explain
select *
from users u, profiles p
where u.id = p.user_id;

    Вы, наверное, думаете, что все полетит? Нет, план останется таким же, то есть очень медленным:

    Hash Join
  (cost=30831.98..59602.98 rows=999999 width=12)
...

    Будет два seq scan-а по обеим таблицам и ручное хеширование. Напомню, я специально создал худший сценарий, когда порядок профилей обратный: первый профиль ссылается на последнего пользователя и так далее. Это делает хэширование дорогим. Стоимость первой строки равна 30831 – это значит, что перед получением данных база будет тупить – считать хэши.

    Сделаем вот что: в запросе выше заменим profiles на подзапрос, отсортированный по user_id:

    explain
select *
from users u, (select * from profiles order by user_id) p
where u.id = p.user_id
order by u.id;

    План:

    Merge Join  (cost=5.14..81384.50 rows=999999 width=12)
Merge Cond: (profiles.user_id = u.id)
Index Scan using idx_profiles_user_id_u on profiles  (cost=0.42..30408.41 rows=999999 width=8)
Index Only Scan using users_pkey on users u  (cost=0.42..25980.41 rows=999999 width=4)

    Оба набора упорядочены по тем полям, по которым их соединяют, поэтому сработает соединение слиянием. Стоимость его гораздо ниже, чем у хеширования. Первая строка доступна уже через 5.14 единиц стоимости – а было 30831.98. Четыре порядка! Когда я вижу в плане Merge Join, все мои железы активируются и выделяют жидкости.

    Планы – полезная вещь. Читайте их, экспериментируйте, пытайтесь понять, почему план именно такой, а не другой.

    Ссылка на код.

  • Совет дня №35

    ,

    В прошлый раз мы говорили об уникальных ограничениях, а еще есть внешние. Это когда значение поля обязано быть первичным ключом другой таблицы. Например, в профиле колонка user_id ссылается на пользователя: таблицу users и ее первичный ключ id.

    create table users (
    id serial primary key...
);

create table profiles(
    id serial primary key,
    user_id integer not null references users(id)
);

    Ключевое слово references создает это ограничение автоматом. Можно задать его явно таким выражением:

    alter table profiles
add constraint fk_profile_user_id
foreign key (user_id)
references users (id);

    Первичные ключи бывают составными, и тогда внешний ключ тоже составной.

    Когда создано подобное ограничение, профиль не может ссылаться на пользователя, которого не существует. При этом значения NULL допускаются, потому что он не равен другим нуллам. Если поле не должно содержать нуллы, это задается свойством NOT NULL.

    Поскольку первичный ключ всегда индексирован, проверка внешнего ключа работает быстро. Например, мы добавляем профиль с полем user_id 100500. Проверка аналогична запросу ниже (обратите внимание, что из него ничего не выбирается):

    select from users where id = 100500

    Под капотом Postgres проверяет только индекс – нет смысла дергать таблицу — поэтому запроса в логах вы не увидите.

    Некоторое разработчики считают, что внешние ключи тоже индексируются. Например, зная пользователя, мы хотим взять его профиль (технику часто называют backref, обратной ссылкой):

    select * from profiles where user_id = 100500

    Увы, это не так. По умолчанию внешний ключ не индексируется, и запрос выше даст full scan. Повесьте на него btree:

    create index idx_profile_user_id
on profiles using btree (user_id);

    Теперь обратная ссылка индексирована, и зная родительскую сущность, легко найти дочерние.

    Пример с профилем можно сделать еще строже: мы допускаем только один профиль на пользователя, поэтому повесим на user_id уникальный индекс:

    create UNIQUE index ...

    Индексы на внешние ключи обязательны, если используется join. Скажем, вы строите отчет по всем пользователям системы:

    select * from users u
left join profiles p on u.id = p.user_id

    Без индекса на profiles.user_id запрос будет очень тяжелым. Зато если поле индексировано и вдобавок обе таблицы отсортированы по коду пользователя, возможно, сработает Merge Join – соединение слиянием. Это самый быстрый алгоритм соединения. Принцип у него такой же, как и у сортировки слиянием.

    Внешние ключи вносят в базу ограничения, и желательно следовать им. В противном случае вы рискуете создать “висяки” – ссылки, ведущие в никуда. Как и в случае с дублями, их тяжело расследовать и удалять.

    Мне известны для случая, когда от внешних ключей отказываются добровольно. Я рассмотрю их в следующих советах.

  • Libpq и Java

    , , ,

    На днях я ввязался в одну авантюру, а она оказалась смоляной ямой. Увяз по самые уши и не знаю, продолжать или бросить. Авантюра, кстати, тоже связана с Postgres.

    Я хотел проверить: будет ли драйвер для Postgres быстрее, если переписать его с чистой Джавы на Libpq. Кто не знает, Libpq – это библиотека на Си для работы с базой. Идея в том, чтобы поручить большую часть работы коду на Си, а самому только дергать функции через JNI.

    Такую сишную обертку я написал; тесты показали, что Libpq как минимум не хуже, а порой и быстрее Джавы. Взаимодействие Джавы с сишным рантаймом – мутная история, в ней много специфики. Ошибся указателем – Джава вылетает. Но это не идет ни в какое сравнение с тем, где я увяз – сборкой.

    Я хотел собрать сишный код под три платформы (винда, мак, линукс) и две архитектуры (x86-64, arm64). Их произведение дает шесть комбинаций. Вопрос: где и как собирать? Допустим, у меня есть Мак на арме; докер на нем дает Линукс на арме. Нужна винда на арме, а где ее взять? То же самое с интелом: у меня есть старый Мак на core i3, но по сегодняшним меркам он такой медленный, что лишний раз трогать его не хочется. Есть игровой комп с Виндой на интеле, но не будешь же носить его с собой? В итоге я поручил сборку Github actions: в нем доступны все шесть видов машин, а сценарий пишется на yaml.

    По наивности я думал, что напишу один Makefile, который вызову с разными переменными – и дело в шляпе. Идея провалилась из-за адского разнообразия сред и платформ. Сборка простого кода на C++ отличается даже не в рамках ОС, а дистрибутива. Везде спонтанные отличия, условности, разные названия папок, путей и так далее.

    Несколько примеров. На винде x64 компилятор MSYS2 ставится в папку c:\temp\a\msys64, а на арме – в d:\temp\a\msys64 (другой диск). Почему был C, а стал D? И почему он ставится не в корень, а куда-то в temp? Уверен, что есть объяснение, но неудобно.

    Мак и его Homebrew тоже хорош. На интеле пакет libpq включает утилиту pg_config – она показывает, где лежат заголовочные файлы и другое барахло. На M1 в таком же пакете утилиты нет. Почему?

    Плохи дела и на этом вашем Линуксе. В той Убунте, что идет на Гитхабе, пакет postgres-client – 16 версии, а мне нужна 18. Нужно подключать частный репозиторий Postgres. У него тоже особенности: на интеле пакет postgres-client-18 включает заголовочные файлы, а на арме – нет. Нужно качать dev-барахло.

    И таких вещей очень много. Разные пути, переменные среды; здесь есть файл, а тут нет и так далее. Смейтесь или нет, но мне понадобилось 166 (сто шестьдесят шесть) попыток, чтобы прошли все билды. Я убил на это вагон времени, забивая на работу и даже личные обязанности. При этом та удачная 166-я попытка – грубый черновик, который еще доводить и доводить до ума.

    Напомню, все это лишь для того, чтобы:

    • получить последнюю версию libpq под нужные ОС и архитектуру;
    • собрать динамическую библиотеку из кода на C++;
    • сохранить libpq и библиотеку в артефакты.

    Допускаю, что плохо знаю тонкости кроссплатформенной сборки; возможно, есть инструменты, которые щелкают эту проблему как дважды два. Почему их нет в поисковой выдаче? Я безвылазно сидел в Гугле и StackOverflow, повидал сотню разных ошибок – и ни разу не было ответа, мол, поставь программу X, и она все тебе соберет.

    Если такая программа есть или вы решали похожую проблему, расскажите, пожалуйста.

  • Хорошо или быстро

    Иногда говорят: я делаю хорошо, а нужно быстро. То есть противопоставляют эти две характеристики: либо одна, либо другая, но не одновременно.

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

    Если кто-то делает хорошо и медленно, возможны варианты: искать удачные подходы, набивать руку. Планировать работу, договариваться: возможно, какое-то требование было избыточным или исказилось, пройдя конфлюэнсы и джиры. Иногда можно срезать углы, аккуратно нарушить правила.

    Часто скорость снижает не качество, а нелепые требования. Например, написать код, используя кривую библиотеку – взять нормальную запрещено. Или хочется обратиться к базе, но нельзя – вызывай сервис, который ходит в базу и выдает то же самое, только на два порядка медленней.

    На проверку оказывается, что главный враг качества – внутренние заморочки, и объяснение у них следующее: мы делаем так, потому что мы так делаем.

    Хорошая практика в том, чтобы следить за ощущениями и спрашивать себя: что мешает сделать работу быстро и качественно? При этом ни в коем случае не врать: если это коллега, руководитель или предубеждение, то не пытаться это скрыть. Честно сказать: если выбор решения за мной, я сделаю за X дней, если как говорят – за 3X дней.

    Качеству и скорости нужен третий компонент – свобода действий. Он – тот самый ингредиент, с которым все удается и прогресс идет. Нет свободы – и начинаются торги: долго, но качественно. Быстро, но тяп-ляп.

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

  • Глава 2. Базовые возможности JSON

    , , ,

    Главы

    1. Введение в документы
    2. Базовые возможности JSON
    3. JSON в таблицах
    4. Индексирование JSON
    5. Ссылки и ограничения в документах
    6. Язык путей JSONPath
    7. Отчеты и функции
    8. Функции на языке Python
    9. Версионирование и архивация документов
    10. Релевантный поиск

    Содержание

    В этой главе мы перейдем к техническим вещам: познакомимся с типом JSON в Postgres. Мы рассмотрим основные операции над ним и ряд функций, которые облегчат работу. Покажем неочевидные трюки, когда JSON полезен: как прочитать его по частям, как передать с его помощью таблицу и многое другое.

    Установка и подключение

    Прежде чем начать работу, убедитесь, что у вас установлен сервер Postgres. На момент написания книги его последняя версия – 18.1, но ранние тоже подойдут. Случаи, когда та или иная техника требуют особой версии, оговариваются особо.

    Если у вас нет Postgres, то вот как установить его в разных системах. Прежде всего это официальный сайт проекта. Посетите страницу загрузок и укажите операционную систему. Вас направят на другую страницу с ссылкой на установщик.

    Компания PostgresPro предлагает графический инсталлятор для Windows. Postgres Pro – это расширенная база данных со своими расширениями и функциями. Наша книга опирается на стандартный Postgres, поэтому Pro-версия тоже подойдет.

    Read more →

  • Совет дня №34

    ,

    Банально, но все же: если какой-то атрибут уникален, нужно повесить на него уникальное ограничение. С ним физически невозможно добавить в базу дубликат. Многие разработчики проверяют уникальность вручную: если нет, то вставить, если есть, то ругнуться. Однажды запрос приходит от потребителя, который не в курсе этих заморочек, и получается дубль. Со временем на него ссылаются другие сущности, он обрастает связями. Когда дубль вскрывается, и все чешут голову — как же так получилось?

    Удаление дубликата, обросшего связями — очень напряжная вещь. Нужно построить дерево ссылок, спланировать перенос, всех предупредить. Раздражает, что это тупая работа, которая не двигает вперед ни тебя, ни фирму. Просто слив времени из-за чужого косяка.

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

    Опытный разработчик знает, как исправить дубль; более опытный знает, как его не допустить.

    При создании таблицы поле можно пометить словом unique. При этом Postgres создаст уникальный btree-индекс на это поле. Заметим, что уникальность допускает значения NULL, потому что они не равны друг другу. Если нулы запрещены, добавьте в поле NOT NULL.

    Можно задать свой уникальный индекс, при этом использовать не колонку, а выражение. Например, уникальность кода или почты нужно проверять без учета регистра и отбрасывая пустые символы по краям. Индекс может быть таким:

    create unique index idx_user_email_u_btree
on users using btree
(trim(lower(email)))

    После этого в базе не может быть емейлов "Ivan@test.com" и " iVan@TEST.com " одновременно.

    Уникальность можно повесить на поле JSON-документа. Если код находится где-то в глубине, индекс выглядит так:

    create unique index idx_item_code_u_btree
on users using btree
(lower(data #>> '{attrs,path,to,code}'))

    Следите за уникальностью. Добавить ее — дело пяти минут, исправлять последствия — пять дней.

  • Совет дня №33

    ,

    Разберем еще один случай, когда нужен срез строк – геохэш (geohash). Это быстрый и дешевый способ кодировать положение объектов, а также искать их.

    Представим себе карту мира. Точки отсчета – Лондон и экватор. Это квадрат. Разделим его пополам по вертикали. Если человек живет западней Лондона, запишем 0, если восточнее – то 1. Теперь разделим область по горизонтали. Если человек находится северней, добавим 0, если южнее – 1. Продолжаем дробить область по горизонтали и вертикали и накапливать нули и единицы. В результате мы достигнем квадрата, достаточного малого, чтобы остановиться. Скажем, если речь о здании, квадрат может быть 25x25 метров. Если стадион, деревня или город, то еще больше.

    Нули и единицы образуют цепочку бит. Переводим их в байты и кодируем base53 или похожим алгоритмом. Получаем строку вида hsGHrgga3ysg6, которая указывает на квадрат определенной точности.

    Прелесть вот в чем: есть взять какой-то квадрат, то хэши всех точек в нем имеют общую часть. Например, есть квадрат hsGHrgga. В нем будут точки hsGHrgga3ysg6, hsGHrgga3ysgS, hsGHrgga6sg и так далее. Это значит, для их поиска нужно выбрать строки, которые начинаются с hsGHrgga. С индексом btree, что мы рассмотрели в прошлом совете, это крайне эффективно.

    Похоже устроен поиск ближних объектов. Скажем, точка hsGHrgga3ysg6 указывает на кинотеатр и нужно показать ближайшие. Отломаем у хэша последний символ и таким образом поднимемся на квадрат выше: hsGHrgga3ysg. Найдем по нему все кинотеатры и покажем. Что-то лишнее можно почистить в приложении, так дешевле. Вопрос лишь в том, насколько “отъезжать” при поиске: на один символ, два и так далее.

    Недостаток геохеша в том, что один символ означает сразу восемь операций разбиения (потому что восемь битов). Если это критично, рассмотрите тип bit в Postgres. Это битовая маска заданной длины, при этом поддерживаются наложение другой маски, сравнение, вхождение и так далее.

    Геохэш работает не только для плоскости, но и кубов. Пространство – это куб, который делится на 8 под-кубов, те – еще на 8 и так далее. Чтобы продвинуться на шаг, нужны три бита – по числу измерений. Такая структура называется октодеревом. По аналогии можно работать с многомерным пространством.

    И не только многомерным – одномерным! Представим, на отрезке множество точек. Делим отрезок пополам: слева – 0, справа – 1. Переходим на нужный под-отрезок, делим пополам и так далее, пока не достигнем нужной точности. Накопленные нули и единицы кодируем в строку. Потом, чтобы получить точки в нужном отрезке, делаем срез по префиксу.

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

  • Совет дня №32

    ,

    В Postgres индексы бывают разных типов. Самый базовый и нужный называется btree, который основан на одноименной структуре данных – дереве B-Tree. Оно состоит из распределительных узлов, и на последнем уровне находятся пары вида (значение, страница).

    Btree поддерживает равенство и сравнение. Это значит, в нем можно искать по точному значению и диапазонам, а еще он подходит для сортировки, потому что упорядочен.

    В случаях, когда нужно частичное сравнение, индекс btree не подходит. Вместо него используют Gin или Gist (отдавая предпочтение первому). Эти индексы сложнее и в целом медленнее btree. Поэтому пока возможно, используйте btree.

    Есть, однако, лазейка, чтобы использовать btree для частичного сравнения. Если применить его к строке с особой опцией, можно искать по началу строки оператором (i)like и регулярным выражением.

    Предположим, в таблице demo хранятся пути к файлам:

    create table demo(
    id integer primary key,
    path text not null
);

    Сгенерируем миллион файлов. Пути начинаются с года, месяца, дня и часа. Даты разнообразны в рамках десяти лет:

    insert into demo
select
    x,
    format('%s/%s/picture.jpeg', to_char((now() - interval '10 years' *  random()), 'yyyy/MM/DD/HH'), gen_random_uuid())
from
    generate_series(1, 999999) as seq(x);

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

    create index path_btree on demo
using btree
(path text_pattern_ops);

    Выберем файлы за октябрь 2023 года:

    select * from demo
where path like '2023/10/12%'
limit 100;

    Справа от like стоит шаблон, а не простой текст. Символ % означает любые символы. Вот что вернет запрос:

    ┌────────┬─────────────────────────────────────────┐
│   id   │                path                     │
├────────┼─────────────────────────────────────────┤
│ 213875 │ 2023/10/12/01/00ec...af263/picture.jpeg │
│ 670319 │ 2023/10/12/01/04e2...67afd/picture.jpeg │
│  34516 │ 2023/10/12/01/063a...ebddc/picture.jpeg │
│ 122843 │ 2023/10/12/01/3237...6ffd7/picture.jpeg │
│ 227530 │ 2023/10/12/01/5a48...c4ec0/picture.jpeg │
│ 141900 │ 2023/10/12/01/6a78...da021/picture.jpeg │
│ 663626 │ 2023/10/12/01/9d6d...84da7/picture.jpeg │
│ 154138 │ 2023/10/12/01/a02e...5570c/picture.jpeg │
│  37955 │ 2023/10/12/01/a465...47a7a/picture.jpeg │
│ 864446 │ 2023/10/12/01/ae47...943d9/picture.jpeg │
│ 196849 │ 2023/10/12/01/cd15...25874/picture.jpeg │

    Но гораздо интересней план:

    explain analyze
select * from demo
where path like '2023/10/12%'
limit 100;

│ Limit  (cost=0.55..8.57 rows=100 width=68)
│ (actual time=0.054..0.364 rows=100 loops=1)
│   ->  Index Scan using path_btree on demo
│       (cost=0.55..8.57 rows=100 width=68)
│         Index Cond: ((path ~>=~ '2023/10/12'::text)
│                  AND (path ~<~ '2023/10/13'::text))
│         Filter: (path ~~ '2023/10/12%'::text)
│ Planning Time: 0.375 ms
│ Execution Time: 0.400 ms
└────────────────────────────────────────────────────

    Видим, что Postgres поступает хитро: заключает путь в диапазон 2023/10/12 и 2023/10/13. Цифра 3 на конце получилась как следующий символ за 2.

    Попадаем в индекс, стоимость копеечная.

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

    Индекс и оператор like позволяют срезать пути по лидирующей строке. При этом не обязательно с точностью до папки. Например, шаблон может быть таким:

    2025/10/23/%cat%.jpeg

    Так мы получим все фотографии в папке 2025/10/23/… со словом cat в названии и расширением jpeg. Кроме шаблонов like, индекс поддерживает регулярки, и с ними критерий поиска можно описать точнее.

    Чем больше лидирующих символов мы задали, тем быстрее будет поиск.

    Еще один трюк: что если нужно искать с конца строки? Например, имеется таблица товаров с серийными номерами:

    create table demo2(
    id integer primary key,
    serial_number text not null
);

    Вставим миллион серийных номеров:

    insert into demo2
select
    x,
    to_char(random() * 1000000000000, '0000-0000-0000')
from
    generate_series(1, 999999) as seq(x);

┌────────┬─────────────────┐
│   id   │  serial_number  │
├────────┼─────────────────┤
│      1 │  7084-1644-4953 │
│      2 │  2694-3476-5136 │
│      3 │  3274-5880-3765 │
│      4 │  9346-6945-3461 │
│      5 │  3352-3981-1479 │
│      6 │  7103-7860-4732 │
│      7 │  2634-9208-2518 │
│      8 │  1485-3601-0146 │
│      9 │  8068-5128-1222 │
│     10 │  5832-3252-5642 │

    Сотрудники ищут продукцию по последним числам серийного номера. Чтобы сработал индекс btree, сделаем функциональный индекс на выражение reverse(serial_number). В результате в индексе будут храниться перевернутые номера:

    create index path_btree_rev on demo2
using btree
(reverse(serial_number) text_pattern_ops);

    Чтобы искать по ним, выражение поиска тоже нужно перевернуть. Давайте найдем все номера, которые заканчиваются на -0500:

    select * from demo2
where reverse(serial_number) like reverse('%-0500')
limit 100;

    Результат:

    ┌────────┬─────────────────┐
│   id   │  serial_number  │
├────────┼─────────────────┤
│ 237074 │  5088-3410-0500 │
│ 231067 │  0411-7020-0500 │
│ 728812 │  3489-6520-0500 │
│ 618494 │  3972-6720-0500 │
│ 486950 │  4871-5330-0500 │
│ 634762 │  8038-7440-0500 │
│ 733815 │  8856-2250-0500 │
│ 451464 │  3640-0450-0500 │
│ 868649 │  7289-2270-0500 │
│ 485383 │  7016-0370-0500 │
│ 782061 │  4076-8080-0500 │
│ 234715 │  4279-2180-0500 │
│  36948 │  9033-7280-0500 │
│ 460010 │  5881-8090-0500 │

    Самое интересное – план:

    │ Limit  (cost=0.42..8.45 rows=100 width=16) (actual
│   ->  Index Scan using path_btree_rev on demo2  (co
│         Index Cond: ((reverse(serial_number) ~>=~ '
│         Filter: (reverse(serial_number) ~~ '0050-%'
│ Planning Time: 0.286 ms
│ Execution Time: 1.088 ms
└────────────────────────────────────────────────────

    Работает!

    Повторю, что btree и text_pattern_ops работают только для начала строки. Если нужен поиск посередине, обратитесь к расширению pg_tgrm (триграммы). Этот индекс, однако, требует Gin.

    У text_pattern_ops есть еще один полезный сценарий, но о нем – в следующий раз.

Страница 1 из 108