B+Tree indices: ongoing progress

[Robert Collins]

On Wed, 2008-07-02 at 10:57 -0500, John Arbash Meinel wrote:

Good catch on the bloom creation at new horizontal nodes. I think this
is what you meant?:

@@ -174,6 +174,8 @@
                             internal_row.writer.write(_INTERNAL_FLAG)
                             internal_row.writer.write(_INTERNAL_OFFSET+
                                 str(self.rows[pos + 1].nodes) + "\n")
+                            # new bloom for the new node
+                            internal_row.bloom = BloomSHA1(256 * 8)
                     # add a new leaf
                     length = _PAGE_SIZE
                     if self.rows[-1].nodes == 0:

Before this bugfix:
robertc at lifeless-64:/tmp$ bzr  indexbench ~/source/baz --no-graph
--drop-cache
Baseline overhead: Read 92994 keys in 11.185
BTreeIndex: Wrote 4108432 bytes in 27.501
BTreeIndex: iter_all_entries in 3.295
BTreeIndex: iter_random_one in 127.231
BTreeIndex: get_components_positions(2000) in 63.741, bloom(139980)
BTreeIndex: search_from_revid in 7.066, bloom(32233)
BTreeIndex: miss torture in 49.830, bloom(413765)

and after:
robertc at lifeless-64:/tmp$ bzr  indexbench ~/source/baz --no-graph
--drop-cache
Baseline overhead: Read 92994 keys in 11.837
BTreeIndex: Wrote 4108432 bytes in 26.720
BTreeIndex: iter_all_entries in 2.844
BTreeIndex: iter_random_one in 120.613
BTreeIndex: get_components_positions(2000) in 59.603, bloom(148027)
BTreeIndex: search_from_revid in 6.906, bloom(32233)
BTreeIndex: miss torture in 48.210, bloom(413775)
BTreeIndex: -------Done---------

So - higher hit rates on the blooms.

-Rob
-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080703/875c19ca/attachment.pgp