Hoạt động bitwise của MySQL, bộ lọc hoa

Question

Tôi muốn thực hiện một số bloom filter bằng cách sử dụng MySQL (một giải pháp thay thế được đề xuất khác).

Vấn đề là như sau:

Giả sử tôi có một bảng lưu trữ 8 số nguyên bit, với những giá trị sau:

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

Tôi muốn tìm tất cả các kết quả đó là Bitwise AND để này:

00011000 

Kết quả nên hàng 1 và 5.

Howev er, trong vấn đề của tôi, chúng không phải là số nguyên 8 bit, mà là số nguyên n bit. Làm cách nào để lưu trữ thông tin này và làm cách nào để truy vấn? Tốc độ là chìa khóa.

Answer 1

Tạo bảng có cột int (sử dụng this link để chọn đúng kích thước int). Không lưu trữ số như là một chuỗi từ 0 và 1.

Đối với dữ liệu của bạn sẽ trông như thế này:

number 

154 
53 
148 
38 
59 
106 

và bạn cần phải tìm tất cả các mục phù hợp với 24.

Sau đó, bạn có thể chạy một truy vấn như

SELECT * FROM test WHERE number & 24 = 24 

Nếu bạn muốn tránh chuyển đổi thành 10 số cơ sở trong ứng dụng của bạn, bạn có thể đưa nó ra để mysql:

INSERT INTO test SET number = b'00110101'; 

và tìm kiếm như thế này

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

Answer 2

Hãy xem xét không sử dụng MySQL cho việc này.

Trước hết, có thể không phải là cách tích hợp cho nhiều bảng hơn 64 bit. Bạn sẽ phải sử dụng các hàm do người dùng định nghĩa được viết bằng C.

Thứ hai, mỗi truy vấn sẽ yêu cầu quét toàn bộ bảng vì MySQL không thể sử dụng chỉ mục cho truy vấn của bạn. Vì vậy, trừ khi bảng của bạn là rất nhỏ, điều này sẽ không được nhanh chóng.

Answer 3

Chuyển sang PostgreSQL và sử dụng bit (n)

Answer 4

Quét bộ lọc theo bản chất của chúng yêu cầu quét bảng để đánh giá kết quả phù hợp. Trong MySQL không có loại bộ lọc nở. Giải pháp đơn giản là ánh xạ các byte của bộ lọc nở lên BitInteger (các từ 8 byte) và thực hiện kiểm tra trong truy vấn. Vì vậy, giả định rằng nở filteris 8 byte hoặc ít hơn (một bộ lọc rất nhỏ), bạn có thể thực hiện một tuyên bố chuẩn bị như:

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

và thay thế các thông số với giá trị mà bạn đang tìm kiếm. Tuy nhiên đối với các bộ lọc lớn hơn, bạn phải tạo nhiều cột filter và chia bộ lọc mục tiêu thành nhiều từ. Bạn phải truyền sang unsigned để thực hiện kiểm tra đúng cách.

Vì nhiều bộ lọc nở hợp lý có kích thước từ Kilo đến Megabyte nên sử dụng các đốm màu để lưu trữ chúng.Một khi bạn chuyển sang blobs thì không có cơ chế riêng để thực hiện so sánh mức byte. Và kéo một bảng toàn bộ các đốm màu lớn trên mạng để làm bộ lọc trong mã cục bộ không có ý nghĩa nhiều.

Giải pháp hợp lý duy nhất tôi tìm thấy là UDF. UDF nên chấp nhận một char* và lặp lại nó để đúc char* đến một unsigned char* và thực hiện kiểm tra target & candidate = target. Mã này sẽ giống như thế:

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; 
} 

Giải pháp này được thực hiện và có sẵn tại https://github.com/Claudenw/mysql_bloom

Answer 5

Đối với lên đến 64 bit, bạn có thể sử dụng một loại nguyên liệu MySQL, như tinyint (8b), int (16b), trung bình (24b) và bigint (64b). Sử dụng các biến thể chưa ký.

Trên 64b, hãy sử dụng loại BINARY của MySQL (VAR). Đó là bộ đệm byte thô. Ví dụ: BINARY (16) là tốt cho 128 bit.

Để tránh quét bảng, bạn cần chỉ mục cho mỗi bit hữu ích và/hoặc chỉ mục cho mỗi bộ bit liên quan. Bạn có thể tạo các cột ảo cho điều đó và đặt một chỉ mục trên mỗi cột.