Hiệu suất của Delta E (CIE Lab) tính toán và sắp xếp trong SQL

Hai điều:1) bạn không sử dụng cơ sở dữ liệu ở mức độ đầy đủ của nó và 2) vấn đề của bạn là một ví dụ tuyệt vời cho tiện ích mở rộng PostgreSQL tùy chỉnh. Đây là lý do tại sao.

Bạn chỉ đang sử dụng cơ sở dữ liệu làm nơi lưu trữ, lưu trữ màu dưới dạng vật nổi. Trong cấu hình hiện tại của bạn, bất kể loại truy vấn nào, cơ sở dữ liệu sẽ luôn phải kiểm tra tất cả các giá trị (thực hiện quét tuần tự). Điều này có nghĩa là rất nhiều IO và rất nhiều tính toán cho một vài trận đấu được trả về. Bạn đang cố gắng tìm N màu gần nhất, vì vậy có một số khả năng về cách tránh thực hiện các phép tính trên tất cả dữ liệu.

Cải tiến đơn giản

Đơn giản nhất là giới hạn các phép tính của bạn trong một tập hợp con dữ liệu nhỏ hơn. Bạn có thể cho rằng sự khác biệt sẽ lớn hơn nếu các thành phần khác nhau nhiều hơn. Nếu bạn có thể tìm thấy sự khác biệt an toàn giữa các thành phần, nơi kết quả luôn không phù hợp, bạn có thể loại trừ hoàn toàn những màu đó bằng cách sử dụng WHERE có phạm vi với chỉ mục btree. Tuy nhiên, do bản chất của không gian màu L * a * b, điều này có thể sẽ làm xấu kết quả của bạn.

Đầu tiên, hãy tạo các chỉ mục:

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

Sau đó, tôi đã điều chỉnh truy vấn của bạn để bao gồm mệnh đề WHERE để chỉ lọc các màu, trong đó bất kỳ thành phần nào khác nhau nhiều nhất là 20.

Cập nhật: Sau khi xem xét lại, thêm giới hạn 20 sẽ rất có thể làm xấu kết quả, vì tôi đã tìm thấy ít nhất một điểm trong không gian, điều này đúng.:

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 ;

Tôi đã điền vào bảng với 100000 màu ngẫu nhiên với tập lệnh của bạn và đã kiểm tra:

Thời gian không có chỉ mục:44006,851 ms

Thời gian với chỉ mục và truy vấn phạm vi:1293,092 mili giây

Bạn có thể thêm mệnh đề WHERE này vào delta_e_cie1976_query cũng vậy, trên dữ liệu ngẫu nhiên của tôi, nó giảm thời gian truy vấn từ ~ 110 mili giây xuống còn ~ 22 mili giây.

BTW:Theo kinh nghiệm, tôi đã nhận được số 20:Tôi đã thử với 10, nhưng chỉ nhận được 380 bản ghi, có vẻ hơi thấp và có thể loại trừ một số tùy chọn tốt hơn vì giới hạn là 100. Với 20, bộ đầy đủ là 2900 hàng và một hàng có thể khá chắc chắn rằng các trận đấu gần nhất sẽ có. Tôi không nghiên cứu chi tiết về không gian màu DELTA_E_CIE2000 hoặc L * a * b *, vì vậy, ngưỡng này có thể cần được điều chỉnh cùng với các thành phần khác nhau để điều đó thực sự đúng, nhưng nguyên tắc loại trừ lưu giữ dữ liệu không thú vị.

Viết lại Delta E CIE 2000 trong C

Như bạn đã nói, Delta E CIE 2000 rất phức tạp và không phù hợp để triển khai trong SQL. Nó hiện sử dụng khoảng 0,4 ms cho mỗi cuộc gọi trên máy tính xách tay của tôi. Việc triển khai nó trong C sẽ tăng tốc đáng kể. PostgreSQL chỉ định chi phí mặc định cho các hàm SQL là 100 và các hàm C là 1. Tôi đoán điều này dựa trên kinh nghiệm thực tế.

Cập nhật: Vì điều này cũng làm xước một trong những chỗ ngứa của tôi, nên tôi đã hoàn thiện lại các chức năng Delta E từ mô-đun colormath trong C dưới dạng tiện ích mở rộng PostgreSQL, có sẵn trên PGXN . Với điều này, tôi có thể thấy tốc độ tăng khoảng 150 lần cho CIE2000 khi truy vấn tất cả các bản ghi từ bảng với 100 nghìn bản ghi.

Với hàm C này, tôi nhận được thời gian truy vấn từ 147 ms đến 160 ms cho 100k màu. Với WHERE bổ sung, thời gian truy vấn là khoảng 20 mili giây, điều này có vẻ khá chấp nhận được đối với tôi.

Giải pháp tốt nhất nhưng nâng cao

Tuy nhiên, vì vấn đề của bạn là N tìm kiếm hàng xóm gần nhất trong không gian 3 chiều, bạn có thể sử dụng K-Nearest-Neighbor Indexing trong PostgreSQL kể từ phiên bản 9.1 .

Để điều đó hoạt động, bạn sẽ đặt các thành phần L * a * b * vào một khối lập phương . Tiện ích mở rộng này chưa hỗ trợ toán tử khoảng cách ( nó đang hoạt động ), nhưng ngay cả khi có, nó sẽ không hỗ trợ khoảng cách Delta E và bạn sẽ cần phải thực hiện lại nó như một phần mở rộng C.

Điều này có nghĩa là triển khai lớp toán tử chỉ mục GiST ( btree_gist tiện ích mở rộng PostgreSQL để hỗ trợ lập chỉ mục theo khoảng cách Delta E. Phần tốt là bạn có thể sử dụng các toán tử khác nhau cho các phiên bản khác nhau của Delta E, ví dụ. <-> cho Delta E CIE 2000 và <#> cho Delta E CIE 1976 và các truy vấn sẽ thực sự rất nhanh cho LIMIT nhỏ ngay cả với Delta E CIE 2000.

Cuối cùng, nó có thể phụ thuộc vào yêu cầu và ràng buộc (doanh nghiệp) của bạn là gì.