Repository: genjidb/genji
Pull request #194 (2020-09-20 14:23:27)

Improved key encoding
This PR changes how values are encoded to keys and how indexes and primary keys use these keys.
- Doubles and integers are now encoded in a way that makes them ordered without having to convert them.
- Indexes now encode every value in the same store, instead of one store per type.
- docids now use varints
- Index implementations have been merged into a single type and the `Index` interface has been removed



Patch:
diff --git a/database/config.go b/database/config.go
index 92c71a13..e785db7a 100644
--- a/database/config.go
+++ b/database/config.go
@@ -372,8 +372,8 @@ func (i *IndexConfig) ToDocument() document.Document {
 	buf := document.NewFieldBuffer()
 
 	buf.Add("unique", document.NewBoolValue(i.Unique))
-	buf.Add("indexname", document.NewTextValue(i.IndexName))
-	buf.Add("tablename", document.NewTextValue(i.TableName))
+	buf.Add("index_name", document.NewTextValue(i.IndexName))
+	buf.Add("table_name", document.NewTextValue(i.TableName))
 	buf.Add("path", document.NewArrayValue(valuePathToArray(i.Path)))
 	return buf
 }
@@ -386,13 +386,13 @@ func (i *IndexConfig) ScanDocument(d document.Document) error {
 	}
 	i.Unique = v.V.(bool)
 
-	v, err = d.GetByField("indexname")
+	v, err = d.GetByField("index_name")
 	if err != nil {
 		return err
 	}
 	i.IndexName = string(v.V.(string))
 
-	v, err = d.GetByField("tablename")
+	v, err = d.GetByField("table_name")
 	if err != nil {
 		return err
 	}
