FAQ
Why not just write the first byte as 0 for a bitsit, and 1 for a
sparse bit set (compressed), and make the determination when writing
based on the segment size and/or number of set bits.
On Jan 7, 2009, at 8:38 PM, Marvin Humphrey (JIRA) wrote:


[ https://issues.apache.org/jira/browse/LUCENE-1476?
page=com.atlassian.jira.plugin.system.issuetabpanels:comment-
tabpanel&focusedCommentId=12661829#action_12661829 ]

Marvin Humphrey commented on LUCENE-1476:
-----------------------------------------

Jason Rutherglen:
For realtime search where a new transaction may only have a
handful of
deletes the tombstones may not be optimal
The whole tombstone idea arose out of the need for (close to)
realtime search! It's intended to improve write speed.

When you make deletes with the BitSet model, you have to rewrite
files that scale with segment size, regardless of how few deletions
you make. Deletion of a single document in a large segment may
necessitate writing out a substantial bit vector file.

In contrast, i/o throughput for writing out a tombstone file scales
with the number of tombstones.
because too many tombstones would accumulate (I believe).
Say that you make a string of commits that are nothing but deleting
a single document -- thus adding a new segment each time that
contains nothing but a single tombstone. Those are going to be
cheap to merge, so it seems unlikely that we'll end up with an
unwieldy number of tombstone streams to interleave at search-time.

The more likely problem is the one McCandless articulated regarding
a large segment accumulating a lot of tombstone streams against
it. But I agree with him that it only gets truly serious if your
merge policy neglects such segments and allows them to deteriorate
for too long.
For this scenario rolling bitsets may be better. Meaning pool bit
sets and
throw away unused readers.
I don't think I understand. Is this the "combination index reader/
writer" model, where the writer prepares a data structure that then
gets handed off to the reader?
BitVector implement DocIdSet
----------------------------

Key: LUCENE-1476
URL: https://issues.apache.org/jira/browse/
LUCENE-1476
Project: Lucene - Java
Issue Type: Improvement
Components: Index
Affects Versions: 2.4
Reporter: Jason Rutherglen
Priority: Trivial
Attachments: LUCENE-1476.patch

Original Estimate: 12h
Remaining Estimate: 12h

BitVector can implement DocIdSet. This is for making
SegmentReader.deletedDocs pluggable.
--
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

Search Discussions

  • Marvin Humphrey at Jan 8, 2009 at 4:29 am

    On Wed, Jan 07, 2009 at 09:28:40PM -0600, robert engels wrote:
    Why not just write the first byte as 0 for a bitsit, and 1 for a
    sparse bit set (compressed), and make the determination when writing
    based on the segment size and/or number of set bits.
    Are you offering that as a solution to the problem I described here?
    When you make deletes with the BitSet model, you have to rewrite
    files that scale with segment size, regardless of how few deletions
    you make. Deletion of a single document in a large segment may
    necessitate writing out a substantial bit vector file.

    In contrast, i/o throughput for writing out a tombstone file scales
    with the number of tombstones.
    Worst-case i/o costs don't improve under such a regime. You could still end
    up writing a large, uncompressed bit vector file to accommodate a single
    deletion.

    I suppose that has to be weighed against the search-time costs of interleaving
    the tombstone streams. We can either pay the interleaving penalty at
    index-time or search-time. It's annoying to write out a 1 MB uncompressed bit
    vector file for a single deleted doc against an 8-million doc segment, but if
    there are enough deletions to justify an uncompressed file, iterating through
    them via merged-on-the-fly tombstone streams would be annoying too.

    Marvin Humphrey


    ---------------------------------------------------------------------
    To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
    For additional commands, e-mail: java-dev-help@lucene.apache.org
  • Robert engels at Jan 8, 2009 at 4:36 am
    Yes, and I don't think the "worst-case" is correct.

    When you go to write that segment, you determine that it is a "large"
    segment, but has few deletions (one in this case), it will be written
    compressed in probably less than 10 bytes (1 byte header, vlong
    start, vint length - you only write the ones...)...

    You would not write the file as uncompressed in this case. The only
    time you would write a uncompressed bitset is when you determine it
    is large with many deletions, or it is very small (more efficient to
    just write the bytes quickly). The very small case should probably
    be less than the size "standard" disk block (which is probably 32k
    these days, meaning 256k documents).
    On Jan 7, 2009, at 10:28 PM, Marvin Humphrey wrote:
    On Wed, Jan 07, 2009 at 09:28:40PM -0600, robert engels wrote:
    Why not just write the first byte as 0 for a bitsit, and 1 for a
    sparse bit set (compressed), and make the determination when writing
    based on the segment size and/or number of set bits.
    Are you offering that as a solution to the problem I described here?
    When you make deletes with the BitSet model, you have to rewrite
    files that scale with segment size, regardless of how few deletions
    you make. Deletion of a single document in a large segment may
    necessitate writing out a substantial bit vector file.

    In contrast, i/o throughput for writing out a tombstone file scales
    with the number of tombstones.
    Worst-case i/o costs don't improve under such a regime. You could
    still end
    up writing a large, uncompressed bit vector file to accommodate a
    single
    deletion.

    I suppose that has to be weighed against the search-time costs of
    interleaving
    the tombstone streams. We can either pay the interleaving penalty at
    index-time or search-time. It's annoying to write out a 1 MB
    uncompressed bit
    vector file for a single deleted doc against an 8-million doc
    segment, but if
    there are enough deletions to justify an uncompressed file,
    iterating through
    them via merged-on-the-fly tombstone streams would be annoying too.

    Marvin Humphrey


    ---------------------------------------------------------------------
    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
  • Marvin Humphrey at Jan 8, 2009 at 6:04 am

    On Wed, Jan 07, 2009 at 10:36:01PM -0600, robert engels wrote:
    Yes, and I don't think the "worst-case" is correct.

    When you go to write that segment, you determine that it is a "large"
    segment, but has few deletions (one in this case), it will be written
    compressed in probably less than 10 bytes (1 byte header, vlong
    start, vint length - you only write the ones...)...
    If a segment slowly accumulates deletions over time during different indexing
    sessions, at some point you will cross the threshold where the deletions file
    needs to be written out as an uncompressed bit vector. From then on, adding a
    single additional deletion to the segment during any subsequent indexing
    session triggers what I'm calling "worst-case" behavior: the whole bit vector
    file needs to be rewritten for the sake of a one deletion.

    Marvin Humphrey

    ---------------------------------------------------------------------
    To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
    For additional commands, e-mail: java-dev-help@lucene.apache.org
  • Robert engels at Jan 8, 2009 at 6:18 am
    Then why not always write segment.delXXXX, where XXXX is
    incremented. Each file may be compressed or uncompressed based on
    the number of deletions it contains.

    It should not matter in high performance "server mode" cases, since
    the deletion data for the segment should be in memory anyway, so no
    need to read all of the files (during merging). They are only there
    for crash recovery situations.

    If you are using lucene in the "shared networking" mode, then
    performance is probably not a huge concern anyway, so reading the
    multiple files when opening the segment is the penalty.

    Or the policy can be pluggable and the "shared" can use the old
    bitset method.
    On Jan 8, 2009, at 12:04 AM, Marvin Humphrey wrote:
    On Wed, Jan 07, 2009 at 10:36:01PM -0600, robert engels wrote:
    Yes, and I don't think the "worst-case" is correct.

    When you go to write that segment, you determine that it is a "large"
    segment, but has few deletions (one in this case), it will be written
    compressed in probably less than 10 bytes (1 byte header, vlong
    start, vint length - you only write the ones...)...
    If a segment slowly accumulates deletions over time during
    different indexing
    sessions, at some point you will cross the threshold where the
    deletions file
    needs to be written out as an uncompressed bit vector. From then
    on, adding a
    single additional deletion to the segment during any subsequent
    indexing
    session triggers what I'm calling "worst-case" behavior: the whole
    bit vector
    file needs to be rewritten for the sake of a one deletion.

    Marvin Humphrey

    ---------------------------------------------------------------------
    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
  • Michael McCandless at Jan 8, 2009 at 10:35 am

    robert engels wrote:

    Then why not always write segment.delXXXX, where XXXX is incremented.
    This is what Lucene does today. It's "write once".
    Each file may be compressed or uncompressed based on the number of
    deletions it contains.
    Lucene also does this.

    Still, as Marvin pointed out, the cost of committing a delete is in
    proportion to either the number of deletes already on the segment (if
    written sparse) or the number of documents in the segment (if written
    non-sparse). It doesn't scale well... though the constant factor may
    be very small (ie may not matter that much in practice?). With
    tombstones the commit cost would be in proportion to how many deletes
    you did (scales perfectly), at the expense of added per-search cost
    and search iterator state.

    For realtime search this could be a good tradeoff to make (lower
    latency on add/delete -> refreshed searcher, at higher per-search
    cost), but... in the realtime search discussion we are now thinking
    that the deletes live with the reader and are carried in RAM over to
    the reopened reader (LUCENE-1314), bypassing having to commit to the
    filesystem at all.

    One downside to this is it's single-JRE only, ie to do distributed
    realtime search you'd have to also re-apply the deletes to the head
    IndexReader on each JRE. (Whereas added docs would be written with a
    single IndexWriter, and propagated via the filesystem ).

    If we go forward with this model then indeed slowish commit times for
    new deletes are less important since it's for crash recovery and not
    for opening a new reader.

    But we'd have many "control" issues to work through... eg how the
    reader can re-open against old segments right after a new merge is
    committed (because the newly merged segment isn't warmed yet), and,
    how IndexReader can open segments written by the writer but not truly
    committed (sync'd).

    Mike

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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupdev @
categorieslucene
postedJan 8, '09 at 3:28a
activeJan 8, '09 at 10:35a
posts6
users3
websitelucene.apache.org

People

Translate

site design / logo © 2021 Grokbase