From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | Oleg Bartunov <oleg(at)sai(dot)msu(dot)su> |
Cc: | PostgreSQL - Hans-Jürgen Schönig <postgres(at)cybertec(dot)at>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: workaround for expensive KNN? |
Date: | 2011-04-08 15:59:03 |
Message-ID: | 12816.1302278343@sss.pgh.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Oleg Bartunov <oleg(at)sai(dot)msu(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Merlin Moncure | 2011-04-08 16:06:09 | Re: WIP: Allow SQL-language functions to reference parameters by parameter name |
Previous Message | Robert Haas | 2011-04-08 15:57:57 | Re: WIP: Allow SQL-language functions to reference parameters by parameter name |