Mailing List Archive

Two-phase range queries?
Hi folks-

I've been spending a little time getting familiar with the BKD-tree-based
range query support currently implemented in Lucene, and wonder if there's
ever been a discussion around supporting two-phase iteration in this space.
If I'm understanding the current implementation properly (specifically
looking at PointRangeQuery), it appears that all matches are determined
up-front by 1) identifying segments of the tree that contain candidate
matches (i.e., containing part of the query range), and then 2) confirming
whether-or-not the contained points actually fall within the range. I'm
also a little low on coffee this morning so it's entirely possible I'm
misunderstanding the current implementation (please correct me if so).

With this approach, it seems like we could potentially be doing quite a bit
of wasted effort in some situations. I have no thoughts on how to actually
implement this yet, but I wonder if we could support two-phase iteration by
1) returning all docs with points contained in candidate BKD-tree segments
as an approximation, and then 2) only checking the points against the query
range when confirming matches in the second phase? I think the idea would
extend to LatLonPointDistanceQuery as well (and maybe others?).

I did a Jira search for a related issue but came up empty. Anyone know if
this idea has been discussed previously, or if there's some inherent flaw
with the approach that would make it a non-starter? I don't really have any
cycles to work on this at the moment, but can at least open a Jira issue to
track if it seems like a reasonable thing to explore.

Cheers,
-Greg
Re: Two-phase range queries? [ In reply to ]
Greg, I don't think this works the way that you are imagining. It
doesn't go document-at-a-time actually, and I don't think it is a good
fit for two-phases.

It also does not do this two-part confirmation. It reads rectangles
from the index and determines if a rectangle fits in the range.

For example, if i query on Virginia, USA it might iterate like this:

phase 1
* descend deeper into the USA rectangle, as it intersects the query range
* discard the Germany rectangle, as it is completely outside of query range.

phase 2
* discard entire western USA rectangle, outside of query range
* descend deeper into eastern USA rectangle

...

phase N
* accept some county-sized rectangles that fit entirely inside
virginia, they are inside query range
* descend deeper into some county-sized rectangles on the border with
north carolina, west virginia, maryland, etc

It might even have to test some individual points at the end of the
day to sort out the stuff on the "border" with the other states. But
the number of individual points tested should not be large, as the BKD
organizes itself based on density.

Try this video that Mike made, as I am short on coffee too:
https://www.youtube.com/watch?v=8BCf9Kx-AxY

On Tue, Jun 29, 2021 at 9:30 AM Greg Miller <gsmiller@gmail.com> wrote:
>
> Hi folks-
>
> I've been spending a little time getting familiar with the BKD-tree-based range query support currently implemented in Lucene, and wonder if there's ever been a discussion around supporting two-phase iteration in this space. If I'm understanding the current implementation properly (specifically looking at PointRangeQuery), it appears that all matches are determined up-front by 1) identifying segments of the tree that contain candidate matches (i.e., containing part of the query range), and then 2) confirming whether-or-not the contained points actually fall within the range. I'm also a little low on coffee this morning so it's entirely possible I'm misunderstanding the current implementation (please correct me if so).
>
> With this approach, it seems like we could potentially be doing quite a bit of wasted effort in some situations. I have no thoughts on how to actually implement this yet, but I wonder if we could support two-phase iteration by 1) returning all docs with points contained in candidate BKD-tree segments as an approximation, and then 2) only checking the points against the query range when confirming matches in the second phase? I think the idea would extend to LatLonPointDistanceQuery as well (and maybe others?).
>
> I did a Jira search for a related issue but came up empty. Anyone know if this idea has been discussed previously, or if there's some inherent flaw with the approach that would make it a non-starter? I don't really have any cycles to work on this at the moment, but can at least open a Jira issue to track if it seems like a reasonable thing to explore.
>
> Cheers,
> -Greg

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Two-phase range queries? [ In reply to ]
Hi Greg,

