You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Mark Harwood (JIRA)" <ji...@apache.org> on 2007/02/13 00:39:05 UTC
[jira] Created: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Factory for RangeFilters that caches sections of ranges to reduce disk reads
----------------------------------------------------------------------------
Key: LUCENE-798
URL: https://issues.apache.org/jira/browse/LUCENE-798
Project: Lucene - Java
Issue Type: New Feature
Components: Search
Reporter: Mark Harwood
RangeFilters can be cached using CachingWrapperFilter but are only re-used if a user happens to use *exactly* the same upper/lower bounds.
This class demonstrates a caching approach where *sections* of ranges are cached as bitsets and these are re-used/combined to construct large range filters if they fall within the required range. This can improve the "cache hit" ratio and avoid going to disk to read large lists of Doc ids from TermDocs.
This class needs some more work to add thread safety but I'm making it available to gather feedback on the design at this early stage before making robust.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: [jira] Created: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Posted by markharw00d <ma...@yahoo.co.uk>.
Chris Hostetter wrote:
> i haven't read the patch, but based on the jira description i don't think
> this is attempting to reuse cached info across updates -- i think it's
> just trying to address the issue of eliminating redundent TermEnum/TermDoc
> iterating for similar ranges.
>
Correct. I have conveniently ignored the issue of index updates and
concerned myself with how to best handle similar (but not exactly the
same) queries.
The logic is this:
* Certain types of field (dates/location coordinates) are commonly
accessed as a range rather than as individual terms
* Reading these ranges requires reading a lot of info off disk
* To avoid reading too much disk we cache a set doc ids (typically in a
bitset)
The options for caching these sets of doc ids are:
1) Caching sets representing a particular query - cache hits are likely
to be low because users request different ranges of values and they
would need to be exactly the same start/end range for such a scheme to work.
2) Caching sets representing uniform ranges of values e.g. years/months
- this requires knowledge of the term value format plus some ranges may
be very sparse e.g. months or years with no content - when using bitsets
for caching this is inefficient.
3) Caching sets representing non-uniform value ranges depending on index
content distribution
Option 3 is the approach I took. Initialization involves ripping
through a TermEnum counting the total number of docs the terms
represent. I then create a collection of ascending term ranges (e.g.
20010101 to 20020327, 20020328 to 20020415) which represent
equally-sized numbers of doc references and therefore a guarantee of a
reasonably non-sparse set for caching purposes.
At query time I create range filters dynamically by comparing the query
range against these partitions to see which ranges are wholly contained
- these are deemed cache hits. Each range records the number of "cache
hits" and bitsets are cached for only the top "n" ranges that seem
popular. Unpopular ranges continue to hit the disk (via
TermEnum/TermDocs) and do not cache this info. Popular ranges that have
a bitset cache "OR" their cached bitset into the final filter's bitset.
Performance seems to vary depending on the number of ranges you
configure, the number of bitsets you allow to be cached and the query
ranges in use.
Cheers
Mark
The approach I took therefore is to cache
> : Given, a sample date range:
> : 01/01/2001 to 01/01/2007
> : has a bit set associated.
> :
> : If I did a query for
> : 12/31/2000 to 01/01/2007
> :
> : the current filter code would cause a new filter to be created (which
> : is what I assume you are attempting to solve). Under you solution I
>
> i don't think it's an attempt at reducing the number of bitsets, just at
> reducing the amount of time spent computing those bitsets -- with the
> filter on "01/01/2001 to 01/01/2007" already in the cache, the filter on
> "12/31/2000 to 01/01/2007" only needs to look at the terms between
> 12/31/2000 and 01/01/2001 - and can and the result with the existing
> bitset.
>
>
> -Hoss
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
>
>
___________________________________________________________
All new Yahoo! Mail "The new Interface is stunning in its simplicity and ease of use." - PC Magazine
http://uk.docs.yahoo.com/nowyoucan.html
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: [jira] Created: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Posted by Chris Hostetter <ho...@fucit.org>.
: You are correct on that point, but it seems rather difficult for you
: to do the range caching and have it work across any document updates
: (unless a lot more notification interfaces are added to Lucene), so I
: guess I don't see the point of your caching.
i haven't read the patch, but based on the jira description i don't think
this is attempting to reuse cached info across updates -- i think it's
just trying to address the issue of eliminating redundent TermEnum/TermDoc
iterating for similar ranges.
: Given, a sample date range:
: 01/01/2001 to 01/01/2007
: has a bit set associated.
:
: If I did a query for
: 12/31/2000 to 01/01/2007
:
: the current filter code would cause a new filter to be created (which
: is what I assume you are attempting to solve). Under you solution I
i don't think it's an attempt at reducing the number of bitsets, just at
reducing the amount of time spent computing those bitsets -- with the
filter on "01/01/2001 to 01/01/2007" already in the cache, the filter on
"12/31/2000 to 01/01/2007" only needs to look at the terms between
12/31/2000 and 01/01/2001 - and can and the result with the existing
bitset.
-Hoss
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: [jira] Created: (LUCENE-798) Factory for RangeFilters that caches sections of ranges to reduce disk reads
Posted by robert engels <re...@ix.netcom.com>.
You are correct on that point, but it seems rather difficult for you
to do the range caching and have it work across any document updates
(unless a lot more notification interfaces are added to Lucene), so I
guess I don't see the point of your caching.
Given, a sample date range:
01/01/2001 to 01/01/2007
has a bit set associated.
If I did a query for
12/31/2000 to 01/01/2007
the current filter code would cause a new filter to be created (which
is what I assume you are attempting to solve). Under you solution I
would end up
with 2 filters
12/31/2000 to 01/01/2001 and 01/01/2001 to 01/01/2007
the problem is that the documents that match 12/31/2000 to 01/01/2001
could be all other index - necessitating sparse bit sets, but even
then I guess I don't see the benefit, unless you REALLY know your
dataset, and if you do you could just create all of the needed
filters ahead of time (but you would still need the code I added if
your index changes at all).
From my understanding of the Lucene design, filters are designed for
common, frequently reused queries terms. if you attempt to trun
everything into a filter I think you are going to have a hard time.
I may have a poor understanding of what you are trying to do though.
On Feb 12, 2007, at 5:59 PM, markharw00d wrote:
> Thanks for the pointer, Robert.
>
> Was that the "MultiSegmentQueryFilter enhancement for interactive
> indexes?" thread?
>
> If so, was that not a solution to caching sets in the event of
> variable index content rather than my approach which is for caching
> sets in the event of variable query ranges? Maybe a mix of the 2
> approaches is required?
>
>
> Cheers
> Mark
>
>
>
>
>
> ___________________________________________________________ All new
> Yahoo! Mail "The new Interface is stunning in its simplicity and
> ease of use." - PC Magazine http://uk.docs.yahoo.com/nowyoucan.html
>
> ---------------------------------------------------------------------
> 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
Re: [jira] Created: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Posted by markharw00d <ma...@yahoo.co.uk>.
Thanks for the pointer, Robert.
Was that the "MultiSegmentQueryFilter enhancement for interactive
indexes?" thread?
If so, was that not a solution to caching sets in the event of variable
index content rather than my approach which is for caching sets in the
event of variable query ranges? Maybe a mix of the 2 approaches is required?
Cheers
Mark
___________________________________________________________
All new Yahoo! Mail "The new Interface is stunning in its simplicity and ease of use." - PC Magazine
http://uk.docs.yahoo.com/nowyoucan.html
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: [jira] Created: (LUCENE-798) Factory for RangeFilters that caches sections of ranges to reduce disk reads
Posted by robert engels <re...@ix.netcom.com>.
FYI, I posted a fully working version of this several months ago - it
uses the natural segment boundaries to break a filter into multiple
filters for caching.
On Feb 12, 2007, at 5:39 PM, Mark Harwood (JIRA) wrote:
> Factory for RangeFilters that caches sections of ranges to reduce
> disk reads
> ----------------------------------------------------------------------
> ------
>
> Key: LUCENE-798
> URL: https://issues.apache.org/jira/browse/LUCENE-798
> Project: Lucene - Java
> Issue Type: New Feature
> Components: Search
> Reporter: Mark Harwood
>
>
> RangeFilters can be cached using CachingWrapperFilter but are only
> re-used if a user happens to use *exactly* the same upper/lower
> bounds.
>
> This class demonstrates a caching approach where *sections* of
> ranges are cached as bitsets and these are re-used/combined to
> construct large range filters if they fall within the required
> range. This can improve the "cache hit" ratio and avoid going to
> disk to read large lists of Doc ids from TermDocs.
>
> This class needs some more work to add thread safety but I'm making
> it available to gather feedback on the design at this early stage
> before making robust.
>
>
>
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
> ---------------------------------------------------------------------
> 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
[jira] Updated: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Posted by "Mark Harwood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-798?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mark Harwood updated LUCENE-798:
--------------------------------
Attachment: CachedRangesFilterFactory.java
> Factory for RangeFilters that caches sections of ranges to reduce disk reads
> ----------------------------------------------------------------------------
>
> Key: LUCENE-798
> URL: https://issues.apache.org/jira/browse/LUCENE-798
> Project: Lucene - Java
> Issue Type: New Feature
> Components: Search
> Reporter: Mark Harwood
> Attachments: CachedRangesFilterFactory.java
>
>
> RangeFilters can be cached using CachingWrapperFilter but are only re-used if a user happens to use *exactly* the same upper/lower bounds.
> This class demonstrates a caching approach where *sections* of ranges are cached as bitsets and these are re-used/combined to construct large range filters if they fall within the required range. This can improve the "cache hit" ratio and avoid going to disk to read large lists of Doc ids from TermDocs.
> This class needs some more work to add thread safety but I'm making it available to gather feedback on the design at this early stage before making robust.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-798) Factory for RangeFilters that caches
sections of ranges to reduce disk reads
Posted by "Matt Ericson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-798?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12486768 ]
Matt Ericson commented on LUCENE-798:
-------------------------------------
I am working on a patch that will use the Field cache to do range queries.
The bit sets will be proxies to the field cache. This way the data is stored in the filed cache and if you change the limits of your range it will just need a new proxy BitSet
> Factory for RangeFilters that caches sections of ranges to reduce disk reads
> ----------------------------------------------------------------------------
>
> Key: LUCENE-798
> URL: https://issues.apache.org/jira/browse/LUCENE-798
> Project: Lucene - Java
> Issue Type: New Feature
> Components: Search
> Reporter: Mark Harwood
> Attachments: CachedRangesFilterFactory.java
>
>
> RangeFilters can be cached using CachingWrapperFilter but are only re-used if a user happens to use *exactly* the same upper/lower bounds.
> This class demonstrates a caching approach where *sections* of ranges are cached as bitsets and these are re-used/combined to construct large range filters if they fall within the required range. This can improve the "cache hit" ratio and avoid going to disk to read large lists of Doc ids from TermDocs.
> This class needs some more work to add thread safety but I'm making it available to gather feedback on the design at this early stage before making robust.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org