Статьи · Исследование

Как найти дубликаты SQL-запросов: пять алгоритмов

~12 мин · 30 000 SQL-запросов · PL/SQL и MySQL · июнь 2026

72% запросов, которые выглядели по-разному, оказались структурно идентичны. Их разделяло только форматирование. SHA-256 от текста не нашёл бы ни одного из них.

Зачем это нужно

Архив большой ERP-системы — 30 000 SQL-запросов. Разработчики копировали процедуры, меняли отступы, переименовывали псевдонимы. Парсить все 30 000 — часы работы. Найти дубли заранее — дубли получают результат из кэша бесплатно.

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

-- Это одно и то же?
SELECT id FROM orders WHERE status = 1
SELECT  id  FROM orders WHERE status = 999

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

Мы проверили пять. Вот что получилось.

Три уровня строгости

Алгоритмы разбились на три уровня в зависимости от того, что они считают «одинаковым»:

  • Уровень 1 — байтовое тождество. Лишний пробел = другой запрос.
  • Уровень 2 — структурное тождество. AST совпадает, форматирование не важно.
  • Уровень 3 — структурное сходство. «Похожие» запросы → один кластер.
уровень 1 (точные копии) уровень 2 (структурные дубли) уровень 3 (near-duplicate)

text_hash Точные копии — SHA-256 от сырых байтов

Самый простой: SHA-256 от сырых байтов SQL-строки. Парсер не нужен. Лишний пробел — уже другой хэш.

text_hash: SHA-256 от сырых байтов SQL-текста SELECT id FROM orders сырые байты, без разбора SHA-256 никакой нормализации пробел = другой хэш text_hash a3f8b2c1d4e5f6a7 16 hex-символов (первые)

Применение: идеален как первый фильтр. Нулевые ложные срабатывания. Но находит только буквально идентичные байты — то есть наименьшее множество дублей.

ast_hash Структурные дубли — нормализованный токен-поток

Парсер ANTLR4 строит дерево. L2HashVisitor обходит его слева направо. Узлы-правила он проходит насквозь — в хэш вносят только терминальные токены: пробелы и комментарии отброшены, ключевые слова приведены к UPPER. Накопленный поток токенов → SHA-256.

Результат: два запроса с разным форматированием, но одной структурой дают одинаковый ast_hash.

ast_hash: дерево обходится слева направо, терминалы собираются в плоский токен-поток statement ← объемлет все узлы ├─ SELECT → 'SELECT ' ├─ column_ref ← только структура │ ├─ f → 'F ' │ └─ id → 'ID ' ├─ FROM → 'FROM ' ├─ table_ref ← только структура │ ├─ dwh → 'DWH ' │ └─ orders → 'ORDERS ' ├─ AS → 'AS ' └─ f → 'F ' Плоский токен-поток (обход слева направо): 'SELECT' ▸ 'F' ▸ 'ID' ▸ 'FROM' ▸ 'DWH' ▸ 'ORDERS' ▸ 'AS' ▸ 'F' SHA-256 ast_hash: a3f8b2c1…

Ключевое свойство: ast_hash не зависит от форматирования — пробелы, переносы, комментарии не влияют на хэш. Именно этот алгоритм работает в продакшне в HOUND.

merkle_hash Строже: структура правил грамматики в хэше

То же дерево, но хэш идёт снизу вверх. Каждый лист хэширует свой токен. Каждый узел-правило — хэшируетcя от своего индекса rule_idx и хэшей всех своих детей. Разные правила → разные индексы → разные хэши, даже при одинаковом тексте.

merkle_hash: три шага снизу вверх — листья, правила, корень ① Листья: каждый хэширует только свой токен терминал f SHA-256 h_f = SHA-256("F") = 2a3f… терминал id SHA-256 h_id = SHA-256("ID") = 7c1e… терминал orders h_ord = SHA-256("ORDERS") = b8d5… ② Правило: SHA-256 от (idx_rule ‖ хэши всех детей в порядке обхода) idx_col =12 ‖ { h_f 2a3f… ‖ h_id 7c1e… } хэши детей SHA-256 column_ref H_col = SHA-256(12 ‖ h_f ‖ h_id) { h_ord b8d5… } хэши детей table_ref H_tbl = SHA-256(17 ‖ h_ord) ③ Корень: то же правило — хэш от idx_root и хэшей всех узлов первого уровня { h_sel a9b1… ‖ H_col 3d72… ‖ h_from c4f8… ‖ H_tbl f2a1… ‖ h_as 11e4… ‖ h_alias_f 2a3f… } SHA-256(idx_stmt ‖ …) statement merkle_hash = корневой хэш

Почему merkle строже ast_hash: один и тот же идентификатор в разных позициях дерева получает разный вклад в хэш, потому что rule_idx родителя разный. Например, f как псевдоним колонки (column_ref) и f как псевдоним таблицы (table_ref) дадут разные хэши. ast_hash их не различает — токен один и тот же.

