Optymalizacja odległości Hamminga dla MySQL lub PostgreSQL?

Question

Próbuję poprawić wyszukiwanie podobnych zdjęć Odtłuszczony w bazie danych MySQL. Teraz ja porównując pHash licząc odległość Hamminga tak:

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

wyników dla wybierając (MyISAM silnika)

• 20000 wierszy; czas zapytania: < 20ms
• 100000 wierszy; czas zapytania ~ 60ms # to było w porządku, aż osiągnięto 150000 wierszy
• 300000 wierszy; czas zapytania ~ 150ms

Tak więc zwiększenie czasu zapytania zależy od liczby wierszy w tabeli.

---

ja także spróbować znaleźć rozwiązanie na 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 

rzędy 300000; czas zapytania ~ 240ms

---

Zmieniłem silnik bazy danych na PostgreSQL. Translate this MySQL query to PyGreSQL Bez powodzenia. wiersze 300000; Czas zapytania ~ 18s

---

Czy istnieje rozwiązanie do optymalizacji powyżej kwerendy? Mam na myśli optymalizację nie zależy od liczby wierszy.

Mam ograniczone sposoby (narzędzia), aby rozwiązać ten problem. MySQL do tej pory wydawało się najprostszym rozwiązaniem, ale mogę wdrożyć kod na każdym silniku bazy danych open source, który będzie działał z Ruby na dedykowanym komputerze. Istnieje kilka gotowych rozwiązań dla MsSQL https://stackoverflow.com/a/5930944/766217 (nie testowane). Może ktoś wie jak to przetłumaczyć na MySQL lub PostgreSQL.

Proszę pisać odpowiedzi na podstawie niektórych kodów lub obserwacji. Mamy wiele teoretycznych problemów związanych z hamming distance na stackoverflow.com

Dzięki!

Answer 1

Rozważając efektywność algorytmów, informatycy używają pojęcia porządek oznaczonego O (coś), gdzie coś jest funkcją n, liczba rzeczy, które są obliczane, w tym przypadku wiersze.Więc mamy w rosnącej czas:

• O (1) - niezależnie od liczby elementów
• O (log (n)) - zwiększa się logarytmu pozycji
• O (n) - wzrost odsetka elementów (co masz)
• o (n^2) - rośnie wraz z kwadratem pozycji
• o (n^3) - etc
• o (2^n) - wzrasta wykładniczo
• O (n!) - wzrasta wraz z faktem rial o numerze

Ostatnie 2 są faktycznie nieobliczalne dla każdej rozsądnej liczby n (80+).

tylko najważniejsze sprawy termin ponieważ dominuje na dużą n so n^2 i 65 * n^2 + 787 * n + 4656566 są zarówno O (N^2)

Biorąc pod uwagę, że jest to Konstrukcja matematyczna i czas, w jakim algorytm przyjmuje rzeczywiste oprogramowanie na rzeczywistym sprzęcie przy użyciu rzeczywistych danych, mogą być silnie uzależnione od innych rzeczy (np. operacja pamięci O (n^2) może zająć mniej czasu niż operacja na dysku O (n)).

Aby rozwiązać problem, należy wykonać każdy wiersz i obliczyć wartość BIT_COUNT(hash^2028359052535108275) <= 4. Jest to operacja O (n).

Jedynym sposobem, w jaki można to poprawić, jest użycie indeksu, ponieważ pobieranie indeksu b-drzewa jest operacją O (log (n)).

Jednak ponieważ twoje pole kolumny jest zawarte w funkcji, nie można użyć indeksu dla tej kolumny. Masz 2 możliwości:

1. To jest rozwiązanie dla serwera SQL i nie wiem, czy jest ono przenośne dla MySQL. Utwórz utrwaloną kolumnę obliczeniową w tabeli z formułą BIT_COUNT(hash^2028359052535108275) i umieść na niej indeks. To będzie , a nie odpowiednie, jeśli chcesz zmienić maskę bitową.
2. Wypracować sposób wykonywania arytmetyki bitowych bez użycia funkcji BIT_COUNT.

Answer 2

Dzięki temu rozwiązaniu sprawy stały się nieco szybsze. Tworzy wyprowadzoną tabelę dla każdego porównania hash i zwraca tylko wyniki, które są mniejsze niż odległość szynki. W ten sposób nie robi BIT_COUNT na pHash, który już przekroczył szynkę. Zwraca wszystkie dopasowania w około 2,25 sekundy na 2,6 miliona rekordów.

To InnoDB, a mam bardzo mało indeksów.

Jeśli ktoś może zrobić to szybciej, doceniam cię.

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 

To jest zapytanie równoważne, ale bez tabel pochodnych. Jego czas powrotu jest prawie 3 razy dłuższy.

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 

Pamiętaj, że im niższa wartość szynki na pierwszej, tym szybciej będzie działać.