Repository: genjidb/genji
Pull request #199 (2020-09-25 19:27:11)

Support for array and document indexing
This PR adds support for array and document indexing, as well as being able to use them as primary keys


Patch:
diff --git a/database/table.go b/database/table.go
index 3d277831..6c7924d5 100644
--- a/database/table.go
+++ b/database/table.go
@@ -92,11 +92,6 @@ func (t *Table) Insert(d document.Document) ([]byte, error) {
 			v = document.NewNullValue()
 		}
 
-		// arrays and documents are not indexed.
-		if v.Type == document.ArrayValue || v.Type == document.DocumentValue {
-			continue
-		}
-
 		err = idx.Set(v, key)
 		if err != nil {
 			if err == index.ErrDuplicate {
diff --git a/document/compare.go b/document/compare.go
index 74972415..e1d1cb19 100644
--- a/document/compare.go
+++ b/document/compare.go
@@ -35,7 +35,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)
+	return compare(operatorEq, v, other, false)
 }
 
 // IsNotEqual returns true if v is not equal to the given value.
@@ -50,25 +50,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)
+	return compare(operatorGt, v, other, false)
 }
 
 // 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)
+	return compare(operatorGte, v, other, false)
 }
 
 // IsLesserThan returns true if v is lesser than the given value.
 func (v Value) IsLesserThan(other Value) (bool, error) {
-	return compare(operatorLt, v, other)
+	return compare(operatorLt, v, other, false)
 }
 
 // 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)
+	return compare(operatorLte, v, other, false)
 }
 
