I understand that it also produces some correct (or correct looking) results, but the code sounds like it has lots of false positives from what you're saying, so it's probably not the correct algorithm.
As for the time it takes, it doesn't sound like something that should take so much time, but not sure how it's in the code.
I'd look for these things:
Is the DB storing the color info as CMYK? If so, maybe go through your existing table and add another table or extra columns with pre-computed columns for lightness, hue and chroma.
Then you can get a CMYK value as input, translate it to lightness, hue and chroma, and select only the rows where the query attribute (e.g. lightness) is different to the one you got. You can even apply the scale factor in the SQL query directly (e.g.
WHERE
CASE
WHEN $direction = 1 THEN lightness > $lightness + ($scale_ratio * $lightness)
ELSE lightness < $lightness - ($scale_ratio * $lightness)
END
Is the DB the slow part? Do you even need the DB? Perhaps you can loop through the colors (creating each in memory), and if you need to lookup some unrelated attribute like an assigned per-row id, you could query the DB for that after you found the N "matching" colors, and only for those.Can you express the distance algorithm in SQL (or a PL/SQL function)? Is it faster?
My guess is that you are replacing each pixel in an image with the "best" color in the database. Is this correct? Can you post a good and a bad sample image?