Did you try integer arrays with GIN (inverted index) ?
Oleg
On Wed, 9 Jan 2008, J?rg Kiegeland wrote:
Hello,
I have an interesting generic search task, for which I have done different
performance tests and I would like to share and discuss my results on this
newsgroup.
So I begin to describe the search task:
=========
You have a set of N unique IDs. Every ID is associated with an integer
scoring value. Every ID is also associated with up to K different keywords
(there are totally K different keywords K1 ... Kn). Now find the first Z
best-scored IDs which are associated with a given set of keywords in one of
two ways:
(C1) The ID must be associated with all keywords of the given set of
keywords.
(C2) The ID must be associated with at least one keyword of the given set of
keywords.
=========
My tests showed that only a Multiple-Column-approach resulted in a acceptable
query response time. I also tried out an int-array approach using gist, a
sub-string approach, a bit-column approach, and even a sub-string approach
using Solr.
Actually, the int-array approach was 20% faster for Z=infinity, but it became
linear for the test case [Z=1000 and *all* IDs matches the search condition].
(To be not misunderstood, "acceptable time" means: having a fixed Z, a fixed
set of keywords K, a fixed query, and an increasing N, results in constant up
to logarithmic response time; linear or worser-than-linear time is not
accepted)
In the Multiple-Column-approach, there is one table. The table has a boolean
column for each keyword. It has also a column for the ID and for the scoring.
Now, for each keyword column and for the scoring column a separate index is
created.
C1 is implemented by an AND-query on the keyword columns, C2 by and OR query,
and the result is sorted for the scoring column, cutting of after the first Z
results.
However our requirements for the search task have changed and I not yet
managed to find a search approach with acceptable response time for following
variation:
Namely that one uses C2 and do not sort for a scoring column but use as
scoring value the number of matched keywords for a given ID.
The difficulty in this query type is that the scoring is dependent on the
query itself..
So has anyone an idea how to solve this query type with acceptable response
time, or can anybody tell/prove, that this is theoretically not possible?
---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend
Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@xxxxxxxxxx, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83
---------------------------(end of broadcast)---------------------------
TIP 7: You can help support the PostgreSQL project by donating at
http://www.postgresql.org/about/donate
