Repository: genjidb/genji (go)

Issue:
query on indexed field only returns 29 records
If I run a query on an indexed field where there are 100 duplicate records in the database, I only get 29 results. For a similar field that is not indexed, a query returns the full 100 documents. Is this expected?

Source for test: https://github.com/simpleiot/simpleiot/tree/feature-genji/cmd/genji-test2

output of test:

```
2020/08/27 10:54:50 SELECT * FROM tests WHERE field1 = "test1": documents found: 29, time: 306.057µs
2020/08/27 10:54:50 SELECT * FROM tests WHERE field2 = "test1": documents found: 100, time: 618.836µs
2020/08/27 10:54:50 indexed field returned 29 records, non indexed filed returned 100 records, expected 100 records for both
2020/08/27 10:54:50 All done :-)
```

test source:

```go
package main

import (
	"log"
	"time"

	"github.com/genjidb/genji"
	"github.com/genjidb/genji/database"
	"github.com/genjidb/genji/document"
)

// Test type
type Test struct {
	Field1 string
	Field2 string
}

// returns true if db already exists
func setup(db *genji.DB) bool {
	err := db.Exec("CREATE TABLE tests;")
	if err != nil {
		if err != database.ErrTableAlreadyExists {
			log.Fatal("error creating tests: ", err)
		}
	}

	err = db.Exec("CREATE INDEX idx_tests_field1 ON tests(field1)")
	if err != nil {
		if err != database.ErrIndexAlreadyExists {
			log.Fatal("error creating index: ", err)
		}
		return true
	}

	return false
}

func populateData(db *genji.DB) {
	// insert first user, then a lot of another user
	t := Test{
		Field1: "test1",
		Field2: "test1",
	}

	count := 100
	for i := 0; i < count; i++ {
		err := db.Exec("INSERT INTO tests VALUES ?", &t)
		if err != nil {
			log.Fatal("Error inserting test: ", err)
		}
	}
}

// returns # of docs found
func query(db *genji.DB, q string) int {
	start := time.Now()

	res, err := db.Query(q)

	if err != nil {
		log.Fatal("query error: ", err)
	}

	defer res.Close()

	count := 0

	err = res.Iterate(func(d document.Document) error {
		t := Test{}
		err := document.StructScan(d, &t)
		if err != nil {
			log.Fatal("Error scanning document: ", err)
		}

		count++

		return nil
	})

	log.Printf("%v: documents found: %v, time: %v", q, count, time.Since(start))
	return count
}

func main() {
	db, err := genji.Open(":memory:")

	if err != nil {
		log.Fatal(err)
	}

	defer db.Close()

	dataExists := setup(db)

	if !dataExists {
		populateData(db)
	}

	// look for the record at the beginning of the collection
	count1 := query(db, `SELECT * FROM tests WHERE field1 = "test1"`)
	count2 := query(db, `SELECT * FROM tests WHERE field2 = "test1"`)

	if count1 != count2 {
		log.Printf("indexed field returned %v records, non indexed filed returned %v records, expected 100 records for both", count1, count2)
	}

	log.Println("All done :-)")
}

```

Pull request description:
Fix list index implementation
This PR fixes #170 by changing how list indexes are implemented. Previously, each couple _value to index / key_ was stored in a store as following:

| store key | store value |
| - | - |
| `value to index`+`separator`+`key of the associated document` | nil |

This used to be valued as some point but this now has some obvious issues as the separator can be contained in both the value to index and the key of the document, making it impossible to determine where the separator is.

The new implementation uses a new method added to the engines called `NextSequence()`, which is responsible of returning a monotonically increasing integer.
This integer will be encoded and appended to every value to index, while the document key will be stored in the value of the store:

| store key | store value |
| - | - |
| `value to index`+`integer` |`key of the associated document` |