Have you looked at IndexOrDocValuesQuery? It dynamically chooses between
computing the range up-front using the BKD tree and running the range query
using doc values depending on the estimated cost of the range query
(computed by counting the number of leaf nodes of the BKD tree that have
matches, which is cheap to compute) vs. the cost of the overall query.
Hopefully the javadocs are not too bad, and I wrote a small blog
<https://www.elastic.co/blog/better-query-planning-for-range-queries-in-elasticsearch>
about this query a few years ago.


On Tue, Jun 29, 2021 at 3:30 PM Greg Miller <gsmiller@gmail.com> wrote:

> Hi folks-
>
> I've been spending a little time getting familiar with the BKD-tree-based
> range query support currently implemented in Lucene, and wonder if there's
> ever been a discussion around supporting two-phase iteration in this space.
> If I'm understanding the current implementation properly (specifically
> looking at PointRangeQuery), it appears that all matches are determined
> up-front by 1) identifying segments of the tree that contain candidate
> matches (i.e., containing part of the query range), and then 2) confirming
> whether-or-not the contained points actually fall within the range. I'm
> also a little low on coffee this morning so it's entirely possible I'm
> misunderstanding the current implementation (please correct me if so).
>
> With this approach, it seems like we could potentially be doing quite a
> bit of wasted effort in some situations. I have no thoughts on how to
> actually implement this yet, but I wonder if we could support two-phase
> iteration by 1) returning all docs with points contained in candidate
> BKD-tree segments as an approximation, and then 2) only checking the points
> against the query range when confirming matches in the second phase? I
> think the idea would extend to LatLonPointDistanceQuery as well (and maybe
> others?).
>
> I did a Jira search for a related issue but came up empty. Anyone know if
> this idea has been discussed previously, or if there's some inherent flaw
> with the approach that would make it a non-starter? I don't really have any
> cycles to work on this at the moment, but can at least open a Jira issue to
> track if it seems like a reasonable thing to explore.
>
> Cheers,
> -Greg
>


--
Adrien
Re: Two-phase range queries? [ In reply to ]
Thanks Robert/Adrien for the quick thoughts!

Robert- Just to clarify a little bit (slightly more caffeinated now): For
the cases where an indexed rectangle fits entirely within the query
rectangle, these would be "confirmed" matches up-front, relying on the
efficiency of the BKD-tree data structure (as you describe). The second
phase confirmation I had in mind were the cases where the query
rectangle overlaps,
or sits inside the indexed rectangle, and the individual points/docs within
the indexed rectangle need to be checked against the boundaries of the
query rectangle. That step seemed like a good candidate for a second phase,
effectively avoiding that check if it doesn't end up being necessary. But,
if that is relatively rare compared to the case where an indexed shape fits
entirely within the query shape, then maybe there isn't value.

Adrien- Oh cool! Was not aware of this actually, but after reading the blog
and looking at the code a little bit, this is in the neighborhood of what I
was thinking. I suppose what I had in mind is a little bit of a hybrid of
the two approaches currently implemented. I wonder if, in the case where
the range query is used to "verify" matches (to borrow from your
terminology), there's a benefit to still using the BKD-tree to quickly
eliminate docs that don't match before using the doc values to confirm
matches for "approximate" matches. Said differently, what if there was a
range query implementation that collected "definite" matches as well as
"potential" matches using the BKD-tree up-front (so definite matches are
docs where the indexed shape is entirely contained in the query shape and
potential matches are cases where the indexed shape overlaps the query
shape), then in a second phase used the doc values to confirm/reject
"potential" matches? Just a thought.

Unwinding a bit, these responses are exactly what I was looking for. As a
starting point, I wanted to understand if this had been explored, and it
looks like it certainly has—so thanks for all the pointers!

Cheers,
-Greg

On Tue, Jun 29, 2021 at 7:40 AM Adrien Grand <jpountz@gmail.com> wrote:

