Как Google оптимизирует сортировку данных в базах данных для поддержки множества языков

Термины и определения

Auxiliary Table (Вспомогательная таблица)

Вторая таблица базы данных, используемая для хранения многоязычного индекса сортировки. Содержит Sort Keys и ссылки на записи в основной таблице.

Collation Element (Элемент сопоставления)

Логическое отображение уровней сортировки в последовательность весов (например, первичный, вторичный, третичный вес), как описано в Unicode Collation Algorithm. Используется для генерации Sort Key.

Collation Element Mapping Table (Таблица отображения элементов сопоставления)

Таблица, которая хранит соответствия между последовательностями символов и последовательностями Collation Elements для определенного языка.

Combined Mapping Table (Объединенная таблица отображения)

Таблица, объединяющая Collation Element Mapping Tables для нескольких языков. Используется для параллельной генерации нескольких Sort Keys за один проход.

Degenerate Sort Keys (Вырожденные ключи сортировки)

Ключи сортировки, которые могут быть сгенерированы при использовании Combined Mapping Table, но которые не соответствуют правилам сортировки ни одного из поддерживаемых языков.

Sort Key (Ключ сортировки)

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

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает основной метод использования многоязычного индекса.

1. Для первой строки в первой таблице (содержащей строки на разных языках):
   • Вычисляется первый Sort Key для строки на первом языке.
   • Вторая таблица (Auxiliary Table) сохраняет первую запись, связывающую первый Sort Key с исходной строкой.
   • Вычисляется второй Sort Key для строки на втором языке.
   • Вторая таблица сохраняет вторую запись, связывающую второй Sort Key с исходной строкой.
2. Принимается запрос на отсортированный результат элементов из первой таблицы для первого языка.
3. Генерируется набор результатов, включающий первую запись для первой строки, позиция которой определяется на основе первого Sort Key.
4. Набор результатов фильтруется для удаления записей для строк на втором языке.
5. Набор результатов предоставляется пользователю.

Claim 2 (Зависимый от 1): Уточняет процесс индексации.

Система вычисляет Sort Key для строки на каждом из множества языков и сохраняет запись во второй таблице для каждого вычисленного Sort Key, который не является дубликатом ключа, ранее сохраненного в этой таблице. Это ключевой момент оптимизации размера индекса.

Claim 4 (Зависимый от 1): Детализирует обработку диапазонных запросов (типа SELECT BETWEEN).

1. Запрос указывает начальную и конечную строки.
2. Генерируются начальный и конечный Sort Keys для этих строк на первом языке.
3. Идентифицируются Sort Keys во второй таблице, которые находятся между начальным и конечным ключами.
4. Записи для строк из первой таблицы, связанные с этими идентифицированными ключами, добавляются в набор результатов.

Claim 5 (Зависимый от 1): Уточняет процесс фильтрации для диапазонных запросов.

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

Где и как применяется

Изобретение относится к уровню системы управления базами данных (СУБД) и оптимизации выполнения запросов, требующих сортировки (например, ORDER BY, BETWEEN) в многоязычной среде.

Применение в архитектуре поиска Google:

Патент не описывает применение этого механизма в стандартной архитектуре веб-поиска Google (Crawling, Indexing, Ranking и т.д.). Он не влияет на вычисление релевантности, PageRank или сигналов качества. Это инфраструктурная технология, которая может использоваться в любых приложениях Google, где требуется эффективная сортировка пользовательских данных по языковым правилам (например, сортировка контактов в Gmail, сортировка файлов на Google Диске или сортировка данных в отчетах Google Analytics/Search Console).

Входные данные:

• Строки данных из основной таблицы базы данных.
• Набор поддерживаемых языков и их правила сортировки (Collation Element Mapping Tables).
• Запрос пользователя на сортировку (например, SQL-запрос) с указанием языка.

Выходные данные:

• Отсортированный набор результатов, соответствующий правилам сортировки запрошенного языка.

На что влияет

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

• Типы контента/Запросы/Ниши: Не влияет на ранжирование каких-либо типов контента, запросов или тематик в поиске. Влияет на любые данные, которые могут быть отсортированы (имена, названия, адреса и т.д.) в рамках базы данных, использующей эту технологию.

Когда применяется

• Триггеры активации: Активируется при получении запроса к базе данных, требующего сортировки результатов в определенном языке (например, запрос с операторами ORDER BY или BETWEEN).
• Условия работы: Применяется в системах, которые должны поддерживать сортировку одного и того же набора данных по правилам нескольких разных языков.

Пошаговый алгоритм

Процесс А: Создание многоязычного индекса сортировки

1. Инициализация: Определяется основная таблица данных и набор поддерживаемых языков. Создается пустая вспомогательная таблица (Auxiliary Table).
2. Генерация ключей сортировки: Для каждой строки в основной таблице вычисляются Sort Keys для всех поддерживаемых языков. Может использоваться техника параллельной генерации (см. Процесс Б).
3. Сохранение в Auxiliary Table: Для каждого сгенерированного Sort Key система проверяет его наличие во вспомогательной таблице.
   • Если ключ уникален, он сохраняется вместе со ссылкой на исходную запись в основной таблице.
   • Если ключ уже существует (т.е. совпадает с ключом для другого языка или другой строки), дубликат не создается.

Процесс Б: Параллельная генерация ключей сортировки (Использование Combined Mapping Table)

Этот процесс оптимизирует Шаг 2 Процесса А.

