You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Toke Eskildsen <te...@statsbiblioteket.dk> on 2011/02/21 15:27:32 UTC

Proper use of TermsEnum.seek?

My low-memory sorting/faceting-hacking requires terms to be accessed by
ordinals. With Lucene 4.0 I cannot depend on TermsEnums supporting ord()
and seek(long), so the code switches to a cache that keeps track of
every X terms if they are not implemented. When the terms for an ordinal
is requested, it jumps to the nearest previously cached term and calls
next() from there until the ordinal matches. So far so good.

Two methods for seeking terms are:
seek(BytesRef text) and seek(BytesRef term, TermState state).

The JavaDoc indicates that the seek with TermState is (potentially) the
fastest in this scenario as implementations can seek very efficient
using a custom TermState.

My problem is that I am going for low memory and it seems that I need to
keep track of both BytesRef term and TermState state in order to use
this method. This is quite a burden, memory-wise.

I tried calling with an empty BytesRef term. This gave me an empty
result back for the call itself, but the correct terms for subsequent
calls to next. This works perfectly for my scenario. However, that was
just an experiment using the default variable gap codec, so I am unsure
if I can count on this behavior for any given codec?

Any thoughts on how to reduce the memory needed for ordinal-based
lookup, without killing performance, would be appreciated.


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


Re: Proper use of TermsEnum.seek?

Posted by Simon Willnauer <si...@googlemail.com>.
On Fri, Feb 25, 2011 at 1:28 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> On Tue, 2011-02-22 at 12:19 +0100, Simon Willnauer wrote:
>
> [Toke: Using a partial cache of BytesRef+TermState]
>
>> I don't know how you did implement that part but you might consider
>> using something like ByteBlockPool instead of BytesRef instances to
>> safe an extra amount of memory. Just as a hint you can look at
>> BytesRefHash for an example.
>
> Avoiding the overhead of representing the BytesRefs as separate Objects
> seems sensible. Unfortunately this isn't possible with TermState, at
> least not in general. As I focus quite a bit on memory overhead, tt
> might make sense to just store the BytesRef and take the performance
> penalty of seek(BytesRef) to avoid the Object-overhead of TermStats.
>
>> I think we need to check if that BytesRef is really needed. I hope we
>> can get rid of it eventually.
>
> It does seem a bit peculiar that is is needed for a seek using a
> previously delivered marker. Maybe the TermState could hold a reference
> to the BytesRef itself, if it is needed by the implementation?

Yeah I agree, but it seems that we still need it for all the impls
right now. I did not look at the block reader in very detail but it
still seems to be necessary somehow....

I opened https://issues.apache.org/jira/browse/LUCENE-2938 for this!


>
> Regards,
> Toke Eskildsen
>
>

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


Re: Proper use of TermsEnum.seek?

Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
On Tue, 2011-02-22 at 12:19 +0100, Simon Willnauer wrote: 

[Toke: Using a partial cache of BytesRef+TermState]

> I don't know how you did implement that part but you might consider
> using something like ByteBlockPool instead of BytesRef instances to
> safe an extra amount of memory. Just as a hint you can look at
> BytesRefHash for an example.

Avoiding the overhead of representing the BytesRefs as separate Objects
seems sensible. Unfortunately this isn't possible with TermState, at
least not in general. As I focus quite a bit on memory overhead, tt
might make sense to just store the BytesRef and take the performance
penalty of seek(BytesRef) to avoid the Object-overhead of TermStats.

> I think we need to check if that BytesRef is really needed. I hope we
> can get rid of it eventually.

It does seem a bit peculiar that is is needed for a seek using a
previously delivered marker. Maybe the TermState could hold a reference
to the BytesRef itself, if it is needed by the implementation?

Regards,
Toke Eskildsen


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


Re: Proper use of TermsEnum.seek?

Posted by Simon Willnauer <si...@googlemail.com>.
On Tue, Feb 22, 2011 at 11:55 AM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> On Mon, 2011-02-21 at 16:00 +0100, Simon Willnauer wrote:
>> For all real codecs seek(BR, TermState) should be as fast as it gets.
>> There are some codecs which simply forward to seek(BR) so if you have
>> the TermState already you won't loose anything. This might also answer
>> your other question, if you pass an empty BytesRef to a codec that did
>> not override the seek(BR, TermState) method it will seek to the empty
>> term and your code might not work anymore.
>
> Thanks, that makes sense.
>
> It seems to me that I'll have to use the strategy pattern and make a
> TermsEnum-implementation-aware wrapper (or rather codec-aware?), if I
> want the "best" ordinal-seeker.
>
> Toke:
>> > I tried calling with an empty BytesRef term. This gave me an empty
>> > result back for the call itself, but the correct terms for subsequent
>> > calls to next. This works perfectly for my scenario. However, that was
>> > just an experiment using the default variable gap codec, so I am unsure
>> > if I can count on this behavior for any given codec?
>>
>> what do you mean by an empty result for the call itself?
>
> Sorry, I mixed things up. I mean I tried calling with an empty term and
> getting the term with the term()-method, which returned an empty
> BytesRef after the initial call.
Ah ok that makes sense ;) thanks for clarifying.

> Anyway, since codec are free to fall
> back to BytesRef-seek, my options are reduced to
> seek(Bytesref, TermState) with real values
> or
> seek(Bytesref) which I expect is normally log(n) or better.
Currently any of our 'real' codecs does support the fast TermState
lookup which is O(1) in those cases.

