wiredtiger/wiredtiger — pull request #594 by keithbostic (2013-07-13 23:20:51+00:00)
Title: Reference on-page internal keys instead of copying them to allocated memory.

@michaelcahill, @agorrod: here are the changes for #592.

I did a couple of things differently than we discussed in the issue.

The simple change was I'm no longer Huffman encoding keys on internal pages. As mentioned in the issue, I think the argument that "instantiating the keys in allocated memory is likely to cost us more memory than Huffman encoding will buy us back", is a good one. I included overflow keys in that decision too, I'm not Huffman encoding any keys, including overflow keys. To encode overflow keys but not normal keys would have required more complexity, and I didn't think the use case was common enough to do the work.

The more complex change is I didn't allocate a separate structure that references the on-page keys. Instead, I expanded the union in the WT_REF structure to include a page offset/size pair (in the same 8B we have the WT_IKEY pointer), and I'm using a bit in the page offset to figure out if it's the WT_IKEY reference or the offset/size pair. It's a hack, but it saves us another 8B per internal-page key (in my smoke tests, I'm seeing internal pages require anywhere from 25% to 75% less memory).

There is an unused 4B in the WT_REF structure because of padding, but I'd like to leave that alone, it could be useful someday.

Anyway, if you both could take a look at 468b533 (the changes in include/btree.i and include/btmem.h are the most interesting), and let me know what you think and/or if you can think of a better flag I could use in the WT_REF structure to make this work.

As a side-effect, this makes our tree only support little-endian systems. We could obviously make it work on big-endian as well, but I didn't bother (does anybody care about PowerPC any more, and/or does anybody run bi-endian ARMs in big-endian mode?)

Finally, the changes in dc6e9f9 are to clean up our version processing: I incremented the btree minor version and dropped the previous versions off the back of the supported revisions list, this is a real format change.

Alex, would you be my reviewer? I'd also be interested in knowing if this makes the test case you found run any better?

One review request: I'm not confident in my understanding of btree/rec_merge.c, would you please carefully check my changes in there? I doubt my test runs are going through that code much, if at all.