Какая БД наиболее оптимальна для выборки на основе побитового XOR?

Question

[Константин]

Приветствую всех знающих и заинтересованных!
Буду крайне признателен за полезные рекомендации по решению задачи или указание вектора "куда копать".

Исходные: имеется большой массив строк [все по 32 байта] - ориентировочно over 100 млн.
Задача: опишу запросом MySQL

SELECT str FROM tbl WHERE BIT_COUNT(str ^ :search) / 256 <= :pc

Пример:

a = X'fffffffffff727d9181b191bf95ffc1f981f981f98399839ffffffffffffffff' // искомая строка
b = X'ffffffffffe407e9181b191bf91ffe1f981f981f98399839ffffffffffffffff' // одна из строк в БД
r = X'0000000000132030000000000040020000000000000000000000000000000000' // результат побитового XOR
c = 8 // число установленных бит в результате

если :pc = 0.05, то будет выбрана строка "b" из базы, т.к. 8 / 256 = 0.03125

Сейчас занимаюсь тестированием этого дела, используя MySQL. Но, что-то мне подсказывает, что результат меня не удовлетворит.
Подскажите, пожалуйста, инструмент и/или алгоритм, который ускорит процесс поиска...но не ценой вложения больших временных ресурсов на изучение и внедрение - вопрос времени стоит достаточно остро.

Comments

[xmoonlight]

Можете пример привести (для наглядности) и что требуется получить....

[Константин]

Написал, надеюсь прояснит вопрос.

Answer 1

[xmoonlight]

Один из вариантов решения (он не лучший!):
Тут отвечал про хеширование строк.
Для нахождения максимального совпадения строк...
Конечно, это не очень красиво, но вполне работоспособно....

Comments

[Константин]

Интересное решение, но не совсем понятно как его применить к моей задаче. В моем случае поиск осуществляется через XOR и расстояние Хэмминга.

[xmoonlight]

Еще вариант такой:
stackoverflow.com/questions/21037578/mysql-hamming...

[Константин]

этот вариант и используется (описан в примере запроса)

Answer 2

[Alex Chistyakov]

Никакая.
Ваш запрос - это всегда full scan, для него даже функциональный индекс невозможно построить (в MySQL их, правда, нет, но есть в MariaDB и в PostgreSQL).
Вам нужно менять алгоритм так, чтобы он искал не путем перебора всей таблицы.

Comments

[Константин]

Вот habrahabr.ru/post/211264 ещё прототип, отчасти решающий мою задачу. Но не решающий, к сожалению, основной задачи - время на реализацию/интеграцию. Спасибо за ответ.