Разгоним Unicode в PostgreSQL / forpes.ru

Главная
Разгоним Unicode в PostgreSQL

Разгоним Unicode в PostgreSQL

11.11.2025 21:31

lastmac 0 8 Источник

Всем привет!

Меня зовут Александр Борисов, я главный эксперт по технологиям в СберТехе. В статье расскажу про свой алгоритм, который позволил повысить скорость Unicode в PostgreSQL 18. На эту тему уже выпущен патч Optimization for lower(), upper(), casefold() functions, принятый сообществом PostgreSQL.

Статья будет интересна разработчикам, которые работают с большими объемами текстовых данных, а также всем, кто следит за развитием PostgreSQL и интересуется оптимизацией.

Начнём с краткого обзора: что же удалось ускорить в PostgreSQL?

Повышаем производительность функций lower(), upper(), casefold():

латиницы — на 20%;
кириллицы — на 100%;
всего Unicode — на 20%.

Увеличиваем производительность normalize() [0] в два раза. А также уменьшаем размер объектных файлов.

Начнём издалека

В PostgreSQL есть такие функции, как lower(), upper(), casefold(), normalize(). Уверен, что многие о них слышали и использовали. Например, нередко разработчики, сравнивая две строки, приводят их к нижнему регистру с помощью функции lower() [1].

Как вы уже поняли, а скорее всего знаете, перечисленные выше функции преобразуют текст следующим образом:

lower() — в нижний регистр;
upper() — в верхний регистр;
casefold() — нормализует текст для регистронезависимого сравнения;
normalize() — выполняет нормализацию Unicode.

Уверен, что большинство даже догадываются, как работают перечисленные функции.
Ну а чего тут сложного: есть у нас большая буква П, а мы хотим, чтобы она стала маленькой — п. Как реализовать преобразование? Всё верно — необходимо иметь таблицу сопоставления:

...
П => п
Р => р
С => с
Т => т
и так далее

Каждый символ — это кодовая точка (codepoint) в таблице Unicode. Иначе говоря, это число. К примеру, в верхнем регистре П — это 1055 (0x041F в шестнадцатеричном формате, обычно принято писать U+041F), а в нижнем регистре п — 1087 (U+043F). Осознав эту информацию, мы можем приведённую выше таблицу преобразования символов представить в виде чисел:

1055 => 1087
1056 => 1088
1057 => 1089
1058 => 1090

Вроде бы всё просто — бери и преобразовывай! Но, как это часто бывает, на практике не всё так однозначно.

Проблемы

Символов в Unicode много, пригодных для преобразования в тот или иной регистр — около 3000. Ну ладно, первое, что может прийти в голову — давайте поместим их все в одну таблицу, и дело с концом, всего-то 3000.
Но здесь возникает проблема: коды символов (codepoints) идут не подряд. Диапазон для преобразования начинается с 0x0041 (65) и заканчивается 0x1E921 (125217). То есть числа расположены далеко не последовательно, с большими пробелами между ними. Конечно, можно создать таблицу на 125217 значений и не заморачиваться.
Однако нужно понимать, что таких таблиц необходимо минимум три — для lower(), upper() и casefold() — а это уже 375651 значений. Многовато.
Что же делать? Пришло время вспомнить все доступные алгоритмы. Какой из них лучше всего подойдет? В интернете обычно используют три подхода:

Раз: бинарный поиск [2]

Плюсы:

небольшой размер таблиц. Минусы:
медленный поиск;
необходимо хранить исходный codepoint чтобы сравнивать искомое значение (3к * uint32_t).

Два: хеш-таблица [3]

Плюсы:

быстрый поиск. Минусы:
нужна дополнительная таблица;
необходимо хранить исходный codepoint чтобы сравнивать искомое значение (3к * uint32_t).

Три: радиксные деревья [4]

Плюсы:

быстрый поиск;
не нужно хранить искомое значение для сравнения. Минусы:
нужна дополнительная таблица (но она маленькая);
дерево получается большим и избыточным, но это компенсируется тем, что не нужно хранить исходное значение.

Что использует PostgreSQL?

В PostgreSQL используют все три описанных подхода, но в разных условиях. Например, для юникод-номализации на фронтенде применяется бинарный поиск по таблицам, а на бэкенде — хеш-таблицы. Это связано с тем, что для фронтенда важен размер объектных файлов. Чем они меньше, тем лучше, а скорость работы в данном случае стоит на втором месте.

Муки выбора

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

Цель и ожидаемый результат

необходимо очень быстро находить нужные значения в таблице;
таблицы не должны иметь большой объем.

Вперед к приключениям!

Давайте посмотрим, что у нас есть:

Есть список codepoint — ограниченный список.
Codepoint идут по возрастанию;
Между codepoint есть разрывы, codepoint идут не подряд.

Если присмотреться ещё внимательнее, то можно увидеть, что codepoint идут некоторыми диапазонами. Для примера:
Первый диапазон:

0x0041 (65)
0x0042 (66)
0x0043 (67)
0x0044 (68)
0x0045 (69)
0x0046 (70)
0x0047 (71)
0x0048 (72)
0x0049 (73)
0x004A (74)
0x004B (75)
0x004C (76)
0x004D (77)
0x004E (78)
0x004F (79)
0x0050 (80)
0x0051 (81)
0x0052 (82)
0x0053 (83)
0x0054 (84)
0x0055 (85)
0x0056 (86)
0x0057 (87)
0x0058 (88)
0x0059 (89)
0x005A (90)