@@ -409,7 +409,7 @@ func (i *IndexConfig) ScanDocument(d document.Document) error {
 // Index of a table field. Contains information about
 // the index configuration and provides methods to manipulate the index.
 type Index struct {
-	index.Index
+	*index.Index
 	Opts IndexConfig
 }
 
diff --git a/database/table.go b/database/table.go
index 86d86bab..1edc9309 100644
--- a/database/table.go
+++ b/database/table.go
@@ -2,6 +2,7 @@ package database
 
 import (
 	"bytes"
+	"encoding/binary"
 	"errors"
 	"fmt"
 
@@ -238,7 +239,7 @@ func (t *Table) Indexes() (map[string]Index, error) {
 
 	err = document.NewStream(&tb).
 		Filter(func(d document.Document) (bool, error) {
-			v, err := d.GetByField("tablename")
+			v, err := d.GetByField("table_name")
 			if err != nil {
 				return false, err
 			}
@@ -252,12 +253,7 @@ func (t *Table) Indexes() (map[string]Index, error) {
 				return err
 			}
 
-			var idx index.Index
-			if opts.Unique {
-				idx = index.NewUniqueIndex(t.tx.tx, opts.IndexName)
-			} else {
-				idx = index.NewListIndex(t.tx.tx, opts.IndexName)
-			}
+			idx := index.NewIndex(t.tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
 
 			indexes[opts.Path.String()] = Index{
 				Index: idx,
@@ -392,7 +388,15 @@ func (t *Table) generateKey(d document.Document) ([]byte, error) {
 			return nil, err
 		}
 
-		return key.AppendValue(nil, v), nil
+		// if a primary key type is specified,
+		// encode the key using the optimized encoding solution
+		if pk.Type != 0 {
+			return key.Append(nil, v.Type, v.V)
+		}
+
+		// it no primary key type is specified,
+		// encode keys regardless of type.
+		return key.AppendValue(nil, v)
 	}
 
 	docid, err := t.Store.NextSequence()
@@ -400,7 +404,9 @@ func (t *Table) generateKey(d document.Document) ([]byte, error) {
 		return nil, err
 	}
 
-	return key.AppendInt64(nil, int64(docid)), nil
+	buf := make([]byte, binary.MaxVarintLen64)
+	n := binary.PutUvarint(buf, docid)
+	return buf[:n], nil
 }
 
 // ValidateConstraints check the table configuration for constraints and validates the document
diff --git a/database/transaction.go b/database/transaction.go
index 32889993..009ec9b4 100644
--- a/database/transaction.go
+++ b/database/transaction.go
@@ -237,12 +237,7 @@ func (tx *Transaction) GetIndex(name string) (*Index, error) {
 		return nil, err
 	}
 
-	var idx index.Index
-	if opts.Unique {
-		idx = index.NewUniqueIndex(tx.tx, opts.IndexName)
-	} else {
-		idx = index.NewListIndex(tx.tx, opts.IndexName)
-	}
+	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
 
 	return &Index{
 		Index: idx,
@@ -261,12 +256,7 @@ func (tx *Transaction) DropIndex(name string) error {
 		return err
 	}
 
-	var idx index.Index
-	if opts.Unique {
-		idx = index.NewUniqueIndex(tx.tx, opts.IndexName)
-	} else {
-		idx = index.NewListIndex(tx.tx, opts.IndexName)
-	}
+	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{Unique: opts.Unique})
 
 	return idx.Truncate()
 }
diff --git a/document/compare.go b/document/compare.go
index c2cddd24..74972415 100644
--- a/document/compare.go
+++ b/document/compare.go
@@ -86,6 +86,10 @@ func compare(op operator, l, r Value) (bool, error) {
 	case r.Type == BlobValue && l.Type == BlobValue:
 		return compareBlobs(op, l.V.([]byte), r.V.([]byte)), nil
 
+	// compare integers together
+	case l.Type == IntegerValue && r.Type == IntegerValue:
+		return compareIntegers(op, l.V.(int64), r.V.(int64)), nil
+
 	// compare numbers together
 	case l.Type.IsNumber() && r.Type.IsNumber():
 		return compareNumbers(op, l, r)
diff --git a/index/index.go b/index/index.go
index ac85efb9..d64dbc63 100644
--- a/index/index.go
+++ b/index/index.go
@@ -2,10 +2,12 @@ package index
 
 import (
 	"bytes"
+	"encoding/binary"
 	"errors"
 
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
+	"github.com/genjidb/genji/key"
 )
 
 const (
@@ -31,60 +33,180 @@ var (
 
 // An Index associates encoded values with keys.
 // It is sorted by value following the lexicographic order.
-type Index interface {
-	// Set associates a value with a key.
-	Set(val document.Value, key []byte) error
-
-	// Delete all the references to the key from the index.
-	Delete(val document.Value, key []byte) error
-
-	// 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.
-	// If the given function returns an error, the iteration stops and returns that error.
-	// If the pivot is nil, starts from the beginning.
-	// If val is equal to the pivot, isEqual is set to true.
-	AscendGreaterOrEqual(pivot document.Value, fn func(val []byte, key []byte, isEqual bool) error) error
-
-	// DescendLessOrEqual seeks for the pivot and then goes through all the subsequent key value pairs in descreasing order and calls the given function for each pair.
-	// If the given function returns an error, the iteration stops and returns that error.
-	// If the pivot is nil, starts from the end.
-	// If val is equal to the pivot, isEqual is set to true.
-	DescendLessOrEqual(pivot document.Value, fn func(val []byte, key []byte, isEqual bool) error) error
-
-	// Truncate deletes all the index data.
-	Truncate() error
+type Index struct {
+	Unique bool
+
+	tx        engine.Transaction
+	storeName []byte
+}
+
+// Options of the index.
+type Options struct {
+	Unique bool
 }
 
-// NewListIndex creates an index that associates a value with a list of keys.
-func NewListIndex(tx engine.Transaction, idxName string) *ListIndex {
-	return &ListIndex{
-		tx:   tx,
-		name: idxName,
+// NewIndex creates an index that associates a value with a list of keys.
+func NewIndex(tx engine.Transaction, idxName string, opts Options) *Index {
+	return &Index{
+		tx:        tx,
+		storeName: append([]byte(storePrefix), idxName...),
+		Unique:    opts.Unique,
 	}
 }
 
-// NewUniqueIndex creates an index that associates a value with a exactly one key.
-func NewUniqueIndex(tx engine.Transaction, idxName string) *UniqueIndex {
-	return &UniqueIndex{
-		tx:   tx,
-		name: idxName,
+var errStop = errors.New("stop")
+
+// Set associates a value with a key. If Unique is set to false, it is
+// possible to associate multiple keys for the same value
+// but a key can be associated to only one value.
+func (idx *Index) Set(v document.Value, k []byte) error {
+	var err error
+
+	if len(k) == 0 {
+		return errors.New("cannot index value without a key")
+	}
+
+	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)
+	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)
+
+	_, err = st.Get(lookupKey)
+	switch err {
+	case nil:
+		// the value already exists
+		// if this is a unique index, return an error
+		if idx.Unique {
+			return ErrDuplicate
+		}
+
+		// the value already exists
+		// add a prefix to that value
+		seq, err := st.NextSequence()
+		if err != nil {
+			return err
+		}
+		vbuf := make([]byte, binary.MaxVarintLen64)
+		n := binary.PutUvarint(vbuf, seq)
+		buf = append(buf, vbuf[:n]...)
+		// duplicated values always end with the size of the varint
+		buf = append(buf, byte(n))
+	case engine.ErrKeyNotFound:
+		// the value doesn't exist
+		// use the lookup as value
+		buf = lookupKey
+	default:
+		return err
 	}
+
+	return st.Put(buf, k)
 }
 
-func buildIndexName(name []byte, t document.ValueType) []byte {
-	var buf bytes.Buffer
+// Delete all the references to the key from the index.
+func (idx *Index) Delete(v document.Value, k []byte) error {
+	st, err := getOrCreateStore(idx.tx, idx.storeName)
+	if err != nil {
+		return nil
+	}
+
+	var toDelete []byte
+	var buf []byte
+	err = iterate(st, v, false, func(item engine.Item) error {
+		buf, err = item.ValueCopy(buf[:0])
+		if err != nil {
+			return err
+		}
+		if bytes.Equal(buf, k) {
+			toDelete = item.Key()
+			return errStop
+		}
+
+		return nil
+	})
+	if err != errStop && err != nil {
+		return err
+	}
+
+	if toDelete != nil {
+		return st.Delete(toDelete)
+	}
 
-	buf.Grow(len(storePrefix) + len(name) + 1)
+	return engine.ErrKeyNotFound
+}
 
-	buf.WriteString(storePrefix)
-	buf.Write(name)
-	buf.WriteByte(byte(t))
+// 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.
+// If the given function returns an error, the iteration stops and returns that error.
+// If the pivot is empty, starts from the beginning.
+func (idx *Index) AscendGreaterOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
+	return idx.iterateOnStore(pivot, false, fn)
+}
 
-	return buf.Bytes()
+// DescendLessOrEqual seeks for the pivot and then goes through all the subsequent key value pairs in descreasing order and calls the given function for each pair.
+// If the given function returns an error, the iteration stops and returns that error.
+// If the pivot is empty, starts from the end.
+func (idx *Index) DescendLessOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
+	return idx.iterateOnStore(pivot, true, fn)
 }
 
-func getOrCreateStore(tx engine.Transaction, t document.ValueType, name string) (engine.Store, error) {
-	idxName := buildIndexName([]byte(name), t)
-	st, err := tx.GetStore(idxName)
+func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val, key []byte, isEqual bool) error) error {
+	st, err := idx.tx.GetStore(idx.storeName)
+	if err != nil && err != engine.ErrStoreNotFound {
+		return err
+	}
+	if st == nil {
+		return nil
+	}
+
+	var enc []byte
+	if pivot.V != nil {
+		enc, err = key.AppendValue(nil, pivot)
+		if err != nil {
+			return err
+		}
+	}
+
+	var buf []byte
+	return iterate(st, pivot, reverse, func(item engine.Item) error {
+		var err error
+
+		k := item.Key()
+
+		// the last byte of the key 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]
+
+		buf, err = item.ValueCopy(buf[:0])
+		if err != nil {
+			return err
+		}
+
+		return fn(k, buf, bytes.Equal(k, enc))
+	})
+}
+
+// Truncate deletes all the index data.
+func (idx *Index) Truncate() error {
+	err := idx.tx.DropStore(idx.storeName)
+	if err != nil && err != engine.ErrStoreNotFound {
+		return err
+	}
+
+	return nil
+}
+
+func getOrCreateStore(tx engine.Transaction, name []byte) (engine.Store, error) {
+	st, err := tx.GetStore(name)
 	if err == nil {
 		return st, nil
 	}
@@ -93,34 +215,56 @@ func getOrCreateStore(tx engine.Transaction, t document.ValueType, name string)
 		return nil, err
 	}
 
-	err = tx.CreateStore(idxName)
+	err = tx.CreateStore(name)
 	if err != nil {
 		return nil, err
 	}
 
-	return tx.GetStore(idxName)
+	return tx.GetStore(name)
 }
 
-func getStore(tx engine.Transaction, t document.ValueType, name string) (engine.Store, error) {
-	idxName := buildIndexName([]byte(name), t)
-	st, err := tx.GetStore(idxName)
-	if err == nil || err == engine.ErrStoreNotFound {
-		return st, nil
+func iterate(st engine.Store, pivot document.Value, reverse bool, fn func(item engine.Item) error) error {
+	var seek []byte
+	var err error
+
+	if pivot.V != nil {
+		seek, err = key.AppendValue(nil, pivot)
+		if err != nil {
+			return err
+		}
+
+		if reverse {
+			seek = append(seek, 0xFF)
+		}
 	}
 
-	return nil, err
-}
+	if pivot.Type == document.IntegerValue {
+		pivot.Type = document.DoubleValue
+	}
 
-func dropStore(tx engine.Transaction, t document.ValueType, name string) error {
-	idxName := buildIndexName([]byte(name), t)
-	_, err := tx.GetStore(idxName)
-	if err != nil && err != engine.ErrStoreNotFound {
-		return err
+	if pivot.Type != 0 && pivot.V == nil {
+		seek = []byte{byte(pivot.Type)}
+
+		if reverse {
+			seek = append(seek, 0xFF)
+		}
 	}
 
-	if err == engine.ErrStoreNotFound {
-		return nil
+	it := st.NewIterator(engine.IteratorConfig{Reverse: reverse})
+	defer it.Close()
+
+	for it.Seek(seek); it.Valid(); it.Next() {
+		itm := it.Item()
+
+		if pivot.Type != 0 && itm.Key()[0] != byte(pivot.Type) {
+			return nil
+		}
+
+		err := fn(itm)
+		if err != nil {
+			return err
+		}
 	}
 
-	return tx.DropStore(idxName)
+	return nil
 }
diff --git a/index/list.go b/index/list.go
deleted file mode 100644
index 8cc2b7a7..00000000
--- a/index/list.go
+++ /dev/null
@@ -1,190 +0,0 @@
-package index
-
-import (
-	"bytes"
-
-	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/engine"
-	"github.com/genjidb/genji/key"
-)
-
-// ListIndex is an implementation that associates a value with a list of keys.
-type ListIndex struct {
-	tx   engine.Transaction
-	name string
-}
-
-// Set associates a value with a key. It is possible to associate multiple keys for the same value
-// but a key can be associated to only one value.
-func (idx *ListIndex) Set(v document.Value, k []byte) error {
-	var err error
-
-	if v.Type == document.IntegerValue {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	st, err := getOrCreateStore(idx.tx, v.Type, idx.name)
-	if err != nil {
-		return err
-	}
-
-	buf := key.AppendValue(nil, v)
-	seq, err := st.NextSequence()
-	if err != nil {
-		return err
-	}
-	buf = key.AppendInt64(buf, int64(seq))
-
-	return st.Put(buf, k)
-}
-
-// Delete all the references to the key from the index.
-func (idx *ListIndex) Delete(v document.Value, k []byte) error {
-	var err error
-
-	if v.Type == document.IntegerValue {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	st, err := getOrCreateStore(idx.tx, v.Type, idx.name)
-	if err != nil {
-		return err
-	}
-
-	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 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.
-// If the given function returns an error, the iteration stops and returns that error.
-// If the pivot is nil, starts from the beginning.
-func (idx *ListIndex) AscendGreaterOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
-	// iterate over all stores in order
-	if pivot.Type == 0 {
-		for i := 0; i < len(valueTypes); i++ {
-			err := idx.iterateOnStore(document.Value{Type: valueTypes[i]}, false, fn)
-			if err != nil {
-				return err
-			}
-		}
-
-		return nil
-	}
-
-	return idx.iterateOnStore(pivot, false, fn)
-}
-
-// DescendLessOrEqual seeks for the pivot and then goes through all the subsequent key value pairs in descreasing order and calls the given function for each pair.
-// If the given function returns an error, the iteration stops and returns that error.
-// If the pivot is nil, starts from the end.
-func (idx *ListIndex) DescendLessOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
-	// iterate over all stores in order
-	if pivot.Type == 0 {
-		for i := len(valueTypes) - 1; i >= 0; i-- {
-			err := idx.iterateOnStore(document.Value{Type: valueTypes[i]}, true, fn)
-			if err != nil {
-				return err
-			}
-		}
-
-		return nil
-	}
-
-	return idx.iterateOnStore(pivot, true, fn)
-}
-
-func (idx *ListIndex) iterateOnStore(pivot document.Value, reverse bool, fn func(val, key []byte, isEqual bool) error) error {
-	var err error
-
-	if pivot.Type == document.IntegerValue {
-		if pivot.V != nil {
-			pivot, err = pivot.CastAsDouble()
-			if err != nil {
-				return err
-			}
-		} else {
-			pivot.Type = document.DoubleValue
-		}
-	}
-
-	st, err := getStore(idx.tx, pivot.Type, idx.name)
-	if err != nil {
-		return err
-	}
-	if st == nil {
-		return nil
-	}
-
-	var seek, enc []byte
-
-	if pivot.V != nil {
-		enc = key.AppendValue(nil, pivot)
-		seek = enc
-
-		if reverse {
-			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()
-		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
-		}
-	}
-
-	return nil
-}
-
-// Truncate deletes all the index data.
-func (idx *ListIndex) Truncate() error {
-	for t := document.NullValue; t <= document.BlobValue; t++ {
-		err := dropStore(idx.tx, t, idx.name)
-		if err != nil {
-			return err
-		}
-	}
-
-	return nil
-}
diff --git a/index/unique.go b/index/unique.go
deleted file mode 100644
index 93a410ee..00000000
--- a/index/unique.go
+++ /dev/null
@@ -1,172 +0,0 @@
-package index
-
-import (
-	"bytes"
-
-	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/engine"
-	"github.com/genjidb/genji/key"
-)
-
-// UniqueIndex is an implementation that associates a value with a exactly one key.
-type UniqueIndex struct {
-	tx   engine.Transaction
-	name string
-}
-
-// Set associates a value with exactly one key.
-// If the association already exists, it returns an error.
-// It stores integers as doubles.
-func (idx *UniqueIndex) Set(v document.Value, k []byte) error {
-	var err error
-
-	if v.Type == document.IntegerValue {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	st, err := getOrCreateStore(idx.tx, v.Type, idx.name)
-	if err != nil {
-		return err
-	}
-
-	enc := key.AppendValue(nil, v)
-
-	_, err = st.Get(enc)
-	if err == nil {
-		return ErrDuplicate
-	}
-	if err != engine.ErrKeyNotFound {
-		return err
-	}
-
-	return st.Put(enc, k)
-}
-
-// Delete all the references to the key from the index.
-func (idx *UniqueIndex) Delete(v document.Value, k []byte) error {
-	var err error
-
-	if v.Type == document.IntegerValue {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	st, err := getOrCreateStore(idx.tx, v.Type, idx.name)
-	if err != nil {
-		return err
-	}
-
-	enc := key.AppendValue(nil, v)
-
-	return st.Delete(enc)
-}
-
-// 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.
-// If the given function returns an error, the iteration stops and returns that error.
-// If the pivot is nil, starts from the beginning.
-func (idx *UniqueIndex) AscendGreaterOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
-	// iterate over all stores in order
-	if pivot.Type == 0 {
-		for i := 0; i < len(valueTypes); i++ {
-			err := idx.iterateOnStore(document.Value{Type: valueTypes[i]}, false, fn)
-			if err != nil {
-				return err
-			}
-		}
-
-		return nil
-	}
-
-	return idx.iterateOnStore(pivot, false, fn)
-}
-
-// DescendLessOrEqual seeks for the pivot and then goes through all the subsequent key value pairs in descreasing order and calls the given function for each pair.
-// If the given function returns an error, the iteration stops and returns that error.
-// If the pivot is nil, starts from the end.
-func (idx *UniqueIndex) DescendLessOrEqual(pivot document.Value, fn func(val, key []byte, isEqual bool) error) error {
-	// iterate over all stores in order
-	if pivot.Type == 0 {
-		for i := len(valueTypes) - 1; i >= 0; i-- {
-			err := idx.iterateOnStore(document.Value{Type: valueTypes[i]}, true, fn)
-			if err != nil {
-				return err
-			}
-		}
-
-		return nil
-	}
-
-	return idx.iterateOnStore(pivot, true, fn)
-}
-
-func (idx *UniqueIndex) iterateOnStore(pivot document.Value, reverse bool, fn func(val, key []byte, isEqual bool) error) error {
-	var err error
-
-	if pivot.Type == document.IntegerValue {
-		if pivot.V != nil {
-			pivot, err = pivot.CastAsDouble()
-			if err != nil {
-				return err
-			}
-		} else {
-			pivot.Type = document.DoubleValue
-		}
-	}
-
-	st, err := getStore(idx.tx, pivot.Type, idx.name)
-	if err != nil {
-		return err
-	}
-	if st == nil {
-		return nil
-	}
-	var v []byte
-
-	var seek, enc []byte
-
-	if pivot.V != nil {
-		enc = key.AppendValue(nil, pivot)
-		seek = enc
-
-		if reverse {
-			seek = append(seek, 0xFF)
-		}
-	}
-
-	it := st.NewIterator(engine.IteratorConfig{Reverse: reverse})
-	defer it.Close()
-
-	for it.Seek(seek); it.Valid(); it.Next() {
-		item := it.Item()
-
-		v, err = item.ValueCopy(v[:0])
-		if err != nil {
-			return err
-		}
-
-		k := item.Key()
-		err = fn(k, v, bytes.Equal(k, enc))
-		if err != nil {
-			return err
-		}
-	}
-
-	return nil
-}
-
-// Truncate deletes all the index data.
-func (idx *UniqueIndex) Truncate() error {
-	for t := document.NullValue; t <= document.BlobValue; t++ {
-		err := dropStore(idx.tx, t, idx.name)
-		if err != nil {
-			return err
-		}
-	}
-
-	return nil
-}
diff --git a/key/encoding.go b/key/encoding.go
index 3b193b81..35c4e045 100644
--- a/key/encoding.go
+++ b/key/encoding.go
@@ -8,6 +8,7 @@
 package key
 
 import (
+	"bytes"
 	"encoding/binary"
 	"errors"
 	"math"
@@ -83,31 +84,120 @@ func DecodeFloat64(buf []byte) (float64, error) {
 	return math.Float64frombits(x), nil
 }
 
+// AppendNumber takes a number value, integer or double, and encodes it in 16 bytes
+// so that encoded integers and doubles are naturally ordered.
+// Integers will fist be encoded using AppendInt64 on 8 bytes, then 8 zero-bytes will be
+// appended to them.
+// Doubles will first be converted to integer, encoded using AppendInt64,
+// then AppendFloat64 will be called with the float value.
+func AppendNumber(buf []byte, v document.Value) ([]byte, error) {
+	if !v.Type.IsNumber() {
+		return nil, errors.New("expected number type")
+	}
+
+	if v.Type == document.IntegerValue {
+		// appending 8 zero bytes so that the integer has the same size as the double
+		// but always lower for the same value.
+		return append(AppendInt64(buf, v.V.(int64)), 0, 0, 0, 0, 0, 0, 0, 0), nil
+	}
+
+	x := v.V.(float64)
+	if x > math.MaxInt64 {
+		return AppendFloat64(AppendInt64(buf, math.MaxInt64), x), nil
+	}
+	return AppendFloat64(AppendInt64(buf, int64(x)), x), nil
+}
+
 // AppendValue encodes a value as a key.
 // It only works with scalars and doesn't support documents and arrays.
-func AppendValue(buf []byte, v document.Value) []byte {
+func AppendValue(buf []byte, v document.Value) ([]byte, error) {
+	if v.Type == document.IntegerValue || v.Type == document.DoubleValue {
+		buf = append(buf, byte(document.DoubleValue))
+	} else {
+		buf = append(buf, byte(v.Type))
+	}
+
 	switch v.Type {
 	case document.BlobValue:
-		return append(buf, v.V.([]byte)...)
+		return append(buf, v.V.([]byte)...), nil
+	case document.TextValue:
+		return append(buf, v.V.(string)...), nil
+	case document.BoolValue:
+		return AppendBool(buf, v.V.(bool)), nil
+	case document.IntegerValue, document.DoubleValue:
+		return AppendNumber(buf, v)
+	case document.DurationValue:
+		return AppendInt64(buf, int64(v.V.(time.Duration))), nil
+	case document.NullValue:
+		return buf, nil
+	}
+
+	return nil, errors.New("cannot encode type " + v.Type.String() + " as key")
+}
+
+// DecodeValue takes some encoded data and decodes it to the target type t.
+func DecodeValue(data []byte) (document.Value, error) {
+	t := document.ValueType(data[0])
+	data = data[1:]
+
+	switch t {
+	case document.BlobValue:
+		return document.NewBlobValue(data), nil
+	case document.TextValue:
+		return document.NewTextValue(string(data)), nil
+	case document.BoolValue:
+		return document.NewBoolValue(DecodeBool(data)), nil
+	case document.DoubleValue:
+		if bytes.Equal(data[8:], []byte{0, 0, 0, 0, 0, 0, 0, 0}) {
+			x, err := DecodeInt64(data[:8])
+			if err != nil {
+				return document.Value{}, err
+			}
+			return document.NewIntegerValue(x), nil
+		}
+		x, err := DecodeFloat64(data[8:])
+		if err != nil {
+			return document.Value{}, err
+		}
+		return document.NewDoubleValue(x), nil
+	case document.DurationValue:
+		x, err := DecodeInt64(data)
+		if err != nil {
+			return document.Value{}, err
+		}
+		return document.NewDurationValue(time.Duration(x)), nil
+	case document.NullValue:
+		return document.NewNullValue(), nil
+	}
+
+	return document.Value{}, errors.New("unknown type")
+}
+
+// Append encodes a value of the type t as a key.
+// The encoded key doesn't include type information.
+func Append(buf []byte, t document.ValueType, v interface{}) ([]byte, error) {
+	switch t {
+	case document.BlobValue:
+		return append(buf, v.([]byte)...), nil
 	case document.TextValue:
-		return append(buf, v.V.(string)...)
+		return append(buf, v.(string)...), nil
 	case document.BoolValue:
-		return AppendBool(buf, v.V.(bool))
+		return AppendBool(buf, v.(bool)), nil
 	case document.IntegerValue:
-		return AppendInt64(buf, v.V.(int64))
+		return AppendInt64(buf, v.(int64)), nil
 	case document.DoubleValue:
-		return AppendFloat64(buf, v.V.(float64))
+		return AppendFloat64(buf, v.(float64)), nil
 	case document.DurationValue:
-		return AppendInt64(buf, int64(v.V.(time.Duration)))
+		return AppendInt64(buf, int64(v.(time.Duration))), nil
 	case document.NullValue:
-		return buf
+		return buf, nil
 	}
 
-	panic("cannot encode type " + v.Type.String() + " as key")
+	return nil, errors.New("cannot encode type " + t.String() + " as key")
 }
 
-// DecodeValue takes some encoded data and decodes it to the target type t.
-func DecodeValue(t document.ValueType, data []byte) (document.Value, error) {
+// Decode takes some encoded data and decodes it to the target type t.
+func Decode(t document.ValueType, data []byte) (document.Value, error) {
 	switch t {
 	case document.BlobValue:
 		return document.NewBlobValue(data), nil
@@ -120,6 +210,7 @@ func DecodeValue(t document.ValueType, data []byte) (document.Value, error) {
 		if err != nil {
 			return document.Value{}, err
 		}
+
 		return document.NewIntegerValue(x), nil
 	case document.DoubleValue:
 		x, err := DecodeFloat64(data)
diff --git a/sql/planner/input.go b/sql/planner/input.go
index 9c4fbe8a..542fb2cc 100644
--- a/sql/planner/input.go
+++ b/sql/planner/input.go
@@ -6,7 +6,6 @@ import (
 
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/index"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
 )
@@ -57,7 +56,7 @@ type indexInputNode struct {
 	tx               *database.Transaction
 	params           []expr.Param
 	table            *database.Table
-	index            index.Index
+	index            *database.Index
 	iop              IndexIteratorOperator
 	e                expr.Expr
 	orderByDirection scanner.Token
@@ -117,14 +116,14 @@ func (n *indexInputNode) String() string {
 // IndexIteratorOperator is an operator that can be used
 // as an input node.
 type IndexIteratorOperator interface {
-	IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error
+	IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error
 }
 
 type indexIterator struct {
 	tx               *database.Transaction
 	tb               *database.Table
 	params           []expr.Param
-	index            index.Index
+	index            *database.Index
 	iop              IndexIteratorOperator
 	e                expr.Expr
 	orderByDirection scanner.Token
diff --git a/sql/planner/optimizer.go b/sql/planner/optimizer.go
index c999c384..afcab60c 100644
--- a/sql/planner/optimizer.go
+++ b/sql/planner/optimizer.go
@@ -3,7 +3,6 @@ package planner
 import (
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/index"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
 )
@@ -321,8 +320,8 @@ func UseIndexBasedOnSelectionNodeRule(t *Tree) (*Tree, error) {
 
 		// if the candidate's related index is a unique index,
 		// select it.
-		idx := candidate.in.index.(database.Index)
-		if _, ok := idx.Index.(*index.UniqueIndex); ok {
+		idx := candidate.in.index
+		if idx.Unique {
 			selectedCandidate = &candidates[i]
 		}
 	}
@@ -399,7 +398,7 @@ func selectionNodeValidForIndex(sn *selectionNode, tableName string, indexes map
 	}
 
 	in := NewIndexInputNode(tableName, idx.Opts.IndexName, iop, e, scanner.ASC).(*indexInputNode)
-	in.index = idx
+	in.index = &idx
 
 	return in
 }
diff --git a/sql/planner/sort.go b/sql/planner/sort.go
index 47a3f0ff..7f10eacb 100644
--- a/sql/planner/sort.go
+++ b/sql/planner/sort.go
@@ -141,7 +141,10 @@ func (it *sortIterator) sortStream(st document.Stream) (heap.Interface, error) {
 
 		var value []byte
 		if v.Type != document.ArrayValue && v.Type != document.DocumentValue {
-			value = key.AppendValue(nil, v)
+			value, err = key.AppendValue(nil, v)
+			if err != nil {
+				return err
+			}
 		}
 
 		// to ensure ordering of values based on their types
diff --git a/sql/query/expr/comparison.go b/sql/query/expr/comparison.go
index eff386e7..5415d605 100644
--- a/sql/query/expr/comparison.go
+++ b/sql/query/expr/comparison.go
@@ -8,7 +8,6 @@ import (
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
-	"github.com/genjidb/genji/index"
 	"github.com/genjidb/genji/key"
 	"github.com/genjidb/genji/sql/scanner"
 )
@@ -34,7 +33,7 @@ func Eq(a, b Expr) Expr {
 
 var errStop = errors.New("errStop")
 
-func (op eqOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op eqOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	err := idx.AscendGreaterOrEqual(v, func(val, key []byte, isEqual bool) error {
 		if isEqual {
 			d, err := tb.GetDocument(key)
@@ -61,7 +60,10 @@ func (op eqOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return nil
 	}
 
-	data := key.AppendValue(nil, v)
+	data, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 
 	val, err := tb.Store.Get(data)
 	if err != nil {
@@ -100,7 +102,7 @@ func Gt(a, b Expr) Expr {
 	return gtOp{newCmpOp(a, b, scanner.GT)}
 }
 
-func (op gtOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op gtOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	err := idx.AscendGreaterOrEqual(v, func(val, key []byte, isEqual bool) error {
 		if isEqual {
 			return nil
@@ -127,7 +129,10 @@ func (op gtOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return err
 	}
 
-	data := key.AppendValue(nil, v)
+	data, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 
 	it := tb.Store.NewIterator(engine.IteratorConfig{})
 	defer it.Close()
@@ -164,7 +169,7 @@ func Gte(a, b Expr) Expr {
 	return gteOp{newCmpOp(a, b, scanner.GTE)}
 }
 
-func (op gteOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op gteOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	err := idx.AscendGreaterOrEqual(v, func(val, key []byte, isEqual bool) error {
 		d, err := tb.GetDocument(key)
 		if err != nil {
@@ -187,7 +192,10 @@ func (op gteOp) IteratePK(tb *database.Table, v document.Value, pkType document.
 		return err
 	}
 
-	data := key.AppendValue(nil, v)
+	data, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 
 	it := tb.Store.NewIterator(engine.IteratorConfig{})
 	defer it.Close()
@@ -221,7 +229,7 @@ func Lt(a, b Expr) Expr {
 	return ltOp{newCmpOp(a, b, scanner.LT)}
 }
 
-func (op ltOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op ltOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	var err error
 
 	if v.Type == document.IntegerValue {
@@ -231,7 +239,10 @@ func (op ltOp) IterateIndex(idx index.Index, tb *database.Table, v document.Valu
 		}
 	}
 
-	enc := key.AppendValue(nil, v)
+	enc, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 	err = idx.AscendGreaterOrEqual(document.Value{Type: v.Type}, func(val, key []byte, isEqual bool) error {
 		if bytes.Compare(enc, val) <= 0 {
 			return errStop
@@ -258,7 +269,10 @@ func (op ltOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return err
 	}
 
-	data := key.AppendValue(nil, v)
+	data, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 
 	it := tb.Store.NewIterator(engine.IteratorConfig{})
 	defer it.Close()
@@ -295,7 +309,7 @@ func Lte(a, b Expr) Expr {
 	return lteOp{newCmpOp(a, b, scanner.LTE)}
 }
 
-func (op lteOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op lteOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	var err error
 
 	if v.Type == document.IntegerValue {
@@ -305,7 +319,11 @@ func (op lteOp) IterateIndex(idx index.Index, tb *database.Table, v document.Val
 		}
 	}
 
-	enc := key.AppendValue(nil, v)
+	enc, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
+
 	err = idx.AscendGreaterOrEqual(document.Value{Type: v.Type}, func(val, key []byte, isEqual bool) error {
 		if bytes.Compare(enc, val) < 0 {
 			return errStop
@@ -332,7 +350,10 @@ func (op lteOp) IteratePK(tb *database.Table, v document.Value, pkType document.
 		return err
 	}
 
-	data := key.AppendValue(nil, v)
+	data, err := key.AppendValue(nil, v)
+	if err != nil {
+		return err
+	}
 
 	it := tb.Store.NewIterator(engine.IteratorConfig{})
 	defer it.Close()
@@ -464,7 +485,7 @@ func (op inOp) Eval(ctx EvalStack) (document.Value, error) {
 	return falseLitteral, nil
 }
 
-func (op inOp) IterateIndex(idx index.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
+func (op inOp) IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error {
 	if v.Type != document.ArrayValue {
 		return errors.New("IN operator takes an array")
 	}
@@ -488,7 +509,10 @@ func (op inOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 			return nil
 		}
 
-		data := key.AppendValue(nil, val)
+		data, err := key.AppendValue(nil, val)
+		if err != nil {
+			return err
+		}
 
 		v, err := tb.Store.Get(data)
 		if err != nil {
diff --git a/sql/query/expr/function.go b/sql/query/expr/function.go
index 13288b31..328574a3 100644
--- a/sql/query/expr/function.go
+++ b/sql/query/expr/function.go
@@ -1,12 +1,12 @@
 package expr
 
 import (
+	"encoding/binary"
 	"errors"
 	"fmt"
 	"strings"
 
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/key"
 )
 
 var functions = map[string]func(args ...Expr) (Expr, error){
@@ -61,7 +61,9 @@ func (k PKFunc) Eval(ctx EvalStack) (document.Value, error) {
 		return pk.Path.GetValue(ctx.Document)
 	}
 
-	return key.DecodeValue(document.IntegerValue, ctx.Document.(document.Keyer).Key())
+	i, _ := binary.Uvarint(ctx.Document.(document.Keyer).Key())
+
+	return document.NewIntegerValue(int64(i)), nil
 }
 
 // IsEqual compares this expression with the other expression and returns


Test patch:
diff --git a/database/table_test.go b/database/table_test.go
index a50f36de..9dce749e 100644
--- a/database/table_test.go
+++ b/database/table_test.go
@@ -1,6 +1,7 @@
 package database_test
 
 import (
+	"encoding/binary"
 	"errors"
 	"fmt"
 	"testing"
@@ -182,10 +183,10 @@ func TestTableInsert(t *testing.T) {
 
 		key2 := insertDoc(db)
 
-		a, err := key.DecodeUint64(key1)
+		a, _ := binary.Uvarint(key1)
 		require.NoError(t, err)
 
-		b, err := key.DecodeUint64(key2)
+		b, _ := binary.Uvarint(key2)
 		require.NoError(t, err)
 
 		require.Equal(t, a+1, b)
diff --git a/database/transaction_test.go b/database/transaction_test.go
index 27c373d7..f3bd93ae 100644
--- a/database/transaction_test.go
+++ b/database/transaction_test.go
@@ -274,7 +274,8 @@ func TestTxReIndex(t *testing.T) {
 
 		var i int
 		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc := key.AppendValue(nil, document.NewDoubleValue(float64(i)))
+			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+			require.NoError(t, err)
 			require.Equal(t, enc, v)
 			i++
 			return nil
@@ -352,7 +353,8 @@ func TestReIndexAll(t *testing.T) {
 
 		var i int
 		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc := key.AppendValue(nil, document.NewDoubleValue(float64(i)))
+			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+			require.NoError(t, err)
 			require.Equal(t, enc, v)
 			i++
 			return nil
@@ -365,7 +367,8 @@ func TestReIndexAll(t *testing.T) {
 
 		i = 0
 		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc := key.AppendValue(nil, document.NewDoubleValue(float64(i)))
+			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+			require.NoError(t, err)
 			require.Equal(t, enc, v)
 			i++
 			return nil
diff --git a/index/index_test.go b/index/index_test.go
index 68aeb9a5..624ef6d3 100644
--- a/index/index_test.go
+++ b/index/index_test.go
@@ -14,18 +14,12 @@ import (
 	"github.com/stretchr/testify/require"
 )
 
-func getIndex(t testing.TB, unique bool) (index.Index, func()) {
+func getIndex(t testing.TB, unique bool) (*index.Index, func()) {
 	ng := memoryengine.NewEngine()
 	tx, err := ng.Begin(true)
 	require.NoError(t, err)
 
-	var idx index.Index
-
-	if unique {
-		idx = index.NewUniqueIndex(tx, "foo")
-	} else {
-		idx = index.NewListIndex(tx, "foo")
-	}
+	idx := index.NewIndex(tx, "foo", index.Options{Unique: unique})
 
 	return idx, func() {
 		tx.Rollback()
@@ -36,10 +30,10 @@ func TestIndexSet(t *testing.T) {
 	for _, unique := range []bool{true, false} {
 		text := fmt.Sprintf("Unique: %v, ", unique)
 
-		t.Run(text+"Set nil key succeeds", func(t *testing.T) {
+		t.Run(text+"Set nil key falls", func(t *testing.T) {
 			idx, cleanup := getIndex(t, unique)
 			defer cleanup()
-			require.NoError(t, idx.Set(document.NewBoolValue(true), nil))
+			require.Error(t, idx.Set(document.NewBoolValue(true), nil))
 		})
 
 		t.Run(text+"Set value and key succeeds", func(t *testing.T) {
@@ -64,21 +58,21 @@ func TestIndexDelete(t *testing.T) {
 		idx, cleanup := getIndex(t, false)
 		defer cleanup()
 
-		require.NoError(t, idx.Set(document.NewIntegerValue(10), []byte("key")))
+		require.NoError(t, idx.Set(document.NewDoubleValue(10), []byte("key")))
 		require.NoError(t, idx.Set(document.NewIntegerValue(10), []byte("other-key")))
 		require.NoError(t, idx.Set(document.NewIntegerValue(11), []byte("yet-another-key")))
-		require.NoError(t, idx.Delete(document.NewIntegerValue(10), []byte("key")))
+		require.NoError(t, idx.Delete(document.NewDoubleValue(10), []byte("key")))
 
 		pivot := document.NewIntegerValue(10)
 		i := 0
 		err := idx.AscendGreaterOrEqual(pivot, func(v, k []byte, isEqual bool) error {
 			if i == 0 {
 				require.True(t, isEqual)
-				requireEqualEncoded(t, document.NewDoubleValue(10), v)
+				requireEqualEncoded(t, document.NewIntegerValue(10), v)
 				require.Equal(t, "other-key", string(k))
 			} else if i == 1 {
 				require.False(t, isEqual)
-				requireEqualEncoded(t, document.NewDoubleValue(11), v)
+				requireEqualEncoded(t, document.NewIntegerValue(11), v)
 				require.Equal(t, "yet-another-key", string(k))
 			} else {
 				return errors.New("should not reach this point")
@@ -96,20 +90,20 @@ func TestIndexDelete(t *testing.T) {
 		defer cleanup()
 
 		require.NoError(t, idx.Set(document.NewIntegerValue(10), []byte("key1")))
-		require.NoError(t, idx.Set(document.NewIntegerValue(11), []byte("key2")))
+		require.NoError(t, idx.Set(document.NewDoubleValue(11), []byte("key2")))
 		require.NoError(t, idx.Set(document.NewIntegerValue(12), []byte("key3")))
-		require.NoError(t, idx.Delete(document.NewIntegerValue(11), []byte("key2")))
+		require.NoError(t, idx.Delete(document.NewDoubleValue(11), []byte("key2")))
 
 		i := 0
 		err := idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
 			switch i {
 			case 0:
 				require.False(t, isEqual)
-				requireEqualEncoded(t, document.NewDoubleValue(10), v)
+				requireEqualEncoded(t, document.NewIntegerValue(10), v)
 				require.Equal(t, "key1", string(k))
 			case 1:
 				require.False(t, isEqual)
-				requireEqualEncoded(t, document.NewDoubleValue(12), v)
+				requireEqualEncoded(t, document.NewIntegerValue(12), v)
 				require.Equal(t, "key3", string(k))
 			default:
 				return errors.New("should not reach this point")
@@ -137,7 +131,8 @@ func TestIndexDelete(t *testing.T) {
 func requireEqualEncoded(t *testing.T, expected document.Value, actual []byte) {
 	t.Helper()
 
-	enc := key.AppendValue(nil, expected)
+	enc, err := key.AppendValue(nil, expected)
+	require.NoError(t, err)
 	require.Equal(t, enc, actual)
 }
 
@@ -166,6 +161,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 				pivot document.Value
 			}{
 				{"integers", func(i int) document.Value { return document.NewIntegerValue(int64(i)) }, document.IntegerValue, document.Value{Type: document.IntegerValue}},
+				{"doubles", func(i int) document.Value { return document.NewDoubleValue(float64(i) + float64(i)/2) }, document.DoubleValue, document.Value{Type: document.DoubleValue}},
 				{"texts", func(i int) document.Value { return document.NewTextValue(strconv.Itoa(i)) }, document.TextValue, document.Value{Type: document.TextValue}},
 			}
 
@@ -183,7 +179,9 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 					err := idx.AscendGreaterOrEqual(test.pivot, func(val, rid []byte, isEqual bool) error {
 						switch test.t {
 						case document.IntegerValue:
-							requireEqualEncoded(t, document.NewDoubleValue(float64(i)), val)
+							requireEqualEncoded(t, document.NewIntegerValue(int64(i)), val)
+						case document.DoubleValue:
+							requireEqualEncoded(t, document.NewDoubleValue(float64(i)+float64(i)/2), val)
 						case document.TextValue:
 							requireEqualEncoded(t, document.NewTextValue(strconv.Itoa(int(i))), val)
 						case document.BoolValue:
@@ -230,18 +228,27 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 
 			for i := int64(0); i < 10; i++ {
 				require.NoError(t, idx.Set(document.NewIntegerValue(i), []byte{'i', 'a' + byte(i)}))
-				require.NoError(t, idx.Set(document.NewTextValue(strconv.Itoa(int(i))), []byte{'s', 'a' + byte(i)}))
+				require.NoError(t, idx.Set(document.NewDoubleValue(float64(i)), []byte{'d', 'a' + byte(i)}))
+				require.NoError(t, idx.Set(document.NewTextValue(strconv.Itoa(int(i+10))), []byte{'s', 'a' + byte(i)}))
 			}
 
-			var ints, texts int
-			var count int
 			err := idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
-				if count < 10 {
-					requireEqualEncoded(t, document.NewDoubleValue(float64(ints)), val)
+				return nil
+			})
+
+			var ints, doubles, texts int
+			var count int
+			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)
 					ints++
+				} else if count < 20 {
+					requireEqualEncoded(t, document.NewDoubleValue(float64(doubles)), val)
+					require.Equal(t, []byte{'d', 'a' + byte(doubles)}, rid)
+					doubles++
 				} else {
-					requireEqualEncoded(t, document.NewTextValue(strconv.Itoa(int(texts))), val)
+					requireEqualEncoded(t, document.NewTextValue(strconv.Itoa(int(texts+10))), val)
 					require.Equal(t, []byte{'s', 'a' + byte(texts)}, rid)
 					texts++
 				}
@@ -249,7 +256,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 				return nil
 			})
 			require.NoError(t, err)
-			require.Equal(t, 20, count)
+			require.Equal(t, 30, count)
 			require.Equal(t, 10, ints)
 			require.Equal(t, 10, texts)
 		})
@@ -267,7 +274,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 		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)
+			requireEqualEncoded(t, document.NewIntegerValue(1), val)
 			require.Equal(t, key.AppendInt64(nil, i), rid)
 			i++
 			ints++
@@ -316,7 +323,7 @@ func TestIndexDescendLessOrEqual(t *testing.T) {
 			var i uint8 = 8
 			var count int
 			err := idx.DescendLessOrEqual(document.Value{Type: document.IntegerValue}, func(val, key []byte, isEqual bool) error {
-				requireEqualEncoded(t, document.NewDoubleValue(float64(i)), val)
+				requireEqualEncoded(t, document.NewIntegerValue(int64(i)), val)
 				require.Equal(t, []byte{'a' + i}, key)
 
 				i -= 2
@@ -367,7 +374,7 @@ func TestIndexDescendLessOrEqual(t *testing.T) {
 					require.Equal(t, []byte{'s', 'a' + byte(texts)}, rid)
 					texts--
 				} else {
-					requireEqualEncoded(t, document.NewDoubleValue(float64(ints)), val)
+					requireEqualEncoded(t, document.NewIntegerValue(int64(ints)), val)
 					require.Equal(t, []byte{'i', 'a' + byte(ints)}, rid)
 					ints--
 				}
diff --git a/key/encoding_test.go b/key/encoding_test.go
index 801a65df..1449683e 100644
--- a/key/encoding_test.go
+++ b/key/encoding_test.go
@@ -2,6 +2,8 @@ package key
 
 import (
 	"bytes"
+	"math"
+	"sort"
 	"testing"
 	"time"
 
@@ -9,7 +11,7 @@ import (
 	"github.com/stretchr/testify/require"
 )
 
-func TestValueEncodeDecode(t *testing.T) {
+func TestAppendValueDecodeValue(t *testing.T) {
 	tests := []struct {
 		name string
 		v    document.Value
@@ -25,8 +27,36 @@ func TestValueEncodeDecode(t *testing.T) {
 
 	for _, test := range tests {
 		t.Run(test.name, func(t *testing.T) {
-			b := AppendValue(nil, test.v)
-			got, err := DecodeValue(test.v.Type, b)
+			b, err := Append(nil, test.v.Type, test.v.V)
+			require.NoError(t, err)
+
+			got, err := Decode(test.v.Type, b)
+			require.NoError(t, err)
+			require.Equal(t, test.v, got)
+		})
+	}
+}
+
+func TestAppendDecode(t *testing.T) {
+	tests := []struct {
+		name string
+		v    document.Value
+	}{
+		{"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 {
+		t.Run(test.name, func(t *testing.T) {
+			b, err := AppendValue(nil, test.v)
+			require.NoError(t, err)
+
+			got, err := DecodeValue(b)
 			require.NoError(t, err)
 			require.Equal(t, test.v, got)
 		})
@@ -61,4 +91,52 @@ func TestOrdering(t *testing.T) {
 			}
 		})
 	}
+
+	t.Run("Ordered ints and floats", func(t *testing.T) {
+		ints := []int64{
+			40, 7000, math.MaxInt64 - 1, math.MaxInt64,
+		}
+		floats := []float64{
+			-1000.4, 40, 7000.3, math.MaxFloat64 - 1, math.MaxFloat64,
+		}
+
+		var encoded [][]byte
+		for _, nb := range ints {
+			encoded = append(encoded, AppendInt64(nil, nb))
+		}
+		for _, nb := range floats {
+			enc, err := AppendNumber(nil, document.NewDoubleValue(nb))
+			require.NoError(t, err)
+			encoded = append(encoded, enc)
+		}
+
+		sort.Slice(encoded, func(i, j int) bool {
+			return bytes.Compare(encoded[i], encoded[j]) < 0
+		})
+
+		want := []interface{}{
+			-1000.4,
+			int64(40),
+			float64(40),
+			int64(7000),
+			7000.3,
+			int64(math.MaxInt64 - 1),
+			int64(math.MaxInt64),
+			math.MaxFloat64 - 1,
+			math.MaxFloat64,
+		}
+
+		var err error
+		var x interface{}
+
+		for i, enc := range encoded {
+			if len(enc) == 16 {
+				x, err = DecodeFloat64(enc[8:])
+			} else {
+				x, err = DecodeInt64(enc)
+			}
+			require.NoError(t, err)
+			require.Equal(t, want[i], x)
+		}
+	})
 }