lucene-java-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Adrien Grand <jpou...@gmail.com>
Subject Re: prorated early termination
Date Fri, 01 Feb 2019 16:27:39 GMT
Something makes me curious: queries that can leverage sorted indices
should be _very_ fast, for instance in your case they only need to
look at 500 documents per segment at most (less in practice since we
stop collecting as soon as a non-competitive hit is found), so why do
you need to parallelize query execution?

On Fri, Feb 1, 2019 at 3:18 PM Michael Sokolov <msokolov@gmail.com> wrote:
>
> I want to propose an optimization to early termination that gives nice
> speedups for large result sets when searching with multiple threads at the
> cost of a small (controllable) probability of collecting documents out of
> order: in benchmarks I see +60-70% QPS for tasks like HighTermDayOfYearSort
> when topN=500, using 8 threads to search, and in our production system this
> optimization cut the latency of our slowest queries substantially.
>
> In a multi-phase ranking scenario a typical pattern is to retrieve a
> largish number of matches in a first pass using indexed sort, followed by a
> second pass that re-ranks and selects a smaller top K, using a more
> expensive ranking. N is chosen to provide sufficient probabililty of
> finding the desired top K across the whole index, given that the index sort
> is some approximation to the desired sort. When ranking by indexed sort, as
> in TopFieldCollector, we can now early-terminate when a sufficient number
> of matches have been found so that we only need retrieve N documents from
> each segment. In single-threaded mode we can check against
> minCompetitiveScore and terminate collection for each segment
> appropriately, but when using multiple threads to search concurrently there
> is no such coordination and we end up collecting N documents *per segment*,
> which are then merged down to N.
>
> We do not need to collect so many documents though. For any given segment,
> let p=(leaf.maxDoc/topLevel.maxDoc) be the proportion of documents in that
> segment. Assuming that documents are distributed randomly among segments,
> we can expect that on average we will find p*N of the top N documents in
> the given segment. If we only collect p*N documents, we will sometimes miss
> some documents that we should have collected, collecting some
> less-competitive documents from one segment, while not collecting all the
> competitive documents from another. But how many should we collect in order
> to make this occur only very rarely?
>
> The worst case is that all top N documents occur in a single segment. For
> even small values of N and small numbers of segments S, this probability is
> vanishingly small (N=10, S=10) -> 10^(1-N) = 1/10^9. More generally, this
> distribution of documents among segments is a multinomial distribution, and
> the variance of the number of documents in a single segment is that of a
> binomial distribution. The binomial variance in this case (p=probability of
> document in the segment, N number of documents) is p*(1-p)*N; we can use
> this to compute the number of documents to collect per leaf in order to
> bound the probability of a ranking error. I'm using a cutoff of 3 standard
> deviations, i.e.  collecting p*N + 3*(p*(1-p)*N)^1/2 documents for each
> segment. For N=500, p=0.2, we can collect 67 documents instead of 500 at
> the cost of an error that occurs < 3/1000.
>
> Also note that the kind of errors we make are typically benign. In most
> cases we will return the correct top N-1 documents, but instead of
> returning the Nth-ranked document in position N, we return the N+1st.
>
> Implementing this in Lucene requires a small patch to TopFieldCollector to
> introduce a leafHitsThreshold comparable to the existing
> totalHitsThreshold. Given the possibility of error, it might be good to
> have a way to disable this, but my inclination would be to enable it
> whenever approximate counts are enabled (ie by default), and disable when
> totalHitsThreshold is MAX_VALUE.
>
> What do you think? Shall I open an issue?



-- 
Adrien

---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org


Mime
View raw message