Repository: genjidb/genji
Pull request #188 (2020-09-10 05:10:13)

Fix node order
This PR fixes the order of the nodes generated by the parser. Projections are supposed to happen before sorting and limit/offset.

```sql
EXPLAIN SELECT a + 1 FROM test WHERE c > 30 ORDER BY a DESC LIMIT 10 OFFSET 20
```

Before:
```
Table(test) -> σ(cond: c > 30) -> Sort(a DESC) -> Offset(20) -> Limit(10) -> ∏(a + 1)
```

After:
```
Table(test) -> σ(cond: c > 30) -> ∏(a + 1) -> Sort(a DESC) -> Offset(20) -> Limit(10)
```


Patch:
diff --git a/sql/parser/select.go b/sql/parser/select.go
index 26eb9cd4..75269b66 100644
--- a/sql/parser/select.go
+++ b/sql/parser/select.go
@@ -2,6 +2,7 @@ package parser
 
 import (
 	"fmt"
+
 	"github.com/genjidb/genji/sql/planner"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
@@ -194,18 +195,20 @@ type selectConfig struct {
 
 // ToTree turns the statement into an expression tree.
 func (cfg selectConfig) ToTree() (*planner.Tree, error) {
-	if cfg.TableName == "" {
-		return planner.NewTree(planner.NewProjectionNode(nil, cfg.ProjectionExprs, "")), nil
-	}
+	var n planner.Node
 
-	t := planner.NewTableInputNode(cfg.TableName)
+	if cfg.TableName != "" {
+		n = planner.NewTableInputNode(cfg.TableName)
+	}
 
 	if cfg.WhereExpr != nil {
-		t = planner.NewSelectionNode(t, cfg.WhereExpr)
+		n = planner.NewSelectionNode(n, cfg.WhereExpr)
 	}
 
+	n = planner.NewProjectionNode(n, cfg.ProjectionExprs, cfg.TableName)
+
 	if cfg.OrderBy != nil {
-		t = planner.NewSortNode(t, cfg.OrderBy, cfg.OrderByDirection)
+		n = planner.NewSortNode(n, cfg.OrderBy, cfg.OrderByDirection)
 	}
 
 	if cfg.OffsetExpr != nil {
@@ -223,7 +226,7 @@ func (cfg selectConfig) ToTree() (*planner.Tree, error) {
 			return nil, err
 		}
 
-		t = planner.NewOffsetNode(t, int(v.V.(int64)))
+		n = planner.NewOffsetNode(n, int(v.V.(int64)))
 	}
 
 	if cfg.LimitExpr != nil {
@@ -241,10 +244,8 @@ func (cfg selectConfig) ToTree() (*planner.Tree, error) {
 			return nil, err
 		}
 
-		t = planner.NewLimitNode(t, int(v.V.(int64)))
+		n = planner.NewLimitNode(n, int(v.V.(int64)))
 	}
 
-	t = planner.NewProjectionNode(t, cfg.ProjectionExprs, cfg.TableName)
-
-	return &planner.Tree{Root: t}, nil
+	return &planner.Tree{Root: n}, nil
 }
diff --git a/sql/planner/deletion.go b/sql/planner/deletion.go
index ecca9494..47116c95 100644
--- a/sql/planner/deletion.go
+++ b/sql/planner/deletion.go
@@ -6,7 +6,6 @@ import (
 
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/sql/query"
 	"github.com/genjidb/genji/sql/query/expr"
 )
 
@@ -20,7 +19,7 @@ type deletionNode struct {
 	table     *database.Table
 }
 
-var _ outputNode = (*deletionNode)(nil)
+var _ operationNode = (*deletionNode)(nil)
 
 // NewDeletionNode creates a node that delete every document of a stream
 // from their respective table.
@@ -46,7 +45,7 @@ func (n *deletionNode) Bind(tx *database.Transaction, params []expr.Param) (err
 // to a buffer and delete them after the iteration is complete, and it will do that until there is no document
 // left to delete.
 // Increasing deleteBufferSize will occasionate less key searches (O(log n) for most engines) but will take more memory.
-func (n *deletionNode) toResult(st document.Stream) (res query.Result, err error) {
+func (n *deletionNode) toStream(st document.Stream) (document.Stream, error) {
 	st = st.Limit(deleteBufferSize)
 
 	keys := make([][]byte, deleteBufferSize)
@@ -65,7 +64,7 @@ func (n *deletionNode) toResult(st document.Stream) (res query.Result, err error
 			return nil
 		})
 		if err != nil {
-			return res, err
+			return document.Stream{}, err
 		}
 
 		keys = keys[:i]
@@ -73,7 +72,7 @@ func (n *deletionNode) toResult(st document.Stream) (res query.Result, err error
 		for _, key := range keys {
 			err = n.table.Delete(key)
 			if err != nil {
-				return res, err
+				return document.Stream{}, err
 			}
 		}
 
@@ -82,7 +81,7 @@ func (n *deletionNode) toResult(st document.Stream) (res query.Result, err error
 		}
 	}
 
-	return res, nil
+	return document.Stream{}, nil
 }
 
 func (n *deletionNode) String() string {
diff --git a/sql/planner/projection.go b/sql/planner/projection.go
index 1565ac84..f388d342 100644
--- a/sql/planner/projection.go
+++ b/sql/planner/projection.go
@@ -8,7 +8,6 @@ import (
 
 	"github.com/genjidb/genji/database"
 	"github.com/genjidb/genji/document"
-	"github.com/genjidb/genji/sql/query"
 	"github.com/genjidb/genji/sql/query/expr"
 )
 
@@ -25,7 +24,6 @@ type ProjectionNode struct {
 	tx   *database.Transaction
 }
 
-var _ outputNode = (*ProjectionNode)(nil)
 var _ operationNode = (*ProjectionNode)(nil)
 
 // NewProjectionNode creates a ProjectionNode.
@@ -73,23 +71,13 @@ func (n *ProjectionNode) toStream(st document.Stream) (document.Stream, error) {
 	var dm documentMask
 	return st.Map(func(d document.Document) (document.Document, error) {
 		dm.info = n.info
-		dm.r = d
+		dm.d = d
 		dm.resultFields = n.Expressions
 
 		return &dm, nil
 	}), nil
 }
 
-func (n *ProjectionNode) toResult(st document.Stream) (res query.Result, err error) {
-	st, err = n.toStream(st)
-	if err != nil {
-		return
-	}
-
-	res.Stream = st
-	return
-}
-
 func (n *ProjectionNode) String() string {
 	var b strings.Builder
 
@@ -105,7 +93,7 @@ func (n *ProjectionNode) String() string {
 
 type documentMask struct {
 	info         *database.TableInfo
-	r            document.Document
+	d            document.Document
 	resultFields []ResultField
 }
 
@@ -114,7 +102,7 @@ var _ document.Document = documentMask{}
 func (r documentMask) GetByField(field string) (document.Value, error) {
 	for _, rf := range r.resultFields {
 		if rf.Name() == field || rf.Name() == "*" {
-			return r.r.GetByField(field)
+			return r.d.GetByField(field)
 		}
 	}
 
@@ -123,7 +111,7 @@ func (r documentMask) GetByField(field string) (document.Value, error) {
 
 func (r documentMask) Iterate(fn func(field string, value document.Value) error) error {
 	stack := expr.EvalStack{
-		Document: r.r,
+		Document: r.d,
 		Info:     r.info,
 	}
 
diff --git a/sql/planner/replacement.go b/sql/planner/replacement.go
index 25027778..89c53d14 100644
--- a/sql/planner/replacement.go
+++ b/sql/planner/replacement.go
@@ -8,7 +8,6 @@ import (
 	"github.com/genjidb/genji/document"
 	"github.com/genjidb/genji/document/encoding"
 	"github.com/genjidb/genji/engine"
-	"github.com/genjidb/genji/sql/query"
 	"github.com/genjidb/genji/sql/query/expr"
 )
 
@@ -23,7 +22,7 @@ type replacementNode struct {
 	codec     encoding.Codec
 }
 
-var _ outputNode = (*replacementNode)(nil)
+var _ operationNode = (*replacementNode)(nil)
 
 // NewReplacementNode creates a node that stores every document of a stream
 // in their respective table and primary keys.
@@ -48,7 +47,7 @@ func (n *replacementNode) Bind(tx *database.Transaction, params []expr.Param) (e
 // to a buffer and replace them after the iteration is complete, and it will do that until there is no document
 // left to replace.
 // Increasing replaceBufferSize will occasionate less key searches (O(log n) for most engines) but will take more memory.
-func (n *replacementNode) toResult(st document.Stream) (res query.Result, err error) {
+func (n *replacementNode) toStream(st document.Stream) (document.Stream, error) {
 	// replace store implementation by a resumable store, temporarily.
 	rit := resumableIterator{
 		store: n.table.Store,
@@ -60,6 +59,7 @@ func (n *replacementNode) toResult(st document.Stream) (res query.Result, err er
 	keys := make([][]byte, replaceBufferSize)
 	docs := make([]document.FieldBuffer, replaceBufferSize)
 
+	var err error
 	for {
 		var i int
 
@@ -85,7 +85,7 @@ func (n *replacementNode) toResult(st document.Stream) (res query.Result, err er
 		for j := 0; j < i; j++ {
 			err = n.table.Replace(keys[j], docs[j])
 			if err != nil {
-				return res, err
+				return document.Stream{}, err
 			}
 		}
 
@@ -96,7 +96,7 @@ func (n *replacementNode) toResult(st document.Stream) (res query.Result, err er
 		rit.curKey = keys[i-1]
 	}
 
-	return res, err
+	return document.Stream{}, err
 }
 
 func (n *replacementNode) String() string {
diff --git a/sql/planner/sort.go b/sql/planner/sort.go
index 48cb093b..47a3f0ff 100644
--- a/sql/planner/sort.go
+++ b/sql/planner/sort.go
@@ -105,12 +105,27 @@ func (it *sortIterator) sortStream(st document.Stream) (heap.Interface, error) {
 	heap.Init(h)
 
 	return h, st.Iterate(func(d document.Document) error {
+		// It is possible to sort by any projected field
+		// or field of the original document.
 		v, err := path.GetValue(d)
 		if err != nil && err != document.ErrFieldNotFound {
 			return err
 		}
+
+		// If a field is not found in the projected fields
+		// Look for fields in the original document.
 		if err == document.ErrFieldNotFound {
-			v = document.NewNullValue()
+			if dm, ok := d.(*documentMask); ok {
+				v, err = path.GetValue(dm.d)
+				if err != nil && err != document.ErrFieldNotFound {
+					return err
+				}
+				if err == document.ErrFieldNotFound {
+					v = document.NewNullValue()
+				}
+			} else {
+				v = document.NewNullValue()
+			}
 		}
 
 		// We need to make sure sort behaviour
diff --git a/sql/planner/tree.go b/sql/planner/tree.go
index cec8158a..180bf764 100644
--- a/sql/planner/tree.go
+++ b/sql/planner/tree.go
@@ -81,7 +81,14 @@ func (t *Tree) execute() (query.Result, error) {
 		}
 	}
 
-	return t.Root.(outputNode).toResult(st)
+	st, err = t.Root.(operationNode).toStream(st)
+	if err != nil {
+		return query.Result{}, err
+	}
+
+	return query.Result{
+		Stream: st,
+	}, nil
 }
 
 func (t *Tree) String() string {
@@ -156,12 +163,6 @@ type operationNode interface {
 	toStream(st document.Stream) (document.Stream, error)
 }
 
-type outputNode interface {
-	Node
-
-	toResult(st document.Stream) (query.Result, error)
-}
-
 type node struct {
 	op          Operation
 	left, right Node


Test patch:
diff --git a/sql/parser/select_test.go b/sql/parser/select_test.go
index 4c56fc14..7e1cd236 100644
--- a/sql/parser/select_test.go
+++ b/sql/parser/select_test.go
@@ -84,92 +84,92 @@ func TestParserSelect(t *testing.T) {
 			false},
 		{"WithOrderBy", "SELECT * FROM test WHERE age = 10 ORDER BY a.b.c",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewSortNode(
+				planner.NewSortNode(
+					planner.NewProjectionNode(
 						planner.NewSelectionNode(
 							planner.NewTableInputNode("test"),
 							expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 						),
-						expr.FieldSelector(parsePath(t, "a.b.c")),
-						scanner.ASC,
+						[]planner.ResultField{planner.Wildcard{}},
+						"test",
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					expr.FieldSelector(parsePath(t, "a.b.c")),
+					scanner.ASC,
 				)),
 			false},
 		{"WithOrderBy ASC", "SELECT * FROM test WHERE age = 10 ORDER BY a.b.c ASC",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewSortNode(
+				planner.NewSortNode(
+					planner.NewProjectionNode(
 						planner.NewSelectionNode(
 							planner.NewTableInputNode("test"),
 							expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 						),
-						expr.FieldSelector(parsePath(t, "a.b.c")),
-						scanner.ASC,
+						[]planner.ResultField{planner.Wildcard{}},
+						"test",
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					expr.FieldSelector(parsePath(t, "a.b.c")),
+					scanner.ASC,
 				)),
 			false},
 		{"WithOrderBy DESC", "SELECT * FROM test WHERE age = 10 ORDER BY a.b.c DESC",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewSortNode(
+				planner.NewSortNode(
+					planner.NewProjectionNode(
 						planner.NewSelectionNode(
 							planner.NewTableInputNode("test"),
 							expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 						),
-						expr.FieldSelector(parsePath(t, "a.b.c")),
-						scanner.DESC,
+						[]planner.ResultField{planner.Wildcard{}},
+						"test",
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					expr.FieldSelector(parsePath(t, "a.b.c")),
+					scanner.DESC,
 				)),
 			false},
 		{"WithLimit", "SELECT * FROM test WHERE age = 10 LIMIT 20",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewLimitNode(
+				planner.NewLimitNode(
+					planner.NewProjectionNode(
 						planner.NewSelectionNode(
 							planner.NewTableInputNode("test"),
 							expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 						),
-						20,
+						[]planner.ResultField{planner.Wildcard{}},
+						"test",
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					20,
 				)),
 			false},
 		{"WithOffset", "SELECT * FROM test WHERE age = 10 OFFSET 20",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewOffsetNode(
+				planner.NewOffsetNode(
+					planner.NewProjectionNode(
 						planner.NewSelectionNode(
 							planner.NewTableInputNode("test"),
 							expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 						),
-						20,
+						[]planner.ResultField{planner.Wildcard{}},
+						"test",
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					20,
 				)),
 			false},
 		{"WithLimitThenOffset", "SELECT * FROM test WHERE age = 10 LIMIT 10 OFFSET 20",
 			planner.NewTree(
-				planner.NewProjectionNode(
-					planner.NewLimitNode(
-						planner.NewOffsetNode(
+				planner.NewLimitNode(
+					planner.NewOffsetNode(
+						planner.NewProjectionNode(
 							planner.NewSelectionNode(
 								planner.NewTableInputNode("test"),
 								expr.Eq(expr.FieldSelector(parsePath(t, "age")), expr.IntegerValue(10)),
 							),
-							20,
+							[]planner.ResultField{planner.Wildcard{}},
+							"test",
 						),
-						10,
+						20,
 					),
-					[]planner.ResultField{planner.Wildcard{}},
-					"test",
+					10,
 				)),
 			false},
 		{"WithOffsetThenLimit", "SELECT * FROM test WHERE age = 10 OFFSET 20 LIMIT 10", nil, true},
diff --git a/sql/planner/explain_test.go b/sql/planner/explain_test.go
index db36373e..d5720aef 100644
--- a/sql/planner/explain_test.go
+++ b/sql/planner/explain_test.go
@@ -23,7 +23,7 @@ func TestExplainStmt(t *testing.T) {
 		{"EXPLAIN SELECT a + 1 FROM test WHERE c IN [1 + 1, 2 + 2]", false, `"Table(test) -> σ(cond: c IN [2, 4]) -> ∏(a + 1)"`},
 		{"EXPLAIN SELECT a + 1 FROM test WHERE a > 10", false, `"Index(idx_a) -> ∏(a + 1)"`},
 		{"EXPLAIN SELECT a + 1 FROM test WHERE a > 10 AND b > 20 AND c > 30", false, `"Index(idx_b) -> σ(cond: c > 30) -> σ(cond: a > 10) -> ∏(a + 1)"`},
-		{"EXPLAIN SELECT a + 1 FROM test WHERE c > 30 ORDER BY a DESC LIMIT 10 OFFSET 20", false, `"Table(test) -> σ(cond: c > 30) -> Sort(a DESC) -> Offset(20) -> Limit(10) -> ∏(a + 1)"`},
+		{"EXPLAIN SELECT a + 1 FROM test WHERE c > 30 ORDER BY a DESC LIMIT 10 OFFSET 20", false, `"Table(test) -> σ(cond: c > 30) -> ∏(a + 1) -> Sort(a DESC) -> Offset(20) -> Limit(10)"`},
 		{"EXPLAIN UPDATE test SET a = 10", false, `"Table(test) -> Set(a = 10) -> Replace(test)"`},
 		{"EXPLAIN UPDATE test SET a = 10 WHERE c > 10", false, `"Table(test) -> σ(cond: c > 10) -> Set(a = 10) -> Replace(test)"`},
 		{"EXPLAIN UPDATE test SET a = 10 WHERE a > 10", false, `"Index(idx_a) -> Set(a = 10) -> Replace(test)"`},