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

Создайте таблицу со столбцом 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'

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

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

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

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

Фильтры Блума по своей природе требуют сканирования таблиц для оценки совпадений. В MySQL нет типа фильтра Блума. Простое решение - отобразить байты фильтра Блума на BitInteger (8-байтовые слова) и выполнить проверку в запросе. Итак, предполагая, что bloom фильтрует 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;
}

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

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

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

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

Чтобы реализовать фильтр Блума с использованием базы данных, я бы подумал по-другому.

Я бы сделал двухуровневый фильтр. Используйте одну многобитную хеш-функцию для генерации идентификатора (это больше похоже на индекс корзины хеш-таблицы), а затем используйте биты в строке для оставшихся k-1 хеш-функций более классического типа. Внутри строки это может быть (скажем) 100 столбцов bigint (я бы также сравнил производительность с большими двоичными объектами).

Фактически это будет N отдельных фильтров Блума, где N - домен вашей первой хеш-функции. Идея состоит в том, чтобы уменьшить размер требуемого фильтра Блума, выбрав хеш-бакет. Он не обладал бы полной эффективностью фильтра Блума в памяти, но все же мог бы значительно уменьшить объем данных, которые необходимо сохранить, по сравнению с помещением всех значений в базу данных и их индексированием. Предположительно причина использования базы данных в первую очередь заключается в нехватке памяти для полного фильтра Блума.