Repository: genjidb/genji (go)

Issue:
Add ORDER BY clause to DELETE statement
```sql
DELETE FROM foo ORDER BY a DESC

EXPLAIN DELETE FROM foo ORDER BY a DESC
{
  "plan": "Table(foo) -> Sort(a DESC) -> Delete(foo)"
}
```

It must have the same behavior as SELECT.

The parser already knows how to parse `ORDER BY`:  https://github.com/genjidb/genji/blob/707824da1399f16d9242a8e6bfa17ac50ec353af/sql/parser/select.go#L173

Pull request description:
Add ORDER BY, LIMIT and OFFSET clauses to DELETE statement
Hey there!

This PR fixes #318, #319 and #320. I grouped my changes to avoid having to open cascading PRs, as those clauses are dependent on each other to be properly tested (the sort operation from the order by must be done before the skip and take ones). 

I found two bugs along the way in `tx.Clone()` and added some tests for them:
- the `Tx` wasn't copied over, which broke getting the table name after sorting the stream 
- the `Vars` weren't copied properly as well 

Finally, the parsing functions for the clauses were now not just being used by the select statement, so they've been extracted in their own file. 

Please tell me if there is anything that must be fixed, changed or done in a different PR, I'll make the changes!

```
genji> EXPLAIN DELETE FROM foo ORDER BY a DESC;
{
  "plan": "seqScan(foo) | sortReverse(a) | tableDelete('foo')"
}
```

```
genji> EXPLAIN DELETE FROM foo LIMIT 1 + 1;
{
  "plan": "seqScan(foo) | take(2) | tableDelete('foo')"
}
```

```
genji> EXPLAIN DELETE FROM foo OFFSET 1 + 1;
{
  "plan": "seqScan(foo) | skip(2) | tableDelete('foo')"
}
```

```
genji> EXPLAIN DELETE FROM foo ORDER BY a LIMIT 5 OFFSET 1 + 1;
{
  "plan": "seqScan(foo) | sort(a) | skip(2) | take(5) | tableDelete('foo')"
}
```

