Почему семантически выровненный индекс?

Что происходит, когда идентификатор – это знание, а не адрес

Адрес ничего не знает

Чтобы найти Ли Сунсина в базе данных, нужен идентификатор.

В Wikidata идентификатор Ли Сунсина – Q8492.

Это число указывает на Ли Сунсина. Но сама строка Q8492 ничего не знает.

Она не знает, человек это или здание. Она не знает, кореец это или гражданин Франции. Она не знает, фигура это XVI или XXI века. Она не знает, жив этот человек или мёртв.

Q8492 – это адрес. Почтальон, доставляющий письма, понятия не имеет, что написано внутри конверта. Он просто смотрит на адрес на конверте и доставляет.

UUID – то же самое. 550e8400-e29b-41d4-a716-446655440000. 128 бит случайных чисел. Уникальный лишь ради избежания коллизий – он ничего не сообщает о том, на что ссылается.

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

Чтобы узнать, нужно перейти по ссылке

Почему это проблема?

Предположим, вы хотите найти “мужчину-философа немецкого гражданства, родившегося в XIX веке”.

В традиционной базе данных это выглядит так:

1. Фильтрация таблицы persons по gender = 'male'
2. JOIN с таблицей nationalities и фильтрация country = 'Germany'
3. JOIN с таблицей birth_dates и фильтрация year BETWEEN 1800 AND 1899
4. JOIN с таблицей occupations и фильтрация occupation = 'philosopher'

Четыре операции JOIN. Каждый JOIN сравнивает строки двух таблиц. Если таблицы большие, он обходит индекс; если индекса нет, выполняет полное сканирование. При миллиарде записей этот процесс занимает от секунд до десятков секунд.

Почему всё так сложно?

Потому что идентификатор ничего не знает. Глядя на Q8492, невозможно сказать, немец это или кореец, поэтому приходится обращаться к другой таблице за этой информацией.

На каждый вопрос приходится переходить туда, куда указывает идентификатор. Это та цена, которую базы данных платят уже пятьдесят лет.

Что, если бы идентификатор уже знал?

Перевернём предпосылку.

Что, если бы сам идентификатор содержал существенную информацию?

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

Чтобы найти “немецкого мужчину-философа XIX века”, JOIN-операции становятся ненужными.

Сканируя миллиард идентификаторов, можно мгновенно определить соответствие каждого, исследуя его биты.

Это основная идея семантически выровненного индекса.

Выравнивание смысла в идентификаторе

SIDX (Semantically-Aligned Index) – это 64-битный идентификатор.

Эти 64 бита – не случайные числа. Смысл присвоен позиции каждого бита.

Старшие биты содержат самую важную информацию. Какой это тип сущности? Человек, место, событие, концепция?

Следующие биты содержат классификационную информацию. Если это человек – какой эпохи? Из какого региона?

Младшие биты несут всё более конкретную информацию.

Ключевой принцип таков:

Порядок битов – это порядок важности информации.

Самая фундаментальная классификация вверху, самые тонкие различия внизу.

Это не просто сортировка. Это философия проектирования.

От миллиарда к десяти тысячам за один проход

Практическая мощь SIDX проявляется в цифрах.

WMS содержит один миллиард сущностей. SIDX каждой сущности – 64 бита. Общий размер: 1 миллиард x 8 байт = 8 ГБ.

Эти 8 ГБ целиком помещаются в память.

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

mask   = 0xFF00_0000_0000_0000  (старшие 8 бит: тип + регион)
target = 0x8100_0000_0000_0000  (человек + Восточная Азия)

for each sidx in 1_billion:
    if (sidx & mask) == target:
        add to candidates

Эта операция параллелизуется с помощью SIMD. С AVX-512 вы сравниваете 8 SIDX одновременно одной инструкцией. Сканирование 1 миллиарда записей: примерно 12 миллисекунд.

На GPU? Менее 1 миллисекунды.

Миллиард записей сужен до десяти тысяч. Детальная фильтрация оставшихся десяти тысяч – мгновенна.

Ноль JOIN-операций. Ноль обходов индексных деревьев. Всего одна побитовая операция AND.

Почему 64 бит достаточно

Поначалу я думал, что нужно большее пространство.

32 байта (256 бит). 32-мерный вектор FP16. Я пытался втиснуть каждый ключевой атрибут сущности в идентификатор. Человек ли это, пол, гражданство, эпоха, профессия, регион, статус жизни, путь классификации…

Но затем я понял одну вещь.

Идентификатору не нужно знать всё.

Ему нужно лишь сузить миллиард записей до десяти тысяч. Остальное берёт на себя WMS.

Думайте об этом как о контрольном пункте. На пропускном пункте автомагистрали, чтобы определить, что “этот автомобиль направляется в провинцию Кёнги” по номерному знаку, не нужно знать, что загружено в багажник.

