Hamming Tối ưu hóa khoảng cách cho MySQL hoặc PostgreSQL?

Question

Tôi đang cố gắng cải thiện các hình ảnh tương tự như tìm kiếm được nhúng trong cơ sở dữ liệu MySQL. Ngay bây giờ tôi so sánh pHash đếm Hamming khoảng cách như thế này:

SELECT * FROM images WHERE BIT_COUNT(hash^2028359052535108275) <= 4 

Kết quả lựa chọn (động cơ MyISAM)

• 20000 hàng; thời gian truy vấn < 20ms
• 100000 hàng; thời gian truy vấn ~ 60ms # điều này là tốt, cho đến khi đạt đến 150000 hàng
• 300000 hàng; thời gian truy vấn ~ 150ms

Vì vậy, thời gian truy vấn sẽ tùy thuộc vào số lượng hàng trong bảng.

---

tôi cũng cố gắng giải pháp được tìm thấy trên stackoverflow Hamming distance on binary strings in SQL

SELECT * FROM images WHERE 
BIT_COUNT(h1^11110011) + 
BIT_COUNT(h2^10110100) + 
BIT_COUNT(h3^11001001) + 
BIT_COUNT(h4^11010001) + 
BIT_COUNT(h5^00100011) + 
BIT_COUNT(h6^00010100) + 
BIT_COUNT(h7^00011111) + 
BIT_COUNT(h8^00001111) <= 4 

hàng 300000; thời gian truy vấn ~ 240ms

---

Tôi đã thay đổi công cụ cơ sở dữ liệu thành PostgreSQL. Translate this MySQL query to PyGreSQL Không thành công. hàng 300000; thời gian truy vấn ~ 18s

---

Có giải pháp nào để tối ưu hóa các truy vấn trên không? Tôi có nghĩa là tối ưu hóa không phụ thuộc vào số hàng.

Tôi có các cách hạn chế (công cụ) để giải quyết vấn đề này. MySQL cho đến nay dường như là giải pháp đơn giản nhất nhưng tôi có thể triển khai mã trên mọi công cụ cơ sở dữ liệu nguồn mở sẽ làm việc với Ruby trên máy chuyên dụng. Có một số giải pháp sẵn sàng cho MsSQL https://stackoverflow.com/a/5930944/766217 (không được kiểm tra). Có thể ai đó biết cách dịch nó cho MySQL hoặc PostgreSQL.

Vui lòng đăng câu trả lời dựa trên một số mã hoặc quan sát. Chúng tôi có rất nhiều vấn đề lý thuyết về khoảng cách ham mê trên stackoverflow.com

Cảm ơn!

Answer 1

Khi xem xét hiệu quả của thuật toán, các nhà khoa học máy tính sử dụng khái niệm thứ tự biểu thị O (cái gì đó) ở đâu đó là hàm n, số thứ được tính, trong trường hợp này.Vì vậy, chúng tôi nhận được, trong thời gian tăng:

• O (1) - không phụ thuộc vào số lượng các mục
• O (log (n)) - tăng lên khi logarit của các mục
• O (n) - tăng theo tỷ lệ của các mục (bạn có)
• O (n^2) - tăng theo bình phương của các mục
• O (n^3) - vv
• O (2^n) - tăng theo cấp số nhân
• O (n!) - tăng với thực tế rial of the number

2 cuối cùng là không thể chối cãi hiệu quả đối với bất kỳ số lượng hợp lý n (80+) nào.

Chỉ những vấn đề quan trọng nhất hạn vì đây chiếm ưu thế cho lớn n để n^2 và 65 * n^2 + 787 * n + 4.656.566 đều O (n^2)

Mang trong tâm trí rằng đây là xây dựng toán học và thời gian mà thuật toán thực hiện với phần mềm thực trên phần cứng thực sử dụng dữ liệu thực có thể bị ảnh hưởng nặng nề bởi những thứ khác (ví dụ: hoạt động bộ nhớ O (n^2) có thể mất ít thời gian hơn thao tác đĩa O (n)).

Đối với sự cố của bạn, bạn cần phải chạy qua từng hàng và tính BIT_COUNT(hash^2028359052535108275) <= 4. Đây là một hoạt động O (n).

Cách duy nhất có thể cải thiện này là sử dụng chỉ mục vì truy xuất chỉ mục b-tree là thao tác O (log (n)).

Tuy nhiên, vì trường cột của bạn được chứa trong một hàm, bạn không thể sử dụng chỉ mục trên cột đó. Bạn có 2 khả năng:

1. Đây là giải pháp máy chủ SQL và tôi không biết liệu đó có phải là di động với MySQL hay không. Tạo cột được tính toán liên tục trong bảng của bạn với công thức BIT_COUNT(hash^2028359052535108275) và đặt chỉ mục trên đó. Điều này sẽ không phù hợp nếu bạn cần thay đổi mặt nạ bit.
2. Làm việc ra một cách để thực hiện số học bitwise mà không sử dụng hàm BIT_COUNT.

Answer 2

Giải pháp này làm mọi việc nhanh hơn một chút đối với tôi. Nó làm cho một bảng có nguồn gốc cho mỗi so sánh băm, và trả về chỉ các kết quả nhỏ hơn khoảng cách ham. Bằng cách này, nó không làm BIT_COUNT trên một pHash đã vượt quá ham. Nó trả về tất cả các trận đấu trong khoảng 2,25 giây trên 2,6 triệu bản ghi.

Đó là InnoDB và tôi có rất ít chỉ mục.

Nếu ai đó có thể làm cho nó nhanh hơn, tôi sẽ đánh giá cao bạn.

SELECT *, BIT_COUNT(pHash3^42597524) + BC2 AS BC3 
FROM ( 
    SELECT *, BIT_COUNT(pHash2^258741369) + BC1 AS BC2 
    FROM ( 
     SELECT *, BIT_COUNT(pHash1^5678910) + BC0 AS BC1 
     FROM ( 
      SELECT `Key`, pHash0, pHash1, pHash2, pHash3, BIT_COUNT(pHash0^1234567) as BC0 
      FROM files 
      WHERE BIT_COUNT(pHash0^1234567) <= 3 
     ) AS BCQ0 
     WHERE BIT_COUNT(pHash1^5678910) + BC0 <= 3 
    ) AS BCQ1 
    WHERE BIT_COUNT(pHash2^258741369) + BC1 <= 3 
    ) AS BCQ2 
WHERE BIT_COUNT(pHash3^42597524) + BC2 <= 3 

Đây là truy vấn tương đương, nhưng không có bảng dẫn xuất. Thời gian trở về của nó dài gấp 3 lần.

SELECT `Key`, pHash0, pHash1, pHash2, pHash3 
FROM Files 
WHERE BIT_COUNT(pHash0^1234567) + BIT_COUNT(pHash1^5678910) + BIT_COUNT(pHash2^258741369) + BIT_COUNT(pHash3^42597524) <=3 

Hãy nhớ rằng giá trị ham thấp hơn trên giá trị đầu tiên sẽ càng chạy nhanh hơn.