>
>> can't you us a codec that supports ord for your facet / sort fields?
>
> That was also Mike McCandless suggestion in
> https://issues.apache.org/jira/browse/LUCENE-2843
>
> I think this might be counter-productive. If a non-ordinal-supporting
> codec has significantly lower impact on memory, the extra bookkeeping
> for a BytesRef/TermState-seek-cache might be small enough so that the
> total overhead is still less than that of an ordinal-supporting codec.

I don't know how you did implement that part but you might consider
using something like ByteBlockPool instead of BytesRef instances to
safe an extra amount of memory. Just as a hint you can look at
BytesRefHash for an example.
>
> I did try a quick experiment with the variable gap vs. fixed gap codec,
> where I kept every 32nd BytesRef+TermState for the variable gap. With a
> 50M term field, this increased the overhead from 600MB to 800MB (or
> about 130 bytes for each BytesRef/TermState-pair, ignoring the
> memory-impact-difference for variable vs. fixed). This clearly does not
> support my theory. I'll have to make a proper test, but a strong
> recommendation of using ordinal-supporting codec might very well be the
> best solution.

I think we need to check if that BytesRef is really needed. I hope we
can get rid of it eventually.

simon
>
> Thanks for helping,
> Toke Eskildsen
>
>

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


Re: Proper use of TermsEnum.seek?

Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
On Mon, 2011-02-21 at 16:00 +0100, Simon Willnauer wrote:
> For all real codecs seek(BR, TermState) should be as fast as it gets.
> There are some codecs which simply forward to seek(BR) so if you have
> the TermState already you won't loose anything. This might also answer
> your other question, if you pass an empty BytesRef to a codec that did
> not override the seek(BR, TermState) method it will seek to the empty
> term and your code might not work anymore.

Thanks, that makes sense. 

It seems to me that I'll have to use the strategy pattern and make a
TermsEnum-implementation-aware wrapper (or rather codec-aware?), if I
want the "best" ordinal-seeker.

Toke:
> > I tried calling with an empty BytesRef term. This gave me an empty
> > result back for the call itself, but the correct terms for subsequent
> > calls to next. This works perfectly for my scenario. However, that was
> > just an experiment using the default variable gap codec, so I am unsure
> > if I can count on this behavior for any given codec?
> 
> what do you mean by an empty result for the call itself?

Sorry, I mixed things up. I mean I tried calling with an empty term and
getting the term with the term()-method, which returned an empty
BytesRef after the initial call. Anyway, since codec are free to fall
back to BytesRef-seek, my options are reduced to
seek(Bytesref, TermState) with real values
or
seek(Bytesref) which I expect is normally log(n) or better.

> can't you us a codec that supports ord for your facet / sort fields?

That was also Mike McCandless suggestion in
https://issues.apache.org/jira/browse/LUCENE-2843

I think this might be counter-productive. If a non-ordinal-supporting
codec has significantly lower impact on memory, the extra bookkeeping
for a BytesRef/TermState-seek-cache might be small enough so that the
total overhead is still less than that of an ordinal-supporting codec.

I did try a quick experiment with the variable gap vs. fixed gap codec,
where I kept every 32nd BytesRef+TermState for the variable gap. With a
50M term field, this increased the overhead from 600MB to 800MB (or
about 130 bytes for each BytesRef/TermState-pair, ignoring the
memory-impact-difference for variable vs. fixed). This clearly does not
support my theory. I'll have to make a proper test, but a strong
recommendation of using ordinal-supporting codec might very well be the
best solution.

Thanks for helping,
Toke Eskildsen


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


Re: Proper use of TermsEnum.seek?

Posted by Simon Willnauer <si...@googlemail.com>.
Hey Toke,

On Mon, Feb 21, 2011 at 3:27 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> My low-memory sorting/faceting-hacking requires terms to be accessed by
> ordinals. With Lucene 4.0 I cannot depend on TermsEnums supporting ord()
> and seek(long), so the code switches to a cache that keeps track of
> every X terms if they are not implemented. When the terms for an ordinal
> is requested, it jumps to the nearest previously cached term and calls
> next() from there until the ordinal matches. So far so good.
>
> Two methods for seeking terms are:
> seek(BytesRef text) and seek(BytesRef term, TermState state).
>
> The JavaDoc indicates that the seek with TermState is (potentially) the
> fastest in this scenario as implementations can seek very efficient
> using a custom TermState.

For all real codecs seek(BR, TermState) should be as fast as it gets.
There are some codecs which simply forward to seek(BR) so if you have
the TermState already you won't loose anything. This might also answer
your other question, if you pass an empty BytesRef to a codec that did
not override the seek(BR, TermState) method it will seek to the empty
term and your code might not work anymore. Historically, this was
needed for standard TermsReader to initialize the DeltaBytesReader
which is gone now. I am not sure if it is only needed for
initialization though, it seems so. I think we can now reinvestigate
if we still really need it since we now read terms in blocks.
>
> My problem is that I am going for low memory and it seems that I need to
> keep track of both BytesRef term and TermState state in order to use
> this method. This is quite a burden, memory-wise.

yeah I agree this is a problem without a solution right away.

>
> I tried calling with an empty BytesRef term. This gave me an empty
> result back for the call itself, but the correct terms for subsequent
> calls to next. This works perfectly for my scenario. However, that was
> just an experiment using the default variable gap codec, so I am unsure
> if I can count on this behavior for any given codec?

what do you mean by an empty result for the call itself?

>
> Any thoughts on how to reduce the memory needed for ordinal-based
> lookup, without killing performance, would be appreciated.

can't you us a codec that supports ord for your facet / sort fields?

simon
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>

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