Re: workaround for expensive KNN?

Oleg Bartunov <oleg@sai.msu.su> writes:
> what if you create index (price,title) ?

I think that SELECT ... WHERE ... ORDER BY ... LIMIT is basically an
intractable problem.  We've recognized the difficulty in connection with
btree indexes for a long time, and there is no reason at all to think
that KNNGist will somehow magically dodge it.  You can either visit
*all* of the rows satisfying WHERE (and then sort them), or you can
visit the rows in ORDER BY order and hope that you find enough of them
satisfying the WHERE in a reasonable amount of time.  Either of these
strategies loses badly in many real-world cases.

Maybe with some sort of fuzzy notion of ordering it'd be possible to go
faster, but as long as you insist on an exact ORDER BY result, I don't
see any way out of it.

One way to be fuzzy is to introduce a maximum search distance:

SELECT ... WHERE x < limit AND other-conditions ORDER BY x LIMIT n

which essentially works by limiting the damage in the visit-all-the-rows
approach.  Hans didn't do that in his example, but I wonder how much
it'd help (and whether the existing GIST support is adequate for it).
        regards, tom lane