[Xapian-discuss] merge speed and multiple local DBs design

[Olly Betts]

On Tue, Oct 16, 2007 at 12:17:29PM +0200, Ron Kass wrote:
> 40G     FTS_1_part1
> 26G     FTS_1_part2
> 23G     FTS_1_part3
> 69G     FTS_1_FINAL

Did you pick a 3-way merge for a particular reason?  Is that how this
would work if you used it?

I ask because my experience is that 3-way is slower than 2-way (merging
two 15 million document databases is quicker than three 10 million,
presumably because streaming data from two places can be handled more
efficiently than from three).

> Test machine specs:
> 
> CPU: quad-core, intel Xeon
> 
> HDD: 500GB SATA2 WD
> 
> Mem: 16GB 677MHz

That seems rather unbalanced.  It has plenty of CPU grunt and lots of
memory, but no RAID system for the disk storage.  I/O is often the
limiting factor in this game.

> Speed though... the process took a bit more than 5 hours and took some 
> CPU with it. Not too much but some. But more importantly, it did take 
> some I/O.

What xapian-compact does is data between files with a very small amount
of adjustment, so it'll be I/O limited on most machines.

> In this case, DB size shrinking is not a goal. If anything, the noted 
> fact that the speed of changes to a compressed database will be slower 
> than on original uncompressed one (due to decreased reserved space for 
> updates) is considered a drawback.

I haven't experimentally verified this myself.  It was something which
Martin Porter noted in the Btrees used by Xapian's precursor (a
proprietary system called "Muscat 3.6").

The issue is that when you want to insert and there's no space in the
block when the item would go, you have to split the block, and then
rewrite the parent block to point to the new child.  If the parent block
is also full, then this will have to be split and its parent rewritten.
And so on up the tree.  After a compact, this will probably happen for
the next few insertions (unless they form a linear sequence), and will
then happen progressively less on average as more blocks end up with
some free space.

On the other hand, the fact the database is smaller means that fewer
blocks need reading to do anything, so that will counter this effect.
Also, Xapian should have a shallower tree for the same amount of data
which probably lessens the effect since there's less of a cascade effect
from having to modify blocks up to the root.

> But I assume for now that this speed 
> difference is not major (certainly not in the longer run?).

It's something I'd like to measure, but my suspicion is that it's not
a huge issue.  It's not an issue in the longer run.

> I think it is safe to assume that the time it takes to merge the 
> databases is linearly related to the size of the databases. In this case 
> 90GB for 30M docs.

It seems very likely it would be linear, or at least tending to linear
as the size increases.

> If that took 5 hours, merging 100M docs (about 300GB) will probably take 
> about 17 hours.
> 
> Which basically rules out daily merges.

Indeed.  Faster disks would help, or even reading from one disk and
writing to another, but you're going to need to speed this up a lot
if it's going to be feasible.

> Any thought/suggestions about the above?

I was talking to someone a couple of months ago who suggested that our
current default block size (8KB) is probably too small to get the best
out of modern systems.  A VM page is typically 4KB or 8KB, but a larger
size would benefit from read-ahead, and would also result in less
percentage overhead per block from both the block header and unusable
space at the end of a block (when there's not enough space for another
item).

I've not had a chance to investigate yet, but if you're looking for
things to try, it might reap rewards for little effort.  Currently any
power of 2 size between 2KB and 64KB is supported, but I doubt smaller
is worth looking at.

You can specify the size when creating a database using
Xapian::Flint::open(), except ISTR you're using Perl where that isn't
wrapped so the easiest way is probably to convert the database when it
is small (or empty) using xapian-compact's -b command-line option.

If regular merging isn't feasible, you can just search several databases
at once (see Xapian::Database::add_database()).

Cheers,
    Olly