rabin64 Быстрый XOR-fingerprint для файлов

Тот же нормализованный токен-поток, что у ast_hash, но CRC64 по полиному ECMA вместо SHA-256. Быстрее на CPU. Главное свойство — XOR-комбинируемость: хэш файла = XOR всех хэшей его запросов. Не нужно повторно обходить дерево.

rabin64: CRC64 по токенам, XOR для объединения запросов файла нормализованный токен-поток CRC64-ECMA 0xC96C5795D7870F42 byte-by-byte table lookup stmt_rabin64 64-bit unsigned ⊕ XOR по всем запросам файла file_rabin64 XOR всех stmt_rabin64 файла ⚠ Не криптографический — возможны коллизии. При N → 2³² стейтментов вероятность коллизий растёт. На корпусах <100k стейтментов — безопасен.

Применение: потоковое хэширование файлов с SQL-процедурами. Можно сравнить два файла целиком без разбора содержимого.

simhash64 Похожие шаблоны — Locality-Sensitive Hashing

64-битный SimHash из семейства LSH. Каждый токен голосует за каждый из 64 битов: берём SHA-256 токена, берём i-й бит — если 1, то acc[i] += +1, если 0 — acc[i] += −1. Финальный fingerprint: бит i = 1, если acc[i] > 0.

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

simhash64: каждый токен голосует по 64 аккумуляторам, знак суммы — бит SELECT id FROM orders для каждого токена: h = SHA-256(токен)[0:8] бит h[i] → +1 или -1 в acc[i] токен ↓ acc[0] acc[1] acc[2] acc[3] acc[4] acc[5] acc[6] acc[7] ··· (64 всего) SELECT +1 -1 +1 +1 -1 +1 -1 +1 ··· id +1 +1 -1 +1 +1 -1 +1 -1 ··· FROM +1 -1 +1 -1 +1 -1 +1 +1 ··· orders -1 +1 +1 -1 +1 +1 -1 +1 ··· Σ +2 0 +2 0 +2 0 0 +2 bit 1 0 1 0 1 0 0 1 ··· simhash64 10100100… LSH-свойство: похожие запросы → похожий словарь токенов → похожее голосование в 64 acc. → малое расстояние Хэмминга между fingerprint'ами. Пример: заменить "id" на "customer_id" → большинство бит совпадут → запросы в одной near-duplicate группе.

Что получилось на четырёх корпусах

30 000 SQL-запросов, два диалекта — PL/SQL и MySQL, четыре корпуса.

01
Три алгоритма уровня 2 — это один результат
ПараСовпадение
ast_hash = rabin64100%
ast_hash = merkle_hash100% (при единообразных кавычках)
ast_hash ≈ simhash6493–98%

Для дедупликации перед парсингом достаточно ast_hash — самого простого из трёх.

02
SimHash в 2–7 раз агрессивнее точных алгоритмов

Крупнейшая near-duplicate группа в PL/SQL-корпусе — 63 запроса CREATE TABLE с одинаковой структурой колонок, но разными именами таблиц: DWH-таблицы из одного scaffold-шаблона. ast_hash их различает (имя таблицы входит в токен-поток). SimHash объединяет — структурные токены доминируют в голосовании.

03
72% «разных» запросов разделяет только стиль записи

Два PL/SQL-корпуса разделяли 12 955 одинаковых ast_hash. Из них 28% — байтово идентичные. Оставшиеся 72% — одна структура, разное форматирование: один корпус прошёл через автоформат, второй нет. text_hash нашёл бы только 28%.

04
Диалекты — абсолютная изоляция

PL/SQL ∩ MySQL = ноль общих ast_hash. Даже SELECT id FROM t даёт разные хэши: парсеры разные, нормализация диалект-специфична. Сравнивать SQL через диалекты только хэшем нельзя.

Merkle vs ast_hash: когда что выбрать

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

Когда Merkle выгоднее

  • Инкрементальный парсинг. Merkle позволяет найти, какое именно поддерево изменилось между двумя версиями запроса — без повторного разбора всего AST. Достаточно сравнить хэши ветвей сверху вниз.
  • Строгая синтаксическая верификация. Если требуется различать "id" (ANSI), `id` (MySQL) и id без кавычек как три разные сущности — Merkle делает это автоматически, без дополнительного кода.
  • Нормализованный вход. Когда SQL перед хэшированием проходит через единый форматтер и цитирование унифицировано, проблема кавычек исчезает — и Merkle даёт чуть более точную сигнатуру, чем ast_hash.
  • Поддеревья как единицы кэширования. В некоторых query-оптимизаторах поддеревья AST кэшируются по отдельности. Merkle-хэш поддерева достаётся «бесплатно» при построении дерева снизу вверх.

