lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless" <luc...@mikemccandless.com>
Subject RE: [jira] Updated: (LUCENE-843) improve how IndexWriter uses RAM to buffer added documents
Date Fri, 23 Mar 2007 01:21:44 GMT
Steven Parkes wrote:

>> Right I'm calling a newly created segment (ie flushed from RAM)
>> level 0 and then a level 1 segment is created when you merge 10
>> level 0 segments, level 2 is created when merge 10 level 1 segments,
>> etc.
>
> This isn't the way the current code treats things. I'm not saying
> it's the only way to look at things, just making sure I/we are clear
> on the current state. The current code effectively computes level
> as a function of size of the segment, independent of how the
> segment was created and of the size of its neighbors.

Yes the code re-computes the level of a given segment from the current
values of maxBufferedDocs & mergeFactor.  But when these values have
changed (or, segments were flushed by RAM not by maxBufferedDocs) then
the way it computes level no longer results in the logarithmic policy
that it's trying to implement, I think.

>> Backing up a bit ... I think the lowest amortized cost merge policy
>> should always try to merge roughly equal sized segments
>
> Well, logarithmic does do this, it just clumps logarithmically,
> with, in this case, the boundary condition (size of the lowest
> level) being defined by maxBufferedDocs. Do you consider 99999 and
> 10001 to be roughly equal sized?

Exactly, when logarithmic works "correctly" (you don't change
mergeFactor/maxBufferedDocs and your docs are all uniform in size), it
does achieve this "merge roughly equal size in byte" segments (yes
those two numbers are roughly equal).  Though now I have to go ponder
KS's Fibonacci series approach!.

> Of course, without deletes and not worrying about edge cases caused
> by flushes/closes, everything will be of the form
> maxBufferedDocs*mergeFactor^n. I'm curious to know if they stay that
> way: in particular what happens to the sizes of big old
> segments. Can everybody afford an optimize?

I think for high turnover content the way old segments will be mostly
deleted but at some point the merge will fully cascade (basically
an optimize) and they will be cleaned up?

> I think it'd be interesting to play with merge policies and see what
> we can do. One thing I'm interested in is tweaking the behavior on
> the big end of the scale. Exponentials get big fast and I think in
> some cases, treating the big segments differently from the smaller
> segments makes sense, for example, self-merging an old segment as
> deletes build up, or merging small subsequences of segments for a
> simlar reason. This is mostly what motivated me to work on factoring
> out the merge policy from the rest of IndexWriter. I've got
> something reasonably stable (though by no means perfect) that'll
> I'll post, hopefully later today.

Agreed!  There are lots of interesting things to explore here.

> It's really interesting to think about this. I'm not a algorithms
> expert, but I still find it interesting. It's appealing to think of
> a "best" policy but is it possible to have a best policy without
> making assumptions on the operations sequence (adds, deletes)?

I think there is no global "best"; it does depend on adds/deletes and
also what's important to you (search performance vs index
performance).

> Also, "best" has to trade off multiple constraints. You mentioned
> copying bytes as rarely as possible. But the number of segments has
> both hard and soft impacts on lookups, too, right? The hard limit is
> the number of file descriptors: every reader is opening every
> segment: that's the limiting case for file descriptors (mergers only
> need to open mergeFactor+1). The soft impact is doing the join when
> walking posting lists from each segment.

You're right, it's searching that has to open all the segments and
that's a hard limit once you start bumping up to max # descriptors and
soft, in slowing down your search.

>> Merging is costly because you read all data in then write all data
>> out, so, you want to minimize for byte of data in the index in the
>> index how many times it will be "serviced" (read in, written out) as
>> part of a merge.

> I've thought about this, as I looked through the existing merge
> code. I think you can get cases where you'll get a perfect storm of
> bad merges, copying a large segment multiple times to merge it with
> small segments.  Ick. But an edge condition? I guess the question is
> what is the expected value of the cost, i.e., the absolute cost but
> mitigated by the unlikelihood of it occurring.

Hmmm.  What cases lead to this?

>> I think instead of calling segments "level N" we should just measure
>> their net sizes and merge on that basis?

> I think this is a great candidate, given that you factor in the number
> of segments and sometimes merge just to keep the total number down.

Basically, this would keep the same logarithmic approach now, but
derive levels somehow from the net size in bytes.

>> Yes, at no time should you merge more than mergeFactor segments at
>> once.
>
> Why is this? File descriptors? Like I said before, readers are more
> an issue there, right? I don't see that there's a huge difference
> between mergeFactor and mergeFactor+1 if for other reasons, one
> might think mergeFactor+1 was better than mergeFactor for a
> particular merge.

Good point and good question.  I'm not sure.  The only thing I wonder
is whether reading from say 20 segments at once is slower (more
than 2X slower) than reading from 10?  Or it could actually be
faster (since OS/disk heads can better schedule IO access to a
larger number of spots)?  I don't know.

> Hmmm ... I guess I think of mergeFactor as more setting the size
> boundaries of segments than I do the n-way-ness of a merge, though
> the word itself lends itself to the latter interpretation.

True.  It means both!

Mike

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


Mime
View raw message