Performa penghitungan dan pengurutan Delta E (CIE Lab) dalam SQL

Dua hal:1) Anda tidak menggunakan database sepenuhnya dan 2) masalah Anda adalah contoh yang bagus untuk ekstensi PostgreSQL khusus. Inilah alasannya.

Anda hanya menggunakan database sebagai penyimpanan, menyimpan warna sebagai pelampung. Dalam konfigurasi Anda saat ini, apa pun jenis kuerinya, database harus selalu memeriksa semua nilai (melakukan pemindaian berurutan). Ini berarti banyak IO dan banyak perhitungan untuk beberapa pertandingan yang dikembalikan. Anda mencoba mencari warna N terdekat, jadi ada beberapa kemungkinan tentang cara menghindari penghitungan pada semua data.

Peningkatan sederhana

Yang paling sederhana adalah membatasi perhitungan Anda ke subset data yang lebih kecil. Anda dapat mengasumsikan perbedaannya akan lebih besar jika komponennya lebih berbeda. Jika Anda dapat menemukan perbedaan yang aman antara komponen, di mana hasilnya selalu tidak sesuai, Anda dapat mengecualikan warna tersebut sama sekali menggunakan WHERE ranged dengan indeks btree. Namun, karena sifat ruang warna L*a*b, ini kemungkinan akan memperburuk hasil Anda.

Pertama buat indeks:

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

Kemudian saya mengadaptasi kueri Anda untuk menyertakan klausa WHERE untuk memfilter warna saja, di mana salah satu komponen berbeda paling banyak 20.

Pembaruan: Setelah melihat lagi, menambahkan batas 20 kemungkinan besar akan memperburuk hasil, karena saya menemukan setidaknya satu titik di ruang, yang ini berlaku.:

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 ;

Saya mengisi tabel dengan 100.000 warna acak dengan skrip Anda dan menguji:

Waktu tanpa indeks:44006.851 md

Waktu dengan indeks dan kueri rentang:1293.092 md

Anda dapat menambahkan klausa WHERE ini ke delta_e_cie1976_query juga, pada data acak saya, waktu kueri turun dari ~110 md menjadi ~22 md.

BTW:Saya mendapat nomor 20 secara empiris:Saya mencoba dengan 10, tetapi hanya mendapat 380 catatan, yang tampaknya sedikit rendah dan mungkin mengecualikan beberapa opsi yang lebih baik karena batasnya adalah 100. Dengan 20 set lengkap adalah 2900 baris dan satu bisa cukup yakin bahwa pertandingan terdekat akan ada di sana. Saya tidak mempelajari ruang warna DELTA_E_CIE2000 atau L*a*b* secara detail sehingga ambang batas mungkin memerlukan penyesuaian di sepanjang komponen yang berbeda agar benar-benar benar, tetapi prinsip mengecualikan penyimpanan data yang tidak menarik.

Tulis ulang Delta E CIE 2000 dalam C

Seperti yang telah Anda katakan, Delta E CIE 2000 rumit dan tidak cocok untuk diimplementasikan dalam SQL. Saat ini menggunakan sekitar 0,4 ms per panggilan di laptop saya. Menerapkannya dalam C akan sangat mempercepat ini. PostgreSQL menetapkan biaya default untuk fungsi SQL sebagai 100 dan fungsi C sebagai 1. Saya kira ini didasarkan pada pengalaman nyata.

Pembaruan: Karena ini juga menggaruk salah satu gatal saya, saya menerapkan kembali fungsi Delta E dari modul colormath di C sebagai ekstensi PostgreSQL, tersedia di PGXN . Dengan ini saya dapat melihat peningkatan sekitar 150x untuk CIE2000 saat menanyakan semua record dari tabel dengan 100k record.

Dengan fungsi C ini, saya mendapatkan waktu kueri antara 147 md dan 160 md untuk 100 ribu warna. Dengan WHERE ekstra, waktu kueri sekitar 20 mdtk, yang menurut saya cukup dapat diterima.

Solusi terbaik, tapi canggih

Namun, karena masalah Anda adalah N pencarian tetangga terdekat dalam ruang 3 dimensi, Anda dapat menggunakan Pengindeksan K-Nearest-Neighbor yang ada di PostgreSQL sejak versi 9.1 .

Agar itu berfungsi, Anda akan memasukkan komponen L*a*b* ke dalam kubus . Ekstensi ini belum mendukung operator jarak jauh ( sedang dalam pengerjaan ), tetapi meskipun demikian, itu tidak akan mendukung jarak Delta E dan Anda perlu mengimplementasikannya kembali sebagai ekstensi C.

Ini berarti mengimplementasikan kelas operator indeks GiST (btree_gist PostgreSQL extension in contrib melakukan ini) untuk mendukung pengindeksan menurut jarak Delta E. Bagian baiknya adalah Anda kemudian dapat menggunakan operator yang berbeda untuk versi Delta E yang berbeda, mis. <-> untuk Delta E CIE 2000 dan <#> untuk Delta E CIE 1976 dan kueri akan menjadi sangat cepat untuk LIMIT kecil bahkan dengan Delta E CIE 2000.

Pada akhirnya mungkin tergantung pada persyaratan dan kendala (bisnis) Anda.