You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-user@lucene.apache.org by sol myr <so...@yahoo.com> on 2011/10/23 15:06:02 UTC
performance question - number of documents
Hi,
We've noticed some Lucene performance phenomenon, and would appreciate an explanation from anyone familiar with Lucene internals
(I know Lucene as a user, but haven't looked under its hood).
We have a Lucene index of about 30 million records.
We ran 2 queries: "AND" and "OR" ("+john +doe" versus "john doe").
The AND query had much better performance (AND takes about 500 millis, while OR takes about 2000 millis).
We wondered whether this has anything to do with the number of potential matches?
Our AND has only about 5000 matches (5000 documents contain *both* "john" and "doe").
Our OR has about 8 million matches (8 million documents contain *either* "john" or "doe").
Does this explain the performance difference?
But why would it matter, as long as we take only the top 5 matches ( indexSearcher.search(query, 5))...?
Is there any other explanation?
Thanks :)
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: performance question - number of documents
Posted by Felipe Hummel <fe...@gmail.com>.
Hi,
there are two types of query processing in document retrieval:
document-at-a-time and term-at-a-time.
Lucene uses document-at-a-time processing. That means the posting lists (the
list of documents a word appears in) is sorted by the document IDs.
This type of processing is usually better for large datasets because of the
better memory usage. It is also great for AND queries as it can
skip documents (using skip-lists) during the processing.
On a term-at-a-time processing, on the other hand, the documents are sorted
by some "metric", usually Term-frequency. So what you said would apply.
See the first page of this
article<http://www.cis.upenn.edu/~jstoy/cis650/papers/WAND.pdf>for
more information.
Felipe Hummel
On Mon, Oct 24, 2011 at 8:29 AM, sol myr <so...@yahoo.com> wrote:
> Hi,
>
> Thanks for this reply.
>
> Could I please just ask - doesn't Lucene keep the data sorted, at least
> partially (heuristically)?
>
> E.g. if the reverse index says "the word DOE appears in documents #1, #7,
> #5" .
> Won't Lucene do some smart sorting on this list of documents? Maybe by
> frequency, first listing documents that contain many appearances of DOE?
>
> I know ranking considers more subtle factors such as document length, "idf"
> to prioritize rare words, etc.
> But if there are 8 million documents with the word DOE, and I only asked
> for the top 5, I might take a risk and limit the change to (say) 1000
> documents that contain most appearances of that word, and only between them
> bother to calculate the exact ranking...
>
> That's not criticism, I'm no algorithms expert, I just raise the question
> and try to learn...
> Insights would be appreciated :)
> Thanks again.
>
>
>
>
> ----- Original Message -----
> From: Erick Erickson <er...@gmail.com>
> To: java-user@lucene.apache.org; sol myr <so...@yahoo.com>
> Cc:
> Sent: Sunday, October 23, 2011 7:18 PM
> Subject: Re: performance question - number of documents
>
> "Why would it matter...top 5 matches" Because Lucene has to calculate
> the score of all documents in order to insure that it returns those 5
> documents.
> What if the very last document scored was the most relevant?
>
> Best
> Erick
>
> On Sun, Oct 23, 2011 at 3:06 PM, sol myr <so...@yahoo.com> wrote:
> > Hi,
> >
> > We've noticed some Lucene performance phenomenon, and would appreciate an
> explanation from anyone familiar with Lucene internals
> >
> > (I know Lucene as a user, but haven't looked under its hood).
> >
> > We have a Lucene index of about 30 million records.
> > We ran 2 queries: "AND" and "OR" ("+john +doe" versus "john doe").
> > The AND query had much better performance (AND takes about 500 millis,
> while OR takes about 2000 millis).
> >
> > We wondered whether this has anything to do with the number of potential
> matches?
> > Our AND has only about 5000 matches (5000 documents contain *both* "john"
> and "doe").
> > Our OR has about 8 million matches (8 million documents contain *either*
> "john" or "doe").
> >
> >
> > Does this explain the performance difference?
> > But why would it matter, as long as we take only the top 5 matches (
> indexSearcher.search(query, 5))...?
> > Is there any other explanation?
> >
> > Thanks :)
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> > For additional commands, e-mail: java-user-help@lucene.apache.org
> >
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
Re: performance question - number of documents
Posted by sol myr <so...@yahoo.com>.
Hi,
Thanks for this reply.
Could I please just ask - doesn't Lucene keep the data sorted, at least partially (heuristically)?
E.g. if the reverse index says "the word DOE appears in documents #1, #7, #5" .
Won't Lucene do some smart sorting on this list of documents? Maybe by frequency, first listing documents that contain many appearances of DOE?
I know ranking considers more subtle factors such as document length, "idf" to prioritize rare words, etc.
But if there are 8 million documents with the word DOE, and I only asked for the top 5, I might take a risk and limit the change to (say) 1000 documents that contain most appearances of that word, and only between them bother to calculate the exact ranking...
That's not criticism, I'm no algorithms expert, I just raise the question and try to learn...
Insights would be appreciated :)
Thanks again.
----- Original Message -----
From: Erick Erickson <er...@gmail.com>
To: java-user@lucene.apache.org; sol myr <so...@yahoo.com>
Cc:
Sent: Sunday, October 23, 2011 7:18 PM
Subject: Re: performance question - number of documents
"Why would it matter...top 5 matches" Because Lucene has to calculate
the score of all documents in order to insure that it returns those 5 documents.
What if the very last document scored was the most relevant?
Best
Erick
On Sun, Oct 23, 2011 at 3:06 PM, sol myr <so...@yahoo.com> wrote:
> Hi,
>
> We've noticed some Lucene performance phenomenon, and would appreciate an explanation from anyone familiar with Lucene internals
>
> (I know Lucene as a user, but haven't looked under its hood).
>
> We have a Lucene index of about 30 million records.
> We ran 2 queries: "AND" and "OR" ("+john +doe" versus "john doe").
> The AND query had much better performance (AND takes about 500 millis, while OR takes about 2000 millis).
>
> We wondered whether this has anything to do with the number of potential matches?
> Our AND has only about 5000 matches (5000 documents contain *both* "john" and "doe").
> Our OR has about 8 million matches (8 million documents contain *either* "john" or "doe").
>
>
> Does this explain the performance difference?
> But why would it matter, as long as we take only the top 5 matches ( indexSearcher.search(query, 5))...?
> Is there any other explanation?
>
> Thanks :)
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: performance question - number of documents
Posted by Antony Sequeira <an...@gmail.com>.
This may not be directly relevant to Lucene, but I wanted to learn:
How does a web search engine do something like this.
Do they also "score every matching document on every query" OR
do they pick a subset first based on some static/offlline ranking criteria
then do what Lucene does OR
do they search and find every matching document, pick a subset of the
results based on a static ranking and then score that subset based on the
query terms.
I guess the assumption I am making is that it's not practical to "score
every matching document on every query" at www scale.
May be that assumption is wrong.
I also haven't understood how search scales :(
-Antony
On Sun, Oct 23, 2011 at 10:18 AM, Erick Erickson <er...@gmail.com>wrote:
> "Why would it matter...top 5 matches" Because Lucene has to calculate
> the score of all documents in order to insure that it returns those 5
> documents.
> What if the very last document scored was the most relevant?
>
> Best
> Erick
>
> On Sun, Oct 23, 2011 at 3:06 PM, sol myr <so...@yahoo.com> wrote:
> > Hi,
> >
> > We've noticed some Lucene performance phenomenon, and would appreciate an
> explanation from anyone familiar with Lucene internals
> >
> > (I know Lucene as a user, but haven't looked under its hood).
> >
> > We have a Lucene index of about 30 million records.
> > We ran 2 queries: "AND" and "OR" ("+john +doe" versus "john doe").
> > The AND query had much better performance (AND takes about 500 millis,
> while OR takes about 2000 millis).
> >
> > We wondered whether this has anything to do with the number of potential
> matches?
> > Our AND has only about 5000 matches (5000 documents contain *both* "john"
> and "doe").
> > Our OR has about 8 million matches (8 million documents contain *either*
> "john" or "doe").
> >
> >
> > Does this explain the performance difference?
> > But why would it matter, as long as we take only the top 5 matches (
> indexSearcher.search(query, 5))...?
> > Is there any other explanation?
> >
> > Thanks :)
> >
>
Re: performance question - number of documents
Posted by Erick Erickson <er...@gmail.com>.
"Why would it matter...top 5 matches" Because Lucene has to calculate
the score of all documents in order to insure that it returns those 5 documents.
What if the very last document scored was the most relevant?
Best
Erick
On Sun, Oct 23, 2011 at 3:06 PM, sol myr <so...@yahoo.com> wrote:
> Hi,
>
> We've noticed some Lucene performance phenomenon, and would appreciate an explanation from anyone familiar with Lucene internals
>
> (I know Lucene as a user, but haven't looked under its hood).
>
> We have a Lucene index of about 30 million records.
> We ran 2 queries: "AND" and "OR" ("+john +doe" versus "john doe").
> The AND query had much better performance (AND takes about 500 millis, while OR takes about 2000 millis).
>
> We wondered whether this has anything to do with the number of potential matches?
> Our AND has only about 5000 matches (5000 documents contain *both* "john" and "doe").
> Our OR has about 8 million matches (8 million documents contain *either* "john" or "doe").
>
>
> Does this explain the performance difference?
> But why would it matter, as long as we take only the top 5 matches ( indexSearcher.search(query, 5))...?
> Is there any other explanation?
>
> Thanks :)
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org