1. Подготовка: Таблицы отображения элементов сопоставления (Collation Element Mapping Tables) для всех языков объединяются в Combined Mapping Table.
2. Получение строки: Принимается строка, для которой нужно сгенерировать ключи.
3. Рекурсивный обход: Система рекурсивно обходит строку, начиная с текущего смещения (offset).
4. Идентификация подстрок: На текущем смещении идентифицируются все возможные подстроки, имеющие запись в Combined Mapping Table.
5. Добавление элементов сопоставления: Для каждой идентифицированной подстроки соответствующий Collation Element добавляется к текущей последовательности. Процесс ветвится для каждой возможной подстроки.
6. Завершение последовательностей: Когда достигается конец строки, формируется полный набор возможных последовательностей Collation Elements.
7. Конвертация в Sort Keys: Каждая последовательность конвертируется в Sort Key путем объединения весов разных уровней (первичный, вторичный и т.д.).
8. Удаление вырожденных ключей (Опционально): Система может удалить Degenerate Sort Keys, которые не соответствуют ни одному языку, хотя патент отмечает, что их сохранение может быть более эффективным.

Процесс В: Обработка запроса на сортировку (например, SELECT BETWEEN 'Start' AND 'End' на Языке L)

1. Получение запроса: Система получает запрос и язык сортировки L.
2. Генерация граничных ключей: Вычисляются Sort Keys для начальной ('Start') и конечной ('End') строк на языке L.
3. Запрос к Auxiliary Table: Извлекаются все записи из вспомогательной таблицы, чьи Sort Keys находятся между начальным и конечным ключами.
4. Формирование предварительного набора: Создается предварительный набор результатов на основе ссылок из Auxiliary Table.
5. Фильтрация результатов: Предварительный набор фильтруется:
   • Удаляются строки, которые фактически не находятся в диапазоне между 'Start' и 'End' согласно правилам сортировки языка L (ложные срабатывания из-за ключей других языков).
   • Удаляются дубликаты строк.
6. Вывод: Отфильтрованный и отсортированный набор результатов возвращается пользователю.

Какие данные и как использует

Патент является чисто техническим и фокусируется исключительно на механизме сортировки строк текста. Он не использует стандартные SEO-факторы.

Данные на входе

• Контентные факторы: Используются только сами строки текста, хранящиеся в базе данных, для генерации ключей сортировки.
• Языковые данные: Критически важными являются правила сортировки для разных языков, представленные в виде Collation Element Mapping Tables или Combined Mapping Table.

Другие факторы (технические, ссылочные, поведенческие, временные и т.д.) в патенте не упоминаются.

Какие метрики используются и как они считаются

В патенте не используются метрики для оценки качества или релевантности. Используются только вычисленные значения для сортировки.

• Sort Key: Вычисляется на основе Collation Elements (первичные, вторичные, третичные веса) для строки в соответствии с правилами языка.
• Сравнение ключей: Используется стандартное байтовое сравнение Sort Keys для определения порядка сортировки.

1. Патент инфраструктурный, а не алгоритмический: Основной вывод заключается в том, что этот патент описывает метод оптимизации производительности баз данных и сокращения размера индекса при работе с многоязычными данными. Он не имеет отношения к алгоритмам ранжирования Google.
2. Разделение сортировки и ранжирования: Патент четко демонстрирует разницу между сортировкой (определение порядка по заданному критерию, например, алфавиту) и ранжированием (определение порядка по релевантности и качеству). SEO-специалисты работают над улучшением ранжирования, а этот патент решает задачи сортировки.
3. Эффективность за счет устранения дубликатов: Ключевая инновация заключается в признании того, что многие языки имеют одинаковые правила сортировки для многих строк, и в использовании этого факта для создания единого, компактного Auxiliary Table вместо отдельных индексов для каждого языка.
4. Обработка языковых различий: Система учитывает сложные языковые нюансы (например, "German Phonebook" порядок) и использует Collation Elements для точного определения порядка сортировки.
5. Отсутствие практической ценности для SEO: Патент не дает никаких инсайтов о том, как улучшить позиции сайта в поисковой выдаче, какие факторы контента или ссылок важны для Google.

Best practices (это мы делаем)

Патент описывает внутренние процессы Google без прямых рекомендаций для SEO. Практических выводов для SEO-специалистов нет.

Worst practices (это делать не надо)

Патент не описывает SEO-тактики, которые становятся неэффективными или опасными. Практических выводов для SEO-специалистов нет.

Стратегическое значение

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

Практические примеры

Практических примеров для SEO нет. Пример из области баз данных:

Сценарий: Сортировка списка контактов на разных языках

1. Задача: Приложение для контактов должно сортировать имя "Töch" по-разному для пользователей из Германии и Швеции.
2. Индексация: Система генерирует Sort Keys:
   • Немецкий: 4D 43 2B 35...
   • Шведский: 4D 5A A3 06...
   Оба ключа сохраняются в Auxiliary Table.
3. Запрос (Немецкий пользователь): Пользователь запрашивает список контактов. Система использует немецкие Sort Keys. "Töch" будет отсортирован перед "Z".
4. Запрос (Шведский пользователь): Пользователь запрашивает тот же список. Система использует шведские Sort Keys. "Töch" будет отсортирован после "Z".
5. Оптимизация: Для имени "John", которое сортируется одинаково в обоих языках, в Auxiliary Table будет сохранен только один Sort Key, что экономит место по сравнению с созданием двух отдельных индексов.