Repository: genjidb/genji
Pull request #195 (2020-09-20 17:25:56)

Add typed indexes
This PR introduces types in indexes. A typed index only accepts one type of values, this allows for several space efficient optimizations.


Patch:
diff --git a/database/config.go b/database/config.go
index e785db7a..8e68e1ff 100644
--- a/database/config.go
+++ b/database/config.go
@@ -2,12 +2,12 @@ package database
 
 import (
 	"bytes"
+	"encoding/binary"
 	"sync"
 
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
 	"github.com/genjidb/genji/index"
-	"github.com/genjidb/genji/key"
 )
 
 const storePrefix = 't'
@@ -202,7 +202,10 @@ func (t *tableInfoStore) Insert(tx *Transaction, tableName string, info *TableIn
 		if err != nil {
 			return err
 		}
-		info.storeName = key.AppendInt64([]byte{storePrefix}, int64(seq))
+		buf := make([]byte, binary.MaxVarintLen64+1)
+		buf[0] = storePrefix
+		n := binary.PutUvarint(buf[1:], seq)
+		info.storeName = buf[:n+1]
 	}
 
 	var buf bytes.Buffer
@@ -365,6 +368,9 @@ type IndexConfig struct {
 
 	// If set to true, values will be associated with at most one key. False by default.
 	Unique bool
+
+	// If set, the index is typed and only accepts that type
+	Type document.ValueType
 }
 
 // ToDocument creates a document from an IndexConfig.
@@ -375,6 +381,9 @@ func (i *IndexConfig) ToDocument() document.Document {
 	buf.Add("index_name", document.NewTextValue(i.IndexName))
 	buf.Add("table_name", document.NewTextValue(i.TableName))
 	buf.Add("path", document.NewArrayValue(valuePathToArray(i.Path)))
+	if i.Type != 0 {
+		buf.Add("type", document.NewIntegerValue(int64(i.Type)))
+	}
 	return buf
 }
 
@@ -403,7 +412,19 @@ func (i *IndexConfig) ScanDocument(d document.Document) error {
 		return err
 	}
 	i.Path, err = arrayToValuePath(v)
-	return err
+	if err != nil {
+		return err
+	}
+
+	v, err = d.GetByField("type")
+	if err != nil && err != document.ErrFieldNotFound {
+		return err
+	}
+	if err == nil {
+		i.Type = document.ValueType(v.V.(int64))
+	}
+
+	return nil
 }
 
 // Index of a table field. Contains information about
diff --git a/database/table.go b/database/table.go
index 1edc9309..3d277831 100644
--- a/database/table.go
+++ b/database/table.go
@@ -253,7 +253,10 @@ func (t *Table) Indexes() (map[string]Index, error) {
 				return err
 			}
 
