Wydajność obliczeń i sortowania Delta E (CIE Lab) w SQL

Dwie rzeczy:1) nie używasz bazy danych w pełnym zakresie i 2) Twój problem jest doskonałym przykładem niestandardowego rozszerzenia PostgreSQL. Oto dlaczego.

Używasz tylko bazy danych jako magazynu, przechowując kolory jako pływaki. W Twojej obecnej konfiguracji, niezależnie od rodzaju zapytania, baza danych zawsze będzie musiała sprawdzić wszystkie wartości (wykonać skanowanie sekwencyjne). Oznacza to dużo IO i dużo kalkulacji za kilka zwróconych meczów. Próbujesz znaleźć najbliższe N ​​kolorów, więc istnieje kilka możliwości uniknięcia wykonywania obliczeń na wszystkich danych.

Proste ulepszenie

Najprościej jest ograniczyć obliczenia do mniejszego podzbioru danych. Można założyć, że różnica będzie większa, jeśli komponenty będą się bardziej różnić. Jeśli możesz znaleźć bezpieczną różnicę między składnikami, gdzie wyniki są zawsze nieodpowiednie, możesz całkowicie wykluczyć te kolory, używając zakresu WHERE z indeksami btree. Jednak ze względu na naturę przestrzeni kolorów L*a*b, prawdopodobnie pogorszy to twoje wyniki.

Najpierw utwórz indeksy:

CREATE INDEX color_lab_l_btree ON color USING btree (lab_l);
CREATE INDEX color_lab_a_btree ON color USING btree (lab_a);
CREATE INDEX color_lab_b_btree ON color USING btree (lab_b);

Następnie dostosowałem zapytanie tak, aby zawierało klauzulę WHERE, aby filtrować tylko kolory, w przypadku których dowolny ze składników różni się co najwyżej o 20.

Aktualizacja: Po kolejnym spojrzeniu dodanie limitu 20 najprawdopodobniej pogorszy wyniki, ponieważ znalazłem co najmniej jeden punkt w przestrzeni, dla którego jest to prawdą.:

SELECT 
    c.rgb_r, c.rgb_g, c.rgb_b,
    DELTA_E_CIE2000(
        25.805780252087963, 53.33446637366859, -45.03961353720049, 
        c.lab_l, c.lab_a, c.lab_b,
        1.0, 1.0, 1.0) AS de2000
FROM color c 
WHERE 
    c.lab_l BETWEEN 25.805780252087963 - 20 AND 25.805780252087963 + 20 
    AND c.lab_a BETWEEN 53.33446637366859 - 20 AND 53.33446637366859 + 20 
    AND c.lab_b BETWEEN -45.03961353720049 - 20 AND -45.03961353720049 + 20 
ORDER BY de2000 ;

Wypełniłem tabelę 100 000 losowych kolorów twoim skryptem i przetestowałem:

Czas bez indeksów:44006,851 ms

Czas z indeksami i zapytaniem o zakres:1293 092 ms

Możesz dodać tę klauzulę WHERE do delta_e_cie1976_query też, na moich losowych danych zmniejsza czas zapytania z ~110 ms do ~22 ms.

BTW:Dostałem liczbę 20 empirycznie:próbowałem z 10, ale uzyskałem tylko 380 rekordów, co wydaje się trochę za mało i może wykluczać lepsze opcje, ponieważ limit wynosi 100. Przy 20 pełny zestaw miał 2900 wierszy i jeden może być całkiem uczciwy pewni, że będą tam najbliższe mecze. Nie studiowałem szczegółowo przestrzeni kolorów DELTA_E_CIE2000 lub L*a*b*, więc próg może wymagać dostosowania według różnych składników, aby rzeczywiście było to prawdą, ale zasada wykluczania nieinteresujących danych obowiązuje.

Przepisz Delta E CIE 2000 w C

Jak już powiedziałeś, Delta E CIE 2000 jest złożona i nie nadaje się do implementacji w SQL. Obecnie używa około 0,4 ms na połączenie na moim laptopie. Wdrożenie go w C powinno to znacznie przyspieszyć. PostgreSQL przypisuje domyślny koszt funkcjom SQL jako 100, a funkcjom C jako 1. Zgaduję, że jest to oparte na prawdziwym doświadczeniu.

Aktualizacja: Ponieważ to również mnie drapie, ponownie zaimplementowałem funkcje Delta E z modułu colormath w C jako rozszerzenie PostgreSQL, dostępne na PGXN . Dzięki temu widzę przyspieszenie około 150x dla CIE2000 podczas odpytywania wszystkich rekordów z tabeli z rekordami 100k.

Dzięki tej funkcji C otrzymuję czasy zapytań od 147 ms do 160 ms dla 100 tys. kolorów. Z dodatkowym WHERE czas zapytania wynosi około 20 ms, co wydaje mi się całkiem do przyjęcia.

Najlepsze, ale zaawansowane rozwiązanie

Ponieważ jednak Twoim problemem jest N szukanie najbliższego sąsiada w przestrzeni trójwymiarowej, możesz użyć indeksowania K-Nearest-Neighbor Indexing, które jest w PostgreSQL od wersji 9.1 .

Aby to zadziałało, należy umieścić komponenty L*a*b* w kostka . To rozszerzenie nie obsługuje jeszcze operatora odległości ( jest w trakcie prac ), ale nawet gdyby tak było, nie obsługiwałby odległości Delta E i konieczne byłoby ponowne zaimplementowanie go jako rozszerzenia C.

Oznacza to wdrożenie klasy operatora indeksu GiST (btree_gist rozszerzenie PostgreSQL in contrib to robi), aby obsługiwać indeksowanie według odległości Delta E. Dobrą stroną jest to, że możesz użyć różnych operatorów dla różnych wersji Delta E, np. <-> dla Delta E CIE 2000 i <#> dla Delta E CIE 1976 i zapytania byłyby naprawdę bardzo szybkie dla małych LIMITÓW nawet z Delta E CIE 2000.