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

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

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

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

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

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

00011000

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

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

11.12.2008 20:54:38
6 ОТВЕТОВ

Создайте таблицу со столбцом 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'
19
23.04.2013 23:21:45
Спасибо за совет вопроса. Однако что мне делать, если я хочу хранить «n-битные» числа, которые длиннее, чем целые числа (32 бита) ... например, 64 или 128 бит?
Sam 11.12.2008 22:09:06
Тип данных Mysql BIT поддерживает до 64 бит. Означает ли это, что вы можете хранить только 64 элемента в фильтре Блума?
Alexei Tenitski 12.12.2008 02:11:52
Я должен быть в состоянии хранить n-бит ... это ограничивает меня до 64.
Sam 16.12.2008 08:24:28
Используйте более одного столбца.
Chris 8.11.2010 18:10:45
Предлагаемый ответ будет перебирать ВСЕ строки в таблице. Это идет вразрез с «Скорость является ключом» в главном вопросе.
Dzmitry Lazerka 30.05.2017 00:55:22

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

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

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

8
14.12.2008 05:37:13
Это избегает вопроса, а не ответа.
Pacerier 19.10.2014 20:57:14

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

2
17.12.2008 18:23:35

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

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

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

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

Единственное разумное решение, которое я нашел, это 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;
}

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

2
2.03.2019 06:20:46

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

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

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

0
17.12.2017 12:06:41

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

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

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

0
15.10.2019 15:10:29