B+Tree indices: ongoing progress

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert Collins wrote:
| 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:

Yeah, I added that in my branch.

|
| 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

Not as much as I would have hoped for, but yes. And I've done enough
tests now that I know it is actually correct. :)

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkhr+G8ACgkQJdeBCYSNAAPM+ACgiY7qRV85815B9DXt3Dl5FYn/
RcQAniKfxXIBJOQ3zDtQcm0ws2Ru/vEk
=HlQe
-----END PGP SIGNATURE-----