-			idx := index.NewIndex(t.tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
+			idx := index.NewIndex(t.tx.tx, opts.IndexName, index.Options{
+				Unique: opts.Unique,
+				Type:   opts.Type,
+			})
 
 			indexes[opts.Path.String()] = Index{
 				Index: idx,
diff --git a/database/transaction.go b/database/transaction.go
index 009ec9b4..a4c851cb 100644
--- a/database/transaction.go
+++ b/database/transaction.go
@@ -222,11 +222,28 @@ func (tx *Transaction) DropTable(name string) error {
 // CreateIndex creates an index with the given name.
 // If it already exists, returns ErrIndexAlreadyExists.
 func (tx *Transaction) CreateIndex(opts IndexConfig) error {
-	_, err := tx.GetTable(opts.TableName)
+	t, err := tx.GetTable(opts.TableName)
 	if err != nil {
 		return err
 	}
 
+	info, err := t.Info()
+	if err != nil {
+		return err
+	}
+
+	// if the index is created on a field on which we know the type,
+	// create a typed index.
+	for _, fc := range info.FieldConstraints {
+		if fc.Path.IsEqual(opts.Path) {
+			if fc.Type != 0 {
+				opts.Type = fc.Type
+			}
+
+			break
+		}
+	}
+
 	return tx.indexStore.Insert(opts)
 }
 
@@ -237,7 +254,10 @@ func (tx *Transaction) GetIndex(name string) (*Index, error) {
 		return nil, err
 	}
 
-	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
+	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{
+		Unique: opts.Unique,
+		Type:   opts.Type,
+	})
 
 	return &Index{
 		Index: idx,
@@ -256,7 +276,10 @@ func (tx *Transaction) DropIndex(name string) error {
 		return err
 	}
 
-	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
+	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{
+		Unique: opts.Unique,
+		Type:   opts.Type,
+	})
 
 	return idx.Truncate()
 }
@@ -285,6 +308,9 @@ func (tx *Transaction) ReIndex(indexName string) error {
 
 	return tb.Iterate(func(d document.Document) error {
 		v, err := idx.Opts.Path.GetValue(d)
+		if err == document.ErrFieldNotFound {
+			return nil
+		}
 		if err != nil {
 			return err
 		}
diff --git a/index/index.go b/index/index.go
index d64dbc63..5159764f 100644
--- a/index/index.go
+++ b/index/index.go
@@ -4,6 +4,7 @@ import (
 	"bytes"
 	"encoding/binary"
 	"errors"
+	"fmt"
 
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
@@ -35,6 +36,7 @@ var (
 // It is sorted by value following the lexicographic order.
 type Index struct {
 	Unique bool
+	Type   document.ValueType
 
 	tx        engine.Transaction
 	storeName []byte
@@ -43,6 +45,9 @@ type Index struct {
 // Options of the index.
 type Options struct {
 	Unique bool
+
+	// If specified, the indexed expects only one type.
+	Type document.ValueType
 }
 
 // NewIndex creates an index that associates a value with a list of keys.
@@ -51,6 +56,7 @@ func NewIndex(tx engine.Transaction, idxName string, opts Options) *Index {
 		tx:        tx,
 		storeName: append([]byte(storePrefix), idxName...),
 		Unique:    opts.Unique,
+		Type:      opts.Type,
 	}
 }
 
@@ -66,20 +72,28 @@ func (idx *Index) Set(v document.Value, k []byte) error {
 		return errors.New("cannot index value without a key")
 	}
 
+	if idx.Type != 0 && idx.Type != v.Type {
+		return fmt.Errorf("cannot index value of type %s in %s index", v.Type, idx.Type)
+	}
+
 	st, err := getOrCreateStore(idx.tx, idx.storeName)
 	if err != nil {
 		return nil
 	}
 
 	// encode the value we are going to use as a key
-	buf, err := key.AppendValue(nil, v)
+	buf, err := idx.encodeValue(v)
 	if err != nil {
 		return err
 	}
 
 	// lookup for an already existing value in the index.
-	// every value ends with a zero byte.
-	lookupKey := append(buf, 0)
+	var lookupKey = buf
+
+	// every value of a non-unique index ends with a byte that starts at zero.
+	if !idx.Unique {
+		lookupKey = append(lookupKey, 0)
+	}
 
 	_, err = st.Get(lookupKey)
 	switch err {
@@ -169,7 +183,7 @@ func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val
 
 	var enc []byte
 	if pivot.V != nil {
-		enc, err = key.AppendValue(nil, pivot)
+		enc, err = idx.encodeValue(pivot)
 		if err != nil {
 			return err
 		}
@@ -181,10 +195,12 @@ func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val
 
 		k := item.Key()
 
-		// the last byte of the key is the size of the varint.
+		// the last byte of the key of a non-unique index is the size of the varint.
 		// if that byte is 0, it means that key is not duplicated.
-		n := k[len(k)-1]
-		k = k[:len(k)-int(n)-1]
+		if !idx.Unique {
+			n := k[len(k)-1]
+			k = k[:len(k)-int(n)-1]
+		}
 
 		buf, err = item.ValueCopy(buf[:0])
 		if err != nil {
@@ -205,6 +221,19 @@ func (idx *Index) Truncate() error {
 	return nil
 }
 
+// encode the value we are going to use as a key
+// if the index is typed, encode the value without expecting
+// the presence of other types.
+// if not, encode so that order is preserved regardless of the type.
+func (idx *Index) encodeValue(v document.Value) (buf []byte, err error) {
+	if idx.Type != 0 {
+		buf, err = key.Append(buf, v.Type, v.V)
+	} else {
+		buf, err = key.AppendValue(buf, v)
+	}
+	return
+}
+
 func getOrCreateStore(tx engine.Transaction, name []byte) (engine.Store, error) {
 	st, err := tx.GetStore(name)
 	if err == nil {


Test patch:
diff --git a/database/config_test.go b/database/config_test.go
index b5b62705..c56ffa95 100644
--- a/database/config_test.go
+++ b/database/config_test.go
@@ -153,6 +153,7 @@ func TestIndexStore(t *testing.T) {
 			TableName: "test",
 			IndexName: "idx_test",
 			Unique:    true,
+			Type:      document.BoolValue,
 		}
 
 		err = idxs.Insert(cfg)
diff --git a/database/transaction_test.go b/database/transaction_test.go
index f3bd93ae..f4ffd5fb 100644
--- a/database/transaction_test.go
+++ b/database/transaction_test.go
@@ -262,6 +262,30 @@ func TestTxReIndex(t *testing.T) {
 		require.Equal(t, database.ErrIndexNotFound, err)
 	})
 
+	t.Run("Should not fail if field not found", func(t *testing.T) {
+		tx, cleanup := newTestDB(t)
+		defer cleanup()
+
+		err := tx.CreateTable("test", nil)
+		require.NoError(t, err)
+		tb, err := tx.GetTable("test")
+		require.NoError(t, err)
+
+		_, err = tb.Insert(document.NewFieldBuffer().
+			Add("a", document.NewIntegerValue(1)),
+		)
+		require.NoError(t, err)
+
+		err = tx.CreateIndex(database.IndexConfig{
+			IndexName: "b",
+			TableName: "test",
+			Path:      parsePath(t, "b"),
+		})
+
+		err = tx.ReIndex("b")
+		require.NoError(t, err)
+	})
+
 	t.Run("Should reindex the right index", func(t *testing.T) {
 		tx, _, cleanup := newTestTableFn(t)
 		defer cleanup()
diff --git a/index/index_test.go b/index/index_test.go
index 624ef6d3..19cfd49d 100644
--- a/index/index_test.go
+++ b/index/index_test.go
@@ -51,6 +51,16 @@ func TestIndexSet(t *testing.T) {
 		require.NoError(t, idx.Set(document.NewIntegerValue(11), []byte("key")))
 		require.Equal(t, index.ErrDuplicate, idx.Set(document.NewIntegerValue(10), []byte("key")))
 	})
+
+	t.Run("Unique: true, Type: integer Duplicate", func(t *testing.T) {
+		idx, cleanup := getIndex(t, true)
+		idx.Type = document.IntegerValue
+		defer cleanup()
+
+		require.NoError(t, idx.Set(document.NewIntegerValue(10), []byte("key")))
+		require.NoError(t, idx.Set(document.NewIntegerValue(11), []byte("key")))
+		require.Equal(t, index.ErrDuplicate, idx.Set(document.NewIntegerValue(10), []byte("key")))
+	})
 }
 
 func TestIndexDelete(t *testing.T) {
@@ -232,13 +242,9 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 				require.NoError(t, idx.Set(document.NewTextValue(strconv.Itoa(int(i+10))), []byte{'s', 'a' + byte(i)}))
 			}
 
-			err := idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
-				return nil
-			})
-
 			var ints, doubles, texts int
 			var count int
-			err = idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
+			err := idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
 				if count < 20 && count%2 == 0 {
 					requireEqualEncoded(t, document.NewIntegerValue(int64(ints)), val)
 					require.Equal(t, []byte{'i', 'a' + byte(ints)}, rid)
@@ -260,6 +266,29 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 			require.Equal(t, 10, ints)
 			require.Equal(t, 10, texts)
 		})
+
+		t.Run(text+"With no pivot and typed index, should iterate over all documents in order", func(t *testing.T) {
+			idx, cleanup := getIndex(t, unique)
+			idx.Type = document.IntegerValue
+			defer cleanup()
+
+			for i := int64(0); i < 10; i++ {
+				require.NoError(t, idx.Set(document.NewIntegerValue(i), []byte{'i', 'a' + byte(i)}))
+			}
+
+			var ints int
+			err := idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
+				enc, err := key.Append(nil, document.IntegerValue, int64(ints))
+				require.NoError(t, err)
+				require.Equal(t, enc, val)
+				require.Equal(t, []byte{'i', 'a' + byte(ints)}, rid)
+				ints++
+
+				return nil
+			})
+			require.NoError(t, err)
+			require.Equal(t, 10, ints)
+		})
 	}
 
 	t.Run("Unique: false, Must iterate through similar values properly", func(t *testing.T) {