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 2010/03/19 16:06:22 UTC
Sorting with little memory: A suggestion
I've been tinkering with the SegmentReader and tried to make a sorter
that keeps track of ordinals for terms instead of the terms themselves.
I call it Exposed, as it exposes inner details.
A detailed description of the idea can be found at
http://sbdevel.wordpress.com/2010/03/19/string-sorting-in-lucene-without-the-memory-penalty/
but the important points are below.
The idea is simple enough: Make an array of ordinals for the sort-terms,
sort them with a Collator that performs a lookup of the actual Strings.
Using that array of ordinals, another array going from docID to index in
the sorted ordinals array is created.
When a sort is performed, a comparison of the entries in the
docID->sorted ordinals array is enough to determine the order.
The memory savings compared to the traditional approach of holding the
terms in memory are substantial. When the structure has been build, it
takes ~5MB to hold sorting information for 1M docs containing 1M unique
terms in the sort field, ~55MB for 10M (using the PackedInts from
LUCENE-1990).
Temporary memory use for building is around 2 * #docs * 4 bytes for
merge sort + cruft. In theory. Also in theory, this could be closer to
#docs * 4 bytes. In reality I haven't had the time to switch Integers to
ints in the sorter, so it's quite a bit more.
As all sorting is done upfront, the startup time is non-trivial.
For ~10M sort terms it takes 6 minutes on my i7-machine using a
conventional harddisk. After that, sorted searches are a factor 10
faster than sorting by String-compare for ~1M hits (top 20 displayed).
To kick things off, I've created a Lucene-fork at
http://github.com/tokee/lucene/ with the tag lucene_3_0_exposed.
It contains a proof of concept that can be used on an optimized Lucene
index. It can be tested by running
java-cp /home/te/projects/lucene/build/lucene-core-3.1-dev.jar
org.apache.lucene.index.ExposedPOC.
To me, the trade-offs seems to be
new Sort(new SortField(field, locale))
* Fast startup
* High memory consumption
* Slow sorted searches (Collator.compare)
* Instantaneous String delivery
Exposed
* Slow startup (this is per-segment, so re-open should work well)
* Low temporary and very low permanent memory consumption
* Fast sorted searches (integer compare)
* Fast String delivery (Term-lookup by ordinal)
As memory-problems with sorting is a recurring topic on the user-list,
having an easy alternative to buying more RAM would be nice. I would
like to hear if Exposed sounds like a feasible idea to the more seasoned
Lucene developers.
Regards,
Toke Eskildsen
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Robert Muir <rc...@gmail.com>.
On Fri, Mar 19, 2010 at 6:07 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> Ah... I should have seen that. I does not change the overall picture though: Althought the ICU collation keys are impressively small, they still take up nearly as much space as the original Strings when they themselves are represented as Strings. Thus the collation keys does not help memory usage (much).
>
yeah they will only hurt you in trunk, because they are not really
stored as byte[]. But if collation keys can actually be kept as just
byte[] in flex, perhaps it could be handy by allowing you to offline
the Collator stuff to index-time.
--
Robert Muir
rcmuir@gmail.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
RE: Sorting with little memory: A suggestion
Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
From: Robert Muir [rcmuir@gmail.com]:
> Right, JDK collation sucks, use the ICU for collation keys too:
> http://site.icu-project.org/charts/collation-icu4j-sun
> at 1.59 bytes/char, thats less than UTF-16
Ah... I should have seen that. I does not change the overall picture though: Althought the ICU collation keys are impressively small, they still take up nearly as much space as the original Strings when they themselves are represented as Strings. Thus the collation keys does not help memory usage (much).
When they are stored as bytes, it helps significantly, but even then there's still a huge difference between having them in-memory and using an array of positions. Even with optimal storing (the collator keys takes up exactly the number of bytes they contain), an index of 10M documents with 10M unique terms of length 20 in a sort field would use about 300MB for a given locale vs. the 10M*log2(10M)/8 = 27MB for a compressed order array.
Still, depending on how little space a byte-array will take in flex, using the indexed collator key approach might turn out to be the best choice in a lot of cases as it works really well for incremental updates.
Regards,
Toke Eskildsen
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Robert Muir <rc...@gmail.com>.
On Fri, Mar 19, 2010 at 5:42 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> I sounds like I'm missing something here... A quick check of running 20000 random Strings of 30 characters from a-zA-Z0-1 + 20 different national characters through Java's Collator returned an average collatorKey-length of 175 bytes. On http://wiki.apache.org/solr/UnicodeCollation it is stated that a standard sort is used, which - to my knowledge - loads the Strings into memory. For my quick test, this means a tripling of memory usage for the sort field when indexing collatorKeys?
>
Right, JDK collation sucks, use the ICU for collation keys too:
http://site.icu-project.org/charts/collation-icu4j-sun
at 1.59 bytes/char, thats less than UTF-16
--
Robert Muir
rcmuir@gmail.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
RE: Sorting with little memory: A suggestion
Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
From: Robert Muir [rcmuir@gmail.com]:
[Toke: Indexing collation keys only helps with the speed problem]
> I don't really understand this measurement, collation keys are
> byte[]... (although its true we don't yet encode them this way in
> flex, I think we should)
I sounds like I'm missing something here... A quick check of running 20000 random Strings of 30 characters from a-zA-Z0-1 + 20 different national characters through Java's Collator returned an average collatorKey-length of 175 bytes. On http://wiki.apache.org/solr/UnicodeCollation it is stated that a standard sort is used, which - to my knowledge - loads the Strings into memory. For my quick test, this means a tripling of memory usage for the sort field when indexing collatorKeys?
Regards,
Toke Eskildsen
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Robert Muir <rc...@gmail.com>.
On Fri, Mar 19, 2010 at 1:46 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> From: Robert Muir [rcmuir@gmail.com]:
>> Toke, only partially-on-topic here, is it possible to describe your
>> use-case a little more where its preferable to use this Locale-based
>> sort instead of indexing collation keys (e.g. you have to support so
>> many locales this would be too much indexing overhead?)
>
> My original use case was to avoid the memory overhead: Looking at our current index, we have ~7.5M documents with ~7M unique titles. They take up about 362MB as UTF-8 bytes, which translates to a neat 1GB of RAM as Java Strings. That's 1GB less heap for other stuff for us, plus a sort is fairly slow. Indexing collation keys only helps with the speed problem.
I don't really understand this measurement, collation keys are
byte[]... (although its true we don't yet encode them this way in
flex, I think we should)
--
Robert Muir
rcmuir@gmail.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Michael McCandless <lu...@mikemccandless.com>.
On Fri, Mar 19, 2010 at 12:46 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> However, it is not set in stone that we will shift to using Exposed or similar: As many others we're pursuing real-time indexing and while Exposed sits at the segment-level and thus works well for re-open, big segment changes still occur from time to time. It is hard to see a way around this, unless the initial build time can be optimized further (a co-worker gave a great suggestion today and I think I know another way to shave 30-40% of).
You should set a merged segment warmer on the IndexWriter to handle this case.
It warms the newly merged segment before committing it, without
blocking ongoing reopens of new NRT readers.
Mike
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
RE: Sorting with little memory: A suggestion
Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
From: Robert Muir [rcmuir@gmail.com]:
> Toke, only partially-on-topic here, is it possible to describe your
> use-case a little more where its preferable to use this Locale-based
> sort instead of indexing collation keys (e.g. you have to support so
> many locales this would be too much indexing overhead?)
My original use case was to avoid the memory overhead: Looking at our current index, we have ~7.5M documents with ~7M unique titles. They take up about 362MB as UTF-8 bytes, which translates to a neat 1GB of RAM as Java Strings. That's 1GB less heap for other stuff for us, plus a sort is fairly slow. Indexing collation keys only helps with the speed problem. Using Exposed, the permanent overhead would be 40MB with a temporary overhead of 60-80MB for building and with far greater sort speed.
However, it is not set in stone that we will shift to using Exposed or similar: As many others we're pursuing real-time indexing and while Exposed sits at the segment-level and thus works well for re-open, big segment changes still occur from time to time. It is hard to see a way around this, unless the initial build time can be optimized further (a co-worker gave a great suggestion today and I think I know another way to shave 30-40% of). Still, for Exposed to be the default choice, we'd need to get down to a few seconds for million-document segments.
It would be possible to generate the Exposed structure at indexing time, but since it works on the whole term array (okay, the part to sort) of the segment, a small incremental update would require rebuilding the whole structure for the changes segments. In reality it would just move the same penalty from open to index.
> For reference, I tried to give some various tricks for using the
> Collation package here (admittedly for Solr, but the same principles
> apply): http://wiki.apache.org/solr/UnicodeCollation
I can see why this will give faster sorts over just indexing the Strings at the cost of memory footprint.
> Separately, if there is some reason you really need to use the
> Locale-based runtime sort, perhaps we should rethink ways to allow the
> ICU collator to be used instead of the JDK one, somehow.
I see no reason not to support the ICU collator. As long as it can compare two Strings, I am not at all religious about which comparator to use. Currently the seatch API works both ways, providing methods both for simple Locale and for custom sorting, so I guess it would be the same for Exposed.
Regards,
Toke Eskildsen
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Robert Muir <rc...@gmail.com>.
On Fri, Mar 19, 2010 at 11:06 AM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
>
> To me, the trade-offs seems to be
>
> new Sort(new SortField(field, locale))
Toke, only partially-on-topic here, is it possible to describe your
use-case a little more where its preferable to use this Locale-based
sort instead of indexing collation keys (e.g. you have to support so
many locales this would be too much indexing overhead?)
For reference, I tried to give some various tricks for using the
Collation package here (admittedly for Solr, but the same principles
apply): http://wiki.apache.org/solr/UnicodeCollation
Separately, if there is some reason you really need to use the
Locale-based runtime sort, perhaps we should rethink ways to allow the
ICU collator to be used instead of the JDK one, somehow.
For key generation speed and indexing size its only slightly faster
for us, but for runtime comparisons, considerably more so:
http://site.icu-project.org/charts/collation-icu4j-sun
--
Robert Muir
rcmuir@gmail.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Sorting with little memory: A suggestion
Posted by Michael McCandless <lu...@mikemccandless.com>.
If you build the ords per-segment, how do you compare results across segments?
Ie, in the non-Collator case, Lucene stores ords but must also store
the actual String so that the FieldComparator is able to compare
results across segments
Mike
On Fri, Mar 19, 2010 at 10:06 AM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> I've been tinkering with the SegmentReader and tried to make a sorter
> that keeps track of ordinals for terms instead of the terms themselves.
> I call it Exposed, as it exposes inner details.
>
> A detailed description of the idea can be found at
> http://sbdevel.wordpress.com/2010/03/19/string-sorting-in-lucene-without-the-memory-penalty/
> but the important points are below.
>
>
> The idea is simple enough: Make an array of ordinals for the sort-terms,
> sort them with a Collator that performs a lookup of the actual Strings.
> Using that array of ordinals, another array going from docID to index in
> the sorted ordinals array is created.
>
> When a sort is performed, a comparison of the entries in the
> docID->sorted ordinals array is enough to determine the order.
>
> The memory savings compared to the traditional approach of holding the
> terms in memory are substantial. When the structure has been build, it
> takes ~5MB to hold sorting information for 1M docs containing 1M unique
> terms in the sort field, ~55MB for 10M (using the PackedInts from
> LUCENE-1990).
>
> Temporary memory use for building is around 2 * #docs * 4 bytes for
> merge sort + cruft. In theory. Also in theory, this could be closer to
> #docs * 4 bytes. In reality I haven't had the time to switch Integers to
> ints in the sorter, so it's quite a bit more.
>
> As all sorting is done upfront, the startup time is non-trivial.
> For ~10M sort terms it takes 6 minutes on my i7-machine using a
> conventional harddisk. After that, sorted searches are a factor 10
> faster than sorting by String-compare for ~1M hits (top 20 displayed).
>
>
> To kick things off, I've created a Lucene-fork at
> http://github.com/tokee/lucene/ with the tag lucene_3_0_exposed.
> It contains a proof of concept that can be used on an optimized Lucene
> index. It can be tested by running
> java-cp /home/te/projects/lucene/build/lucene-core-3.1-dev.jar
> org.apache.lucene.index.ExposedPOC.
>
>
> To me, the trade-offs seems to be
>
> new Sort(new SortField(field, locale))
> * Fast startup
> * High memory consumption
> * Slow sorted searches (Collator.compare)
> * Instantaneous String delivery
>
> Exposed
> * Slow startup (this is per-segment, so re-open should work well)
> * Low temporary and very low permanent memory consumption
> * Fast sorted searches (integer compare)
> * Fast String delivery (Term-lookup by ordinal)
>
>
> As memory-problems with sorting is a recurring topic on the user-list,
> having an easy alternative to buying more RAM would be nice. I would
> like to hear if Exposed sounds like a feasible idea to the more seasoned
> Lucene developers.
>
> Regards,
> Toke Eskildsen
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org