Почему мы остались на ast_hash: доказательство через сложность

На нашем корпусе merkle_hash и ast_hash дали идентичный результат — расхождений не было (находка 1). Выбор определила стоимость вычисления. Докажем разницу строго.

Обозначения для одного запроса: n — число токенов (листьев AST), i — число внутренних узлов (правила грамматики).

Факт 1

ast_hash делает ровно 1 SHA-256-вызов на запрос.

Алгоритм: один проход по AST → токены в буфер → sha256(buffer). Одна инициализация, один финализирующий вызов. □

Факт 2

merkle_hash делает n + i SHA-256-вызовов на запрос.

По построению: каждый лист → SHA-256(token_bytes), каждый внутренний узел v → SHA-256(rule_idx ‖ h1 ‖ … ‖ hk). Итого ровно n + i вызовов. □

Лемма: i = O(n)

Связное дерево с n + i узлами имеет ровно n + i − 1 рёбер. Каждое ребро идёт от родителя к ребёнку, поэтому суммарное число детей равно числу рёбер:

∑ children(v) = n + i − 1

Случай 1 — нет унарных правил (каждый внутренний узел имеет ≥ 2 детей):

∑ children(v) ≥ 2i
n + i − 1 ≥ 2i   →   i ≤ n − 1
──────────────────────────────────
n + i ≤ 2n − 1

Случай 2 — есть унарные цепочки (unit rules). Пусть H — максимальная длина цепочки (константа грамматики). В ANTLR4 MySQL для идентификатора:

tableName → fullId → uid → simpleId → ID     (H = 4)

Каждый из n листьев имеет не более H унарных предков, поэтому U ≤ n·H, B ≤ n−1. Итого:

i = B + U ≤ (n − 1) + n · H = n(1 + H) − 1
────────────────────────────────────────────
n + i ≤ n(2 + H) − 1   →   O(n) при H ≤ 4. □
Следствие 
ast_hash    : Θ(1)  хэш-вызовов на запрос
merkle_hash : Θ(n)  хэш-вызовов на запрос,   n + i ∈ [2n−1, 6n−1]

На корпусе 30 000 запросов при n ≈ 80 токенов:

ast_hash    :  30 000 × 1          =          30 000 вызовов
merkle_hash :  30 000 × [159, 479] ≈  4.8 – 14.4 млн вызовов
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
соотношение :  160× – 480×
Правило выбора: нужен diff поддеревьев или инкрементальный кэш — берёте Merkle, платите Θ(n) хэш-вызовов на запрос. Нужна дедупликация плоским сравнением — берёте ast_hash, платите Θ(1).

Итог: какой алгоритм для чего

ЗадачаАлгоритмУсловие
Дедупликация перед парсингом — живой legacy-кодast_hashвход не нормализован
Дедупликация — нормализованный входmerkle_hashединый форматтер на входе
Инкрементальный парсинг, diff поддеревьевmerkle_hashнужна локализация изменений
Поиск шаблонных семейств (template mining)simhash64допустимы ложные группировки
Потоковый fingerprint по файлу / пакетуrabin64XOR-комбинируемость
Точные копии, нулевая толерантностьtext_hashбайтовое тождество

Главное открытие: identity > similarity

72% пар, которые text_hash не находит — это не «похожие» запросы. Это идентичные запросы, которые текстово выглядят по-разному. Поверхностное несходство — артефакт автоматического форматирования, а не семантическое различие.

Это переворачивает привычную интуицию: когда задача — дедупликация перед парсингом, точное структурное совпадение надёжнее семантического сходства. SimHash находит «похожие», но пропускает часть «идентичных» (Hamming-порог не равен нулю). ast_hash находит именно идентичные — и только их.

Источники методов

АлгоритмАвторы / организацияГодПубликация
text_hash NIST 2015 FIPS PUB 180-4 — Secure Hash Standard (SHS)
ast_hash HOUND · внутренняя 2024 Реализация L2HashVisitor. Концепция AST-дедупликации: Jiang et al., DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, ICSE 2007
merkle_hash Ralph C. Merkle 1987 A Digital Signature Based on a Conventional Encryption Function — CRYPTO 1987, LNCS 293, pp. 369–378
rabin64 — концепция Michael O. Rabin 1981 Fingerprinting by Random Polynomials — Harvard University TR-15-81
rabin64 — полином ECMA 1992 ECMA-182. Полином CRC64: 0xC96C5795D7870F42
simhash64 — метод Moses S. Charikar 2002 Similarity Estimation Techniques from Rounding Algorithms — STOC 2002, pp. 380–388
simhash64 — масштаб Manku, Jain, Das Sarma 2007 Detecting Near-Duplicates for Web Crawling — WWW 2007, pp. 141–150. 8 млрд страниц, Hamming ≤ 3

Читать также