You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by Peter Karman <pe...@peknet.com> on 2011/06/21 07:42:43 UTC

[lucy-dev] RangeQuery and multi-value fields

Lucy does not (yet) support multi-value fields natively.

I want to override the behavior of the RangeQuery class to support my pseudo
multi-value fields, which I achieve by concatenating values with the \x03 byte.

I have fields containing values like:

doc 1:  "123\x{03}abc"
doc 2:  "def\x{03}456"

and I want to be able to do a range query like:

 lower => 'abc',
 upper => 'def'

and match both docs.

It looks like there are 2 possible approaches:

 * override the static methods in core/Lucy/Search/RangeQuery.c for
find_lower_bound() and find_upper_bound(), or

 * the core/Lucy/Index/SortCache.c Find() and Value() functions, so that they
can split the field values on the \x03 delimiter and treat each substring as a
separate value.

It seems like that second option is the better one since that should also affect
sorting, which would be a nice side effect. Maybe. :/

I'm wondering if (a) SortCache or RangeCompiler could/should be exposed as
public classes for overriding, and/or (b) if I'm just way off on this line of
thought.

pek

-- 
Peter Karman  .  http://peknet.com/  .  peter@peknet.com

Re: [lucy-dev] RangeQuery and multi-value fields

Posted by Dan Markham <dm...@gmail.com>.
The only thing that is a bit different is we encode (bases62) the numbers of xxxx's in the last digit mainly so the terms are smaller in length.


my @foo =  encode_trie(100000);
print Dumper(\@foo);

The output would look like this:
$VAR1 = [
          '1a',                     ## 1xxxxxxxxxx
          '129',                  ##  12xxxxxxxxx
          '1208',         
          '12007',
          '120026',
          '1200205',
          '12002014',
          '120020113',
          '1200201122',
          '12002011201',
          '120020112010'   ## the exact match for  base 3  @ 100000
        ];



So you really only use encode_trie(int) to build the terms to index and  
query_trie( minint, maxint ) for search  terms at query time.


few things i'm pretty sure need some love are:
 1.   encode() and qery_trie() are hard coded for base3.
 2.  If the length if your trie gets longer than 62 chars the cute disk saving trick above will surely not work.


enjoy,
-Dan


On Jun 22, 2011, at 7:19 PM, Peter Karman wrote:

> Marvin Humphrey wrote on 6/22/11 8:51 PM:
>>> On Tue, Jun 21, 2011 at 12:42:43AM -0500, Peter Karman wrote:
>>>> I want to override the behavior of the RangeQuery class to support my pseudo
>>>> multi-value fields, which I achieve by concatenating values with the \x03 byte.
>> 
>> OK, there's another option which has suddenly become more attractive. :)  My
>> Eventful colleague Dan Markham has submitted a trie implementation that can be
>> used for generating numeric ranges:
>> 
>>    https://issues.apache.org/jira/browse/LUCY-159
>> 
>> It is to some degree based on the algorithm used by Lucene's NumericRangeQuery:
>> 
>>    http://s.apache.org/QOx
>> 
> 
> Thanks to both you and Dan for this contribution!
> 
> I'll have a look at the code and the docs and see if it feels workable for my
> particular need. In any case, I think it's great to see contributions like
> these, expanding the Lucy ecosystem.
> 
> 
> -- 
> Peter Karman  .  http://peknet.com/  .  peter@peknet.com


Re: [lucy-dev] RangeQuery and multi-value fields

Posted by Peter Karman <pe...@peknet.com>.
Marvin Humphrey wrote on 6/22/11 8:51 PM:
>> On Tue, Jun 21, 2011 at 12:42:43AM -0500, Peter Karman wrote:
>>> I want to override the behavior of the RangeQuery class to support my pseudo
>>> multi-value fields, which I achieve by concatenating values with the \x03 byte.
> 
> OK, there's another option which has suddenly become more attractive. :)  My
> Eventful colleague Dan Markham has submitted a trie implementation that can be
> used for generating numeric ranges:
> 
>     https://issues.apache.org/jira/browse/LUCY-159
> 
> It is to some degree based on the algorithm used by Lucene's NumericRangeQuery:
> 
>     http://s.apache.org/QOx
> 

Thanks to both you and Dan for this contribution!

I'll have a look at the code and the docs and see if it feels workable for my
particular need. In any case, I think it's great to see contributions like
these, expanding the Lucy ecosystem.


-- 
Peter Karman  .  http://peknet.com/  .  peter@peknet.com

Re: [lucy-dev] RangeQuery and multi-value fields

Posted by Marvin Humphrey <ma...@rectangular.com>.
> On Tue, Jun 21, 2011 at 12:42:43AM -0500, Peter Karman wrote:
> > I want to override the behavior of the RangeQuery class to support my pseudo
> > multi-value fields, which I achieve by concatenating values with the \x03 byte.

