Битовые операции MySQL, фильтр Блума

Question

Я бы хотел реализовать фильтр Блума с использованием MySQL (другой предложенный вариант).

Проблема заключается в следующем:

Предположим, у меня есть таблица, в которой хранятся 8-битные целые числа со следующими значениями:

1: 10011010
2: 00110101
3: 10010100
4: 00100110
5: 00111011
6: 01101010

Я бы хотел найти все побитовые результаты И к этому:

00011000

Результатами должны быть строки 1 и 5.

Однако в моей задаче это не 8-битные целые числа, а n-битные целые числа. Как мне сохранить это и как я могу сделать запрос? Скорость - это ключ.

Answer 1

Создайте таблицу со столбцом int (используйте эту ссылку , чтобы выбрать правильный размер int). Не храните числа в виде последовательности от 0 до 1.

Для ваших данных это будет выглядеть так:

number

154
53
148
38
59
106

и вам нужно найти все записи, соответствующие 24.

Затем вы можете запустить запрос, как

SELECT * FROM test WHERE number & 24 = 24

Если вы хотите избежать преобразования в 10 базовых чисел в вашем приложении, вы можете передать его mysql:

INSERT INTO test SET number = b'00110101';

и ищите вот так

SELECT bin(number) FROM test WHERE number & b'00011000' = b'00011000'

Answer 2

Не используйте MySQL для этого.

Во-первых, вероятно, не существует встроенного способа для более чем 64-битных таблиц. Вам придется прибегнуть к пользовательским функциям, написанным на C.

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

Answer 3

Фильтры Блума по своей природе требуют сканирования таблицы для оценки совпадений. В MySQL нет типа фильтра Блума. Простое решение - отобразить байты фильтра Блума на BitInteger (8-байтовые слова) и выполнить проверку в запросе. Таким образом, предполагая, что блум фильтрует 8 байтов или меньше (очень маленький фильтр), вы можете выполнить подготовленный оператор, например:

SELECT * FROM test WHERE cast(filter, UNSIGNED) & cast(?, UNSIGNED) = cast(?, UNSIGNED)

и замените параметры на значение, которое вы ищете. Однако для более крупных фильтров необходимо создать несколько столбцов filter и разбить целевой фильтр на несколько слов. Вы должны привести к беззнаковому, чтобы сделать проверку правильно.

Поскольку многие разумные фильтры Блума находятся в диапазоне от килограмма до мегабайта, имеет смысл использовать капли для их хранения. После того, как вы переключитесь на большие двоичные объекты, не будет собственных механизмов для сравнения уровня байтов. А тянуть всю таблицу больших больших двоичных объектов по сети для локальной фильтрации кода не имеет особого смысла.

Единственное разумное решение, которое я нашел, - это UDF. UDF должен принять char* и выполнить итерацию, приведя char* к unsigned char* и выполнить проверку target & candidate = target. Этот код будет выглядеть примерно так:

my_bool bloommatch(UDF_INIT *initid, UDF_ARGS *args, char* result, unsigned long* length, char *is_null, char *error)
{
    if (args->lengths[0] > args->lengths[1])
    {
        return 0;
    }
    char* b1=args->args[0];
    char* b2=args->args[1];
    int limit = args->lengths[0];
    unsigned char a;
    unsigned char b;
    int i;
    for (i=0;i<limit;i++)
    {
        a = (unsigned char) b1[i];
        b = (unsigned char) b2[i];
        if ((a & b) != a)
        {
            return 0;
        }
    }
    return 1;
}

Это решение реализовано и доступно здесь

Answer 4

Переключиться на PostgreSQL и использовать бит (n)

Answer 5

Для 64 битов вы можете использовать целочисленный тип MySQL, например tinyint (8b), int (16b), mediumint (24b) и bigint (64b). Используйте варианты без знака.

Свыше 64b используйте тип MySQL (VAR) BINARY. Это необработанные байтовые буферы. Например, BINARY (16) подходит для 128 бит.

Чтобы предотвратить сканирование таблицы, вам нужен индекс для каждого полезного бита и / или индекс для набора связанных битов. Для этого вы можете создать виртуальные столбцы и поставить индекс для каждого из них.