code review 9118043: leveldb/db: concatenating and merging iterators.

leveldb/db: concatenating and merging iterators.

[nigeltao, 2013-05-02 12:34:38]

Hello bradfitz@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/leveldb-go

[bradfitz, 2013-05-07 20:09:30]

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db.go
File leveldb/db/db.go (right):

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db.go#newcode259
leveldb/db/db.go:259: // Find the smallest key. We could maintain a heap instead
of doing
I think the heap way is actually simpler than this.  And you ultimately do fewer
bytes.Compare operations if this is a heap.

See the latest version of the sstable merging iterator, which uses a heap
efficiently (related: https://code.google.com/p/go/issues/detail?id=5372) and
only calls & caches the sub-iterator.Key() when the subiterators are initialized
or advance.

[nigeltao, 2013-05-08 03:53:14]

PTAL.

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db.go
File leveldb/db/db.go (right):

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db.go#newcode259
leveldb/db/db.go:259: // Find the smallest key. We could maintain a heap instead
of doing
On 2013/05/07 20:09:30, bradfitz wrote:
> I think the heap way is actually simpler than this.

Well, the C++ code just does a linear scan:
https://code.google.com/p/leveldb/source/browse/table/merger.cc#139

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db_test.go
File leveldb/db/db_test.go (right):

https://codereview.appspot.com/9118043/diff/5001/leveldb/db/db_test.go#newcod...
leveldb/db/db_test.go:143: // TODO: test all sub-iterators being empty.
These TODOs are now done.

[bradfitz, 2013-05-08 04:22:03]

LGTM

https://codereview.appspot.com/9118043/diff/11001/leveldb/db/db_test.go
File leveldb/db/db_test.go (right):

https://codereview.appspot.com/9118043/diff/11001/leveldb/db/db_test.go#newco...
leveldb/db/db_test.go:117: b := bytes.NewBuffer(nil)
var b bytes.Buffer   ?

https://codereview.appspot.com/9118043/diff/11001/leveldb/db/db_test.go#newco...
leveldb/db/db_test.go:120: fmt.Fprintf(b, "<%s:%s>", iter.Key(), iter.Value())
&b

https://codereview.appspot.com/9118043/diff/11001/leveldb/db/db_test.go#newco...
leveldb/db/db_test.go:123: fmt.Fprintf(b, "err=%v", err)
&b

[nigeltao, 2013-05-08 16:29:05]

*** Submitted as
https://code.google.com/p/leveldb-go/source/detail?r=47c9ec4eeea3 ***

leveldb/db: concatenating and merging iterators.

R=bradfitz
CC=golang-dev
https://codereview.appspot.com/9118043