Repository: genjidb/genji
Pull request #312 (2020-11-09 19:33:05)

Rework type system
This PR makes an important change in Genji's type system and indexes.

### Background

Currently, Genji parses integers and doubles based on their literal representations:

```sql
1 -- integer
2.0 -- double

INSERT INTO foo (a) VALUES 
(1), -- integer
(1.2), -- double
(1.3); -- double
```

This means that the same table can have both integers and doubles depending on how values have been parsed.
Initially, comparison operators were very strict: only values of the same type can be compared together.
However, this led to situations like this:

```sql
SELECT * FROM foo WHERE a > 0;
{
  "a": 1
}
```

Because `0` is parsed as an integer, it was only compared to integers, skipping double values.

We then changed the behavior of comparison operators to support an edge case: If we compare integers and doubles, convert the integer to a double prior comparison.
Since comparison operators are also used for ordering, we expect the following behavior:

```sql
SELECT * FROM foo WHERE a > 0 ORDER BY a DESC;
{
  "a": 1.3
}
{
  "a": 1.2
}
{
  "a": 1
}
```

However, this kind of behavior is also expected if `a` is indexed:

- Integers and doubles must be indexed together
- Comparing integers together must be lossless (no conversion to double)
- Ordering must be respected

And this is _very complex_. As of today, we still don't have proper support for the above requirements.

This led for example to the creation of the `binarysort` package (former `key` package) which encodes integers and doubles on 16 bytes. While this works, this adds too much complexity and performance issues during index iteration, while obviously taking much more space.

### Solution

The solution proposed here is to change the rules: **numbers are stored as doubles by default**

The parser doesn't change, integers are scanned as integers, doubles as doubles.
Comparison and arithmetic operators keep the same behavior.

```sql
SELECT 1 + 1;
{
  "1 + 1": 2 // -- 2 here is an integer
}
```

The only difference is that _right before storing the document_, every integer field will be converted to double if there is no explicit constraint on that field.

This means that one field can never be both a double or an integer on two different documents:

- No field constraint: All numbers stored as doubles
- Field constraint: All numbers stored as specified by the field constraint

This new property allows us to simplify index implementation and to remove all the edge cases.

```sql
INSERT INTO foo (a) VALUES 
(1), -- parsed as int, stored as double
(1.5), -- parsed as double, stored as double
([1, 2]); -- array and sub-document values are also stored as double
SELECT * FROM foo WHERE a > 0 ORDER BY a DESC;
{
  "a": [1, 2]
}
{
  "a": 1.5
}
{
  "a": 1
}
```


