You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Ype Kingma <yk...@xs4all.nl> on 2003/02/03 23:23:50 UTC
MultiSearcher discards interim results
Dear developers,
public TopDocs search(Query query, Filter filter, int nDocs)
contains an
else break;
which discards previous interim results.
Since I expect to need in the order of 100 best results from
20 databases on a regular basis I don't really like this.
This is the current code:
for (int i = 0; i < searchables.length; i++) { // search each searcher
TopDocs docs = searchables[i].search(query, filter, nDocs);
totalHits += docs.totalHits; // update totalHits
ScoreDoc[] scoreDocs = docs.scoreDocs;
for (int j = 0; j < scoreDocs.length; j++) { // merge scoreDocs into hq
ScoreDoc scoreDoc = scoreDocs[j];
if (scoreDoc.score >= minScore) {
scoreDoc.doc += starts[i]; // convert doc
hq.put(scoreDoc); // update hit queue
if (hq.size() > nDocs) { // if hit queue overfull
hq.pop(); // remove lowest in hit queue
minScore = ((ScoreDoc)hq.top()).score; // reset minScore
}
} else
break; // no more scores > minScore
}
}
Attached is an untested patch for this. It works by implementing
a MultiCollector that has the state to collect results from
the subsearchers without discarding interim results.
The patch is a dif -c against current CVS.
I'd like to add some test cases, but before I do that
I'd prefer to have comments.
I checked the testcases for MultiSearcher, but they don't
seem to exercise the code in the patch.
The existing test-unit build runs fine with the patch.
Regards,
Ype
Re: MultiSearcher discards interim results
Posted by Ype Kingma <yk...@xs4all.nl>.
On Tuesday 11 February 2003 21:39, you wrote:
> Ype Kingma wrote:
> >>I'm confused. The contract of this method is to return the top-scoring
> >>nDocs. For a multi-searcher it must compute the top-scoring nDocs from
> >>each sub-searcher, then find the top-scoring nDocs among these. If you
> >
> > For the first sub-searcher: yes. For the remaining sub-searchers it is
> > only necessary to collect docs with a score not smaller than the minimum
> > score provided by the first subsearcher.
>
> Okay, now I see what you're after. You wish to minimize the cost of
> maintaining the queue of top-scoring documents. But does hit queue
> maintenance ever significantly affect overall search performance? I'd
> be very surprised if it does. So, while perhaps not optimal, I suspect
> the current implementation is adequate.
It's probably adequate, but I have a typical case of needing the 100 to
200 best results from 15 to 20 searchers, so I don't like to see a suboptimal
implementation...
> Also, the current approach works well with RemoteSearchable, while I
> suspect your optimized version would not. And if someone were ever to
Quite so, because the current approach would only need one remote call per
searcher, but see below.
> implement a parallel (distributed or not) version of MultiSearcher, then
> your optimization would be difficult to implement.
A parallel implementation would require to update the minimum score to each
subsearcher, which might substantially reduce the communication requirements.
A bit of delay is quite tolerable in this update.
To balance computation and communication, it might well be necessary to use a
priority queue with an asynchronously updated minimum score for each
subsearcher.
.And yes, I hope to use a parallel version in the future: more processors,
more threads, more disks :).
> In summary, please tell me of a use case where this optimization
> substantially improves overall performance.
I have not done any real life measurements because I'm not (yet) using
the development version of Lucene. For the next few months I'm tied to java
1.1.8, would that be a problem?
Regards,
Ype
---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org
Re: MultiSearcher discards interim results
Posted by Doug Cutting <cu...@lucene.com>.
Ype Kingma wrote:
>>I'm confused. The contract of this method is to return the top-scoring
>>nDocs. For a multi-searcher it must compute the top-scoring nDocs from
>>each sub-searcher, then find the top-scoring nDocs among these. If you
>
> For the first sub-searcher: yes. For the remaining sub-searchers it is only
> necessary to collect docs with a score not smaller than the minimum
> score provided by the first subsearcher.
Okay, now I see what you're after. You wish to minimize the cost of
maintaining the queue of top-scoring documents. But does hit queue
maintenance ever significantly affect overall search performance? I'd
be very surprised if it does. So, while perhaps not optimal, I suspect
the current implementation is adequate.
Also, the current approach works well with RemoteSearchable, while I
suspect your optimized version would not. And if someone were ever to
implement a parallel (distributed or not) version of MultiSearcher, then
your optimization would be difficult to implement.
In summary, please tell me of a use case where this optimization
substantially improves overall performance.
Doug
---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org
Re: MultiSearcher discards interim results
Posted by Ype Kingma <yk...@xs4all.nl>.
Doug,
I tried to reply through a webmail facility earlier today, but it seems
to have failed. I'll try and provide a similar reply now. Please discard
the earlier attempt, if it gets through...
On Friday 07 February 2003 19:58, you wrote:
> I'm confused. The contract of this method is to return the top-scoring
> nDocs. For a multi-searcher it must compute the top-scoring nDocs from
> each sub-searcher, then find the top-scoring nDocs among these. If you
For the first sub-searcher: yes. For the remaining sub-searchers it is only
necessary to collect docs with a score not smaller than the minimum
score provided by the first subsearcher.
In the worst case all the results of the remaining subsearchers will be
discarded anyway, so there is no point in collecting the best ndocs
for each of them, and in doing all the work in their priority queues.
The patch attempts to avoid this by using a single hit collector
with a single priority queue.
Some time ago I tried to implement a multi searcher and retriever
using the best ndocs from each subsearcher and discarding all
superfluous results. The real problem was that it would also retrieve
all documents before discarding them. Needless to say that I
switched to a home brewn hit collector very soon. After collecting,
the retrieval is now done in order of document number per index reader.
As the new MultiSearcher also provides more consistent scoring
between subsearchers, I going to give it a try it asap.
I'd also like to try the new scoring explanation facilities.
Are there people using the nightly builds with some success?
Kind regards,
Ype
---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org
Re: MultiSearcher discards interim results
Posted by yk...@xs4all.nl.
Doug,
Sorry for the delay. I'm having a hardware problem on my home machine and
I'm using webmail now. It might take some time before I can continue.
> I'm confused. The contract of this method is to return the top-scoring
> nDocs. For a multi-searcher it must compute the top-scoring nDocs from
> each sub-searcher, then find the top-scoring nDocs among these.
For the first sub-searcher, yes. For later sub-searchers it
is only necessary to keep the documents that score not smaller
than the current minimum score.
Worst case: consider what happens when later subsearchers only find scores
smaller than the minimum score kept by the first
sub-searcher.
In that case the current code builds up a full ndocs size priority queue
for each later subsearcher, and all these results are going to be
discarded.
The patch intends to avoid the housekeeping of the nDocs size priority
queues for the later sub-searchers by using a single priority queue for
all sub-searchers.
The story behind this is that at some point I actually had a very bad
implementation of a multi searcher and retriever using
a TopDocs result from each subsearcher. The net effect was that not only
where all results kept, but also all the stored results had to be
retrieved, before discarding most of them.
Needless to say that I switched to a home grown HitCollector
very soon...
As the current MultiSearcher also provides consistent scoring
between databases, I'm going to use it asap.
Are people actually using the nightly builds? I'd also
like to give the scoring explanation facilities a try.
Kind regards,
Ype Kingma
---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org
Re: MultiSearcher discards interim results
Posted by Doug Cutting <cu...@lucene.com>.
I'm confused. The contract of this method is to return the top-scoring
nDocs. For a multi-searcher it must compute the top-scoring nDocs from
each sub-searcher, then find the top-scoring nDocs among these. If you
want more of the top-scoring documents, just pass in a larger value for
nDocs. If you want all of the matching documents, pass
Integer.MAX_VALUE. How does this not meet your needs?
Doug
Ype Kingma wrote:
> Dear developers,
>
> public TopDocs search(Query query, Filter filter, int nDocs)
> contains an
> else break;
> which discards previous interim results.
>
> Since I expect to need in the order of 100 best results from
> 20 databases on a regular basis I don't really like this.
>
> This is the current code:
>
> for (int i = 0; i < searchables.length; i++) { // search each searcher
> TopDocs docs = searchables[i].search(query, filter, nDocs);
> totalHits += docs.totalHits; // update totalHits
> ScoreDoc[] scoreDocs = docs.scoreDocs;
> for (int j = 0; j < scoreDocs.length; j++) { // merge scoreDocs into hq
> ScoreDoc scoreDoc = scoreDocs[j];
> if (scoreDoc.score >= minScore) {
> scoreDoc.doc += starts[i]; // convert doc
> hq.put(scoreDoc); // update hit queue
> if (hq.size() > nDocs) { // if hit queue overfull
> hq.pop(); // remove lowest in hit queue
> minScore = ((ScoreDoc)hq.top()).score; // reset minScore
> }
> } else
> break; // no more scores > minScore
> }
> }
>
>
> Attached is an untested patch for this. It works by implementing
> a MultiCollector that has the state to collect results from
> the subsearchers without discarding interim results.
> The patch is a dif -c against current CVS.
>
> I'd like to add some test cases, but before I do that
> I'd prefer to have comments.
>
> I checked the testcases for MultiSearcher, but they don't
> seem to exercise the code in the patch.
> The existing test-unit build runs fine with the patch.
>
> Regards,
> Ype
>
>
> ------------------------------------------------------------------------
>
> Index: jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java
> ===================================================================
> RCS file: /home/cvspublic/jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java,v
> retrieving revision 1.10
> diff -c -r1.10 MultiSearcher.java
> *** jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java 29 Jan 2003 17:18:54 -0000 1.10
> --- jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java 3 Feb 2003 22:43:35 -0000
> ***************
> *** 141,175 ****
> return maxDoc;
> }
>
> public TopDocs search(Query query, Filter filter, int nDocs)
> throws IOException {
> ! HitQueue hq = new HitQueue(nDocs);
> ! float minScore = 0.0f;
> ! int totalHits = 0;
> !
> ! for (int i = 0; i < searchables.length; i++) { // search each searcher
> ! TopDocs docs = searchables[i].search(query, filter, nDocs);
> ! totalHits += docs.totalHits; // update totalHits
> ! ScoreDoc[] scoreDocs = docs.scoreDocs;
> ! for (int j = 0; j < scoreDocs.length; j++) { // merge scoreDocs into hq
> ! ScoreDoc scoreDoc = scoreDocs[j];
> ! if (scoreDoc.score >= minScore) {
> ! scoreDoc.doc += starts[i]; // convert doc
> ! hq.put(scoreDoc); // update hit queue
> ! if (hq.size() > nDocs) { // if hit queue overfull
> ! hq.pop(); // remove lowest in hit queue
> ! minScore = ((ScoreDoc)hq.top()).score; // reset minScore
> }
> ! } else
> ! break; // no more scores > minScore
> }
> }
>
> ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
> ! for (int i = hq.size()-1; i >= 0; i--) // put docs in array
> scoreDocs[i] = (ScoreDoc)hq.pop();
>
> ! return new TopDocs(totalHits, scoreDocs);
> }
>
>
> --- 141,198 ----
> return maxDoc;
> }
>
> +
> public TopDocs search(Query query, Filter filter, int nDocs)
> throws IOException {
> !
> ! class MultiCollector extends HitCollector {
> ! HitQueue hq;
> ! int nDocs = 0;
> ! int totalHits = 0;
> ! int start = 0;
> ! float minScore = 0.0f;
> ! ScoreDoc scoreDoc = null; /* reuse last one discarded from hitqueue hq */
> !
> ! public MultiCollector(int nd) {
> ! nDocs = nd;
> ! hq = new HitQueue(nd);
> ! }
> !
> ! public void collect(int doc, float score) {
> ! totalHits++;
> ! System.out.println(getClass() + " hits: " + totalHits + ", start: " + start
> ! + ", docNr: " + doc + ", score: " + score);
> ! if (score >= minScore) {
> ! if (scoreDoc == null) {
> ! scoreDoc = new ScoreDoc(doc + start, score);
> ! } else {
> ! scoreDoc.doc = doc + start;
> ! scoreDoc.score = score;
> ! }
> ! hq.put(scoreDoc);
> ! if (hq.size() > nDocs) {
> ! scoreDoc = (ScoreDoc) hq.pop();
> ! minScore = ((ScoreDoc)hq.top()).score;
> ! } else {
> ! scoreDoc = null;
> }
> ! }
> }
> }
>
> + MultiCollector mc = new MultiCollector(nDocs);
> +
> + for (int i = 0; i < searchables.length; i++) {
> + mc.start = starts[i];
> + searchables[i].search(query, filter, mc);
> + }
> +
> + HitQueue hq = mc.hq;
> ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
> ! for (int i = hq.size()-1; i >= 0; i--)
> scoreDocs[i] = (ScoreDoc)hq.pop();
>
> ! return new TopDocs(mc.totalHits, scoreDocs);
> }
>
>
> ***************
> *** 201,207 ****
>
> }
> }
> !
> public Query rewrite(Query original) throws IOException {
> Query[] queries = new Query[searchables.length];
> for (int i = 0; i < searchables.length; i++) {
> --- 224,230 ----
>
> }
> }
> !
> public Query rewrite(Query original) throws IOException {
> Query[] queries = new Query[searchables.length];
> for (int i = 0; i < searchables.length; i++) {
>
>
> ------------------------------------------------------------------------
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: lucene-dev-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org