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


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

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

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

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

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

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

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 сравнивает строки двух таблиц. Если таблицы большие, он обходит индекс; если индекса нет, выполняет полное сканирование. При миллиарде записей этот процесс занимает от секунд до десятков секунд.

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

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

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


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

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

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

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

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

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

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


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

SIDX (Semantically-Aligned Index) — исследование того, как построить такой идентификатор. В грамматике GEUL уже есть место Reference, указывающее на объект через SIDX (GEUL-SIDX). Но ширина и способ назначения ещё не решены. Их определят по накопленной статистике использования. Ниже для объяснения в качестве примера взяты 64 бита.

Биты SIDX — не случайное число. Каждой позиции бита приписан смысл.

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

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

Чем младше биты, тем конкретнее информация.

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

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

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

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


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

Практическая сила SIDX видна в цифрах.

Пусть есть миллиард сущностей, у каждой 64-битный SIDX. Общий объём: 1 миллиард × 8 байт = 8 ГБ.

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

Нужно найти «сущности, которые являются людьми и происходят из Восточной Азии». Если старшие биты содержат флаг «человек» и код «Восточная Азия», отфильтровать можно одной битовой маской.

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

for each sidx in 1_миллиард:
    if (sidx & mask) == target:
        добавить в кандидаты

Эта операция распараллеливается с помощью SIMD. Предел задаёт не вычисление, а пропускная способность памяти. В предварительном измерении для SILK сканирование маской 100 миллионов 128-битных сигнатур (1,6 ГБ) заняло около 27 миллисекунд на 8 потоках Go. При той же скорости миллиард 64-битных SIDX (8 ГБ) займёт немногим больше 0,1 секунды.

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

Ноль JOIN. Ноль обходов дерева индекса. Одна битовая операция AND.


Какой должна быть ширина?

Сначала я думал, что нужно больше места.

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

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

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

Достаточно сузить миллиард записей до десяти тысяч. Остальное сделает точная проверка.

Это как контрольно-пропускной пункт. На платной автодороге, чтобы по номерному знаку понять, что «эта машина едет в сторону провинции Кёнгидо», не нужно знать, что лежит в багажнике.

Значит, 64 бит, возможно, хватит. Старшими битами — тип и крупную классификацию, младшими — детальную, и сузить миллиард до десяти тысяч, похоже, вполне по силам. 64 бита = четыре 16-битных слова. Легко даже внутри потока.

Но это пока гипотеза. GEUL не определяет ширину за письменным столом. Среди кандидатов вроде 4 WORD (64 бита) и 16 WORD выбор сделают по реальной статистике использования. До тех пор объекты указываются идентификаторами, выдаваемыми по порядку, а после назначения SIDX оба идентификатора связываются как один и тот же объект.


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

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

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

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

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

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

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

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


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

Самая интригующая возможность, которую открывает семантически выровненный индекс:

что, если запрос на естественном языке можно превратить во временный SIDX?

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

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

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

Сверив подробную информацию с кандидатами, получаем окончательный ответ.

Поиск и связывание сущностей (entity linking) могут стать одним механизмом. Без отдельной поисковой системы, без отдельного конвейера NER (распознавания именованных сущностей), одним сравнением SIDX.


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

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

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

Но для «найди все сущности-людей из Восточной Азии» оно слабо. Поиск по составным условиям требует пересечения нескольких индексов, а стоимость пересечения резко растёт с объёмом данных.

Полное сканирование SIDX + SIMD — другой подход.

Если B-дерево — телефонный справочник, быстро отвечающий «кто живёт по этому адресу», то сканирование SIDX — профилирование, быстро отвечающее «у кого такие признаки».

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

Тип запросаB-деревоСканирование SIDX
Поиск по конкретному IDO(log n), оптимальноНе нужно (решается хешем)
Фильтрация по составным условиямНужны JOIN, медленноОдин битовый AND, быстро
Поиск похожих сущностейНевозможноВозможно по сходству битов
ВставкаO(log n), перебалансировкаO(1), дописывание
Сложность реализацииВысокаяНизкая

Они не конкурируют, а делят работу. Сегодня SILK отвечает на точные запросы вроде «документы с предикатом P106 и объектом Q169470» с помощью отсортированных прогонов и двоичного поиска. Сканирование битовых сигнатур как первичный фильтр перед этим запланировано следующим шагом.

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


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

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

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

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

Назначение Codec в грамматике GEUL следует тому же принципу. Форматы с подтверждённой частотой получают короткий прямой код внутри TAG WORD, а редкие уходят в форматы Issuer с расширенным TAG.

Мудрость Хаффмана пронизывает весь этот дизайн. Наименьшая цена — для самого используемого.


Резюме

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

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

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