codecov-io: # [Codecov](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=h1) Report
> Merging [#312](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=desc) (5146a0f) into [master](https://codecov.io/gh/genjidb/genji/commit/a42cf4e06da3afdce33bcdee7da3e0922e8edb02?el=desc) (a42cf4e) will **decrease** coverage by `0.00%`.
> The diff coverage is `61.13%`.

[![Impacted file tree graph](https://codecov.io/gh/genjidb/genji/pull/312/graphs/tree.svg?width=650&height=150&src=pr&token=nwR1GpvtyH)](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #312      +/-   ##
==========================================
- Coverage   61.37%   61.37%   -0.01%     
==========================================
  Files          73       74       +1     
  Lines        6701     6768      +67     
==========================================
+ Hits         4113     4154      +41     
+ Misses       2053     2052       -1     
- Partials      535      562      +27     
```


| [Impacted Files](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [sql/planner/hash\_set.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-c3FsL3BsYW5uZXIvaGFzaF9zZXQuZ28=) | `0.00% <0.00%> (ø)` | |
| [sql/planner/sort.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-c3FsL3BsYW5uZXIvc29ydC5nbw==) | `16.66% <0.00%> (+1.38%)` | :arrow_up: |
| [sql/query/expr/comparison.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-c3FsL3F1ZXJ5L2V4cHIvY29tcGFyaXNvbi5nbw==) | `35.74% <10.00%> (+11.31%)` | :arrow_up: |
| [binarysort/binarysort.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-YmluYXJ5c29ydC9iaW5hcnlzb3J0Lmdv) | `39.53% <39.53%> (ø)` | |
| [document/encoding/custom/codec.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-ZG9jdW1lbnQvZW5jb2RpbmcvY3VzdG9tL2NvZGVjLmdv) | `64.15% <42.85%> (-0.60%)` | :arrow_down: |
| [sql/planner/input.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-c3FsL3BsYW5uZXIvaW5wdXQuZ28=) | `43.83% <43.47%> (+5.50%)` | :arrow_up: |
| [database/table.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-ZGF0YWJhc2UvdGFibGUuZ28=) | `52.91% <44.44%> (-3.37%)` | :arrow_down: |
| [document/document.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-ZG9jdW1lbnQvZG9jdW1lbnQuZ28=) | `69.81% <54.28%> (-6.12%)` | :arrow_down: |
| [document/array.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-ZG9jdW1lbnQvYXJyYXkuZ28=) | `69.23% <55.55%> (-4.11%)` | :arrow_down: |
| [document/value\_encoding.go](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree#diff-ZG9jdW1lbnQvdmFsdWVfZW5jb2RpbmcuZ28=) | `68.42% <68.42%> (ø)` | |
| ... and [13 more](https://codecov.io/gh/genjidb/genji/pull/312/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=footer). Last update [a42cf4e...5146a0f](https://codecov.io/gh/genjidb/genji/pull/312?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/binarysort/binarysort.go b/binarysort/binarysort.go
new file mode 100644
index 00000000..e0da272f
--- /dev/null
+++ b/binarysort/binarysort.go
@@ -0,0 +1,114 @@
+// Package binarysort provides types and functions to encode into naturally sorted binary representations.
+// That way, if vA < vB, where vA and vB are two unencoded values of the same type, then eA < eB, where eA and eB
+// are the respective encoded values of vA and vB.
+package binarysort
+
+import (
+	"bytes"
+	"encoding/base64"
+	"encoding/binary"
+	"errors"
+	"math"
+)
+
+// Default Base64 encoder string doesn't preserve lexicographic order. This alternative
+// encoder does.
+const base64encoder = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
+
+var base64Encoding = base64.NewEncoding(base64encoder).WithPadding(base64.NoPadding)
+
+// AppendBool takes a bool and returns its binary representation.
+func AppendBool(buf []byte, x bool) []byte {
+	if x {
+		return append(buf, 1)
+	}
+	return append(buf, 0)
+}
+
+// DecodeBool takes a byte slice and decodes it into a boolean.
+func DecodeBool(buf []byte) (bool, error) {
+	if len(buf) == 0 {
+		return false, errors.New("cannot decode buffer to bool")
+	}
+	return buf[0] == 1, nil
+}
+
+// AppendUint64 takes an uint64 and returns its binary representation.
+func AppendUint64(buf []byte, x uint64) []byte {
+	var b [8]byte
+	binary.BigEndian.PutUint64(b[:], x)
+	return append(buf, b[:]...)
+}
+
+// DecodeUint64 takes a byte slice and decodes it into a uint64.
+func DecodeUint64(buf []byte) (uint64, error) {
+	if len(buf) < 8 {
+		return 0, errors.New("cannot decode buffer to uint64")
+	}
+
+	return binary.BigEndian.Uint64(buf), nil
+}
+
+// AppendInt64 takes an int64 and returns its binary representation.
+func AppendInt64(buf []byte, x int64) []byte {
+	var b [8]byte
+
+	binary.BigEndian.PutUint64(b[:], uint64(x)+math.MaxInt64+1)
+	return append(buf, b[:]...)
+}
+
+// DecodeInt64 takes a byte slice and decodes it into an int64.
+func DecodeInt64(buf []byte) (int64, error) {
+	x, err := DecodeUint64(buf)
+	x -= math.MaxInt64 + 1
+	return int64(x), err
+}
+
+// AppendFloat64 takes an float64 and returns its binary representation.
+func AppendFloat64(buf []byte, x float64) []byte {
+	fb := math.Float64bits(x)
+	if x >= 0 {
+		fb ^= 1 << 63
+	} else {
+		fb ^= 1<<64 - 1
+	}
+	return AppendUint64(buf, fb)
+}
+
+// DecodeFloat64 takes a byte slice and decodes it into an float64.
+func DecodeFloat64(buf []byte) (float64, error) {
+	if len(buf) < 8 {
+		return 0, errors.New("cannot decode buffer to float64")
+	}
+	x := binary.BigEndian.Uint64(buf)
+
+	if (x & (1 << 63)) != 0 {
+		x ^= 1 << 63
+	} else {
+		x ^= 1<<64 - 1
+	}
+	return math.Float64frombits(x), nil
+}
+
+// AppendBase64 encodes data into a custom base64 encoding. The resulting slice respects
+// natural sort-ordering.
+func AppendBase64(buf []byte, data []byte) ([]byte, error) {
+	b := bytes.NewBuffer(buf)
+	enc := base64.NewEncoder(base64Encoding, b)
+	_, _ = enc.Write(data)
+	_ = enc.Close()
+
+	return b.Bytes(), nil
+}
+
+// DecodeBase64 decodes a custom base64 encoded byte slice,
+// encoded with AppendBase64.
+func DecodeBase64(data []byte) ([]byte, error) {
+	var buf bytes.Buffer
+	dec := base64.NewDecoder(base64Encoding, bytes.NewReader(data))
+	_, err := buf.ReadFrom(dec)
+	if err != nil {
+		return nil, err
+	}
+	return buf.Bytes(), nil
+}
diff --git a/database/config.go b/database/config.go
index 8638f43b..5f6aa2be 100644
--- a/database/config.go
+++ b/database/config.go
@@ -81,6 +81,90 @@ func (f *FieldConstraint) ScanDocument(d document.Document) error {
 	return nil
 }
 
+// FieldConstraints is a list of field constraints.
+type FieldConstraints []FieldConstraint
+
+// ValidateDocument calls Convert then ensures the document validates against the field constraints.
+func (f FieldConstraints) ValidateDocument(d document.Document) (document.Document, error) {
+	fb, err := f.Convert(d)
+	if err != nil {
+		return nil, err
+	}
+
+	// ensure no field is missing
+	for _, fc := range f {
+		v, err := fc.Path.GetValue(fb)
+		if err == nil {
+			// if field is found, it has already been converted
+			// to the right type above.
+			// check if it is required but null.
+			if v.Type == document.NullValue && fc.IsNotNull {
+				return nil, fmt.Errorf("field %q is required and must be not null", fc.Path)
+			}
+			continue
+		}
+
+		if err != document.ErrFieldNotFound {
+			return nil, err
+		}
+
+		// if field is not found
+		// check if there is a default value
+		if fc.DefaultValue.Type != 0 {
+			err = fb.Set(fc.Path, fc.DefaultValue)
+			if err != nil {
+				return nil, err
+			}
+			// if there is no default value
+			// check if field is required
+		} else if fc.IsNotNull {
+			return nil, fmt.Errorf("field %q is required and must be not null", fc.Path)
+		}
+	}
+
+	return fb, nil
+}
+
+// Convert the document using the field constraints.
+// It converts any path that has a field constraint on it into the specified type.
+// If there is no constraint on an integer field or value, it converts it into a double.
+// Default values on missing fields are not applied.
+func (f FieldConstraints) Convert(d document.Document) (*document.FieldBuffer, error) {
+	fb := document.NewFieldBuffer()
+	err := fb.Copy(d)
+	if err != nil {
+		return nil, err
+	}
+
+	// convert the document using field constraints type information.
+	// if there is a type constraint on a path, apply it.
+	// if a value is an integer and has no constraint, convert it to double.
+	err = fb.Apply(func(p document.Path, v document.Value) (document.Value, error) {
+		for _, fc := range f {
+			if !fc.Path.IsEqual(p) {
+				continue
+			}
+
+			// check if the constraint enforce a particular type
+			// and if so convert the value to the new type.
+			if fc.Type != 0 {
+				return v.CastAs(fc.Type)
+			}
+			break
+		}
+
+		// no constraint have been found for this path.
+		// check if this is an integer and convert it to double.
+		if v.Type == document.IntegerValue {
+			return v.CastAsDouble()
+		}
+
+		return v, nil
+	})
+
+	return fb, err
+}
+
 // TableInfo contains information about a table.
 type TableInfo struct {
 	// name of the table.
@@ -92,7 +176,7 @@ type TableInfo struct {
 	// it will be removed if the transaction is rolled back or set to false if its commited.
 	transactionID int64
 
-	FieldConstraints []FieldConstraint
+	FieldConstraints FieldConstraints
 }
 
 // GetPrimaryKey returns the field constraint of the primary key.
diff --git a/database/table.go b/database/table.go
index bd6f8db3..18a59677 100644
--- a/database/table.go
+++ b/database/table.go
@@ -10,7 +10,6 @@ import (
 	"github.com/genjidb/genji/document/encoding"
 	"github.com/genjidb/genji/engine"
 	"github.com/genjidb/genji/index"
-	"github.com/genjidb/genji/key"
 )
 
 // A Table represents a collection of documents.
@@ -55,7 +54,7 @@ func (t *Table) Insert(d document.Document) ([]byte, error) {
 		return nil, errors.New("cannot write to read-only table")
 	}
 
-	d, err = t.ValidateConstraints(d)
+	d, err = info.FieldConstraints.ValidateDocument(d)
 	if err != nil {
 		return nil, err
 	}
@@ -155,7 +154,7 @@ func (t *Table) Replace(key []byte, d document.Document) error {
 		return errors.New("cannot write to read-only table")
 	}
 
-	d, err = t.ValidateConstraints(d)
+	d, err = info.FieldConstraints.ValidateDocument(d)
 	if err != nil {
 		return err
 	}
@@ -248,7 +247,7 @@ func (t *Table) Indexes() (map[string]Index, error) {
 				return err
 			}
 
-			idx := index.NewIndex(t.tx.tx, opts.IndexName, index.Options{
+			idx := index.New(t.tx.tx, opts.IndexName, index.Options{
 				Unique: opts.Unique,
 				Type:   opts.Type,
 			})
@@ -392,12 +391,17 @@ func (t *Table) generateKey(d document.Document) ([]byte, error) {
 		// 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)
+			return v.MarshalBinary()
 		}
 
 		// it no primary key type is specified,
 		// encode keys regardless of type.
-		return key.AppendValue(nil, v)
+		var buf bytes.Buffer
+		err = document.NewValueEncoder(&buf).Encode(v)
+		if err != nil {
+			return nil, err
+		}
+		return buf.Bytes(), nil
 	}
 
 	docid, err := t.Store.NextSequence()
@@ -410,170 +414,6 @@ func (t *Table) generateKey(d document.Document) ([]byte, error) {
 	return buf[:n], nil
 }
 
-// ValidateConstraints check the table configuration for constraints and validates the document
-// against them. If the types defined by the constraints are different than the ones found in
-// the document, the fields are converted to these types when possible. if the conversion
-// fails, an error is returned.
-func (t *Table) ValidateConstraints(d document.Document) (document.Document, error) {
-	info, err := t.Info()
-	if err != nil {
-		return nil, err
-	}
-
-	pk := info.GetPrimaryKey()
-
-	if len(info.FieldConstraints) == 0 && pk == nil {
-		return d, nil
-	}
-
-	var fb document.FieldBuffer
-
-	// make sure the document tree is full of document.FieldBuffer or document.ValueBuffer
-	// so we can modify them and convert field types.
-	err = fb.Copy(d)
-	if err != nil {
-		return nil, err
-	}
-
-	if pk != nil {
-		err = validateConstraint(&fb, pk)
-		if err != nil {
-			return nil, err
-		}
-	}
-
-	for _, fc := range info.FieldConstraints {
-		err := validateConstraint(&fb, &fc)
-		if err != nil {
-			return nil, err
-		}
-	}
-
-	return &fb, err
-}
-
-func validateConstraint(d document.Document, c *FieldConstraint) error {
-	// get the parent buffer
-	parent, err := getParentValue(d, c.Path)
-	if err != nil {
-		return err
-	}
-
-	switch parent.Type {
-	case document.DocumentValue:
-		// if it's a document, we can assume it's a FieldBuffer
-		buf := parent.V.(*document.FieldBuffer)
-
-		// the field to modify is the last chunk of the path
-		field := c.Path[len(c.Path)-1]
-		if field.FieldName == "" {
-			// if the field is not found we make sure it is not required
-			if c.IsNotNull {
-				if !c.HasDefaultValue() {
-					return fmt.Errorf("field %q is required and must be not null", c.Path)
-				}
-
-				return buf.Set(c.Path, c.DefaultValue)
-			}
-			return nil
-		}
-
-		v, err := buf.GetByField(field.FieldName)
-		// if the field is not found we make sure it is not required
-		if err != nil {
-			if err == document.ErrFieldNotFound {
-				if c.IsNotNull {
-					if !c.HasDefaultValue() {
-						return fmt.Errorf("field %q is required and must be not null", c.Path)
-					}
-
-					return buf.Set(c.Path, c.DefaultValue)
-				}
-				return nil
-			}
-
-			return err
-		}
-		// if the field is null we make sure it is not required
-		if v.Type == document.NullValue && c.IsNotNull {
-			return fmt.Errorf("field %q is required and must be not null", c.Path)
-		}
-
-		// if not we convert it and replace it in the buffer
-
-		// if no type was provided, no need to convert though
-		if c.Type == 0 {
-			return nil
-		}
-
-		v, err = v.CastAs(c.Type)
-		if err != nil {
-			return err
-		}
-
-		err = buf.Replace(field.FieldName, v)
-		if err != nil {
-			return err
-		}
-	case document.ArrayValue:
-		// if it's an array, we can assume it's a ValueBuffer
-		buf := parent.V.(document.ValueBuffer)
-
-		frag := c.Path[len(c.Path)-1]
-		if frag.FieldName != "" {
-			// if the fieldName is not empty, then the path must refer to a document and not an array,
-			// we simply skip
-			return nil
-		}
-
-		v, err := buf.GetByIndex(frag.ArrayIndex)
-		// if the value is not found we make sure it is not required,
-		if err != nil {
-			if err == document.ErrValueNotFound {
-				if c.IsNotNull {
-					if !c.HasDefaultValue() {
-						return fmt.Errorf("field %q is required and must be not null", c.Path)
-					}
-
-					return buf.Copy(c.DefaultValue.V.(document.Array))
-				}
-				return nil
-			}
-
-			return err
-		}
-
-		// if not we convert it and replace it in the buffer
-		if c.Type == 0 {
-			return nil
-		}
-
-		v, err = v.CastAs(c.Type)
-		if err != nil {
-			return err
-		}
-
-		err = buf.Replace(frag.ArrayIndex, v)
-		if err != nil {
-			return err
-		}
-	}
-
-	return nil
-}
-
-func getParentValue(d document.Document, p document.Path) (document.Value, error) {
-	if len(p) == 0 {
-		return document.Value{}, errors.New("empty path")
-	}
-
-	if len(p) == 1 {
-		return document.NewDocumentValue(d), nil
-	}
-
-	return p[:len(p)-1].GetValue(d)
-}
-
 // ReIndex all the indexes of the table.
 func (t *Table) ReIndex() error {
 	info, err := t.Info()
diff --git a/database/transaction.go b/database/transaction.go
index 4c1863a4..aa9f013f 100644
--- a/database/transaction.go
+++ b/database/transaction.go
@@ -276,7 +276,7 @@ func (tx *Transaction) GetIndex(name string) (*Index, error) {
 		return nil, err
 	}
 
-	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{
+	idx := index.New(tx.tx, opts.IndexName, index.Options{
 		Unique: opts.Unique,
 		Type:   opts.Type,
 	})
@@ -298,7 +298,7 @@ func (tx *Transaction) DropIndex(name string) error {
 		return err
 	}
 
-	idx := index.NewIndex(tx.tx, opts.IndexName, index.Options{
+	idx := index.New(tx.tx, opts.IndexName, index.Options{
 		Unique: opts.Unique,
 		Type:   opts.Type,
 	})
diff --git a/document/array.go b/document/array.go
index b1ee610b..02e9c205 100644
--- a/document/array.go
+++ b/document/array.go
@@ -156,6 +156,61 @@ func (vb *ValueBuffer) Copy(a Array) error {
 	return nil
 }
 
+// Apply a function to all the values of the buffer.
+func (vb *ValueBuffer) Apply(fn func(p Path, v Value) (Value, error)) error {
+	path := Path{PathFragment{}}
+
+	for i, v := range *vb {
+		path[0].ArrayIndex = i
+
+		switch v.Type {
+		case DocumentValue:
+			buf, ok := v.V.(*FieldBuffer)
+			if !ok {
+				buf = NewFieldBuffer()
+				err := buf.Copy(v.V.(Document))
+				if err != nil {
+					return err
+				}
+			}
+
+			err := buf.Apply(func(p Path, v Value) (Value, error) {
+				return fn(append(path, p...), v)
+			})
+			if err != nil {
+				return err
+			}
+			(*vb)[i] = NewDocumentValue(buf)
+		case ArrayValue:
+			buf, ok := v.V.(ValueBuffer)
+			if !ok {
+				buf = NewValueBuffer()
+				err := buf.Copy(v.V.(Array))
+				if err != nil {
+					return err
+				}
+			}
+
+			err := buf.Apply(func(p Path, v Value) (Value, error) {
+				return fn(append(path, p...), v)
+			})
+			if err != nil {
+				return err
+			}
+			(*vb)[i] = NewArrayValue(buf)
+		default:
+			var err error
+			v, err = fn(path, v)
+			if err != nil {
+				return err
+			}
+			(*vb)[i] = v
+		}
+	}
+
+	return nil
+}
+
 // Replace the value of the index by v.
 func (vb *ValueBuffer) Replace(index int, v Value) error {
 	if len(*vb) <= index {
diff --git a/document/compare.go b/document/compare.go
index 876e4b12..2d2b12ef 100644
--- a/document/compare.go
+++ b/document/compare.go
@@ -34,7 +34,7 @@ func (op operator) String() string {
 
 // IsEqual returns true if v is equal to the given value.
 func (v Value) IsEqual(other Value) (bool, error) {
-	return compare(operatorEq, v, other, false)
+	return compare(operatorEq, v, other)
 }
 
 // IsNotEqual returns true if v is not equal to the given value.
@@ -49,25 +49,25 @@ func (v Value) IsNotEqual(other Value) (bool, error) {
 
 // IsGreaterThan returns true if v is greather than the given value.
 func (v Value) IsGreaterThan(other Value) (bool, error) {
-	return compare(operatorGt, v, other, false)
+	return compare(operatorGt, v, other)
 }
 
 // IsGreaterThanOrEqual returns true if v is greather than or equal to the given value.
 func (v Value) IsGreaterThanOrEqual(other Value) (bool, error) {
-	return compare(operatorGte, v, other, false)
+	return compare(operatorGte, v, other)
 }
 
 // IsLesserThan returns true if v is lesser than the given value.
 func (v Value) IsLesserThan(other Value) (bool, error) {
-	return compare(operatorLt, v, other, false)
+	return compare(operatorLt, v, other)
 }
 
 // IsLesserThanOrEqual returns true if v is lesser than or equal to the given value.
 func (v Value) IsLesserThanOrEqual(other Value) (bool, error) {
-	return compare(operatorLte, v, other, false)
+	return compare(operatorLte, v, other)
 }
 
-func compare(op operator, l, r Value, compareDifferentTypes bool) (bool, error) {
+func compare(op operator, l, r Value) (bool, error) {
 	switch {
 	// deal with nil
 	case l.Type == NullValue || r.Type == NullValue:
@@ -102,17 +102,6 @@ func compare(op operator, l, r Value, compareDifferentTypes bool) (bool, error)
 		return compareDocuments(op, l.V.(Document), r.V.(Document))
 	}
 
-	if compareDifferentTypes {
-		switch op {
-		case operatorEq:
-			return false, nil
-		case operatorGt, operatorGte:
-			return l.Type > r.Type, nil
-		case operatorLt, operatorLte:
-			return l.Type < r.Type, nil
-		}
-	}
-
 	return false, nil
 }
 
@@ -243,15 +232,26 @@ func compareArrays(op operator, l Array, r Array) (bool, error) {
 		if lerr != nil || rerr != nil {
 			break
 		}
-		isEq, err := compare(operatorEq, lv, rv, true)
-		if err != nil {
-			return false, err
-		}
-		if !isEq && op != operatorEq {
-			return compare(op, lv, rv, true)
-		}
-		if !isEq {
-			return false, nil
+		if lv.Type == rv.Type {
+			isEq, err := compare(operatorEq, lv, rv)
+			if err != nil {
+				return false, err
+			}
+			if !isEq && op != operatorEq {
+				return compare(op, lv, rv)
+			}
+			if !isEq {
+				return false, nil
+			}
+		} else {
+			switch op {
+			case operatorEq:
+				return false, nil
+			case operatorGt, operatorGte:
+				return lv.Type > rv.Type, nil
+			case operatorLt, operatorLte:
+				return lv.Type < rv.Type, nil
+			}
 		}
 	}
 
@@ -349,15 +349,26 @@ func compareDocuments(op operator, l, r Document) (bool, error) {
 		if lerr != nil || rerr != nil {
 			break
 		}
-		isEq, err := compare(operatorEq, lv, rv, true)
-		if err != nil {
-			return false, err
-		}
-		if !isEq && op != operatorEq {
-			return compare(op, lv, rv, true)
-		}
-		if !isEq {
-			return false, nil
+		if lv.Type == rv.Type {
+			isEq, err := compare(operatorEq, lv, rv)
+			if err != nil {
+				return false, err
+			}
+			if !isEq && op != operatorEq {
+				return compare(op, lv, rv)
+			}
+			if !isEq {
+				return false, nil
+			}
+		} else {
+			switch op {
+			case operatorEq:
+				return false, nil
+			case operatorGt, operatorGte:
+				return lv.Type > rv.Type, nil
+			case operatorLt, operatorLte:
+				return lv.Type < rv.Type, nil
+			}
 		}
 	}
 
diff --git a/document/document.go b/document/document.go
index 60ab2646..32554b96 100644
--- a/document/document.go
+++ b/document/document.go
@@ -296,6 +296,61 @@ func (fb *FieldBuffer) Copy(d Document) error {
 	return nil
 }
 
+// Apply a function to all the values of the buffer.
+func (fb *FieldBuffer) Apply(fn func(p Path, v Value) (Value, error)) error {
+	path := Path{PathFragment{}}
+	var err error
+
+	for i, f := range fb.fields {
+		path[0].FieldName = f.Field
+
+		f.Value, err = fn(path, f.Value)
+		if err != nil {
+			return err
+		}
+		fb.fields[i].Value = f.Value
+
+		switch f.Value.Type {
+		case DocumentValue:
+			buf, ok := f.Value.V.(*FieldBuffer)
+			if !ok {
+				buf = NewFieldBuffer()
+				err := buf.Copy(f.Value.V.(Document))
+				if err != nil {
+					return err
+				}
+			}
+
+			err := buf.Apply(func(p Path, v Value) (Value, error) {
+				return fn(append(path, p...), v)
+			})
+			if err != nil {
+				return err
+			}
+			fb.fields[i].Value = NewDocumentValue(buf)
+		case ArrayValue:
+			buf, ok := f.Value.V.(ValueBuffer)
+			if !ok {
+				buf = NewValueBuffer()
+				err := buf.Copy(f.Value.V.(Array))
+				if err != nil {
+					return err
+				}
+			}
+
+			err := buf.Apply(func(p Path, v Value) (Value, error) {
+				return fn(append(path, p...), v)
+			})
+			if err != nil {
+				return err
+			}
+			fb.fields[i].Value = NewArrayValue(buf)
+		}
+	}
+
+	return nil
+}
+
 // Len of the buffer.
 func (fb FieldBuffer) Len() int {
 	return len(fb.fields)
diff --git a/document/encoding/custom/codec.go b/document/encoding/custom/codec.go
index 6e320995..374dc6b2 100644
--- a/document/encoding/custom/codec.go
+++ b/document/encoding/custom/codec.go
@@ -6,9 +6,9 @@ import (
 	"errors"
 	"io"
 
+	"github.com/genjidb/genji/binarysort"
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/document/encoding"
-	"github.com/genjidb/genji/key"
 )
 
 // A Codec is a custom implementation of an encoding.Codec.
@@ -122,11 +122,11 @@ func EncodeValue(v document.Value) ([]byte, error) {
 	case document.TextValue:
 		return []byte(v.V.(string)), nil
 	case document.BoolValue:
-		return key.AppendBool(nil, v.V.(bool)), nil
+		return binarysort.AppendBool(nil, v.V.(bool)), nil
 	case document.IntegerValue:
 		return encodeInt64(v.V.(int64)), nil
 	case document.DoubleValue:
-		key.AppendFloat64(nil, v.V.(float64))
+		binarysort.AppendFloat64(nil, v.V.(float64))
 	case document.NullValue:
 		return nil, nil
 	}
@@ -318,12 +318,16 @@ func DecodeValue(t document.ValueType, data []byte) (document.Value, error) {
 	case document.TextValue:
 		return document.NewTextValue(string(data)), nil
 	case document.BoolValue:
-		return document.NewBoolValue(key.DecodeBool(data)), nil
+		x, err := binarysort.DecodeBool(data)
+		if err != nil {
+			return document.Value{}, err
+		}
+		return document.NewBoolValue(x), nil
 	case document.IntegerValue:
 		x, _ := binary.Varint(data)
 		return document.NewIntegerValue(x), nil
 	case document.DoubleValue:
-		x, err := key.DecodeFloat64(data)
+		x, err := binarysort.DecodeFloat64(data)
 		if err != nil {
 			return document.Value{}, err
 		}
diff --git a/document/value.go b/document/value.go
index 6d920468..edae7eae 100644
--- a/document/value.go
+++ b/document/value.go
@@ -9,6 +9,7 @@ import (
 	"strconv"
 
 	"github.com/buger/jsonparser"
+	"github.com/genjidb/genji/binarysort"
 )
 
 var (
@@ -262,12 +263,6 @@ func (v Value) MarshalJSON() ([]byte, error) {
 		// See https://pkg.go.dev/strconv#FormatFloat
 		prec := -1
 
-		// If fractional floating-point is 0, the precision should be 1 to add a trailing .0
-		_, frac := math.Modf(f)
-		if frac == 0 {
-			prec = 1
-		}
-
 		return strconv.AppendFloat(nil, v.V.(float64), fmt, prec, 64), nil
 	case TextValue:
 		return []byte(strconv.Quote(v.V.(string))), nil
@@ -302,6 +297,93 @@ func (v Value) String() string {
 	return string(d)
 }
 
+// Append appends to buf a binary representation of v.
+// The encoded value doesn't include type information.
+func (v Value) Append(buf []byte) ([]byte, error) {
+	switch v.Type {
+	case BlobValue:
+		return append(buf, v.V.([]byte)...), nil
+	case TextValue:
+		return append(buf, v.V.(string)...), nil
+	case BoolValue:
+		return binarysort.AppendBool(buf, v.V.(bool)), nil
+	case IntegerValue:
+		return binarysort.AppendInt64(buf, v.V.(int64)), nil
+	case DoubleValue:
+		return binarysort.AppendFloat64(buf, v.V.(float64)), nil
+	case NullValue:
+		return buf, nil
+	case ArrayValue:
+		var buf bytes.Buffer
+		err := NewValueEncoder(&buf).appendArray(v.V.(Array))
+		if err != nil {
+			return nil, err
+		}
+		return buf.Bytes(), nil
+	case DocumentValue:
+		var buf bytes.Buffer
+		err := NewValueEncoder(&buf).appendDocument(v.V.(Document))
+		if err != nil {
+			return nil, err
+		}
+		return buf.Bytes(), nil
+	}
+
+	return nil, errors.New("cannot encode type " + v.Type.String() + " as key")
+}
+
+// MarshalBinary returns a binary representation of v.
+// The encoded value doesn't include type information.
+func (v Value) MarshalBinary() ([]byte, error) {
+	return v.Append(nil)
+}
+
+// UnmarshalBinary decodes data to v. Data must not contain type information,
+// instead, v.Type must be set.
+func (v *Value) UnmarshalBinary(data []byte) error {
+	switch v.Type {
+	case NullValue:
+	case BlobValue:
+		v.V = data
+	case TextValue:
+		v.V = string(data)
+	case BoolValue:
+		x, err := binarysort.DecodeBool(data)
+		if err != nil {
+			return err
+		}
+		v.V = x
+	case IntegerValue:
+		x, err := binarysort.DecodeInt64(data)
+		if err != nil {
+			return err
+		}
+		v.V = x
+	case DoubleValue:
+		x, err := binarysort.DecodeFloat64(data)
+		if err != nil {
+			return err
+		}
+		v.V = x
+	case ArrayValue:
+		a, _, err := decodeArray(data)
+		if err != nil {
+			return err
+		}
+		v.V = a
+	case DocumentValue:
+		d, _, err := decodeDocument(data)
+		if err != nil {
+			return err
+		}
+		v.V = d
+	default:
+		return errors.New("unknown type")
+	}
+
+	return nil
+}
+
 // Add u to v and return the result.
 // Only numeric values and booleans can be added together.
 func (v Value) Add(u Value) (res Value, err error) {
diff --git a/document/value_encoding.go b/document/value_encoding.go
new file mode 100644
index 00000000..902478a8
--- /dev/null
+++ b/document/value_encoding.go
@@ -0,0 +1,314 @@
+package document
+
+import (
+	"errors"
+	"io"
+
+	"github.com/genjidb/genji/binarysort"
+)
+
+const (
+	arrayValueDelim    = 0x1f
+	arrayEnd           = 0x1e
+	documentValueDelim = 0x1c
+	documentEnd        = 0x1d
+)
+
+// ValueEncoder encodes natural sort-ordered representations of values.
+// Type information is encoded alongside each value.
+type ValueEncoder struct {
+	w io.Writer
+
+	buf []byte
+}
+
+// NewValueEncoder creates a ValueEncoder that writes to w.
+func NewValueEncoder(w io.Writer) *ValueEncoder {
+	return &ValueEncoder{
+		w: w,
+	}
+}
+
+func (ve *ValueEncoder) append(data ...byte) error {
+	_, err := ve.w.Write(data)
+	return err
+}
+
+// Encode v to the writer.
+func (ve *ValueEncoder) Encode(v Value) error {
+	return ve.appendValue(v)
+}
+
+func (ve *ValueEncoder) appendValue(v Value) error {
+	err := ve.append(byte(v.Type))
+	if err != nil {
+		return err
+	}
+
+	switch v.Type {
+	case NullValue:
+		return nil
+	case ArrayValue:
+		return ve.appendArray(v.V.(Array))
+	case DocumentValue:
+		return ve.appendDocument(v.V.(Document))
+	}
+
+	ve.buf = ve.buf[:0]
+
+	switch v.Type {
+	case BlobValue:
+		ve.buf, err = binarysort.AppendBase64(ve.buf, v.V.([]byte))
+	case TextValue:
+		text := v.V.(string)
+		ve.buf, err = binarysort.AppendBase64(ve.buf, []byte(text))
+	case BoolValue:
+		ve.buf, err = binarysort.AppendBool(ve.buf, v.V.(bool)), nil
+	case IntegerValue:
+		ve.buf = binarysort.AppendInt64(ve.buf, v.V.(int64))
+	case DoubleValue:
+		ve.buf = binarysort.AppendFloat64(ve.buf, v.V.(float64))
+	default:
+		return errors.New("cannot encode type " + v.Type.String() + " as key")
+	}
+	if err != nil {
+		return err
+	}
+	ve.append(ve.buf...)
+
+	return err
+}
+
+// appendArray encodes an array into a sort-ordered binary representation.
+func (ve *ValueEncoder) appendArray(a Array) error {
+	err := a.Iterate(func(i int, value Value) error {
+		if i > 0 {
+			err := ve.append(arrayValueDelim)
+			if err != nil {
+				return err
+			}
+		}
+
+		return ve.appendValue(value)
+	})
+	if err != nil {
+		return err
+	}
+
+	return ve.append(arrayEnd)
+}
+
+// appendDocument encodes a document into a sort-ordered binary representation.
+func (ve *ValueEncoder) appendDocument(d Document) error {
+	var i int
+	err := d.Iterate(func(field string, value Value) error {
+		var err error
+
+		if i > 0 {
+			err = ve.append(documentValueDelim)
+			if err != nil {
+				return err
+			}
+		}
+
+		ve.buf, err = binarysort.AppendBase64(ve.buf[:0], []byte(field))
+		if err != nil {
+			return err
+		}
+		err = ve.append(ve.buf...)
+		if err != nil {
+			return err
+		}
+
+		err = ve.append(documentValueDelim)
+		if err != nil {
+			return err
+		}
+
+		err = ve.appendValue(value)
+		if err != nil {
+			return err
+		}
+
+		i++
+		return nil
+	})
+	if err != nil {
+		return err
+	}
+
+	return ve.append(documentEnd)
+}
+
+// decodeValue decodes a value encoded with ValueEncoder.
+func decodeValue(data []byte) (Value, error) {
+	t := ValueType(data[0])
+	data = data[1:]
+
+	switch t {
+	case NullValue:
+		return NewNullValue(), nil
+	case BlobValue:
+		t, err := binarysort.DecodeBase64(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewBlobValue(t), nil
+	case TextValue:
+		t, err := binarysort.DecodeBase64(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewTextValue(string(t)), nil
+	case BoolValue:
+		b, err := binarysort.DecodeBool(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewBoolValue(b), nil
+	case IntegerValue:
+		x, err := binarysort.DecodeInt64(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewIntegerValue(x), nil
+	case DoubleValue:
+		x, err := binarysort.DecodeFloat64(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewDoubleValue(x), nil
+	case ArrayValue:
+		a, _, err := decodeArray(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewArrayValue(a), nil
+	case DocumentValue:
+		d, _, err := decodeDocument(data)
+		if err != nil {
+			return Value{}, err
+		}
+		return NewDocumentValue(d), nil
+	}
+
+	return Value{}, errors.New("unknown type")
+}
+
+func decodeValueUntil(data []byte, delim, end byte) (Value, int, error) {
+	t := ValueType(data[0])
+	i := 1
+
+	switch t {
+	case ArrayValue:
+		a, n, err := decodeArray(data[i:])
+		i += n
+		if err != nil {
+			return Value{}, i, err
+		}
+		return NewArrayValue(a), i, nil
+	case DocumentValue:
+		d, n, err := decodeDocument(data[i:])
+		i += n
+		if err != nil {
+			return Value{}, i, err
+		}
+		return NewDocumentValue(d), i, nil
+	case NullValue:
+	case BoolValue:
+		i++
+	case IntegerValue, DoubleValue:
+		if i+8 < len(data) && data[i+8] == delim {
+			i += 8
+		} else {
+			return Value{}, 0, errors.New("malformed " + t.String())
+		}
+	case BlobValue, TextValue:
+		for i < len(data) && data[i] != delim && data[i] != end {
+			i++
+		}
+	default:
+		return Value{}, 0, errors.New("invalid type character")
+	}
+
+	v, err := decodeValue(data[:i])
+	return v, i, err
+}
+
+func decodeArray(data []byte) (Array, int, error) {
+	var vb ValueBuffer
+
+	var readCount int
+	for len(data) > 0 && data[0] != arrayEnd {
+		v, i, err := decodeValueUntil(data, arrayValueDelim, arrayEnd)
+		if err != nil {
+			return nil, i, err
+		}
+
+		vb = vb.Append(v)
+
+		// skip the delimiter
+		if data[i] == arrayValueDelim {
+			i++
+		}
+
+		readCount += i
+
+		data = data[i:]
+	}
+
+	// skip the array end character
+	readCount++
+
+	return vb, readCount, nil
+}
+
+func decodeDocument(data []byte) (Document, int, error) {
+	var fb FieldBuffer
+
+	var readCount int
+	for len(data) > 0 && data[0] != documentEnd {
+		i := 0
+
+		for i < len(data) && data[i] != documentValueDelim {
+			i++
+		}
+
+		field, err := binarysort.DecodeBase64(data[:i])
+		if err != nil {
+			return nil, 0, err
+		}
+
+		// skip the delimiter
+		i++
+
+		if i >= len(data) {
+			return nil, 0, errors.New("invalid end of input")
+		}
+
+		readCount += i
+
+		data = data[i:]
+
+		v, i, err := decodeValueUntil(data, documentValueDelim, documentEnd)
+		if err != nil {
+			return nil, i, err
+		}
+
+		fb.Add(string(field), v)
+
+		// skip the delimiter
+		if data[i] == documentValueDelim {
+			i++
+		}
+
+		readCount += i
+
+		data = data[i:]
+	}
+
+	// skip the document end character
+	readCount++
+
+	return &fb, readCount, nil
+}
diff --git a/index/index.go b/index/index.go
index f950f1e4..0771358d 100644
--- a/index/index.go
+++ b/index/index.go
@@ -8,7 +8,6 @@ import (
 
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
-	"github.com/genjidb/genji/key"
 )
 
 const (
@@ -19,6 +18,7 @@ const (
 var valueTypes = []document.ValueType{
 	document.NullValue,
 	document.BoolValue,
+	document.IntegerValue,
 	document.DoubleValue,
 	document.TextValue,
 	document.BlobValue,
@@ -49,8 +49,8 @@ type Options struct {
 	Type document.ValueType
 }
 
-// NewIndex creates an index that associates a value with a list of keys.
-func NewIndex(tx engine.Transaction, idxName string, opts Options) *Index {
+// New creates an index that associates a value with a list of keys.
+func New(tx engine.Transaction, idxName string, opts Options) *Index {
 	return &Index{
 		tx:        tx,
 		storeName: append([]byte(storePrefix), idxName...),
@@ -81,7 +81,7 @@ func (idx *Index) Set(v document.Value, k []byte) error {
 	}
 
 	// encode the value we are going to use as a key
-	buf, err := idx.encodeValue(v)
+	buf, err := idx.EncodeValue(v)
 	if err != nil {
 		return err
 	}
@@ -172,6 +172,8 @@ func (idx *Index) DescendLessOrEqual(pivot document.Value, fn func(val, key []by
 }
 
 func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val, key []byte, isEqual bool) error) error {
+	// if index and pivot are typed but not of the same type
+	// return no result
 	if idx.Type != 0 && pivot.Type != 0 && idx.Type != pivot.Type {
 		return nil
 	}
@@ -186,7 +188,7 @@ func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val
 
 	var enc []byte
 	if pivot.V != nil {
-		enc, err = idx.encodeValue(pivot)
+		enc, err = idx.EncodeValue(pivot)
 		if err != nil {
 			return err
 		}
@@ -224,17 +226,21 @@ 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
+// EncodeValue encodes 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) {
+// Ff not, encode so that order is preserved regardless of the type.
+func (idx *Index) EncodeValue(v document.Value) ([]byte, error) {
 	if idx.Type != 0 {
-		buf, err = key.Append(buf, v.Type, v.V)
-	} else {
-		buf, err = key.AppendValue(buf, v)
+		return v.MarshalBinary()
 	}
-	return
+
+	var buf bytes.Buffer
+	err := document.NewValueEncoder(&buf).Encode(v)
+	if err != nil {
+		return nil, err
+	}
+	return buf.Bytes(), nil
 }
 
 func getOrCreateStore(tx engine.Transaction, name []byte) (engine.Store, error) {
@@ -260,7 +266,7 @@ func (idx *Index) iterate(st engine.Store, pivot document.Value, reverse bool, f
 	var err error
 
 	if pivot.V != nil {
-		seek, err = idx.encodeValue(pivot)
+		seek, err = idx.EncodeValue(pivot)
 		if err != nil {
 			return err
 		}
@@ -270,10 +276,6 @@ func (idx *Index) iterate(st engine.Store, pivot document.Value, reverse bool, f
 		}
 	}
 
-	if pivot.Type == document.IntegerValue {
-		pivot.Type = document.DoubleValue
-	}
-
 	if pivot.Type != 0 && pivot.V == nil {
 		seek = []byte{byte(pivot.Type)}
 
@@ -288,6 +290,7 @@ func (idx *Index) iterate(st engine.Store, pivot document.Value, reverse bool, f
 	for it.Seek(seek); it.Valid(); it.Next() {
 		itm := it.Item()
 
+		// if index is untyped and pivot is typed, only iterate on values with the same type as pivot
 		if idx.Type == 0 && pivot.Type != 0 && itm.Key()[0] != byte(pivot.Type) {
 			return nil
 		}
diff --git a/key/encoding.go b/key/encoding.go
deleted file mode 100644
index 103f6892..00000000
--- a/key/encoding.go
+++ /dev/null
@@ -1,479 +0,0 @@
-// Package key provides types and functions to encode and decode keys.
-//
-// Encoding keys
-//
-// Each type is encoded in a way that allows ordering to be preserved. That way, if vA < vB,
-// where vA and vB are two unencoded values of the same type, then eA < eB, where eA and eB
-// are the respective encoded values of vA and vB.
-package key
-
-import (
-	"bytes"
-	"encoding/base64"
-	"encoding/binary"
-	"errors"
-	"math"
-
-	"github.com/genjidb/genji/document"
-)
-
-const base64encoder = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
-
-var base64Encoding = base64.NewEncoding(base64encoder).WithPadding(base64.NoPadding)
-
-const arrayValueDelim = 0x1f
-const arrayEnd = 0x1e
-const documentValueDelim = 0x1c
-const documentEnd = 0x1d
-
-// AppendBool takes a bool and returns its binary representation.
-func AppendBool(buf []byte, x bool) []byte {
-	if x {
-		return append(buf, 1)
-	}
-	return append(buf, 0)
-}
-
-// DecodeBool takes a byte slice and decodes it into a boolean.
-func DecodeBool(buf []byte) bool {
-	return buf[0] == 1
-}
-
-// AppendUint64 takes an uint64 and returns its binary representation.
-func AppendUint64(buf []byte, x uint64) []byte {
-	var b [8]byte
-	binary.BigEndian.PutUint64(b[:], x)
-	return append(buf, b[:]...)
-}
-
-// DecodeUint64 takes a byte slice and decodes it into a uint64.
-func DecodeUint64(buf []byte) (uint64, error) {
-	if len(buf) < 8 {
-		return 0, errors.New("cannot decode buffer to uint64")
-	}
-
-	return binary.BigEndian.Uint64(buf), nil
-}
-
-// AppendInt64 takes an int64 and returns its binary representation.
-func AppendInt64(buf []byte, x int64) []byte {
-	var b [8]byte
-
-	binary.BigEndian.PutUint64(b[:], uint64(x)+math.MaxInt64+1)
-	return append(buf, b[:]...)
-}
-
-// DecodeInt64 takes a byte slice and decodes it into an int64.
-func DecodeInt64(buf []byte) (int64, error) {
-	x, err := DecodeUint64(buf)
-	x -= math.MaxInt64 + 1
-	return int64(x), err
-}
-
-// AppendFloat64 takes an float64 and returns its binary representation.
-func AppendFloat64(buf []byte, x float64) []byte {
-	fb := math.Float64bits(x)
-	if x >= 0 {
-		fb ^= 1 << 63
-	} else {
-		fb ^= 1<<64 - 1
-	}
-	return AppendUint64(buf, fb)
-}
-
-// DecodeFloat64 takes a byte slice and decodes it into an float64.
-func DecodeFloat64(buf []byte) (float64, error) {
-	x := binary.BigEndian.Uint64(buf)
-
-	if (x & (1 << 63)) != 0 {
-		x ^= 1 << 63
-	} else {
-		x ^= 1<<64 - 1
-	}
-	return math.Float64frombits(x), nil
-}
-
-// AppendBase64 encodes data into a custom base64 encoding. The resulting slice respects
-// natural sort-ordering.
-func AppendBase64(buf []byte, data []byte) ([]byte, error) {
-	b := bytes.NewBuffer(buf)
-	enc := base64.NewEncoder(base64Encoding, b)
-	_, err := enc.Write(data)
-	if err != nil {
-		return nil, err
-	}
-	err = enc.Close()
-	if err != nil {
-		return nil, err
-	}
-
-	return b.Bytes(), nil
-}
-
-// DecodeBase64 decodes a custom base64 encoded byte slice,
-// encoded with AppendBase64.
-func DecodeBase64(data []byte) ([]byte, error) {
-	var buf bytes.Buffer
-	dec := base64.NewDecoder(base64Encoding, bytes.NewReader(data))
-	_, err := buf.ReadFrom(dec)
-	if err != nil {
-		return nil, err
-	}
-	return buf.Bytes(), 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
-}
-
-// AppendArray encodes an array into a sort-ordered binary representation.
-func AppendArray(buf []byte, a document.Array) ([]byte, error) {
-	err := a.Iterate(func(i int, value document.Value) error {
-		var err error
-
-		if i > 0 {
-			buf = append(buf, arrayValueDelim)
-		}
-
-		buf, err = AppendValue(buf, value)
-		if err != nil {
-			return err
-		}
-
-		return nil
-	})
-	if err != nil {
-		return nil, err
-	}
-
-	buf = append(buf, arrayEnd)
-
-	return buf, nil
-}
-
-func decodeValue(data []byte, delim, end byte) (document.Value, int, error) {
-	t := document.ValueType(data[0])
-	i := 1
-
-	switch t {
-	case document.ArrayValue:
-		a, n, err := decodeArray(data[i:])
-		i += n
-		if err != nil {
-			return document.Value{}, i, err
-		}
-		return document.NewArrayValue(a), i, nil
-	case document.DocumentValue:
-		d, n, err := decodeDocument(data[i:])
-		i += n
-		if err != nil {
-			return document.Value{}, i, err
-		}
-		return document.NewDocumentValue(d), i, nil
-	case document.NullValue:
-	case document.BoolValue:
-		i++
-	case document.DoubleValue:
-		i += 16
-	case document.BlobValue, document.TextValue:
-		for i < len(data) && data[i] != delim && data[i] != end {
-			i++
-		}
-	default:
-		return document.Value{}, 0, errors.New("invalid type character")
-	}
-
-	v, err := DecodeValue(data[:i])
-	return v, i, err
-}
-
-// DecodeArray decodes an array.
-func DecodeArray(data []byte) (document.Array, error) {
-	a, _, err := decodeArray(data)
-	return a, err
-}
-
-func decodeArray(data []byte) (document.Array, int, error) {
-	var vb document.ValueBuffer
-
-	var readCount int
-	for len(data) > 0 && data[0] != arrayEnd {
-		v, i, err := decodeValue(data, arrayValueDelim, arrayEnd)
-		if err != nil {
-			return nil, i, err
-		}
-
-		vb = vb.Append(v)
-
-		// skip the delimiter
-		if data[i] == arrayValueDelim {
-			i++
-		}
-
-		readCount += i
-
-		data = data[i:]
-	}
-
-	// skip the array end character
-	readCount++
-
-	return vb, readCount, nil
-}
-
-// AppendDocument encodes a document into a sort-ordered binary representation.
-func AppendDocument(buf []byte, d document.Document) ([]byte, error) {
-	var i int
-	err := d.Iterate(func(field string, value document.Value) error {
-		var err error
-
-		if i > 0 {
-			buf = append(buf, documentValueDelim)
-		}
-
-		buf, err = AppendBase64(buf, []byte(field))
-		if err != nil {
-			return err
-		}
-
-		buf = append(buf, documentValueDelim)
-
-		buf, err = AppendValue(buf, value)
-		if err != nil {
-			return err
-		}
-
-		i++
-		return nil
-	})
-	if err != nil {
-		return nil, err
-	}
-
-	buf = append(buf, documentEnd)
-
-	return buf, nil
-}
-
-// DecodeDocument decodes a document.
-func DecodeDocument(data []byte) (document.Document, error) {
-	a, _, err := decodeDocument(data)
-	return a, err
-}
-
-func decodeDocument(data []byte) (document.Document, int, error) {
-	var fb document.FieldBuffer
-
-	var readCount int
-	for len(data) > 0 && data[0] != documentEnd {
-		i := 0
-
-		for i < len(data) && data[i] != documentValueDelim {
-			i++
-		}
-
-		field, err := DecodeBase64(data[:i])
-		if err != nil {
-			return nil, 0, err
-		}
-
-		// skip the delimiter
-		i++
-
-		if i >= len(data) {
-			return nil, 0, errors.New("invalid end of input")
-		}
-
-		readCount += i
-
-		data = data[i:]
-
-		v, i, err := decodeValue(data, documentValueDelim, documentEnd)
-		if err != nil {
-			return nil, i, err
-		}
-
-		fb.Add(string(field), v)
-
-		// skip the delimiter
-		if data[i] == documentValueDelim {
-			i++
-		}
-
-		readCount += i
-
-		data = data[i:]
-	}
-
-	// skip the document end character
-	readCount++
-
-	return &fb, readCount, nil
-}
-
-// AppendValue encodes a value as a key.
-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 AppendBase64(buf, v.V.([]byte))
-	case document.TextValue:
-		text := v.V.(string)
-		return AppendBase64(buf, []byte(text))
-	case document.BoolValue:
-		return AppendBool(buf, v.V.(bool)), nil
-	case document.IntegerValue, document.DoubleValue:
-		return AppendNumber(buf, v)
-	case document.NullValue:
-		return buf, nil
-	case document.ArrayValue:
-		return AppendArray(buf, v.V.(document.Array))
-	case document.DocumentValue:
-		return AppendDocument(buf, v.V.(document.Document))
-	}
-
-	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:
-		t, err := DecodeBase64(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewBlobValue(t), nil
-	case document.TextValue:
-		t, err := DecodeBase64(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewTextValue(string(t)), 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.NullValue:
-		return document.NewNullValue(), nil
-	case document.ArrayValue:
-		a, err := DecodeArray(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewArrayValue(a), nil
-	case document.DocumentValue:
-		d, err := DecodeDocument(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewDocumentValue(d), 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.(string)...), nil
-	case document.BoolValue:
-		return AppendBool(buf, v.(bool)), nil
-	case document.IntegerValue:
-		return AppendInt64(buf, v.(int64)), nil
-	case document.DoubleValue:
-		return AppendFloat64(buf, v.(float64)), nil
-	case document.NullValue:
-		return buf, nil
-	case document.ArrayValue:
-		return AppendArray(buf, v.(document.Array))
-	case document.DocumentValue:
-		return AppendDocument(buf, v.(document.Document))
-	}
-
-	return nil, errors.New("cannot encode type " + t.String() + " as key")
-}
-
-// 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
-	case document.TextValue:
-		return document.NewTextValue(string(data)), nil
-	case document.BoolValue:
-		return document.NewBoolValue(DecodeBool(data)), nil
-	case document.IntegerValue:
-		x, err := DecodeInt64(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-
-		return document.NewIntegerValue(x), nil
-	case document.DoubleValue:
-		x, err := DecodeFloat64(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewDoubleValue(x), nil
-	case document.NullValue:
-		return document.NewNullValue(), nil
-	case document.ArrayValue:
-		a, err := DecodeArray(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewArrayValue(a), nil
-	case document.DocumentValue:
-		d, err := DecodeDocument(data)
-		if err != nil {
-			return document.Value{}, err
-		}
-		return document.NewDocumentValue(d), nil
-	}
-
-	return document.Value{}, errors.New("unknown type")
-}
diff --git a/sql/parser/create.go b/sql/parser/create.go
index be213f66..79520abd 100644
--- a/sql/parser/create.go
+++ b/sql/parser/create.go
@@ -175,10 +175,6 @@ func (p *Parser) parseFieldConstraint(fc *database.FieldConstraint) error {
 				return err
 			}
 
-			if fc.Type != 0 && fc.Type != d.Type {
-				return &ParseError{Message: fmt.Sprintf("default value must have type %s, got %s", fc.Type, d.Type)}
-			}
-
 			// if it's already default value we return an error
 			if fc.HasDefaultValue() {
 				return newParseError(scanner.Tokstr(tok, lit), []string{"CONSTRAINT", ")"}, pos)
diff --git a/sql/planner/hash_set.go b/sql/planner/hash_set.go
index ccf133fb..165b5440 100644
--- a/sql/planner/hash_set.go
+++ b/sql/planner/hash_set.go
@@ -5,7 +5,6 @@ import (
 	"hash/maphash"
 
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/key"
 )
 
 type documentHashSet struct {
@@ -32,18 +31,15 @@ func (s documentHashSet) generateKey(d document.Document) (uint64, error) {
 		return 0, err
 	}
 
+	enc := document.NewValueEncoder(s.hash)
+
 	for _, field := range fields {
 		value, err := d.GetByField(field)
 		if err != nil {
 			return 0, err
 		}
 
-		buf, err := key.AppendValue(nil, value)
-		if err != nil {
-			return 0, err
-		}
-
-		_, err = s.hash.Write(buf)
+		err = enc.Encode(value)
 		if err != nil {
 			return 0, err
 		}
diff --git a/sql/planner/input.go b/sql/planner/input.go
index 542fb2cc..44bcae96 100644
--- a/sql/planner/input.go
+++ b/sql/planner/input.go
@@ -58,22 +58,25 @@ type indexInputNode struct {
 	table            *database.Table
 	index            *database.Index
 	iop              IndexIteratorOperator
-	e                expr.Expr
+	path             document.Path
+	filter           expr.Expr
+	evaluatedFilter  document.Value
 	orderByDirection scanner.Token
 }
 
 var _ inputNode = (*indexInputNode)(nil)
 
 // NewIndexInputNode creates a node that can be used to read documents using an index.
-func NewIndexInputNode(tableName, indexName string, iop IndexIteratorOperator, filter expr.Expr, orderByDirection scanner.Token) Node {
+func NewIndexInputNode(tableName, indexName string, iop IndexIteratorOperator, path expr.Path, filter expr.Expr, orderByDirection scanner.Token) Node {
 	return &indexInputNode{
 		node: node{
 			op: Input,
 		},
 		tableName:        tableName,
 		indexName:        indexName,
+		path:             document.Path(path),
 		iop:              iop,
-		e:                filter,
+		filter:           filter,
 		orderByDirection: orderByDirection,
 	}
 }
@@ -95,6 +98,38 @@ func (n *indexInputNode) Bind(tx *database.Transaction, params []expr.Param) (er
 
 	n.tx = tx
 	n.params = params
+
+	// evaluate the filter expression
+	n.evaluatedFilter, err = n.filter.Eval(expr.EvalStack{
+		Tx:     n.tx,
+		Params: n.params,
+	})
+	if err != nil {
+		return
+	}
+
+	// if the indexed field has no constraint and the filter is an int, cast that int to a double.
+	if n.evaluatedFilter.Type == document.IntegerValue {
+		info, err := n.table.Info()
+		if err != nil {
+			return err
+		}
+
+		shouldBeConverted := true
+		for _, fc := range info.FieldConstraints {
+			if fc.Path.IsEqual(n.path) && fc.Type != 0 {
+				shouldBeConverted = false
+				break
+			}
+		}
+
+		if shouldBeConverted {
+			n.evaluatedFilter, err = n.evaluatedFilter.CastAsDouble()
+			if err != nil {
+				return err
+			}
+		}
+	}
 	return
 }
 
@@ -104,7 +139,8 @@ func (n *indexInputNode) buildStream() (document.Stream, error) {
 		tb:     n.table,
 		params: n.params,
 		index:  n.index,
-		e:      n.e,
+		path:   n.path,
+		filter: n.evaluatedFilter,
 		iop:    n.iop,
 	}), nil
 }
@@ -124,15 +160,16 @@ type indexIterator struct {
 	tb               *database.Table
 	params           []expr.Param
 	index            *database.Index
+	path             document.Path
 	iop              IndexIteratorOperator
-	e                expr.Expr
+	filter           document.Value
 	orderByDirection scanner.Token
 }
 
 var errStop = errors.New("stop")
 
 func (it indexIterator) Iterate(fn func(d document.Document) error) error {
-	if it.e == nil {
+	if it.filter.Type == 0 {
 		var err error
 
 		if it.orderByDirection == scanner.DESC {
@@ -158,13 +195,5 @@ func (it indexIterator) Iterate(fn func(d document.Document) error) error {
 		return err
 	}
 
-	v, err := it.e.Eval(expr.EvalStack{
-		Tx:     it.tx,
-		Params: it.params,
-	})
-	if err != nil {
-		return err
-	}
-
-	return it.iop.IterateIndex(it.index, it.tb, v, fn)
+	return it.iop.IterateIndex(it.index, it.tb, it.filter, fn)
 }
diff --git a/sql/planner/optimizer.go b/sql/planner/optimizer.go
index 45ba776c..b9a9dda6 100644
--- a/sql/planner/optimizer.go
+++ b/sql/planner/optimizer.go
@@ -438,13 +438,14 @@ func selectionNodeValidForIndex(sn *selectionNode, tableName string, indexes map
 		return nil
 	}
 
+	// determine if the operator can read from the index
 	iop, ok := op.(IndexIteratorOperator)
 	if !ok {
 		return nil
 	}
 
 	// determine if the operator can benefit from an index
-	ok, field, e := opCanUseIndex(op)
+	ok, path, e := opCanUseIndex(op)
 	if !ok {
 		return nil
 	}
@@ -455,12 +456,12 @@ func selectionNodeValidForIndex(sn *selectionNode, tableName string, indexes map
 	}
 
 	// now, we look if an index exists for that path
-	idx, ok := indexes[field.String()]
+	idx, ok := indexes[path.String()]
 	if !ok {
 		return nil
 	}
 
-	in := NewIndexInputNode(tableName, idx.Opts.IndexName, iop, e, scanner.ASC).(*indexInputNode)
+	in := NewIndexInputNode(tableName, idx.Opts.IndexName, iop, path, e, scanner.ASC).(*indexInputNode)
 	in.index = &idx
 
 	return in
diff --git a/sql/planner/sort.go b/sql/planner/sort.go
index 0adfdaaa..aa11a79b 100644
--- a/sql/planner/sort.go
+++ b/sql/planner/sort.go
@@ -7,7 +7,6 @@ import (
 
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/key"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
 )
@@ -132,31 +131,15 @@ func (it *sortIterator) sortStream(st document.Stream) (heap.Interface, error) {
 		// if the same with or without indexes.
 		// To achieve that, the value must be encoded using the same method
 		// as what the index package would do.
-		if v.Type == document.IntegerValue {
-			v, err = v.CastAsDouble()
-			if err != nil {
-				return err
-			}
-		}
+		var buf bytes.Buffer
 
-		var value []byte
-		if v.Type != document.ArrayValue && v.Type != document.DocumentValue {
-			value, err = key.AppendValue(nil, v)
-			if err != nil {
-				return err
-			}
+		err = document.NewValueEncoder(&buf).Encode(v)
+		if err != nil {
+			return err
 		}
 
-		// to ensure ordering of values based on their types
-		// (i.e. booleans < numbers < text, ...,
-		// see index package for more info)
-		// we will prepend the encoded value with one byte
-		// representing the type of the value.
-		// integer will be considered as double
-		value = append([]byte{byte(v.Type)}, value...)
-
 		node := heapNode{
-			value: value,
+			value: buf.Bytes(),
 		}
 		err = node.data.Copy(d)
 		if err != nil {
diff --git a/sql/query/constraint.go b/sql/query/constraint.go
index cec86396..c84117b0 100644
--- a/sql/query/constraint.go
+++ b/sql/query/constraint.go
@@ -131,11 +131,31 @@ func (tree *constraintTree) search(path document.Path) *constraintNode {
 }
 
 func checkConstraints(constraints []database.FieldConstraint) error {
+	var err error
+
 	tree := constraintTree{}
-	for _, fc := range constraints {
+	for i, fc := range constraints {
 		if err := tree.insert(fc.Path, fc.Type); err != nil {
 			return fmt.Errorf("incoherent field constraint: %w", err)
 		}
+
+		if fc.DefaultValue.Type == 0 {
+			continue
+		}
+
+		targetType := fc.Type
+
+		// if there is no type constraint, numbers must be converted to double
+		if fc.DefaultValue.Type == document.IntegerValue && fc.Type == 0 {
+			targetType = document.DoubleValue
+		}
+
+		if targetType != 0 {
+			constraints[i].DefaultValue, err = fc.DefaultValue.CastAs(targetType)
+			if err != nil {
+				return err
+			}
+		}
 	}
 
 	return nil
diff --git a/sql/query/expr/comparison.go b/sql/query/expr/comparison.go
index 6684bdf3..101a666d 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/key"
 	"github.com/genjidb/genji/sql/scanner"
 )
 
@@ -60,12 +59,13 @@ func (op eqOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return nil
 	}
 
-	data, err := key.AppendValue(nil, v)
+	var buf bytes.Buffer
+	err = document.NewValueEncoder(&buf).Encode(v)
 	if err != nil {
 		return err
 	}
 
-	val, err := tb.Store.Get(data)
+	val, err := tb.Store.Get(buf.Bytes())
 	if err != nil {
 		if err == engine.ErrKeyNotFound {
 			return nil
@@ -129,10 +129,12 @@ func (op gtOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return err
 	}
 
-	data, err := key.AppendValue(nil, v)
+	var b bytes.Buffer
+	err = document.NewValueEncoder(&b).Encode(v)
 	if err != nil {
 		return err
 	}
+	data := b.Bytes()
 
 	it := tb.Store.Iterator(engine.IteratorOptions{})
 	defer it.Close()
@@ -195,10 +197,12 @@ func (op gteOp) IteratePK(tb *database.Table, v document.Value, pkType document.
 		return err
 	}
 
-	data, err := key.AppendValue(nil, v)
+	var b bytes.Buffer
+	err = document.NewValueEncoder(&b).Encode(v)
 	if err != nil {
 		return err
 	}
+	data := b.Bytes()
 
 	it := tb.Store.Iterator(engine.IteratorOptions{})
 	defer it.Close()
@@ -236,19 +240,11 @@ func Lt(a, b Expr) Expr {
 }
 
 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 {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	enc, err := key.AppendValue(nil, v)
+	enc, err := idx.EncodeValue(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
@@ -275,10 +271,12 @@ func (op ltOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 		return err
 	}
 
-	data, err := key.AppendValue(nil, v)
+	var b bytes.Buffer
+	err = document.NewValueEncoder(&b).Encode(v)
 	if err != nil {
 		return err
 	}
+	data := b.Bytes()
 
 	it := tb.Store.Iterator(engine.IteratorOptions{})
 	defer it.Close()
@@ -319,16 +317,7 @@ func Lte(a, b Expr) Expr {
 }
 
 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 {
-		v, err = v.CastAsDouble()
-		if err != nil {
-			return err
-		}
-	}
-
-	enc, err := key.AppendValue(nil, v)
+	enc, err := idx.EncodeValue(v)
 	if err != nil {
 		return err
 	}
@@ -359,10 +348,12 @@ func (op lteOp) IteratePK(tb *database.Table, v document.Value, pkType document.
 		return err
 	}
 
-	data, err := key.AppendValue(nil, v)
+	var b bytes.Buffer
+	err = document.NewValueEncoder(&b).Encode(v)
 	if err != nil {
 		return err
 	}
+	data := b.Bytes()
 
 	it := tb.Store.Iterator(engine.IteratorOptions{})
 	defer it.Close()
@@ -521,10 +512,12 @@ func (op inOp) IteratePK(tb *database.Table, v document.Value, pkType document.V
 			return nil
 		}
 
-		data, err := key.AppendValue(nil, val)
+		var b bytes.Buffer
+		err = document.NewValueEncoder(&b).Encode(val)
 		if err != nil {
 			return err
 		}
+		data := b.Bytes()
 
 		v, err := tb.Store.Get(data)
 		if err != nil {


Test patch:
diff --git a/binarysort/binary_test.go b/binarysort/binary_test.go
new file mode 100644
index 00000000..29dc44ed
--- /dev/null
+++ b/binarysort/binary_test.go
@@ -0,0 +1,41 @@
+package binarysort
+
+import (
+	"bytes"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+func TestOrdering(t *testing.T) {
+	tests := []struct {
+		name     string
+		min, max int
+		enc      func([]byte, int) []byte
+	}{
+		{"uint64", 0, 1000, func(buf []byte, i int) []byte { return AppendUint64(buf, uint64(i)) }},
+		{"int64", -1000, 1000, func(buf []byte, i int) []byte { return AppendInt64(buf, int64(i)) }},
+		{"float64", -1000, 1000, func(buf []byte, i int) []byte { return AppendFloat64(buf, float64(i)) }},
+		{"text", -1000, 1000, func(buf []byte, i int) []byte {
+			b, err := AppendBase64(nil, AppendInt64(buf, int64(i)))
+			require.NoError(t, err)
+			return b
+		}},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			var prev, cur []byte
+			for i := test.min; i < test.max; i++ {
+				cur = test.enc(cur[:0], i)
+				if prev == nil {
+					prev = append(prev[:0], cur...)
+					continue
+				}
+
+				require.Equal(t, -1, bytes.Compare(prev, cur))
+				prev = append(prev[:0], cur...)
+			}
+		})
+	}
+}
diff --git a/database/table_test.go b/database/table_test.go
index a0202ae1..0b3a223c 100644
--- a/database/table_test.go
+++ b/database/table_test.go
@@ -7,11 +7,11 @@ import (
 	"fmt"
 	"testing"
 
+	"github.com/genjidb/genji/binarysort"
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/document/encoding/msgpack"
 	"github.com/genjidb/genji/engine/memoryengine"
-	"github.com/genjidb/genji/key"
 	"github.com/genjidb/genji/sql/parser"
 	"github.com/stretchr/testify/require"
 )
@@ -114,7 +114,7 @@ func TestTableGetDocument(t *testing.T) {
 
 		// create two documents, one with an additional field
 		doc1 := newDocument()
-		vc := document.NewIntegerValue(40)
+		vc := document.NewDoubleValue(40)
 		doc1.Add("fieldc", vc)
 		doc2 := newDocument()
 
@@ -218,7 +218,7 @@ func TestTableInsert(t *testing.T) {
 		// insert
 		k, err := tb.Insert(doc)
 		require.NoError(t, err)
-		require.Equal(t, key.AppendInt64(nil, 10), k)
+		require.Equal(t, binarysort.AppendInt64(nil, 10), k)
 
 		// make sure the document is fetchable using the returned key
 		_, err = tb.GetDocument(k)
@@ -353,7 +353,8 @@ func TestTableInsert(t *testing.T) {
 		doc := document.NewFieldBuffer().
 			Add("foo", document.NewIntegerValue(1)).
 			Add("bar", document.NewDoubleValue(10)).
-			Add("baz", document.NewTextValue("baaaaz"))
+			Add("baz", document.NewTextValue("baz")).
+			Add("bat", document.NewIntegerValue(20))
 
 		// insert
 		key, err := tb.Insert(doc)
@@ -370,7 +371,31 @@ func TestTableInsert(t *testing.T) {
 		require.Equal(t, document.NewIntegerValue(10), v)
 		v, err = d.GetByField("baz")
 		require.NoError(t, err)
-		require.Equal(t, document.NewTextValue("baaaaz"), v)
+		require.Equal(t, document.NewTextValue("baz"), v)
+		v, err = d.GetByField("bat")
+		require.NoError(t, err)
+		require.Equal(t, document.NewDoubleValue(20), v)
+	})
+
+	t.Run("Should fail if the fields cannot be converted to specified field constraints", func(t *testing.T) {
+		tx, cleanup := newTestDB(t)
+		defer cleanup()
+
+		err := tx.CreateTable("test", &database.TableInfo{
+			FieldConstraints: []database.FieldConstraint{
+				{parsePath(t, "foo"), document.DoubleValue, false, false, document.Value{}},
+			},
+		})
+		require.NoError(t, err)
+		tb, err := tx.GetTable("test")
+		require.NoError(t, err)
+
+		doc := document.NewFieldBuffer().
+			Add("foo", document.NewArrayValue(document.NewValueBuffer(document.NewIntegerValue(1))))
+
+		// insert
+		_, err = tb.Insert(doc)
+		require.Error(t, err)
 	})
 
 	t.Run("Should fail if there is a not null field constraint on a document field and the field is null or missing", func(t *testing.T) {
@@ -705,7 +730,7 @@ func TestTableReIndex(t *testing.T) {
 
 		countIndexElems := func(idx *database.Index) int {
 			var i int
-			err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
+			err = idx.AscendGreaterOrEqual(document.Value{Type: document.DoubleValue}, func(v, k []byte, isEqual bool) error {
 				i++
 				return nil
 			})
diff --git a/database/transaction_test.go b/database/transaction_test.go
index 98e0e59a..d3f6a8e9 100644
--- a/database/transaction_test.go
+++ b/database/transaction_test.go
@@ -1,6 +1,7 @@
 package database_test
 
 import (
+	"bytes"
 	"context"
 	"errors"
 	"testing"
@@ -9,7 +10,6 @@ import (
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/document/encoding/msgpack"
 	"github.com/genjidb/genji/engine/memoryengine"
-	"github.com/genjidb/genji/key"
 	"github.com/stretchr/testify/require"
 )
 
@@ -361,9 +361,11 @@ func TestTxReIndex(t *testing.T) {
 		require.NoError(t, err)
 
 		var i int
-		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+		err = idx.AscendGreaterOrEqual(document.Value{Type: document.DoubleValue}, func(v, k []byte, isEqual bool) error {
+			var buf bytes.Buffer
+			err = document.NewValueEncoder(&buf).Encode(document.NewDoubleValue(float64(i)))
 			require.NoError(t, err)
+			enc := buf.Bytes()
 			require.Equal(t, enc, v)
 			i++
 			return nil
@@ -440,9 +442,11 @@ func TestReIndexAll(t *testing.T) {
 		require.NoError(t, err)
 
 		var i int
-		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+		err = idx.AscendGreaterOrEqual(document.Value{Type: document.DoubleValue}, func(v, k []byte, isEqual bool) error {
+			var buf bytes.Buffer
+			err = document.NewValueEncoder(&buf).Encode(document.NewDoubleValue(float64(i)))
 			require.NoError(t, err)
+			enc := buf.Bytes()
 			require.Equal(t, enc, v)
 			i++
 			return nil
@@ -454,9 +458,11 @@ func TestReIndexAll(t *testing.T) {
 		require.NoError(t, err)
 
 		i = 0
-		err = idx.AscendGreaterOrEqual(document.Value{Type: document.IntegerValue}, func(v, k []byte, isEqual bool) error {
-			enc, err := key.AppendValue(nil, document.NewIntegerValue(int64(i)))
+		err = idx.AscendGreaterOrEqual(document.Value{Type: document.DoubleValue}, func(v, k []byte, isEqual bool) error {
+			var buf bytes.Buffer
+			err = document.NewValueEncoder(&buf).Encode(document.NewDoubleValue(float64(i)))
 			require.NoError(t, err)
+			enc := buf.Bytes()
 			require.Equal(t, enc, v)
 			i++
 			return nil
diff --git a/document/array_test.go b/document/array_test.go
index 725ece3d..432354a8 100644
--- a/document/array_test.go
+++ b/document/array_test.go
@@ -76,3 +76,17 @@ func TestValueBufferCopy(t *testing.T) {
 		})
 	}
 }
+
+func TestValueBufferApply(t *testing.T) {
+	var buf ValueBuffer
+	err := buf.UnmarshalJSON([]byte(`[1, [1, 3], {"4": 5}]`))
+	require.NoError(t, err)
+
+	err = buf.Apply(func(p Path, v Value) (Value, error) {
+		return NewIntegerValue(6), nil
+	})
+	require.NoError(t, err)
+
+	got, err := json.Marshal(buf)
+	require.JSONEq(t, `[6, [6, 6], {"4": 6}]`, string(got))
+}
diff --git a/document/compare_test.go b/document/compare_test.go
index abdc2d61..387fe56f 100644
--- a/document/compare_test.go
+++ b/document/compare_test.go
@@ -158,7 +158,7 @@ func TestCompare(t *testing.T) {
 		{"=", `[]`, `[]`, true, jsonToArray},
 		{"=", `[1]`, `[1]`, true, jsonToArray},
 		{"=", `[1]`, `[]`, false, jsonToArray},
-		{"=", `[1.0, 2]`, `[1, 2]`, true, jsonToArray},
+		{"=", `[1.0, 2]`, `[1, 2]`, false, jsonToArray},
 		{"=", `[1,2,3]`, `[1,2,3]`, true, jsonToArray},
 		{"!=", `[1]`, `[5]`, true, jsonToArray},
 		{"!=", `[1]`, `[1, 1]`, true, jsonToArray},
diff --git a/document/document_test.go b/document/document_test.go
index ff624b0e..960cd059 100644
--- a/document/document_test.go
+++ b/document/document_test.go
@@ -171,6 +171,30 @@ func TestFieldBuffer(t *testing.T) {
 		require.Error(t, err)
 	})
 
+	t.Run("Apply", func(t *testing.T) {
+		d := document.NewFromJSON([]byte(`{
+			"a": "b",
+			"c": ["d", "e"],
+			"f": {"g": "h"}
+		}`))
+
+		buf := document.NewFieldBuffer()
+		err := buf.Copy(d)
+		require.NoError(t, err)
+
+		err = buf.Apply(func(p document.Path, v document.Value) (document.Value, error) {
+			if v.Type == document.ArrayValue || v.Type == document.DocumentValue {
+				return v, nil
+			}
+
+			return document.NewIntegerValue(1), nil
+		})
+		require.NoError(t, err)
+
+		got, err := json.Marshal(buf)
+		require.JSONEq(t, `{"a": 1, "c": [1, 1], "f": {"g": 1}}`, string(got))
+	})
+
 	t.Run("UnmarshalJSON", func(t *testing.T) {
 		tests := []struct {
 			name     string
diff --git a/document/value_encoding_test.go b/document/value_encoding_test.go
new file mode 100644
index 00000000..5ea39433
--- /dev/null
+++ b/document/value_encoding_test.go
@@ -0,0 +1,77 @@
+package document
+
+import (
+	"bytes"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+func TestValueEncoder(t *testing.T) {
+	tests := []struct {
+		name string
+		v    Value
+	}{
+		{"null", NewNullValue()},
+		{"bool", NewBoolValue(true)},
+		{"integer", NewIntegerValue(-10)},
+		{"double", NewDoubleValue(-3.14)},
+		{"text", NewTextValue("foo")},
+		{"blob", NewBlobValue([]byte("bar"))},
+		{"array", NewArrayValue(NewValueBuffer(
+			NewBoolValue(true),
+			NewIntegerValue(55),
+			NewDoubleValue(789.58),
+			NewArrayValue(NewValueBuffer(
+				NewBoolValue(false),
+				NewIntegerValue(100),
+				NewTextValue("baz"),
+			)),
+			NewBlobValue([]byte("loo")),
+			NewDocumentValue(
+				NewFieldBuffer().
+					Add("foo1", NewBoolValue(true)).
+					Add("foo2", NewIntegerValue(55)).
+					Add("foo3", NewArrayValue(NewValueBuffer(
+						NewBoolValue(false),
+						NewIntegerValue(100),
+						NewTextValue("baz"),
+					))),
+			),
+		))},
+		{"document", NewDocumentValue(
+			NewFieldBuffer().
+				Add("foo1", NewBoolValue(true)).
+				Add("foo2", NewIntegerValue(55)).
+				Add("foo3", NewArrayValue(NewValueBuffer(
+					NewBoolValue(false),
+					NewIntegerValue(100),
+					NewTextValue("baz"),
+				))).
+				Add("foo4", NewDocumentValue(
+					NewFieldBuffer().
+						Add("foo1", NewBoolValue(true)).
+						Add("foo2", NewIntegerValue(55)).
+						Add("foo3", NewArrayValue(NewValueBuffer(
+							NewBoolValue(false),
+							NewIntegerValue(100),
+							NewTextValue("baz"),
+						))),
+				)),
+		)},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			var buf bytes.Buffer
+
+			enc := NewValueEncoder(&buf)
+			err := enc.Encode(test.v)
+			require.NoError(t, err)
+
+			got, err := decodeValue(buf.Bytes())
+			require.NoError(t, err)
+			require.Equal(t, test.v, got)
+		})
+	}
+}
diff --git a/document/value_test.go b/document/value_test.go
index 4b9a502f..181217f9 100644
--- a/document/value_test.go
+++ b/document/value_test.go
@@ -21,8 +21,8 @@ func TestValueString(t *testing.T) {
 		{"bool", document.NewBoolValue(true), "true"},
 		{"int", document.NewIntegerValue(10), "10"},
 		{"double", document.NewDoubleValue(10.1), "10.1"},
-		{"double with trailing .0", document.NewDoubleValue(10), "10.0"},
-		{"big double with trailing .0", document.NewDoubleValue(1e21), "1.0e+21"},
+		{"double with no decimal", document.NewDoubleValue(10), "10"},
+		{"big double", document.NewDoubleValue(1e21), "1e+21"},
 		{"document", document.NewDocumentValue(document.NewFieldBuffer().Add("a", document.NewIntegerValue(10))), "{\"a\": 10}"},
 		{"array", document.NewArrayValue(document.NewValueBuffer(document.NewIntegerValue(10))), "[10]"},
 	}
@@ -374,3 +374,70 @@ func TestValueBitwiseXor(t *testing.T) {
 		})
 	}
 }
+
+func TestValueBinaryMarshaling(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"))},
+		{"array", document.NewArrayValue(document.NewValueBuffer(
+			document.NewBoolValue(true),
+			document.NewIntegerValue(55),
+			document.NewDoubleValue(789.58),
+			document.NewArrayValue(document.NewValueBuffer(
+				document.NewBoolValue(false),
+				document.NewIntegerValue(100),
+				document.NewTextValue("baz"),
+			)),
+			document.NewBlobValue([]byte("loo")),
+			document.NewDocumentValue(
+				document.NewFieldBuffer().
+					Add("foo1", document.NewBoolValue(true)).
+					Add("foo2", document.NewIntegerValue(55)).
+					Add("foo3", document.NewArrayValue(document.NewValueBuffer(
+						document.NewBoolValue(false),
+						document.NewIntegerValue(100),
+						document.NewTextValue("baz"),
+					))),
+			),
+		))},
+		{"document", document.NewDocumentValue(
+			document.NewFieldBuffer().
+				Add("foo1", document.NewBoolValue(true)).
+				Add("foo2", document.NewIntegerValue(55)).
+				Add("foo3", document.NewArrayValue(document.NewValueBuffer(
+					document.NewBoolValue(false),
+					document.NewIntegerValue(100),
+					document.NewTextValue("baz"),
+				))).
+				Add("foo4", document.NewDocumentValue(
+					document.NewFieldBuffer().
+						Add("foo1", document.NewBoolValue(true)).
+						Add("foo2", document.NewIntegerValue(55)).
+						Add("foo3", document.NewArrayValue(document.NewValueBuffer(
+							document.NewBoolValue(false),
+							document.NewIntegerValue(100),
+							document.NewTextValue("baz"),
+						))),
+				)),
+		)},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			b, err := test.v.MarshalBinary()
+			require.NoError(t, err)
+
+			got := document.Value{Type: test.v.Type}
+			err = got.UnmarshalBinary(b)
+			require.NoError(t, err)
+			require.Equal(t, test.v, got)
+		})
+	}
+}
diff --git a/example_test.go b/example_test.go
index 7f1118b7..f5f114d9 100644
--- a/example_test.go
+++ b/example_test.go
@@ -111,7 +111,7 @@ func Example() {
 			if err != nil {
 				return false, err
 			}
-			return v.V.(int64)%2 == 0, err
+			return int64(v.V.(float64))%2 == 0, err
 		}).
 		// Enrich the documents with a new field
 		Map(func(d document.Document) (document.Document, error) {
diff --git a/index/index_test.go b/index/index_test.go
index f7849a8c..f184f581 100644
--- a/index/index_test.go
+++ b/index/index_test.go
@@ -2,17 +2,18 @@
 package index_test
 
 import (
+	"bytes"
 	"context"
 	"errors"
 	"fmt"
 	"strconv"
 	"testing"
 
+	"github.com/genjidb/genji/binarysort"
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/engine"
 	"github.com/genjidb/genji/engine/memoryengine"
 	"github.com/genjidb/genji/index"
-	"github.com/genjidb/genji/key"
 	"github.com/stretchr/testify/require"
 )
 
@@ -23,7 +24,7 @@ func getIndex(t testing.TB, unique bool) (*index.Index, func()) {
 	})
 	require.NoError(t, err)
 
-	idx := index.NewIndex(tx, "foo", index.Options{Unique: unique})
+	idx := index.New(tx, "foo", index.Options{Unique: unique})
 
 	return idx, func() {
 		tx.Rollback()
@@ -145,9 +146,10 @@ func TestIndexDelete(t *testing.T) {
 func requireEqualEncoded(t *testing.T, expected document.Value, actual []byte) {
 	t.Helper()
 
-	enc, err := key.AppendValue(nil, expected)
+	var buf bytes.Buffer
+	err := document.NewValueEncoder(&buf).Encode(expected)
 	require.NoError(t, err)
-	require.Equal(t, enc, actual)
+	require.Equal(t, buf.Bytes(), actual)
 }
 
 func TestIndexAscendGreaterThan(t *testing.T) {
@@ -243,13 +245,13 @@ 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.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)}))
+				require.NoError(t, idx.Set(document.NewTextValue(strconv.Itoa(int(i))), []byte{'s', 'a' + byte(i)}))
 			}
 
 			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 {
+				if count < 10 {
 					requireEqualEncoded(t, document.NewIntegerValue(int64(ints)), val)
 					require.Equal(t, []byte{'i', 'a' + byte(ints)}, rid)
 					ints++
@@ -258,7 +260,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 					require.Equal(t, []byte{'d', 'a' + byte(doubles)}, rid)
 					doubles++
 				} else {
-					requireEqualEncoded(t, document.NewTextValue(strconv.Itoa(int(texts+10))), val)
+					requireEqualEncoded(t, document.NewTextValue(strconv.Itoa(int(texts))), val)
 					require.Equal(t, []byte{'s', 'a' + byte(texts)}, rid)
 					texts++
 				}
@@ -282,7 +284,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 
 			var ints int
 			err := idx.AscendGreaterOrEqual(document.Value{}, func(val, rid []byte, isEqual bool) error {
-				enc, err := key.Append(nil, document.IntegerValue, int64(ints))
+				enc, err := document.NewIntegerValue(int64(ints)).MarshalBinary()
 				require.NoError(t, err)
 				require.Equal(t, enc, val)
 				require.Equal(t, []byte{'i', 'a' + byte(ints)}, rid)
@@ -300,15 +302,15 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 		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)))
+			require.NoError(t, idx.Set(document.NewIntegerValue(1), binarysort.AppendInt64(nil, i)))
+			require.NoError(t, idx.Set(document.NewTextValue("1"), binarysort.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.NewIntegerValue(1), val)
-			require.Equal(t, key.AppendInt64(nil, i), rid)
+			require.Equal(t, binarysort.AppendInt64(nil, i), rid)
 			i++
 			ints++
 			return nil
@@ -317,7 +319,7 @@ func TestIndexAscendGreaterThan(t *testing.T) {
 		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)
+			require.Equal(t, binarysort.AppendInt64(nil, i), rid)
 			i++
 			texts++
 			return nil
diff --git a/key/encoding_test.go b/key/encoding_test.go
deleted file mode 100644
index e0e52781..00000000
--- a/key/encoding_test.go
+++ /dev/null
@@ -1,226 +0,0 @@
-package key
-
-import (
-	"bytes"
-	"math"
-	"sort"
-	"testing"
-
-	"github.com/genjidb/genji/document"
-	"github.com/stretchr/testify/require"
-)
-
-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"))},
-		{"array", document.NewArrayValue(document.NewValueBuffer(
-			document.NewBoolValue(true),
-			document.NewIntegerValue(55),
-			document.NewDoubleValue(789.58),
-			document.NewArrayValue(document.NewValueBuffer(
-				document.NewBoolValue(false),
-				document.NewIntegerValue(100),
-				document.NewTextValue("baz"),
-			)),
-			document.NewBlobValue([]byte("loo")),
-			document.NewDocumentValue(
-				document.NewFieldBuffer().
-					Add("foo1", document.NewBoolValue(true)).
-					Add("foo2", document.NewIntegerValue(55)).
-					Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-						document.NewBoolValue(false),
-						document.NewIntegerValue(100),
-						document.NewTextValue("baz"),
-					))),
-			),
-		))},
-		{"document", document.NewDocumentValue(
-			document.NewFieldBuffer().
-				Add("foo1", document.NewBoolValue(true)).
-				Add("foo2", document.NewIntegerValue(55)).
-				Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-					document.NewBoolValue(false),
-					document.NewIntegerValue(100),
-					document.NewTextValue("baz"),
-				))).
-				Add("foo4", document.NewDocumentValue(
-					document.NewFieldBuffer().
-						Add("foo1", document.NewBoolValue(true)).
-						Add("foo2", document.NewIntegerValue(55)).
-						Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-							document.NewBoolValue(false),
-							document.NewIntegerValue(100),
-							document.NewTextValue("baz"),
-						))),
-				)),
-		)},
-	}
-
-	for _, test := range tests {
-		t.Run(test.name, func(t *testing.T) {
-			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 TestAppendValueDecodeValue(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"))},
-		{"array", document.NewArrayValue(document.NewValueBuffer(
-			document.NewBoolValue(true),
-			document.NewIntegerValue(55),
-			document.NewDoubleValue(789.58),
-			document.NewArrayValue(document.NewValueBuffer(
-				document.NewBoolValue(false),
-				document.NewIntegerValue(100),
-				document.NewTextValue("baz"),
-			)),
-			document.NewBlobValue([]byte("loo")),
-			document.NewDocumentValue(
-				document.NewFieldBuffer().
-					Add("foo1", document.NewBoolValue(true)).
-					Add("foo2", document.NewIntegerValue(55)).
-					Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-						document.NewBoolValue(false),
-						document.NewIntegerValue(100),
-						document.NewTextValue("baz"),
-					))),
-			),
-		))},
-		{"document", document.NewDocumentValue(
-			document.NewFieldBuffer().
-				Add("foo1", document.NewBoolValue(true)).
-				Add("foo2", document.NewIntegerValue(55)).
-				Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-					document.NewBoolValue(false),
-					document.NewIntegerValue(100),
-					document.NewTextValue("baz"),
-				))).
-				Add("foo4", document.NewDocumentValue(
-					document.NewFieldBuffer().
-						Add("foo1", document.NewBoolValue(true)).
-						Add("foo2", document.NewIntegerValue(55)).
-						Add("foo3", document.NewArrayValue(document.NewValueBuffer(
-							document.NewBoolValue(false),
-							document.NewIntegerValue(100),
-							document.NewTextValue("baz"),
-						))),
-				)),
-		)},
-	}
-
-	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)
-		})
-	}
-}
-
-const Rng = 1000
-
-func TestOrdering(t *testing.T) {
-	tests := []struct {
-		name     string
-		min, max int
-		enc      func([]byte, int) []byte
-	}{
-		{"uint64", 0, 1000, func(buf []byte, i int) []byte { return AppendUint64(buf, uint64(i)) }},
-		{"int64", -1000, 1000, func(buf []byte, i int) []byte { return AppendInt64(buf, int64(i)) }},
-		{"float64", -1000, 1000, func(buf []byte, i int) []byte { return AppendFloat64(buf, float64(i)) }},
-		{"text", -1000, 1000, func(buf []byte, i int) []byte {
-			b, err := AppendValue(nil, document.NewTextValue(string(AppendInt64(buf, int64(i)))))
-			require.NoError(t, err)
-			return b
-		}},
-	}
-
-	for _, test := range tests {
-		t.Run(test.name, func(t *testing.T) {
-			var prev, cur []byte
-			for i := test.min; i < test.max; i++ {
-				cur = test.enc(cur[:0], i)
-				if prev == nil {
-					prev = append(prev[:0], cur...)
-					continue
-				}
-
-				require.Equal(t, -1, bytes.Compare(prev, cur))
-				prev = append(prev[:0], cur...)
-			}
-		})
-	}
-
-	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)
-		}
-	})
-}
diff --git a/sql/planner/optimizer_test.go b/sql/planner/optimizer_test.go
index 6dc52898..a0f8928e 100644
--- a/sql/planner/optimizer_test.go
+++ b/sql/planner/optimizer_test.go
@@ -5,12 +5,19 @@ import (
 
 	"github.com/genjidb/genji"
 	"github.com/genjidb/genji/document"
+	"github.com/genjidb/genji/sql/parser"
 	"github.com/genjidb/genji/sql/planner"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
 	"github.com/stretchr/testify/require"
 )
 
+func parsePath(t testing.TB, str string) document.Path {
+	vp, err := parser.ParsePath(str)
+	require.NoError(t, err)
+	return vp
+}
+
 func TestSplitANDConditionRule(t *testing.T) {
 	tests := []struct {
 		name           string
@@ -344,6 +351,7 @@ func TestUseIndexBasedOnSelectionNodeRule(t *testing.T) {
 				"foo",
 				"idx_foo_a",
 				expr.Eq(nil, nil).(planner.IndexIteratorOperator),
+				expr.Path(parsePath(t, "a")),
 				expr.IntegerValue(1),
 				scanner.ASC,
 			),
@@ -367,6 +375,7 @@ func TestUseIndexBasedOnSelectionNodeRule(t *testing.T) {
 					"foo",
 					"idx_foo_b",
 					expr.Eq(nil, nil).(planner.IndexIteratorOperator),
+					expr.Path(parsePath(t, "b")),
 					expr.IntegerValue(2),
 					scanner.ASC,
 				),
@@ -395,6 +404,7 @@ func TestUseIndexBasedOnSelectionNodeRule(t *testing.T) {
 					"foo",
 					"idx_foo_c",
 					expr.Eq(nil, nil).(planner.IndexIteratorOperator),
+					expr.Path(parsePath(t, "c")),
 					expr.IntegerValue(3),
 					scanner.ASC,
 				),
@@ -432,6 +442,7 @@ func TestUseIndexBasedOnSelectionNodeRule(t *testing.T) {
 						"foo",
 						"idx_foo_c",
 						expr.Eq(nil, nil).(planner.IndexIteratorOperator),
+						expr.Path(parsePath(t, "c")),
 						expr.IntegerValue(3),
 						scanner.ASC,
 					),
diff --git a/sql/query/create_test.go b/sql/query/create_test.go
index 0e8689bd..54c09e28 100644
--- a/sql/query/create_test.go
+++ b/sql/query/create_test.go
@@ -82,7 +82,7 @@ func TestCreateTable(t *testing.T) {
 					return err
 				}
 
-				require.Equal(t, []database.FieldConstraint{
+				require.Equal(t, database.FieldConstraints{
 					{Path: parsePath(t, "d"), Type: document.DoubleValue},
 					{Path: parsePath(t, "b"), Type: document.BoolValue},
 				}, info.FieldConstraints)
@@ -110,7 +110,7 @@ func TestCreateTable(t *testing.T) {
 					return err
 				}
 
-				require.Equal(t, []database.FieldConstraint{
+				require.Equal(t, database.FieldConstraints{
 					{Path: parsePath(t, "foo.bar[1].hello"), Type: document.BlobValue, IsPrimaryKey: true},
 					{Path: parsePath(t, "foo.a[1][2]"), Type: document.TextValue, IsNotNull: true},
 					{Path: parsePath(t, "bar[4][0].bat"), Type: document.IntegerValue},
@@ -144,7 +144,7 @@ func TestCreateTable(t *testing.T) {
 					return err
 				}
 
-				require.Equal(t, []database.FieldConstraint{
+				require.Equal(t, database.FieldConstraints{
 					{Path: parsePath(t, "foo.bar[1].hello"), Type: document.BlobValue, IsPrimaryKey: true},
 					{Path: parsePath(t, "foo.a[1][2]"), Type: document.TextValue, IsNotNull: true},
 					{Path: parsePath(t, "bar[4][0].bat"), Type: document.IntegerValue},
@@ -161,6 +161,46 @@ func TestCreateTable(t *testing.T) {
 			require.NoError(t, err)
 		})
 
+		t.Run("default values", func(t *testing.T) {
+			tests := []struct {
+				name        string
+				query       string
+				constraints database.FieldConstraints
+				fails       bool
+			}{
+				{"With default, no type and integer default", "CREATE TABLE test(foo DEFAULT 10)", database.FieldConstraints{{Path: parsePath(t, "foo"), DefaultValue: document.NewDoubleValue(10)}}, false},
+				{"With default, double type and integer default", "CREATE TABLE test(foo DOUBLE DEFAULT 10)", database.FieldConstraints{{Path: parsePath(t, "foo"), Type: document.DoubleValue, DefaultValue: document.NewDoubleValue(10)}}, false},
+				{"With default, some type and compatible default", "CREATE TABLE test(foo BOOL DEFAULT 10)", database.FieldConstraints{{Path: parsePath(t, "foo"), Type: document.BoolValue, DefaultValue: document.NewBoolValue(true)}}, false},
+				{"With default, some type and incompatible default", "CREATE TABLE test(foo BOOL DEFAULT 10.5)", nil, true},
+			}
+
+			for _, test := range tests {
+				t.Run(test.name, func(t *testing.T) {
+					db, err := genji.Open(":memory:")
+					require.NoError(t, err)
+					defer db.Close()
+
+					err = db.Exec(test.query)
+					if test.fails {
+						require.Error(t, err)
+						return
+					}
+					require.NoError(t, err)
+
+					err = db.View(func(tx *genji.Tx) error {
+						tb, err := tx.GetTable("test")
+						info, err := tb.Info()
+						if err != nil {
+							return err
+						}
+
+						require.Equal(t, test.constraints, info.FieldConstraints)
+						return err
+					})
+					require.NoError(t, err)
+				})
+			}
+		})
 	})
 }
 
diff --git a/sql/query/expr/comparison_test.go b/sql/query/expr/comparison_test.go
index eb222bd6..c6ab5768 100644
--- a/sql/query/expr/comparison_test.go
+++ b/sql/query/expr/comparison_test.go
@@ -3,8 +3,11 @@ package expr_test
 import (
 	"testing"
 
+	"github.com/genjidb/genji"
+	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/sql/query/expr"
+	"github.com/stretchr/testify/require"
 )
 
 func TestComparisonExpr(t *testing.T) {
@@ -158,3 +161,78 @@ func TestComparisonExprNodocument(t *testing.T) {
 		})
 	}
 }
+
+func TestIndexedComparisonExpr(t *testing.T) {
+	type idxOp interface {
+		IterateIndex(idx *database.Index, tb *database.Table, v document.Value, fn func(d document.Document) error) error
+	}
+
+	tests := []struct {
+		op       expr.Expr
+		v        document.Value
+		expected []interface{}
+		fails    bool
+	}{
+		{expr.Eq(nil, nil), document.NewDoubleValue(5), []interface{}{5.0}, false},
+		{expr.Eq(nil, nil), document.NewDoubleValue(50), nil, false},
+		{expr.Gt(nil, nil), document.NewDoubleValue(0), []interface{}{1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+		{expr.Gt(nil, nil), document.NewDoubleValue(10), nil, false},
+		{expr.Gt(nil, nil), document.NewDoubleValue(-100), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+		{expr.Gte(nil, nil), document.NewDoubleValue(0), []interface{}{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+		{expr.Gte(nil, nil), document.NewDoubleValue(10), nil, false},
+		{expr.Gte(nil, nil), document.NewDoubleValue(-100), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+		{expr.Lt(nil, nil), document.NewDoubleValue(0), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0}, false},
+		{expr.Lt(nil, nil), document.NewDoubleValue(-11), nil, false},
+		{expr.Lt(nil, nil), document.NewDoubleValue(100), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+		{expr.Lte(nil, nil), document.NewDoubleValue(0), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0, 0.0}, false},
+		{expr.Lte(nil, nil), document.NewDoubleValue(-11), nil, false},
+		{expr.Lte(nil, nil), document.NewDoubleValue(100), []interface{}{-10.0, -9.0, -8.0, -7.0, -6.0, -5.0, -4.0, -3.0, -2.0, -1.0, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, false},
+	}
+
+	db, err := genji.Open(":memory:")
+	require.NoError(t, err)
+	defer db.Close()
+
+	err = db.Update(func(tx *genji.Tx) error {
+		err = tx.Exec("CREATE TABLE foo; CREATE INDEX idx_foo ON foo(a)")
+		if err != nil {
+			return err
+		}
+		for i := -10; i < 10; i++ {
+			err = tx.Exec("INSERT INTO foo(a) VALUES (?)", i)
+			if err != nil {
+				return err
+			}
+		}
+
+		return nil
+	})
+	require.NoError(t, err)
+
+	for _, test := range tests {
+		t.Run(test.op.(expr.Operator).Token().String(), func(t *testing.T) {
+			tx, err := db.Begin(true)
+			require.NoError(t, err)
+			defer tx.Rollback()
+
+			tb, err := tx.GetTable("foo")
+			require.NoError(t, err)
+			idx, err := tx.GetIndex("idx_foo")
+			require.NoError(t, err)
+
+			var docs []interface{}
+
+			err = test.op.(idxOp).IterateIndex(idx, tb, test.v, func(d document.Document) error {
+				v, err := d.GetByField("a")
+				if err != nil {
+					return err
+				}
+				docs = append(docs, v.V)
+				return nil
+			})
+			require.NoError(t, err)
+
+			require.Equal(t, test.expected, docs)
+		})
+	}
+}
diff --git a/sql/query/select_test.go b/sql/query/select_test.go
index c9daace0..160817a6 100644
--- a/sql/query/select_test.go
+++ b/sql/query/select_test.go
@@ -297,3 +297,63 @@ func TestDistinct(t *testing.T) {
 		})
 	}
 }
+
+// func TestSelectIndexedDoubleAndIntegers(t *testing.T) {
+// 	tests := []struct {
+// 		a      interface{}
+// 		query  string
+// 		isTrue bool
+// 		param  interface{}
+// 	}{
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a = ?", true, math.MaxInt64},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a > ?", false, math.MaxInt64},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a > ?", true, math.MaxInt64 - 1},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a >= ?", true, math.MaxInt64},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a >= 9223372036854775807.0", true, nil},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a > 9223372036854775800.0", false, nil},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a < 9223372036854775800.0", false, nil},
+// 		{math.MaxInt64, "SELECT true FROM test WHERE a = 9223372036854775800.0", true, nil},
+// 	}
+
+// 	for _, indexed := range []bool{false, true} {
+// 		for _, test := range tests {
+// 			t.Run(fmt.Sprintf("indexed: %v / %q", indexed, test.query), func(t *testing.T) {
+// 				fmt.Println("---")
+// 				db, err := genji.Open(":memory:")
+// 				require.NoError(t, err)
+// 				defer db.Close()
+
+// 				tx, err := db.Begin(true)
+// 				require.NoError(t, err)
+// 				defer tx.Rollback()
+
+// 				err = tx.Exec("CREATE TABLE test")
+// 				require.NoError(t, err)
+
+// 				if indexed {
+// 					err = tx.Exec("CREATE INDEX idx_foo_a ON test(a)")
+// 					require.NoError(t, err)
+// 				}
+
+// 				// a = math.MaxInt64
+// 				err = tx.Exec("INSERT INTO test (a) VALUES (?)", test.a)
+// 				require.NoError(t, err)
+
+// 				var params []interface{}
+// 				if test.param != nil {
+// 					params = append(params, test.param)
+// 				}
+// 				doc, err := tx.QueryDocument(test.query, params...)
+// 				if test.isTrue {
+// 					require.NoError(t, err)
+// 					var got bool
+// 					err = document.Scan(doc, &got)
+// 					require.NoError(t, err)
+// 					require.True(t, got)
+// 				} else {
+// 					require.Equal(t, database.ErrDocumentNotFound, err)
+// 				}
+// 			})
+// 		}
+// 	}
+// }