Patch:
diff --git a/ARCHITECTURE.md b/ARCHITECTURE.md
new file mode 100644
index 00000000..85b22646
--- /dev/null
+++ b/ARCHITECTURE.md
@@ -0,0 +1,55 @@
+# Genji Architecture
+
+This document sums up the current Genji architecture and will evolve over time.
+
+## Goals
+
+- **SQL first**: SQL is the main way to interact with the database
+- **Documents**: anything can be stored, as long as it can be expressed as a document
+- **Schema is optional and can be partial**: a table containing documents can have value or structurual constraints on some, all or no fields
+- **Run anywhere**: a browser, a low power computer or a server
+
+## Overview
+
+Genji, in a bird's-eye view is structured in the following layers:
+
+- _SQL_, the language and grammar used to express queries to fetch, store and update data
+- _Stream_, an internal representation of the low level operation that will be performed on documents by the database
+- _Database_, defines the base database components, tables, transactions, indexes
+- _Engine_, the storage layer, various KV stores responsible of persiting the data
+
+### Lifecycle of query
+
+1. Genji parses SQL and turns into a Stream
+
+   - the `parser` will use the `scanner` to turn the SQL into a basic, unoptimized `Stream`
+   - packages: `sql/driver`, `sql/scanner`, `sql/parser`, `sql/query`, `sql/query/expr`, `document`
+
+2. the `Planner` will analyze that `Stream` and will optimize it if possible
+
+   - which index to use, removing redundant loads, compute constant expressions, ...
+   - packages: `sql/planner`, `stream`
+
+3. That `Stream` will be executed against the `database`, reading and/or modifying indexes, tables
+
+   - packages: `database`, `index`
+
+4. interactions with the `database` layer will make calls to the `engine`, to perform reads and writes
+
+   - the `database` layer will encode/decode `document`s into bytes
+   - the `engine` layer is responsible of reading or writing bytes in the underlying KV-store
+   - packages: `engine/*`, `document/encoding`, `document`
+
+For a description of each those these package, see the [GoDoc](https://pkg.go.dev/github.com/genjidb/genji).
+
+## Current Trade offs
+
+Presently, in the current state of development, the following trade offs are considered:
+
+- _Concurrency_: one writer, multiple readers
+  - what: no concurrent writes (serialized), but reads are concurrent
+  - why: it simplifies greatly the implementation and avoids dealing with concurrent accesses, which is supported with varying semantics by the underlying store. A solution would be to implement the MVCC layer within Genji, which is a lot of work and isn't the current priority.
+- _Performances_: overall, the focus is more on features than on last mile optimizations
+- _SQL standards_: not bothering to respect them
+  - what: don't expect Genji'sql to be portable, it's not.
+  - why: documents are really different than rows and colums and Genji's SQL syntax is designed for documents
diff --git a/README.md b/README.md
index 214396e4..70cef9dd 100644
--- a/README.md
+++ b/README.md
@@ -292,7 +292,7 @@ genji --badger pathToData
 
 Contributions are welcome!
 
-See [CONTRIBUTING.md](.github/CONTRIBUTING.md).
+See [ARCHITECTURE.md](./ARCHITECTURE.md) and [CONTRIBUTING.md](.github/CONTRIBUTING.md).
 
 Thank you, [contributors](https://github.com/genjidb/genji/graphs/contributors)!
 
diff --git a/cmd/genji/shell/command.go b/cmd/genji/shell/command.go
index fc3a1e08..b4962278 100644
--- a/cmd/genji/shell/command.go
+++ b/cmd/genji/shell/command.go
@@ -242,6 +242,11 @@ func dumpTable(tx *genji.Tx, tableName string, w io.Writer) error {
 		if fc.IsNotNull {
 			buf.WriteString(" NOT NULL")
 		}
+
+		if fc.HasDefaultValue() {
+			buf.WriteString(" DEFAULT ")
+			buf.WriteString(fc.DefaultValue.String())
+		}
 	}
 
 	// Fields constraints close parenthesis.
diff --git a/sql/parser/delete.go b/sql/parser/delete.go
index 548213ae..910b1511 100644
--- a/sql/parser/delete.go
+++ b/sql/parser/delete.go
@@ -1,6 +1,8 @@
 package parser
 
 import (
+	"fmt"
+
 	"github.com/genjidb/genji/sql/planner"
 	"github.com/genjidb/genji/sql/query/expr"
 	"github.com/genjidb/genji/sql/scanner"
@@ -32,26 +34,92 @@ func (p *Parser) parseDeleteStatement() (*planner.Statement, error) {
 		return nil, err
 	}
 
-	return cfg.ToStream(), nil
+	// Parse order by: "ORDER BY path [ASC|DESC]?"
+	cfg.OrderBy, cfg.OrderByDirection, err = p.parseOrderBy()
+	if err != nil {
+		return nil, err
+	}
+
+	// Parse limit: "LIMIT expr"
+	cfg.LimitExpr, err = p.parseLimit()
+	if err != nil {
+		return nil, err
+	}
+
+	// Parse offset: "OFFSET expr"
+	cfg.OffsetExpr, err = p.parseOffset()
+	if err != nil {
+		return nil, err
+	}
+
+	return cfg.ToStream()
 }
 
 // DeleteConfig holds DELETE configuration.
 type deleteConfig struct {
-	TableName string
-	WhereExpr expr.Expr
+	TableName        string
+	WhereExpr        expr.Expr
+	OffsetExpr       expr.Expr
+	OrderBy          expr.Path
+	LimitExpr        expr.Expr
+	OrderByDirection scanner.Token
 }
 
-func (cfg deleteConfig) ToStream() *planner.Statement {
+func (cfg deleteConfig) ToStream() (*planner.Statement, error) {
 	s := stream.New(stream.SeqScan(cfg.TableName))
 
 	if cfg.WhereExpr != nil {
 		s = s.Pipe(stream.Filter(cfg.WhereExpr))
 	}
 
+	if cfg.OrderBy != nil {
+		if cfg.OrderByDirection == scanner.DESC {
+			s = s.Pipe(stream.SortReverse(cfg.OrderBy))
+		} else {
+			s = s.Pipe(stream.Sort(cfg.OrderBy))
+		}
+	}
+
+	if cfg.OffsetExpr != nil {
+		v, err := cfg.OffsetExpr.Eval(&expr.Environment{})
+		if err != nil {
+			return nil, err
+		}
+
+		if !v.Type.IsNumber() {
+			return nil, fmt.Errorf("offset expression must evaluate to a number, got %q", v.Type)
+		}
+
+		v, err = v.CastAsInteger()
+		if err != nil {
+			return nil, err
+		}
+
+		s = s.Pipe(stream.Skip(v.V.(int64)))
+	}
+
+	if cfg.LimitExpr != nil {
+		v, err := cfg.LimitExpr.Eval(&expr.Environment{})
+		if err != nil {
+			return nil, err
+		}
+
+		if !v.Type.IsNumber() {
+			return nil, fmt.Errorf("limit expression must evaluate to a number, got %q", v.Type)
+		}
+
+		v, err = v.CastAsInteger()
+		if err != nil {
+			return nil, err
+		}
+
+		s = s.Pipe(stream.Take(v.V.(int64)))
+	}
+
 	s = s.Pipe(stream.TableDelete(cfg.TableName))
 
 	return &planner.Statement{
 		Stream:   s,
 		ReadOnly: false,
-	}
+	}, nil
 }
diff --git a/sql/parser/order_by.go b/sql/parser/order_by.go
new file mode 100644
index 00000000..acfaa0dc
--- /dev/null
+++ b/sql/parser/order_by.go
@@ -0,0 +1,55 @@
+package parser
+
+import (
+	"github.com/genjidb/genji/sql/query/expr"
+	"github.com/genjidb/genji/sql/scanner"
+)
+
+func (p *Parser) parseOrderBy() (expr.Path, scanner.Token, error) {
+	// parse ORDER token
+	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.ORDER {
+		p.Unscan()
+		return nil, 0, nil
+	}
+
+	// parse BY token
+	if tok, pos, lit := p.ScanIgnoreWhitespace(); tok != scanner.BY {
+		return nil, 0, newParseError(scanner.Tokstr(tok, lit), []string{"BY"}, pos)
+	}
+
+	// parse path
+	path, err := p.parsePath()
+	if err != nil {
+		return nil, 0, err
+	}
+
+	// parse optional ASC or DESC
+	if tok, _, _ := p.ScanIgnoreWhitespace(); tok == scanner.ASC || tok == scanner.DESC {
+		return expr.Path(path), tok, nil
+	}
+	p.Unscan()
+
+	return expr.Path(path), 0, nil
+}
+
+func (p *Parser) parseLimit() (expr.Expr, error) {
+	// parse LIMIT token
+	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.LIMIT {
+		p.Unscan()
+		return nil, nil
+	}
+
+	e, _, err := p.ParseExpr()
+	return e, err
+}
+
+func (p *Parser) parseOffset() (expr.Expr, error) {
+	// parse OFFSET token
+	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.OFFSET {
+		p.Unscan()
+		return nil, nil
+	}
+
+	e, _, err := p.ParseExpr()
+	return e, err
+}
diff --git a/sql/parser/select.go b/sql/parser/select.go
index dd9cad17..db303e0c 100644
--- a/sql/parser/select.go
+++ b/sql/parser/select.go
@@ -173,55 +173,6 @@ func (p *Parser) parseGroupBy() (expr.Expr, error) {
 	return e, err
 }
 
-func (p *Parser) parseOrderBy() (expr.Path, scanner.Token, error) {
-	// parse ORDER token
-	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.ORDER {
-		p.Unscan()
-		return nil, 0, nil
-	}
-
-	// parse BY token
-	if tok, pos, lit := p.ScanIgnoreWhitespace(); tok != scanner.BY {
-		return nil, 0, newParseError(scanner.Tokstr(tok, lit), []string{"BY"}, pos)
-	}
-
-	// parse path
-	path, err := p.parsePath()
-	if err != nil {
-		return nil, 0, err
-	}
-
-	// parse optional ASC or DESC
-	if tok, _, _ := p.ScanIgnoreWhitespace(); tok == scanner.ASC || tok == scanner.DESC {
-		return expr.Path(path), tok, nil
-	}
-	p.Unscan()
-
-	return expr.Path(path), 0, nil
-}
-
-func (p *Parser) parseLimit() (expr.Expr, error) {
-	// parse LIMIT token
-	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.LIMIT {
-		p.Unscan()
-		return nil, nil
-	}
-
-	e, _, err := p.ParseExpr()
-	return e, err
-}
-
-func (p *Parser) parseOffset() (expr.Expr, error) {
-	// parse OFFSET token
-	if tok, _, _ := p.ScanIgnoreWhitespace(); tok != scanner.OFFSET {
-		p.Unscan()
-		return nil, nil
-	}
-
-	e, _, err := p.ParseExpr()
-	return e, err
-}
-
 // SelectConfig holds SELECT configuration.
 type selectConfig struct {
 	TableName        string
diff --git a/sql/query/expr/env.go b/sql/query/expr/env.go
index 956d32ef..20fe3f9a 100644
--- a/sql/query/expr/env.go
+++ b/sql/query/expr/env.go
@@ -112,9 +112,10 @@ func (e *Environment) GetTx() *database.Transaction {
 func (e *Environment) Clone() (*Environment, error) {
 	newEnv := Environment{
 		Params: e.Params,
-		Vars:   document.NewFieldBuffer(),
 	}
 
+	newEnv.Tx = e.Tx
+
 	if e.Doc != nil {
 		fb := document.NewFieldBuffer()
 		err := fb.Copy(e.Doc)
@@ -127,7 +128,7 @@ func (e *Environment) Clone() (*Environment, error) {
 
 	if e.Vars != nil {
 		fb := document.NewFieldBuffer()
-		err := fb.Copy(e.Doc)
+		err := fb.Copy(e.Vars)
 		if err != nil {
 			return nil, err
 		}


Test patch:
diff --git a/cmd/genji/shell/command_test.go b/cmd/genji/shell/command_test.go
index 5930dbf8..7c55b8b5 100644
--- a/cmd/genji/shell/command_test.go
+++ b/cmd/genji/shell/command_test.go
@@ -101,7 +101,7 @@ func TestRunDumpCmd(t *testing.T) {
 	}{
 		{"Values / With columns", `INSERT INTO test (a, b, c) VALUES ('a', 'b', 'c')`, ``, `INSERT INTO test VALUES {"a": "a", "b": "b", "c": "c"};`, false, nil},
 		{"text / not null with type constraint", `INSERT INTO test (a, b, c) VALUES ('a', 'b', 'c')`, `TEXT NOT NULL`, `INSERT INTO test VALUES {"a": "a", "b": "b", "c": "c"};`, false, nil},
-		{"text / pk and not null with type constraint", `INSERT INTO test (a, b, c) VALUES ('a', 'b', 'c')`, `TEXT PRIMARY KEY NOT NULL`, `INSERT INTO test VALUES {"a": "a", "b": "b", "c": "c"};`, false, nil},
+		{"text / pk and not null with type constraint", `INSERT INTO test (a, b, c) VALUES ('a', 'b', 'c')`, `TEXT PRIMARY KEY NOT NULL DEFAULT "foo"`, `INSERT INTO test VALUES {"a": "a", "b": "b", "c": "c"};`, false, nil},
 	}
 
 	for _, tt := range tests {
diff --git a/sql/parser/delete_test.go b/sql/parser/delete_test.go
index ef8556f0..94a13f23 100644
--- a/sql/parser/delete_test.go
+++ b/sql/parser/delete_test.go
@@ -20,6 +20,32 @@ func TestParserDelete(t *testing.T) {
 				Pipe(stream.Filter(MustParseExpr("age = 10"))).
 				Pipe(stream.TableDelete("test")),
 		},
+		{"WithOffset", "DELETE FROM test WHERE age = 10 OFFSET 20",
+			stream.New(stream.SeqScan("test")).
+				Pipe(stream.Filter(MustParseExpr("age = 10"))).
+				Pipe(stream.Skip(20)).
+				Pipe(stream.TableDelete("test")),
+		},
+		{"WithLimit", "DELETE FROM test LIMIT 10",
+			stream.New(stream.SeqScan("test")).
+				Pipe(stream.Take(10)).
+				Pipe(stream.TableDelete("test")),
+		},
+		{"WithOrderByThenOffset", "DELETE FROM test WHERE age = 10 ORDER BY age OFFSET 20",
+			stream.New(stream.SeqScan("test")).
+				Pipe(stream.Filter(MustParseExpr("age = 10"))).
+				Pipe(stream.Sort(MustParseExpr("age"))).
+				Pipe(stream.Skip(20)).
+				Pipe(stream.TableDelete("test")),
+		},
+		{"WithOrderByThenLimitThenOffset", "DELETE FROM test WHERE age = 10 ORDER BY age LIMIT 10 OFFSET 20",
+			stream.New(stream.SeqScan("test")).
+				Pipe(stream.Filter(MustParseExpr("age = 10"))).
+				Pipe(stream.Sort(MustParseExpr("age"))).
+				Pipe(stream.Skip(20)).
+				Pipe(stream.Take(10)).
+				Pipe(stream.TableDelete("test")),
+		},
 	}
 
 	for _, test := range tests {
diff --git a/sql/query/delete_test.go b/sql/query/delete_test.go
index 3ba0a12e..93df7a68 100644
--- a/sql/query/delete_test.go
+++ b/sql/query/delete_test.go
@@ -17,10 +17,15 @@ func TestDeleteStmt(t *testing.T) {
 		expected string
 		params   []interface{}
 	}{
-		{"No cond", `DELETE FROM test`, false, "", nil},
-		{"With cond", "DELETE FROM test WHERE b = 'bar1'", false, `{"d": "foo3", "b": "bar2", "e": "bar3"}`, nil},
-		{"Table not found", "DELETE FROM foo WHERE b = 'bar1'", true, "", nil},
-		{"Read-only table", "DELETE FROM __genji_tables", true, "", nil},
+		{"No cond", `DELETE FROM test`, false, "[]", nil},
+		{"With cond", "DELETE FROM test WHERE b = 'bar1'", false, `[{"d": "foo3", "b": "bar2", "e": "bar3", "n": 1}]`, nil},
+		{"With offset", "DELETE FROM test OFFSET 1", false, `[{"a":"foo1", "b":"bar1", "c":"baz1", "n": 3}]`, nil},
+		{"With order by then offset", "DELETE FROM test ORDER BY n OFFSET 1", false, `[{"d":"foo3", "b":"bar2", "e":"bar3", "n": 1}]`, nil},
+		{"With order by DESC then offset", "DELETE FROM test ORDER BY n DESC OFFSET 1", false, `[{"a": "foo1", "b": "bar1", "c": "baz1", "n": 3}]`, nil},
+		{"With limit", "DELETE FROM test ORDER BY n LIMIT 2", false, `[{"a":"foo1", "b":"bar1", "c":"baz1", "n": 3}]`, nil},
+		{"With order by then limit then offset", "DELETE FROM test ORDER BY n LIMIT 1 OFFSET 1", false, `[{"a": "foo1", "b": "bar1", "c": "baz1", "n": 3}, {"d": "foo3", "b": "bar2", "e": "bar3", "n": 1}]`, nil},
+		{"Table not found", "DELETE FROM foo WHERE b = 'bar1'", true, "[]", nil},
+		{"Read-only table", "DELETE FROM __genji_tables", true, "[]", nil},
 	}
 
 	for _, test := range tests {
@@ -31,11 +36,11 @@ func TestDeleteStmt(t *testing.T) {
 
 			err = db.Exec("CREATE TABLE test")
 			require.NoError(t, err)
-			err = db.Exec("INSERT INTO test (a, b, c) VALUES ('foo1', 'bar1', 'baz1')")
+			err = db.Exec("INSERT INTO test (a, b, c, n) VALUES ('foo1', 'bar1', 'baz1', 3)")
 			require.NoError(t, err)
-			err = db.Exec("INSERT INTO test (a, b) VALUES ('foo2', 'bar1')")
+			err = db.Exec("INSERT INTO test (a, b, n) VALUES ('foo2', 'bar1', 2)")
 			require.NoError(t, err)
-			err = db.Exec("INSERT INTO test (d, b, e) VALUES ('foo3', 'bar2', 'bar3')")
+			err = db.Exec("INSERT INTO test (d, b, e, n) VALUES ('foo3', 'bar2', 'bar3', 1)")
 			require.NoError(t, err)
 
 			err = db.Exec(test.query, test.params...)
@@ -50,13 +55,9 @@ func TestDeleteStmt(t *testing.T) {
 			defer st.Close()
 
 			var buf bytes.Buffer
-			err = document.IteratorToJSON(&buf, st)
+			err = document.IteratorToJSONArray(&buf, st)
 			require.NoError(t, err)
-			if len(test.expected) == 0 {
-				require.Equal(t, 0, buf.Len())
-			} else {
-				require.JSONEq(t, test.expected, buf.String())
-			}
+			require.JSONEq(t, test.expected, buf.String())
 		})
 	}
 }
diff --git a/sql/query/expr/env_test.go b/sql/query/expr/env_test.go
new file mode 100644
index 00000000..18d4868b
--- /dev/null
+++ b/sql/query/expr/env_test.go
@@ -0,0 +1,38 @@
+package expr_test
+
+import (
+	"testing"
+
+	"github.com/genjidb/genji/database"
+	"github.com/genjidb/genji/document"
+	"github.com/genjidb/genji/sql/query/expr"
+	"github.com/stretchr/testify/require"
+)
+
+func TestEnvironmentClone(t *testing.T) {
+	d := document.NewFieldBuffer()
+	d.Add("answer", document.NewIntegerValue(42))
+
+	p := expr.Param{Name: "param", Value: 1}
+	tx := &database.Transaction{}
+
+	vars := document.NewFieldBuffer()
+	vars.Add("var", document.NewIntegerValue(2))
+
+	env := expr.NewEnvironment(d, p)
+	outer := expr.NewEnvironment(nil)
+
+	env.Tx = tx
+	env.Outer = outer
+	env.Vars = vars
+
+	newEnv, err := env.Clone()
+	require.NoError(t, err)
+
+	require.Equal(t, d, newEnv.Doc)
+	require.Equal(t, 1, len(newEnv.Params))
+	require.Equal(t, p, newEnv.Params[0])
+	require.Equal(t, tx, newEnv.Tx)
+	require.Equal(t, vars, newEnv.Vars)
+	require.Equal(t, outer, newEnv.Outer)
+}