OK, there's another option which has suddenly become more attractive. :)  My
Eventful colleague Dan Markham has submitted a trie implementation that can be
used for generating numeric ranges:

    https://issues.apache.org/jira/browse/LUCY-159

It is to some degree based on the algorithm used by Lucene's NumericRangeQuery:

    http://s.apache.org/QOx

We can potentially use these two sources as initial implementations to build a
module that does what you need it to.

Say that you have the following documents:

    { id => 'a', nums => "199", trie => "1xx 19x 199" }
    { id => 'b', nums => "209", trie => "2xx 20x 209" }
    { id => 'c', nums => "211", trie => "2xx 21x 211" }

The "trie" field contains prefixes derived from the value within the "num"
field.  

The presence of the trie field allows us to convert searches for ranges into
searches for collections of terms.

   100 .. 199  =>  1xx
   100 .. 119  =>  10x OR 11x
   200 .. 300  =>  2xx OR 300
   410 .. 422  =>  41x OR 420 OR 421 OR 422

In the example above, the "trie" numbers use base 10 when determining their
prefixes.  In NumericRangeQuery, there is a "precisionStep" measured in bits
which is used to determine the prefixes.  (The materials Dan submitted use a
hard-coded base 3, which happened to be best for our esoteric purposes.)

The samples above only have one number in the "nums" field, but you can have
as many as you want:
    
    { id => 'd', nums => "205 351", trie => "2xx 20x 205 3xx 35x 351" }

A range query for 200..300 (encoded as "2xx OR 300") would match that
document, as would a range query for 351..353 (encoded as
"351 OR 352 OR 353").

Range queries built this way max out at a workable number of OR'd terms, as
opposed to the "dumb" alternative of expressing a range like "400..500" as 101
OR'd terms ("400 401 402 [...] 500")  The NumericRangeQuery documentation
explains the tuning tradeoffs.

Marvin Humphrey


Re: [lucy-dev] RangeQuery and multi-value fields

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Tue, Jun 21, 2011 at 12:42:43AM -0500, Peter Karman wrote:
> Lucy does not (yet) support multi-value fields natively.

While it is true that Lucy has a different document model from Lucene and does
not support "multi-value fields", Lucene's "multi-value field" model does not
support sorting on such fields, either. 

    * Lucene sorts on the first (i.e. lexically-least) token in a multi-value
      field.
    * Lucy sorts on the complete field value.

In both cases, there is only one value associated with each document which
determines sort order.

Building a performant sort structure that behaves any other way is extremely
challenging.

> I want to override the behavior of the RangeQuery class to support my pseudo
> multi-value fields, which I achieve by concatenating values with the \x03 byte.

I suggest adding the document multiple times, once for each unique value of the
multi-value field you want to sort on.  (That's what I've done when faced with
this problem.)

Theoretically, there's another option: capture all hits and "post-sort" them
outside of Lucy after they are returned.  However, that requires that you
figure out what value within the field matched for each document, which is
going to be hard and slow.  And of course the approach won't scale.

> It looks like there are 2 possible approaches:
> 
>  * override the static methods in core/Lucy/Search/RangeQuery.c for
> find_lower_bound() and find_upper_bound(), or
> 
>  * the core/Lucy/Index/SortCache.c Find() and Value() functions, so that they
> can split the field values on the \x03 delimiter and treat each substring as a
> separate value.
> 
> It seems like that second option is the better one since that should also affect
> sorting, which would be a nice side effect. Maybe. :/

The real problem is the ords array, which is immutable,
single-value-per-document, and built at index-time.  Most sorting is not done
according to the what SortCache_Value() returns; the bulk of the comparisons
are performed within core/Lucy/Search/Collector/SortCollector.c using routines
such as this one:

    static INLINE int32_t
    SI_compare_by_ord4(SortCollector *self, uint32_t tick, int32_t a, int32_t b) {
        void *const ords = self->ord_arrays[tick];
        int32_t a_ord = NumUtil_u4get(ords, a); 
        int32_t b_ord = NumUtil_u4get(ords, b); 
        return a_ord - b_ord;
    }

For background, see the "Sort file format" thread from 2009 where Mike
McCandless and I hashed out the design:

    http://markmail.org/message/cfajhki4px5l34fm

> I'm wondering if (a) SortCache or RangeCompiler could/should be exposed as
> public classes for overriding, and/or (b) if I'm just way off on this line of
> thought.

At some point, it would be nice to expose hooks which would allow sorting of
search results by some arbitrary external resource.  That would allow us to
take the non-scaling post-sort approach described above and execute it during
the initial search, eliminating the need to capture all documents prior to
sorting.

Another theoretical possibility is proposed here:

    http://www.slideshare.net/MarkHarwood/proposal-for-nested-document-support-in-lucene
    https://issues.apache.org/jira/browse/LUCENE-2454

Both approaches are difficult and would require a lot of work.  I'm
unenthusiastic about the second option because it would entail adding a lot of
complexity to Lucy's internals.

Marvin Humphrey