Второй:

0x00B5 (181)

Третий:

0x00C0 (192)
0x00C1 (193)
0x00C2 (194)
0x00C3 (195)
0x00C4 (196)
0x00C5 (197)
0x00C6 (198)
0x00C7 (199)
0x00C8 (200)
0x00C9 (201)

и так далее.

Уже что-то: не просто хаотичный разброс чисел, какая-то группировка присутствует. При этом разрывы между диапазонами могут быть совершенно разными: где-то разница составляет 1–3, а где-то — 1000.

Но что с этим делать?

Признаться, я испробовал множество разных подходов, провёл множество экспериментов, замеров скорости и размера. В итоге муза ударила меня по голове, и пришла ИДЕЯ!

Идея: Sparse Array

А что если искать не по этой таблице (основной таблице), а иметь какой-то индекс рядом, как у хеш-таблицы? Но, казалось бы, тогда придётся хранить искомое значение — это uint32_t, между прочим, а оно нам не нужно.
В этот момент рассуждений и пришла идея: а давайте не просто сгенерируем таблицу с индексом, а ещё и функцию, которая будет использовать этот индекс. Причём функцию не простую — в ней будет бинарный поиск в виде ветвлений (if, else).
На этом моменте, если бы я не был автором статьи, я бы спросил: «Что он такое говорит, чем ему поможет функция?!»

Алгоритм Sparse Array

У нас есть диапазоны Unicode codepoints. Возьмём для примера (это условность, используем небольшие числа, чтобы показать суть):

1-5, 8-10, 20-24

Основная таблица выглядит так:

uint32_t main_table[] =
{
    /* Значение по индексу 0 является заглушкой. */
    0, 1, 2, 3, 4, 5, 8, 9, 10, 20, 21, 22, 23, 24
}

У нас есть знание о каждом разрыве (назовём это offset), где он начинается и как долго продолжается.

от 5 до 8: 3
от 10 до 20: 10

Теперь мы можем создать генератор диапазонов с настраиваемым лимитом на разрыв. Группируем codepoints в диапазоны, где разница между соседними элементами не превышает установленный лимит. Если разница больше, создаётся новый диапазон. Это позволит разбить последовательности на диапазоны, где разница между числами больше установленного лимита. Например, если есть числа 1, 2, 3, 5, 6 и лимит = 1, то разница между числами 3 и 5 составляет 2, что больше 1, поэтому будут созданы диапазоны 1-3 и 5-6.

Для нашего примера возьмём лимит в 4. У нас получится два диапазона:

1-10
20-24

Теперь все полученные периоды записываем в таблицу — это будет индексная таблица:

uint16_t index_table[] =
{
    /* Значение по индексу 0 является заглушкой. */
    0,

    /* Первый период 1-10. */
    1,
    2,
    3,
    4,
    5,
    0, /* Отсутствующие значения. */
    0, /* Отсутствующие значения. */
    8,
    9,
    10,

    /* Второй период 20-24. */
    11,
    12,
    13,
    14,
    15
}

То есть теперь у нас есть index_table — индекс, указывающий на позицию в основной таблице main_table. Теперь нам необходимо сгенерировать функцию, которая будет принимать значение и возвращать 0, если ничего не найдено, либо индекс в main_table.
Давайте сразу посмотрим, как будет выглядеть функция:

static inline uint16_t
get_index(uint32_t cp)
{
	if (cp >= 0 && cp < 11)
	{
		return index_table[cp - 0 + 0];
	}
	else if (cp >= 20)
	{
		if (cp < 25)
		{
			return index_table[cp - 20 + 11];
		}
	}

	return 0;
}

Функция содержит offset для каждого диапазона чисел.
С помощью if построен бинарный поиск.

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

Назад к PostgreSQL

Что же удалось добиться в PostgreSQL благодаря алгоритму Sparse Array?
Для функций lower(), upper(), casefold():

Удалено сохранение кодовых точек Unicode (uint32_t) во всех таблицах.
Сокращенно количество записей в основной таблице с 3003 до 1575 (удалены дубликаты).
Заменён указатель (по сути, uint64_t) на uint8_t в основной таблице.
Сокращенно время поиска записи в таблице.
Уменьшен размер конечного объектного файла.

Данные изменения уже приняты сообществом и появились в 18-й версии Postgres.

Для функции юникод нормализации normalize():

Удалено сохранение кодовых точек Unicode (uint32_t) во всех таблицах.
Сокращенно количество записей в основной таблице с 6843 до 3943 (удалены дубликаты).
Сокращенно количество записей в decomposition таблице с 5138 до 4304 (удалены дубликаты).
Удалены все хеш таблицы.
Сокращенно время поиска записи в таблице, в 2 раза.
Уменьшен размер конечного объектного файла.
Удалена рекурсия при нормализации.

Патч с ускоренным normalize() подан в сообщество.

Итог

Плюсы:

очень быстрый поиск;
не нужно хранить искомое значение для сравнения;
избавление от дублей. Минусы:
требуется дополнительная индексная таблица (не большая, uint16_t);
алгоритм не подходит для сильно разреженных диапазонов.

Сноски

[0] https://habr.com/ru/articles/45489/
[1] Такой подход считается не верным, необходимо использовать casefold().
[2] https://ru.wikipedia.org/wiki/Двоичный_поиск
[3] https://ru.wikipedia.org/wiki/Хеш-таблица
[4] https://ru.wikipedia.org/wiki/Сжатое_префиксное_дерево