> Hi Greg,
>
> Have you looked at IndexOrDocValuesQuery? It dynamically chooses between
> computing the range up-front using the BKD tree and running the range query
> using doc values depending on the estimated cost of the range query
> (computed by counting the number of leaf nodes of the BKD tree that have
> matches, which is cheap to compute) vs. the cost of the overall query.
> Hopefully the javadocs are not too bad, and I wrote a small blog
> <https://www.elastic.co/blog/better-query-planning-for-range-queries-in-elasticsearch>
> about this query a few years ago.
>
>
> On Tue, Jun 29, 2021 at 3:30 PM Greg Miller <gsmiller@gmail.com> wrote:
>
>> Hi folks-
>>
>> I've been spending a little time getting familiar with the BKD-tree-based
>> range query support currently implemented in Lucene, and wonder if there's
>> ever been a discussion around supporting two-phase iteration in this space.
>> If I'm understanding the current implementation properly (specifically
>> looking at PointRangeQuery), it appears that all matches are determined
>> up-front by 1) identifying segments of the tree that contain candidate
>> matches (i.e., containing part of the query range), and then 2) confirming
>> whether-or-not the contained points actually fall within the range. I'm
>> also a little low on coffee this morning so it's entirely possible I'm
>> misunderstanding the current implementation (please correct me if so).
>>
>> With this approach, it seems like we could potentially be doing quite a
>> bit of wasted effort in some situations. I have no thoughts on how to
>> actually implement this yet, but I wonder if we could support two-phase
>> iteration by 1) returning all docs with points contained in candidate
>> BKD-tree segments as an approximation, and then 2) only checking the points
>> against the query range when confirming matches in the second phase? I
>> think the idea would extend to LatLonPointDistanceQuery as well (and maybe
>> others?).
>>
>> I did a Jira search for a related issue but came up empty. Anyone know if
>> this idea has been discussed previously, or if there's some inherent flaw
>> with the approach that would make it a non-starter? I don't really have any
>> cycles to work on this at the moment, but can at least open a Jira issue to
>> track if it seems like a reasonable thing to explore.
>>
>> Cheers,
>> -Greg
>>
>
>
> --
> Adrien
>
Re: Two-phase range queries? [ In reply to ]
On Tue, Jun 29, 2021 at 1:17 PM Greg Miller <gsmiller@gmail.com> wrote:

> Robert- Just to clarify a little bit (slightly more caffeinated now): For the cases where an indexed rectangle fits entirely within the query rectangle, these would be "confirmed" matches up-front, relying on the efficiency of the BKD-tree data structure (as you describe). The second phase confirmation I had in mind were the cases where the query rectangle overlaps, or sits inside the indexed rectangle, and the individual points/docs within the indexed rectangle need to be checked against the boundaries of the query rectangle. That step seemed like a good candidate for a second phase, effectively avoiding that check if it doesn't end up being necessary. But, if that is relatively rare compared to the case where an indexed shape fits entirely within the query shape, then maybe there isn't value.

It is rare/contained by definition, because it is a space-partitioned
data structure. If there were a "lot" of these then BKD would form
rectangles out of them and we'd check those rectangles instead.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Two-phase range queries? [ In reply to ]
Hi

There might be a way to improve this using a little bit of extra meta data
for docvalues. For some of the compression strategies used for docvalues
there is already some information that could be used to skip blocks of
documents if no value would match a queries range. By storing the minimum
and maximum for blocks of documents in the docvalue metadata it should be
possible to implement an approximation query that should be able to improve
most cases where a docvalue query is currently used. Postgres has the brin
(block range index) which is similar to this idea and gives in most cases
good performance with extremely small indices.

Am Di., 29. Juni 2021 um 16:39 Uhr schrieb Adrien Grand <jpountz@gmail.com>:

> Hi Greg,
>
> Have you looked at IndexOrDocValuesQuery? It dynamically chooses between
> computing the range up-front using the BKD tree and running the range query
> using doc values depending on the estimated cost of the range query
> (computed by counting the number of leaf nodes of the BKD tree that have
> matches, which is cheap to compute) vs. the cost of the overall query.
> Hopefully the javadocs are not too bad, and I wrote a small blog
> <https://www.elastic.co/blog/better-query-planning-for-range-queries-in-elasticsearch>
> about this query a few years ago.
>
>
> On Tue, Jun 29, 2021 at 3:30 PM Greg Miller <gsmiller@gmail.com> wrote:
>
>> Hi folks-
>>
>> I've been spending a little time getting familiar with the BKD-tree-based
>> range query support currently implemented in Lucene, and wonder if there's
>> ever been a discussion around supporting two-phase iteration in this space.
>> If I'm understanding the current implementation properly (specifically
>> looking at PointRangeQuery), it appears that all matches are determined
>> up-front by 1) identifying segments of the tree that contain candidate
>> matches (i.e., containing part of the query range), and then 2) confirming
>> whether-or-not the contained points actually fall within the range. I'm
>> also a little low on coffee this morning so it's entirely possible I'm
>> misunderstanding the current implementation (please correct me if so).
>>
>> With this approach, it seems like we could potentially be doing quite a
>> bit of wasted effort in some situations. I have no thoughts on how to
>> actually implement this yet, but I wonder if we could support two-phase
>> iteration by 1) returning all docs with points contained in candidate
>> BKD-tree segments as an approximation, and then 2) only checking the points
>> against the query range when confirming matches in the second phase? I
>> think the idea would extend to LatLonPointDistanceQuery as well (and maybe
>> others?).
>>
>> I did a Jira search for a related issue but came up empty. Anyone know if
>> this idea has been discussed previously, or if there's some inherent flaw
>> with the approach that would make it a non-starter? I don't really have any
>> cycles to work on this at the moment, but can at least open a Jira issue to
>> track if it seems like a reasonable thing to explore.
>>
>> Cheers,
>> -Greg
>>
>
>
> --
> Adrien
>


--
------------------------------

*Daniel Penning* / Senior Product Developer
T.: +49 (0)30 5900113-83 / F.: +49 (0)30 5900113-99
E-Mail: d.penning@stroeermediabrands.de
Web: www.stroeermediabrands.de

Ströer Media Brands GmbH, Torstraße 49, 10119 Berlin-Mitte
Geschäftsführer: Tim Nocken, Marc Schmitz
Handelsregister: Amtsgericht Charlottenburg HRB 195991 B
Re: Two-phase range queries? [ In reply to ]
Greg, you may find it interesting to see some code in spatial-extras that
works similar to what you describe. There is a so-called
CompositeSpatialStrategy built off a grid using the terms index (not BKD)
plus another that stores the vector geometry into DocValues. The Query
that does the work is here:
https://github.com/apache/lucene/blob/main/lucene/spatial-extras/src/java/org/apache/lucene/spatial/composite/IntersectsRPTVerifyQuery.java
Only some "shapes" that are at the border of the query shape will require
the potentially expensive DocValues lookup.

~ David Smiley
Apache Lucene/Solr Search Developer
http://www.linkedin.com/in/davidwsmiley


On Tue, Jun 29, 2021 at 9:30 AM Greg Miller <gsmiller@gmail.com> wrote:

> Hi folks-
>
> I've been spending a little time getting familiar with the BKD-tree-based
> range query support currently implemented in Lucene, and wonder if there's
> ever been a discussion around supporting two-phase iteration in this space.
> If I'm understanding the current implementation properly (specifically
> looking at PointRangeQuery), it appears that all matches are determined
> up-front by 1) identifying segments of the tree that contain candidate
> matches (i.e., containing part of the query range), and then 2) confirming
> whether-or-not the contained points actually fall within the range. I'm
> also a little low on coffee this morning so it's entirely possible I'm
> misunderstanding the current implementation (please correct me if so).
>
> With this approach, it seems like we could potentially be doing quite a
> bit of wasted effort in some situations. I have no thoughts on how to
> actually implement this yet, but I wonder if we could support two-phase
> iteration by 1) returning all docs with points contained in candidate
> BKD-tree segments as an approximation, and then 2) only checking the points
> against the query range when confirming matches in the second phase? I
> think the idea would extend to LatLonPointDistanceQuery as well (and maybe
> others?).
>
> I did a Jira search for a related issue but came up empty. Anyone know if
> this idea has been discussed previously, or if there's some inherent flaw
> with the approach that would make it a non-starter? I don't really have any
> cycles to work on this at the moment, but can at least open a Jira issue to
> track if it seems like a reasonable thing to explore.
>
> Cheers,
> -Greg
>