-func compare(op operator, l, r Value) (bool, error) {
+func compare(op operator, l, r Value, compareDifferentTypes bool) (bool, error) {
 	switch {
 	// deal with nil
 	case l.Type == NullValue || r.Type == NullValue:
@@ -97,6 +97,25 @@ func compare(op operator, l, r Value) (bool, error) {
 	// compare durations together
 	case l.Type == DurationValue && r.Type == DurationValue:
 		return compareIntegers(op, int64(l.V.(time.Duration)), int64(r.V.(time.Duration))), nil
+
+	// compare arrays together
+	case l.Type == ArrayValue && r.Type == ArrayValue:
+		return compareArrays(op, l.V.(Array), r.V.(Array))
+
+	// compare documents together
+	case l.Type == DocumentValue && r.Type == DocumentValue:
+		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
@@ -213,3 +232,161 @@ func compareNumbers(op operator, l, r Value) (bool, error) {
 
 	return ok, nil
 }
+
+func compareArrays(op operator, l Array, r Array) (bool, error) {
+	var i, j int
+
+	for {
+		lv, lerr := l.GetByIndex(i)
+		rv, rerr := r.GetByIndex(j)
+		if lerr == nil {
+			i++
+		}
+		if rerr == nil {
+			j++
+		}
+		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
+		}
+	}
+
+	switch {
+	case i > j:
+		switch op {
+		case operatorEq, operatorLt, operatorLte:
+			return false, nil
+		default:
+			return true, nil
+		}
+	case i < j:
+		switch op {
+		case operatorEq, operatorGt, operatorGte:
+			return false, nil
+		default:
+			return true, nil
+		}
+	default:
+		switch op {
+		case operatorEq, operatorGte, operatorLte:
+			return true, nil
+		default:
+			return false, nil
+		}
+	}
+}
+
+func compareDocuments(op operator, l, r Document) (bool, error) {
+	lf, err := Fields(l)
+	if err != nil {
+		return false, err
+	}
+	rf, err := Fields(r)
+	if err != nil {
+		return false, err
+	}
+
+	if len(lf) == 0 && len(rf) > 0 {
+		switch op {
+		case operatorEq:
+			return false, nil
+		case operatorGt:
+			return false, nil
+		case operatorGte:
+			return false, nil
+		case operatorLt:
+			return true, nil
+		case operatorLte:
+			return true, nil
+		}
+	}
+
+	if len(rf) == 0 && len(lf) > 0 {
+		switch op {
+		case operatorEq:
+			return false, nil
+		case operatorGt:
+			return true, nil
+		case operatorGte:
+			return true, nil
+		case operatorLt:
+			return false, nil
+		case operatorLte:
+			return false, nil
+		}
+	}
+
+	var i, j int
+
+	for i < len(lf) && j < len(rf) {
+		if cmp := strings.Compare(lf[i], rf[j]); cmp != 0 {
+			switch op {
+			case operatorEq:
+				return false, nil
+			case operatorGt:
+				return cmp > 0, nil
+			case operatorGte:
+				return cmp >= 0, nil
+			case operatorLt:
+				return cmp < 0, nil
+			case operatorLte:
+				return cmp <= 0, nil
+			}
+		}
+
+		lv, lerr := l.GetByField(lf[i])
+		rv, rerr := r.GetByField(rf[j])
+		if lerr == nil {
+			i++
+		}
+		if rerr == nil {
+			j++
+		}
+		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
+		}
+	}
+
+	switch {
+	case i > j:
+		switch op {
+		case operatorEq, operatorLt, operatorLte:
+			return false, nil
+		default:
+			return true, nil
+		}
+	case i < j:
+		switch op {
+		case operatorEq, operatorGt, operatorGte:
+			return false, nil
+		default:
+			return true, nil
+		}
+	default:
+		switch op {
+		case operatorEq, operatorGte, operatorLte:
+			return true, nil
+		default:
+			return false, nil
+		}
+	}
+}
diff --git a/document/document.go b/document/document.go
index 93fcf6a6..2c22dba0 100644
--- a/document/document.go
+++ b/document/document.go
@@ -3,6 +3,7 @@ package document
 
 import (
 	"errors"
+	"sort"
 	"strconv"
 	"strings"
 )
@@ -41,6 +42,26 @@ func Length(d Document) (int, error) {
 	return len, err
 }
 
+// Fields returns a list of all the fields at the root of the document
+// sorted lexicographically.
+func Fields(d Document) ([]string, error) {
+	if fb, ok := d.(*FieldBuffer); ok {
+		return fb.Fields(), nil
+	}
+
+	var fields []string
+	err := d.Iterate(func(f string, _ Value) error {
+		fields = append(fields, f)
+		return nil
+	})
+	if err != nil {
+		return nil, err
+	}
+
+	sort.Strings(fields)
+	return fields, nil
+}
+
 // FieldBuffer stores a group of fields in memory. It implements the Document interface.
 type FieldBuffer struct {
 	fields []fieldValue
@@ -260,6 +281,18 @@ func (fb *FieldBuffer) Key() []byte {
 	return fb.key
 }
 
+// Fields returns a sorted list of root field names.
+func (fb *FieldBuffer) Fields() []string {
+	fields := make([]string, len(fb.fields))
+
+	for i := range fb.fields {
+		fields[i] = fb.fields[i].Field
+	}
+
+	sort.Strings(fields)
+	return fields
+}
+
 // A ValuePath represents the path to a particular value within a document.
 type ValuePath []ValuePathFragment
 
diff --git a/document/value.go b/document/value.go
index e66e4940..df1ef89e 100644
--- a/document/value.go
+++ b/document/value.go
@@ -36,30 +36,30 @@ type ValueType uint8
 // These types are separated by family so that when
 // new types are introduced we don't need to modify them.
 const (
-	NullValue ValueType = 0x1
+	NullValue ValueType = 0x80
 
-	BoolValue ValueType = 0x5
+	BoolValue ValueType = 0x81
 
-	// integer family: 0x10 to 0x1F
-	IntegerValue ValueType = 0x10
+	// integer family: 0x90 to 0x9F
+	IntegerValue ValueType = 0x90
 
-	// double family: 0x20 to 0x2F
-	DoubleValue ValueType = 0x20
+	// double family: 0xA0 to 0xAF
+	DoubleValue ValueType = 0xA0
 
-	// time family: 0x30 to 0x3F
-	DurationValue ValueType = 0x30
+	// time family: 0xB0 to 0xBF
+	DurationValue ValueType = 0xB0
 
-	// string family: 0x40 to 0x4F
-	TextValue ValueType = 0x40
+	// string family: 0xC0 to 0xCF
+	TextValue ValueType = 0xC0
 
-	// blob family: 0x50 to 0x5F
-	BlobValue ValueType = 0x50
+	// blob family: 0xD0 to 0xDF
+	BlobValue ValueType = 0xD0
 
-	// array family: 0x60 to 0x6F
-	ArrayValue ValueType = 0x60
+	// array family: 0xE0 to 0xEF
+	ArrayValue ValueType = 0xE0
 
-	// document family: 0x70 to 0x7F
-	DocumentValue ValueType = 0x70
+	// document family: 0xF0 to 0xFF
+	DocumentValue ValueType = 0xF0
 )
 
 func (t ValueType) String() string {
diff --git a/index/index.go b/index/index.go
index 5159764f..d14da00d 100644
--- a/index/index.go
+++ b/index/index.go
@@ -135,7 +135,7 @@ func (idx *Index) Delete(v document.Value, k []byte) error {
 
 	var toDelete []byte
 	var buf []byte
-	err = iterate(st, v, false, func(item engine.Item) error {
+	err = idx.iterate(st, v, false, func(item engine.Item) error {
 		buf, err = item.ValueCopy(buf[:0])
 		if err != nil {
 			return err
@@ -173,6 +173,10 @@ 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 idx.Type != 0 && pivot.Type != 0 && idx.Type != pivot.Type {
+		return nil
+	}
+
 	st, err := idx.tx.GetStore(idx.storeName)
 	if err != nil && err != engine.ErrStoreNotFound {
 		return err
@@ -190,7 +194,7 @@ func (idx *Index) iterateOnStore(pivot document.Value, reverse bool, fn func(val
 	}
 
 	var buf []byte
-	return iterate(st, pivot, reverse, func(item engine.Item) error {
+	return idx.iterate(st, pivot, reverse, func(item engine.Item) error {
 		var err error
 
 		k := item.Key()
@@ -252,12 +256,12 @@ func getOrCreateStore(tx engine.Transaction, name []byte) (engine.Store, error)
 	return tx.GetStore(name)
 }
 
-func iterate(st engine.Store, pivot document.Value, reverse bool, fn func(item engine.Item) error) error {
+func (idx *Index) iterate(st engine.Store, pivot document.Value, reverse bool, fn func(item engine.Item) error) error {
 	var seek []byte
 	var err error
 
 	if pivot.V != nil {
-		seek, err = key.AppendValue(nil, pivot)
+		seek, err = idx.encodeValue(pivot)
 		if err != nil {
 			return err
 		}
@@ -285,7 +289,7 @@ func iterate(st engine.Store, pivot document.Value, reverse bool, fn func(item e
 	for it.Seek(seek); it.Valid(); it.Next() {
 		itm := it.Item()
 
-		if pivot.Type != 0 && itm.Key()[0] != byte(pivot.Type) {
+		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
index 35c4e045..f716f950 100644
--- a/key/encoding.go
+++ b/key/encoding.go
@@ -9,6 +9,7 @@ package key
 
 import (
 	"bytes"
+	"encoding/base64"
 	"encoding/binary"
 	"errors"
 	"math"
@@ -17,6 +18,15 @@ import (
 	"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 {
@@ -84,6 +94,35 @@ func DecodeFloat64(buf []byte) (float64, error) {
 	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
@@ -108,8 +147,194 @@ func AppendNumber(buf []byte, v document.Value) ([]byte, error) {
 	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.DurationValue:
+		i += 8
+	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.
-// It only works with scalars and doesn't support documents and arrays.
 func AppendValue(buf []byte, v document.Value) ([]byte, error) {
 	if v.Type == document.IntegerValue || v.Type == document.DoubleValue {
 		buf = append(buf, byte(document.DoubleValue))
@@ -119,9 +344,10 @@ func AppendValue(buf []byte, v document.Value) ([]byte, error) {
 
 	switch v.Type {
 	case document.BlobValue:
-		return append(buf, v.V.([]byte)...), nil
+		return AppendBase64(buf, v.V.([]byte))
 	case document.TextValue:
-		return append(buf, v.V.(string)...), nil
+		text := v.V.(string)
+		return AppendBase64(buf, []byte(text))
 	case document.BoolValue:
 		return AppendBool(buf, v.V.(bool)), nil
 	case document.IntegerValue, document.DoubleValue:
@@ -130,6 +356,10 @@ func AppendValue(buf []byte, v document.Value) ([]byte, error) {
 		return AppendInt64(buf, int64(v.V.(time.Duration))), nil
 	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")
@@ -142,9 +372,17 @@ func DecodeValue(data []byte) (document.Value, error) {
 
 	switch t {
 	case document.BlobValue:
-		return document.NewBlobValue(data), nil
+		t, err := DecodeBase64(data)
+		if err != nil {
+			return document.Value{}, err
+		}
+		return document.NewBlobValue(t), nil
 	case document.TextValue:
-		return document.NewTextValue(string(data)), nil
+		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:
@@ -168,6 +406,18 @@ func DecodeValue(data []byte) (document.Value, error) {
 		return document.NewDurationValue(time.Duration(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")
@@ -191,6 +441,10 @@ func Append(buf []byte, t document.ValueType, v interface{}) ([]byte, error) {
 		return AppendInt64(buf, int64(v.(time.Duration))), 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")
@@ -226,6 +480,18 @@ func Decode(t document.ValueType, data []byte) (document.Value, error) {
 		return document.NewDurationValue(time.Duration(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")


Test patch:
diff --git a/document/array_test.go b/document/array_test.go
index 19f4a724..725ece3d 100644
--- a/document/array_test.go
+++ b/document/array_test.go
@@ -36,8 +36,8 @@ func TestSortArray(t *testing.T) {
 		{"empty array", `[]`, `[]`},
 		{"numbers", `[1.4,3,2.1,-5]`, `[-5,1.4,2.1,3]`},
 		{"text", `["foo","bar",""]`, `["","bar","foo"]`},
-		{"arrays", `[[1, 2],[-1,10],[]]`, `[[1,2],[-1,10],[]]`},
-		{"documents", `[{"z":10},{"a":40},{}]`, `[{"z":10},{"a":40},{}]`},
+		{"arrays", `[[1, 2],[-1,10],[]]`, `[[],[-1,10],[1,2]]`},
+		{"documents", `[{"z":10},{"a":40},{}]`, `[{},{"a":40},{"z":10}]`},
 		{"mixed", `["foo",["a"],{},null,true,10]`, `[null,true,10,"foo",["a"],{}]`},
 	}
 
diff --git a/document/compare_test.go b/document/compare_test.go
index 6e43c8e2..c4370c61 100644
--- a/document/compare_test.go
+++ b/document/compare_test.go
@@ -182,19 +182,73 @@ func TestCompare(t *testing.T) {
 		{"<=", "b", "b", true, toBlob},
 
 		// array
-		{"=", `[1]`, `[1]`, false, jsonToArray},
-		{"!=", `[1]`, `[1]`, false, toBlob},
-		{">", `[1]`, `[1]`, false, jsonToArray},
-		{">=", `[1]`, `[1]`, false, jsonToArray},
-		{"<", `[1]`, `[1]`, false, jsonToArray},
-		{"<=", `[1]`, `[1]`, false, jsonToArray},
+		{"=", `[]`, `[]`, true, jsonToArray},
+		{"=", `[1]`, `[1]`, true, jsonToArray},
+		{"=", `[1]`, `[]`, false, jsonToArray},
+		{"=", `[1.0, 2]`, `[1, 2]`, true, jsonToArray},
+		{"=", `[1,2,3]`, `[1,2,3]`, true, jsonToArray},
+		{"!=", `[1]`, `[5]`, true, jsonToArray},
+		{"!=", `[1]`, `[1, 1]`, true, jsonToArray},
+		{"!=", `[1,2,3]`, `[1,2,3]`, false, jsonToArray},
+		{"!=", `[1]`, `[]`, true, jsonToArray},
+		{">", `[2]`, `[1]`, true, jsonToArray},
+		{">", `[2]`, `[1, 1000]`, true, jsonToArray},
+		{">", `[1]`, `[1, 1000]`, false, jsonToArray},
+		{">", `[1, 2]`, `[1, 1000]`, false, jsonToArray},
+		{">", `[1, 10]`, `[1, true]`, true, jsonToArray},
+		{">", `[1, true]`, `[1, 10]`, false, jsonToArray},
+		{">", `[2, 1000]`, `[1]`, true, jsonToArray},
+		{">", `[2, 1000]`, `[2]`, true, jsonToArray},
+		{">", `[1,2,3]`, `[1,2,3]`, false, jsonToArray},
+		{">", `[1,2,3]`, `[]`, true, jsonToArray},
+		{">=", `[2]`, `[1]`, true, jsonToArray},
+		{">=", `[2]`, `[2]`, true, jsonToArray},
+		{">=", `[2]`, `[1, 1000]`, true, jsonToArray},
+		{">=", `[1]`, `[1, 1000]`, false, jsonToArray},
+		{">=", `[1, 2]`, `[1, 2]`, true, jsonToArray},
+		{">=", `[1, 2]`, `[1, 1000]`, false, jsonToArray},
+		{">=", `[1, 10]`, `[1, true]`, true, jsonToArray},
+		{">=", `[1, true]`, `[1, 10]`, false, jsonToArray},
+		{">=", `[2, 1000]`, `[1]`, true, jsonToArray},
+		{">=", `[2, 1000]`, `[2]`, true, jsonToArray},
+		{">=", `[1,2,3]`, `[1,2,3]`, true, jsonToArray},
+		{">=", `[1,2,3]`, `[]`, true, jsonToArray},
+		{"<", `[1]`, `[2]`, true, jsonToArray},
+		{"<", `[1,2,3]`, `[1,2]`, false, jsonToArray},
+		{"<", `[1,2,3]`, `[1,2,3]`, false, jsonToArray},
+		{"<", `[1,2]`, `[1,2,3]`, true, jsonToArray},
+		{"<", `[1, 1000]`, `[2]`, true, jsonToArray},
+		{"<", `[2]`, `[2, 1000]`, true, jsonToArray},
+		{"<", `[1,2,3]`, `[]`, false, jsonToArray},
+		{"<", `[]`, `[1,2,3]`, true, jsonToArray},
+		{"<", `[1, 10]`, `[1, true]`, false, jsonToArray},
+		{"<", `[1, true]`, `[1, 10]`, true, jsonToArray},
+		{"<=", `[1]`, `[2]`, true, jsonToArray},
+		{"<=", `[1, 1000]`, `[2]`, true, jsonToArray},
+		{"<=", `[1,2,3]`, `[1,2]`, false, jsonToArray},
+		{">=", `[2]`, `[1]`, true, jsonToArray},
+		{">=", `[2]`, `[2]`, true, jsonToArray},
+		{">=", `[2]`, `[1, 1000]`, true, jsonToArray},
+		{">=", `[2, 1000]`, `[1]`, true, jsonToArray},
+		{"<=", `[1,2,3]`, `[1,2,3]`, true, jsonToArray},
+		{"<=", `[]`, `[]`, true, jsonToArray},
+		{"<=", `[]`, `[1,2,3]`, true, jsonToArray},
 
 		// document
-		{"=", `{"a": 1}`, `{"a": 1}`, false, jsonToDocument},
+		{"=", `{}`, `{}`, true, jsonToDocument},
+		{"=", `{"a": 1}`, `{"a": 1}`, true, jsonToDocument},
+		{"=", `{"a": 1, "b": 2}`, `{"b": 2, "a": 1}`, true, jsonToDocument},
+		{"=", `{"a": 1, "b": {"a": 1}}`, `{"b": {"a": 1}, "a": 1}`, true, jsonToDocument},
+		{">", `{"a": 2}`, `{"a": 1}`, true, jsonToDocument},
+		{">", `{"b": 1}`, `{"a": 1}`, true, jsonToDocument},
 		{">", `{"a": 1}`, `{"a": 1}`, false, jsonToDocument},
-		{">=", `{"a": 1}`, `{"a": 1}`, false, jsonToDocument},
+		{">", `{"a": 1}`, `{"a": true}`, true, jsonToDocument},
+		{"<", `{"a": 1}`, `{"a": 2}`, true, jsonToDocument},
+		{"<", `{"a": 1}`, `{"b": 1}`, true, jsonToDocument},
 		{"<", `{"a": 1}`, `{"a": 1}`, false, jsonToDocument},
-		{"<=", `{"a": 1}`, `{"a": 1}`, false, jsonToDocument},
+		{"<", `{"a": 1}`, `{"a": true}`, false, jsonToDocument},
+		{">=", `{"a": 1}`, `{"a": 1}`, true, jsonToDocument},
+		{"<=", `{"a": 1}`, `{"a": 1}`, true, jsonToDocument},
 	}
 
 	for _, test := range tests {
diff --git a/document/document_test.go b/document/document_test.go
index 675f052d..a6dab38e 100644
--- a/document/document_test.go
+++ b/document/document_test.go
@@ -78,6 +78,11 @@ func TestFieldBuffer(t *testing.T) {
 		require.Zero(t, v)
 	})
 
+	t.Run("Fields", func(t *testing.T) {
+		require.Equal(t, []string{}, document.NewFieldBuffer().Fields())
+		require.Equal(t, []string{"a", "b"}, buf.Fields())
+	})
+
 	t.Run("Set", func(t *testing.T) {
 
 		tests := []struct {
@@ -92,9 +97,9 @@ func TestFieldBuffer(t *testing.T) {
 			{"add field", `{"a": {"b": [1, 2, 3]}}`, `c`, document.NewTextValue("foo"), `{"a": {"b": [1, 2, 3]}, "c": "foo"}`, false},
 			{"nested doc", `{"a": "foo"}`, `a`, document.NewDocumentValue(document.NewFieldBuffer().
 				Add("b", document.NewArrayValue(document.NewValueBuffer().
-				Append(document.NewIntegerValue(1)).
-				Append(document.NewIntegerValue(2)).
-				Append(document.NewIntegerValue(3))))), `{"a": {"b": [1, 2, 3]}}`, false},
+					Append(document.NewIntegerValue(1)).
+					Append(document.NewIntegerValue(2)).
+					Append(document.NewIntegerValue(3))))), `{"a": {"b": [1, 2, 3]}}`, false},
 			{"nested doc", `{"a": {"b": [1, 2, 3]}}`, `a.b`, document.NewArrayValue(document.NewValueBuffer().
 				Append(document.NewIntegerValue(1)).
 				Append(document.NewIntegerValue(2)).
@@ -108,7 +113,6 @@ func TestFieldBuffer(t *testing.T) {
 			{"unknown path", `{"a": {"b": [1, 2, 3]}}`, `a.e.f`, document.NewIntegerValue(1), ``, true},
 			{"index out of range", `{"a": {"b": [1, 2, 3]}}`, `a.b[1000]`, document.NewIntegerValue(1), ``, true},
 			{"document not array", `{"a": {"b": "foo"}}`, `a[0].b`, document.NewTextValue("bar"), ``, true},
-
 		}
 
 		for _, tt := range tests {
diff --git a/key/encoding_test.go b/key/encoding_test.go
index 1449683e..003517c6 100644
--- a/key/encoding_test.go
+++ b/key/encoding_test.go
@@ -11,7 +11,7 @@ import (
 	"github.com/stretchr/testify/require"
 )
 
-func TestAppendValueDecodeValue(t *testing.T) {
+func TestAppendDecode(t *testing.T) {
 	tests := []struct {
 		name string
 		v    document.Value
@@ -23,6 +23,47 @@ func TestAppendValueDecodeValue(t *testing.T) {
 		{"text", document.NewTextValue("foo")},
 		{"blob", document.NewBlobValue([]byte("bar"))},
 		{"duration", document.NewDurationValue(10 * time.Second)},
+		{"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 {
@@ -37,7 +78,7 @@ func TestAppendValueDecodeValue(t *testing.T) {
 	}
 }
 
-func TestAppendDecode(t *testing.T) {
+func TestAppendValueDecodeValue(t *testing.T) {
 	tests := []struct {
 		name string
 		v    document.Value
@@ -49,6 +90,47 @@ func TestAppendDecode(t *testing.T) {
 		{"text", document.NewTextValue("foo")},
 		{"blob", document.NewBlobValue([]byte("bar"))},
 		{"duration", document.NewDurationValue(10 * time.Second)},
+		{"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 {
@@ -74,6 +156,11 @@ func TestOrdering(t *testing.T) {
 		{"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 {
diff --git a/sql/query/expr/comparison_test.go b/sql/query/expr/comparison_test.go
index 94ed618f..eb222bd6 100644
--- a/sql/query/expr/comparison_test.go
+++ b/sql/query/expr/comparison_test.go
@@ -51,7 +51,7 @@ func TestComparisonINExpr(t *testing.T) {
 		{"2 IN [2.1, 2.2, 2.0]", document.NewBoolValue(true), false},
 		{"1 IN [2, 3]", document.NewBoolValue(false), false},
 		{"[1] IN [1, 2, 3]", document.NewBoolValue(false), false},
-		{"[1] IN [[1], [2], [3]]", document.NewBoolValue(false), false},
+		{"[1] IN [[1], [2], [3]]", document.NewBoolValue(true), false},
 		{"1 IN {}", document.NewBoolValue(false), false},
 		{"[1, 2] IN 1", document.NewBoolValue(false), false},
 		{"1 IN NULL", nullLitteral, false},
@@ -75,7 +75,7 @@ func TestComparisonNOTINExpr(t *testing.T) {
 		{"1 NOT IN [1, 2, 3]", document.NewBoolValue(false), false},
 		{"1 NOT IN [2, 3]", document.NewBoolValue(true), false},
 		{"[1] NOT IN [1, 2, 3]", document.NewBoolValue(true), false},
-		{"[1] NOT IN [[1], [2], [3]]", document.NewBoolValue(true), false},
+		{"[1] NOT IN [[1], [2], [3]]", document.NewBoolValue(false), false},
 		{"1 NOT IN {}", document.NewBoolValue(true), false},
 		{"[1, 2] NOT IN 1", document.NewBoolValue(true), false},
 		{"1 NOT IN NULL", nullLitteral, false},