64 бит достаточно. Используйте старшие биты для типа и общей классификации, а младшие – для более тонкой классификации. 64 бит более чем достаточно, чтобы сузить миллиард записей до десяти тысяч.

И 64 бита = четыре 16-битных слова. Они естественно перетекают внутри потока. 32-байтный идентификатор сделал бы поток тяжёлым, но 64-битный SIDX лёгок и быстр.

Изящная деградация: смысл сохраняется даже при усечении битов

Ещё одна сильная сторона семантического выравнивания – характеристики деградации.

Поскольку биты SIDX упорядочены от наиболее к наименее важным, даже если младшие биты повреждены или усечены, основная информация в старших битах сохраняется.

Полные 64 бита:  "Ли Сунсин, морской командир Чосона XVI века"
48 бит:          "Военный деятель Чосона XVI века"
32 бита:         "Человек из Восточной Азии XVI века"
16 бит:          "Человек"
8 бит:           "Физическая сущность"

По мере усечения информации специфичность теряется, но самая фундаментальная классификация сохраняется до самого конца.

Это реализация принципа “изящной деградации” на уровне битов.

Даже если прерывание сети доставит лишь частичные данные, система знает: “Я не знаю точно, кто это, но речь как минимум о человеке” и может продолжить рассуждение.

Размытый контур лучше, чем полная тишина. Частичное понимание лучше, чем полный отказ.

Запрос становится идентификатором

Самая интригующая возможность, которую открывает семантически выровненная индексация, – это то, что запрос на естественном языке может быть преобразован во временный SIDX.

Пользователь спрашивает: “Кто был полководцем, разгромившим японский флот во время Имджинской войны?”

Кодировщик анализирует этот вопрос. Человек. Восточная Азия. XVI век. Военная тематика. Сборка этих атрибутов в биты порождает временный SIDX.

Этот временный SIDX сканирует миллиард SIDX в WMS. Сущности, чьи битовые паттерны наиболее похожи, выдвигаются в кандидаты. Ли Сунсин, Вон Гюн, Квон Юль, Ли Окги…

Перекрёстная проверка детальной информации по этим кандидатам даёт окончательный ответ.

Это объединяет поиск и связывание сущностей в единый механизм. Отдельная поисковая система не нужна. Отдельный конвейер NER (распознавания именованных сущностей) не нужен. Одного сравнения SIDX достаточно.

Почему не B-дерево?

Традиционные базы данных используют индексы на основе B-деревьев.

B-деревья отлично находят конкретное значение в отсортированных данных за O(log n). Для запроса “найти Q8492” они оптимальны.

Но для запроса “найти все сущности, которые являются людьми и происходят из Восточной Азии” они слабы. Поиск по составным условиям требует пересечения нескольких индексов, и стоимость пересечения резко возрастает с масштабом данных.

SIDX + SIMD-полное сканирование использует принципиально иной подход.

Если B-дерево – это телефонная книга, быстро отвечающая “кто живёт по этому адресу”, то SIDX-сканирование – это профилирование, быстро отвечающее “кто обладает этими характеристиками”.

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

WMS не использует B-деревья. Он загружает миллиард SIDX в память и выполняет полное сканирование с SIMD-битовыми масками.

Просто. Грубой силой. Быстро.

Мудрость Хаффмана

Структура распределения битов SIDX следует принципу кодирования Хаффмана.

В кодировании Хаффмана часто встречающиеся символы получают короткие коды, а редко встречающиеся – длинные.

В SIDX наиболее часто востребованная классификационная информация занимает старшие биты, а редко нужные детали – младшие.

Тот же принцип управляет префиксами типов пакетов этого языка. Самый высокочастотный Tiny Verb Edge получает самый короткий префикс. Низкочастотный Event6 Edge получает более длинный префикс.

Мудрость Хаффмана пронизывает каждый уровень этого проектирования. Ни один бит не тратится впустую. Минимальная стоимость для самого важного.

Резюме

Традиционный идентификатор – это адрес. Адрес ничего не знает.

1. Когда идентификатор не несёт смысла, приходится каждый раз переходить к данным. Это JOIN.
2. Четыре JOIN по миллиарду записей – медленно.
3. SIDX встраивает смысл прямо в идентификатор через семантическое выравнивание.
4. Одна побитовая AND сужает миллиард записей до десяти тысяч. Ноль JOIN-операций.
5. 64 бит достаточно. Идентификатору не нужно знать всё – ему лишь нужно сузить кандидатов.
6. Поскольку самая важная информация занимает старшие биты, основной смысл сохраняется даже при усечении битов.
7. Преобразование запроса на естественном языке во временный SIDX превращает поиск в векторную операцию.

В тот момент, когда идентификатор перестаёт быть адресом и становится знанием, правила базы данных меняются.