Prestanda för Delta E (CIE Lab) beräkning och sortering i SQL

Två saker:1) du använder inte databasen i dess fulla omfattning och 2) ditt problem är ett bra exempel på en anpassad PostgreSQL-tillägg. Här är varför.

Du använder bara databasen som lagring, och lagrar färger som flytande färger. I din nuvarande konfiguration, oavsett typ av fråga, måste databasen alltid kontrollera alla värden (gör en sekventiell skanning). Detta innebär mycket IO och mycket kalkylering för få returnerade matcher. Du försöker hitta de närmaste N-färgerna, så det finns några möjligheter för hur du undviker att utföra beräkningar på all data.

Enkel förbättring

Det enklaste är att begränsa dina beräkningar till en mindre delmängd av data. Du kan anta att skillnaden blir större om komponenterna skiljer sig mer åt. Om du kan hitta en säker skillnad mellan komponenterna, där resultaten alltid är olämpliga, kan du utesluta dessa färger helt och hållet genom att använda ranged WHERE med btree-index. Men på grund av L*a*b färgrymds natur kommer detta sannolikt att försämra dina resultat.

Skapa först indexen:

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

Sedan anpassade jag din fråga till att inkludera en WHERE-klausul för att endast filtrera färger, där någon av komponenterna skiljer sig högst 20.

Uppdatering: Efter en ny titt, kommer att lägga till en gräns på 20 med stor sannolikhet försämra resultaten, eftersom jag hittade minst en punkt i rymden, vilket detta gäller.:

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 ;

Jag fyllde tabellen med 100 000 slumpmässiga färger med ditt manus och testade:

Tid utan index:44006,851 ms

Tid med index och intervallfråga:1293 092 ms

Du kan lägga till denna WHERE-sats i delta_e_cie1976_query På mina slumpmässiga data sänks också frågetiden från ~110 ms till ~22 ms.

BTW:Jag fick siffran 20 empiriskt:jag försökte med 10, men fick bara 380 poster, vilket verkar lite lågt och kan utesluta några bättre alternativ eftersom gränsen är 100. Med 20 var hela uppsättningen 2900 rader och en kan vara ganska säker på att de närmaste matcherna kommer att finnas där. Jag studerade inte DELTA_E_CIE2000 eller L*a*b* färgrymden i detalj så tröskeln kan behöva justeras längs olika komponenter för att det faktiskt ska vara sant, men principen att utesluta icke-intressanta data gäller.

Skriv om Delta E CIE 2000 i C

Som du redan har sagt är Delta E CIE 2000 komplex och ganska olämplig för implementering i SQL. Den använder för närvarande cirka 0,4 ms per samtal på min bärbara dator. Att implementera det i C borde påskynda detta avsevärt. PostgreSQL tilldelar standardkostnad till SQL-funktioner som 100 och C-funktioner som 1. Jag antar att detta är baserat på verklig erfarenhet.

Uppdatering: Eftersom detta också repar en av mina kliar, implementerade jag om Delta E-funktionerna från colormath-modulen i C som en PostgreSQL-tillägg, tillgänglig på PGXN . Med detta kan jag se en hastighetsökning på cirka 150x för CIE2000 när jag frågar alla poster från tabellen med 100 000 poster.

Med denna C-funktion får jag frågetider mellan 147 ms och 160 ms för 100k färger. Med extra WHERE är frågetiden cirka 20 ms, vilket verkar helt acceptabelt för mig.

Bästa men avancerade lösningen

Men eftersom ditt problem är N närmaste grannesökning i 3-dimensionellt utrymme, kan du använda K-Nearest-Neighbor Indexing som finns i PostgreSQL sedan version 9.1 .

För att det ska fungera skulle du lägga L*a*b*-komponenter i en kub . Det här tillägget stöder ännu inte distansoperatör ( det är på gång ), men även om det skulle göra det skulle det inte stödja Delta E-avstånd och du skulle behöva implementera det igen som en C-förlängning.

Detta innebär implementering av GiST-indexoperatörsklass (btree_gist PostgreSQL-tillägg in contribution gör detta) för att stödja indexering enligt Delta E-avstånd. Det som är bra är att du sedan kan använda olika operatörer för olika versioner av Delta E, t.ex. <-> för Delta E CIE 2000 och <#> för Delta E CIE 1976 och frågor skulle vara riktigt riktigt snabba för liten LIMIT även med Delta E CIE 2000.