Patch:
diff --git a/engine/badgerengine/engine.go b/engine/badgerengine/engine.go
index 4706337a..8dc141df 100644
--- a/engine/badgerengine/engine.go
+++ b/engine/badgerengine/engine.go
@@ -36,6 +36,7 @@ func (e *Engine) Begin(writable bool) (engine.Transaction, error) {
 	tx := e.DB.NewTransaction(writable)
 
 	return &Transaction{
+		ng:       e,
 		tx:       tx,
 		writable: writable,
 	}, nil
@@ -48,6 +49,7 @@ func (e *Engine) Close() error {
 
 // A Transaction uses Badger's transactions.
 type Transaction struct {
+	ng        *Engine
 	tx        *badger.Txn
 	writable  bool
 	discarded bool
@@ -110,6 +112,7 @@ func (t *Transaction) GetStore(name []byte) (engine.Store, error) {
 	pkey := buildStorePrefixKey(name)
 
 	return &Store{
+		ng:       t.ng,
 		tx:       t.tx,
 		prefix:   pkey,
 		writable: t.writable,
diff --git a/engine/badgerengine/store.go b/engine/badgerengine/store.go
index cbf57b80..5733d70f 100644
--- a/engine/badgerengine/store.go
+++ b/engine/badgerengine/store.go
@@ -10,6 +10,7 @@ import (
 
 // A Store is an implementation of the engine.Store interface.
 type Store struct {
+	ng       *Engine
 	tx       *badger.Txn
 	prefix   []byte
 	writable bool
@@ -102,6 +103,30 @@ func (s *Store) Truncate() error {
 	return nil
 }
 
+// NextSequence returns a monotonically increasing integer.
+func (s *Store) NextSequence() (uint64, error) {
+	if !s.writable {
+		return 0, engine.ErrTransactionReadOnly
+	}
+
+	// TODO: this is an ineficient way of generating sequences.
+	// use a bigger lease in the future.
+	seq, err := s.ng.DB.GetSequence([]byte(s.name), 1)
+	if err != nil {
+		return 0, err
+	}
+	defer seq.Release()
+
+	nb, err := seq.Next()
+	if err != nil {
+		return 0, err
+	}
+
+	// the first number in a Badger sequence is always zero
+	// but Genji expects the first to be 1.
+	return nb + 1, nil
+}
+
 // NewIterator uses a Badger iterator with default options.
 // Only one iterator is allowed per read-write transaction.
 func (s *Store) NewIterator(cfg engine.IteratorConfig) engine.Iterator {
diff --git a/engine/boltengine/store.go b/engine/boltengine/store.go
index 3ec0efa2..b49eddd3 100644
--- a/engine/boltengine/store.go
+++ b/engine/boltengine/store.go
@@ -62,6 +62,15 @@ func (s *Store) Truncate() error {
 	return err
 }
 
+// NextSequence returns a monotonically increasing integer.
+func (s *Store) NextSequence() (uint64, error) {
+	if !s.bucket.Writable() {
+		return 0, engine.ErrTransactionReadOnly
+	}
+
+	return s.bucket.NextSequence()
+}
+
 // NewIterator uses the bucket cursor.
 func (s *Store) NewIterator(cfg engine.IteratorConfig) engine.Iterator {
 	return &iterator{
diff --git a/engine/engine.go b/engine/engine.go
index 02b3ee7d..0f9cfb2d 100644
--- a/engine/engine.go
+++ b/engine/engine.go
@@ -67,6 +67,8 @@ type Store interface {
 	Truncate() error
 	// NewIterator creates an iterator with the given config.
 	NewIterator(IteratorConfig) Iterator
+	// NextSequence returns a monotonically increasing integer.
+	NextSequence() (uint64, error)
 }
 
 // IteratorConfig is used to configure an iterator upon creation.
diff --git a/engine/memoryengine/engine.go b/engine/memoryengine/engine.go
index cd5fc7fb..028b6d66 100644
--- a/engine/memoryengine/engine.go
+++ b/engine/memoryengine/engine.go
@@ -17,16 +17,17 @@ const btreeDegree = 12
 // Engine is a simple memory engine implementation that stores data in
 // an in-memory Btree. It allows multiple readers and one single writer.
 type Engine struct {
-	closed bool
-	stores map[string]*btree.BTree
-
-	mu sync.RWMutex
+	closed    bool
+	stores    map[string]*btree.BTree
+	sequences map[string]uint64
+	mu        sync.RWMutex
 }
 
 // NewEngine creates an in-memory engine.
 func NewEngine() *Engine {
 	return &Engine{
-		stores: make(map[string]*btree.BTree),
+		stores:    make(map[string]*btree.BTree),
+		sequences: make(map[string]uint64),
 	}
 }
 
@@ -124,7 +125,7 @@ func (tx *transaction) GetStore(name []byte) (engine.Store, error) {
 		return nil, engine.ErrStoreNotFound
 	}
 
-	return &storeTx{tx: tx, tr: tr}, nil
+	return &storeTx{tx: tx, tr: tr, name: string(name)}, nil
 }
 
 func (tx *transaction) CreateStore(name []byte) error {
diff --git a/engine/memoryengine/store.go b/engine/memoryengine/store.go
index e65fd76f..a8bb742e 100644
--- a/engine/memoryengine/store.go
+++ b/engine/memoryengine/store.go
@@ -37,8 +37,9 @@ func (i *item) Less(than btree.Item) bool {
 
 // storeTx implements an engine.Store.
 type storeTx struct {
-	tr *btree.BTree
-	tx *transaction
+	tr   *btree.BTree
+	tx   *transaction
+	name string
 }
 
 func (s *storeTx) Put(k, v []byte) error {
@@ -159,6 +160,17 @@ func (s *storeTx) Truncate() error {
 	return nil
 }
 
+// NextSequence returns a monotonically increasing integer.
+func (s *storeTx) NextSequence() (uint64, error) {
+	if !s.tx.writable {
+		return 0, engine.ErrTransactionReadOnly
+	}
+
+	s.tx.ng.sequences[s.name]++
+
+	return s.tx.ng.sequences[s.name], nil
+}
+
 func (s *storeTx) NewIterator(cfg engine.IteratorConfig) engine.Iterator {
 	return &iterator{
 		tx:      s.tx,
diff --git a/index/index.go b/index/index.go
index 37392384..ac85efb9 100644
--- a/index/index.go
+++ b/index/index.go
@@ -9,10 +9,8 @@ import (
 )
 
 const (
-	// StorePrefix is the prefix used to name the index store.
-	StorePrefix = "i" + string(separator)
-
-	separator byte = 0x1E
+	// storePrefix is the prefix used to name the index stores.
+	storePrefix = "i"
 )
 
 var valueTypes = []document.ValueType{
@@ -75,13 +73,10 @@ func NewUniqueIndex(tx engine.Transaction, idxName string) *UniqueIndex {
 func buildIndexName(name []byte, t document.ValueType) []byte {
 	var buf bytes.Buffer
 
-	// We can deterministically set the size of the buffer.
-	// The last 2 bytes are for the separator and the Type t.
-	buf.Grow(len(StorePrefix) + len(name) + 2)
+	buf.Grow(len(storePrefix) + len(name) + 1)
 
-	buf.WriteString(StorePrefix)
+	buf.WriteString(storePrefix)
 	buf.Write(name)
-	buf.WriteByte(separator)
 	buf.WriteByte(byte(t))
 
 	return buf.Bytes()
diff --git a/index/list.go b/index/list.go
index 2e32d171..8cc2b7a7 100644
--- a/index/list.go
+++ b/index/list.go
@@ -31,14 +31,14 @@ func (idx *ListIndex) Set(v document.Value, k []byte) error {
 		return err
 	}
 
-	enc := key.AppendValue(nil, v)
-
-	buf := make([]byte, 0, len(enc)+len(k)+1)
-	buf = append(buf, enc...)
-	buf = append(buf, separator)
-	buf = append(buf, k...)
+	buf := key.AppendValue(nil, v)
+	seq, err := st.NextSequence()
+	if err != nil {
+		return err
+	}
+	buf = key.AppendInt64(buf, int64(seq))
 
-	return st.Put(buf, nil)
+	return st.Put(buf, k)
 }
 
 // Delete all the references to the key from the index.
@@ -52,19 +52,35 @@ func (idx *ListIndex) Delete(v document.Value, k []byte) error {
 		}
 	}
 
-	enc := key.AppendValue(nil, v)
-
 	st, err := getOrCreateStore(idx.tx, v.Type, idx.name)
 	if err != nil {
 		return err
 	}
 
-	buf := make([]byte, 0, len(enc)+len(k)+1)
-	buf = append(buf, enc...)
-	buf = append(buf, separator)
-	buf = append(buf, k...)
+	seek := key.AppendValue(nil, v)
+
+	it := st.NewIterator(engine.IteratorConfig{})
+	defer it.Close()
+
+	var buf []byte
+	var toDelete []byte
+	for it.Seek(seek); it.Valid(); it.Next() {
+		item := it.Item()
+		buf, err = item.ValueCopy(buf)
+		if err != nil {
+			return err
+		}
+		if bytes.Equal(buf, k) {
+			toDelete = item.Key()
+			break
+		}
+	}
+
+	if toDelete != nil {
+		return st.Delete(toDelete)
+	}
 
-	return st.Delete(buf)
+	return engine.ErrKeyNotFound
 }
 
 // AscendGreaterOrEqual seeks for the pivot and then goes through all the subsequent key value pairs in increasing order and calls the given function for each pair.
@@ -134,18 +150,25 @@ func (idx *ListIndex) iterateOnStore(pivot document.Value, reverse bool, fn func
 		seek = enc
 
 		if reverse {
-			seek = append(seek, separator, 0xFF)
+			seek = append(seek, 0xFF)
 		}
 	}
 
 	it := st.NewIterator(engine.IteratorConfig{Reverse: reverse})
 	defer it.Close()
 
+	var buf []byte
 	for it.Seek(seek); it.Valid(); it.Next() {
 		item := it.Item()
-		k := item.Key()
-		idx := bytes.LastIndexByte(k, separator)
-		err = fn(k[:idx], k[idx+1:], bytes.Equal(k[:idx], enc))
+		v := item.Key()
+		idx := len(v) - 8
+
+		buf, err = item.ValueCopy(buf)
+		if err != nil {
+			return err
+		}
+
+		err = fn(v[:idx], buf, bytes.Equal(v[:idx], enc))
 		if err != nil {
 			return err
 		}
diff --git a/key/encoding.go b/key/encoding.go
index 5aeb0b98..3b193b81 100644
--- a/key/encoding.go
+++ b/key/encoding.go
@@ -16,11 +16,6 @@ import (
 	"github.com/genjidb/genji/document"
 )
 
-// EncodeString takes a string and returns its binary representation.
-func EncodeString(buf []byte, x string) {
-	copy(buf, x)
-}
-
 // AppendBool takes a bool and returns its binary representation.
 func AppendBool(buf []byte, x bool) []byte {
 	if x {


Test patch:
diff --git a/engine/enginetest/testing.go b/engine/enginetest/testing.go
index 2bcb998b..a2328358 100644
--- a/engine/enginetest/testing.go
+++ b/engine/enginetest/testing.go
@@ -37,6 +37,7 @@ func TestSuite(t *testing.T, builder Builder) {
 		{"Store/Get", TestStoreGet},
 		{"Store/Delete", TestStoreDelete},
 		{"Store/Truncate", TestStoreTruncate},
+		{"Store/NextSequence", TestStoreNextSequence},
 		{"TestQueries", TestQueries},
 		{"TestQueriesSameTransaction", TestQueriesSameTransaction},
 	}
@@ -784,6 +785,68 @@ func TestStoreTruncate(t *testing.T, builder Builder) {
 	})
 }
 
+// TestStoreNextSequence verifies NextSequence behaviour.
+func TestStoreNextSequence(t *testing.T, builder Builder) {
+	t.Run("Should fail if tx not writable", func(t *testing.T) {
+		ng, cleanup := builder()
+		defer cleanup()
+		tx, err := ng.Begin(true)
+		require.NoError(t, err)
+		err = tx.CreateStore([]byte("test"))
+		require.NoError(t, err)
+		err = tx.Commit()
+		require.NoError(t, err)
+
+		tx, err = ng.Begin(false)
+		require.NoError(t, err)
+		defer tx.Rollback()
+
+		st, err := tx.GetStore([]byte("test"))
+		require.NoError(t, err)
+
+		_, err = st.NextSequence()
+		require.Error(t, err)
+	})
+
+	t.Run("Should return the next sequence", func(t *testing.T) {
+		st, cleanup := storeBuilder(t, builder)
+		defer cleanup()
+
+		for i := uint64(1); i < 100; i++ {
+			s, err := st.NextSequence()
+			require.NoError(t, err)
+			require.Equal(t, i, s)
+		}
+	})
+
+	t.Run("Should store the last sequence", func(t *testing.T) {
+		ng, cleanup := builder()
+		defer cleanup()
+		tx, err := ng.Begin(true)
+		require.NoError(t, err)
+		err = tx.CreateStore([]byte("test"))
+		require.NoError(t, err)
+		st, err := tx.GetStore([]byte("test"))
+		require.NoError(t, err)
+
+		s1, err := st.NextSequence()
+		require.NoError(t, err)
+
+		err = tx.Commit()
+		require.NoError(t, err)
+
+		tx, err = ng.Begin(true)
+		require.NoError(t, err)
+		defer tx.Rollback()
+
+		st, err = tx.GetStore([]byte("test"))
+		require.NoError(t, err)
+		s2, err := st.NextSequence()
+		require.NoError(t, err)
+		require.Equal(t, s1+1, s2)
+	})
+}
+
 // TestQueries test simple queries against the engine.
 func TestQueries(t *testing.T, builder Builder) {
 	t.Run("SELECT", func(t *testing.T) {
diff --git a/index/index_test.go b/index/index_test.go
index 47c14549..68aeb9a5 100644
--- a/index/index_test.go
+++ b/index/index_test.go
@@ -254,6 +254,38 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 			require.Equal(t, 10, texts)
 		})
 	}
+
+	t.Run("Unique: false, Must iterate through similar values properly", func(t *testing.T) {
+		idx, cleanup := getIndex(t, false)
+		defer cleanup()
+
+		for i := int64(0); i < 100; i++ {
+			require.NoError(t, idx.Set(document.NewIntegerValue(1), key.AppendInt64(nil, i)))
+			require.NoError(t, idx.Set(document.NewTextValue("1"), key.AppendInt64(nil, i)))
+		}
+
+		var ints, texts int
+		i := int64(0)
+		err := idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(val, rid []byte, isEqual bool) error {
+			requireEqualEncoded(t, document.NewDoubleValue(1), val)
+			require.Equal(t, key.AppendInt64(nil, i), rid)
+			i++
+			ints++
+			return nil
+		})
+
+		i = 0
+		err = idx.AscendGreaterOrEqual(document.Value{Type: document.TextValue}, func(val, rid []byte, isEqual bool) error {
+			requireEqualEncoded(t, document.NewTextValue("1"), val)
+			require.Equal(t, key.AppendInt64(nil, i), rid)
+			i++
+			texts++
+			return nil
+		})
+		require.NoError(t, err)
+		require.Equal(t, 100, ints)
+		require.Equal(t, 100, texts)
+	})
 }
 
 func TestIndexDescendLessOrEqual(t *testing.T) {
diff --git a/key/encoding_test.go b/key/encoding_test.go
index c2dabac3..801a65df 100644
--- a/key/encoding_test.go
+++ b/key/encoding_test.go
@@ -3,30 +3,32 @@ package key
 import (
 	"bytes"
 	"testing"
+	"time"
 
+	"github.com/genjidb/genji/document"
 	"github.com/stretchr/testify/require"
 )
 
 func TestValueEncodeDecode(t *testing.T) {
 	tests := []struct {
-		name     string
-		expected interface{}
-		enc      func([]byte) []byte
-		dec      func([]byte) (interface{}, error)
+		name string
+		v    document.Value
 	}{
-		{"bool", true, func(buf []byte) []byte { return AppendBool(buf, true) }, func(buf []byte) (interface{}, error) { return DecodeBool(buf), nil }},
-		{"uint64", uint64(10), func(buf []byte) []byte { return AppendUint64(buf, 10) }, func(buf []byte) (interface{}, error) { return DecodeUint64(buf) }},
-		{"int64", int64(-10), func(buf []byte) []byte { return AppendInt64(buf, -10) }, func(buf []byte) (interface{}, error) { return DecodeInt64(buf) }},
-		{"float64", float64(-3.14), func(buf []byte) []byte { return AppendFloat64(buf, -3.14) }, func(buf []byte) (interface{}, error) { return DecodeFloat64(buf) }},
+		{"null", document.NewNullValue()},
+		{"bool", document.NewBoolValue(true)},
+		{"integer", document.NewIntegerValue(-10)},
+		{"double", document.NewDoubleValue(-3.14)},
+		{"text", document.NewTextValue("foo")},
+		{"blob", document.NewBlobValue([]byte("bar"))},
+		{"duration", document.NewDurationValue(10 * time.Second)},
 	}
 
 	for _, test := range tests {
-		var buf []byte
 		t.Run(test.name, func(t *testing.T) {
-			buf = test.enc(buf[:0])
-			actual, err := test.dec(buf)
+			b := AppendValue(nil, test.v)
+			got, err := DecodeValue(test.v.Type, b)
 			require.NoError(t, err)
-			require.Equal(t, test.expected, actual)
+			require.Equal(t, test.v, got)
 		})
 	}
 }