Behaviour difference between old and new merge iterator

[jarifibrahim]

Commit 73ea6e6 introduced a tree-based merge iterator. The existing merge iterator was a heap-based iterator.

The following test (taken from here)shows different behavior on the heap-based merge iterator and the tree-based iterator. The test returns different results on both the implementations.

func TestMergeDuplicates(t *testing.T) {
	it := newSimpleIterator([]string{"1", "1", "1"}, []string{"a1", "a3", "a7"}, false)
	it2 := newSimpleIterator([]string{"1", "1", "1"}, []string{"b2", "b3", "b5"}, false)
	it3 := newSimpleIterator([]string{"1"}, []string{"c1"}, false)
	it4 := newSimpleIterator([]string{"1", "1", "2"}, []string{"d1", "d7", "d9"}, false)
	t.Run("forward", func(t *testing.T) {
		expectedKeys := []string{"1", "2"}
		expectedVals := []string{"a1", "d9"}
		mergeIt := NewMergeIterator([]y.Iterator{it, it2, it3, it4}, false)
		mergeIt.Rewind()
		k, v := getAll(mergeIt)
		require.EqualValues(t, expectedKeys, k)
		require.EqualValues(t, expectedVals, v)
		closeAndCheck(t, mergeIt, 4)
	})

	t.Run("reverse", func(t *testing.T) {
		it.reversed = true
		it2.reversed = true
		it3.reversed = true
		it4.reversed = true
		expectedKeys := []string{"2", "1"}
		expectedVals := []string{"d9", "a7"}
		mergeIt := NewMergeIterator([]y.Iterator{it, it2, it3, it4}, true)
		mergeIt.Rewind()
		k, v := getAll(mergeIt)
		require.EqualValues(t, expectedKeys, k)
		require.EqualValues(t, expectedVals, v)
		closeAndCheck(t, mergeIt, 4)
	})
}

The heap-based approach skips all the keys which are same
https://github.com/dgraph-io/badger/blob/385da9100e3534a5f82b3c37e0990305f8008a3a/y/iterator.go#L226-L233
The result is

k = {1, 2,}

while the tree-based implementation does not skip the same keys.

k = {1, 1, 1, 2}