Repository: genjidb/genji
Pull request #408 (2021-06-04 18:47:41)

Add union all clause

codecov-commenter: # [Codecov](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb) Report
> Merging [#408](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb) (fdea749) into [main](https://codecov.io/gh/genjidb/genji/commit/8812a7a39f62aef8bf1adb4b07936307026d07ad?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb) (8812a7a) will **increase** coverage by `0.20%`.
> The diff coverage is `48.27%`.

[![Impacted file tree graph](https://codecov.io/gh/genjidb/genji/pull/408/graphs/tree.svg?width=650&height=150&src=pr&token=nwR1GpvtyH&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb)](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb)

```diff
@@            Coverage Diff             @@
##             main     #408      +/-   ##
==========================================
+ Coverage   68.15%   68.36%   +0.20%     
==========================================
  Files          82       83       +1     
  Lines        7760     7789      +29     
==========================================
+ Hits         5289     5325      +36     
+ Misses       1809     1792      -17     
- Partials      662      672      +10     
```


| [Impacted Files](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb) | Coverage Δ | |
|---|---|---|
| [internal/query/statement/select.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvcXVlcnkvc3RhdGVtZW50L3NlbGVjdC5nbw==) | `87.34% <0.00%> (-2.27%)` | :arrow_down: |
| [internal/sql/scanner/token.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvc3FsL3NjYW5uZXIvdG9rZW4uZ28=) | `10.71% <ø> (ø)` | |
| [internal/sql/parser/select.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvc3FsL3BhcnNlci9zZWxlY3QuZ28=) | `57.83% <50.00%> (-1.33%)` | :arrow_down: |
| [internal/stream/concat.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvc3RyZWFtL2NvbmNhdC5nbw==) | `50.00% <50.00%> (ø)` | |
| [internal/planner/optimizer.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvcGxhbm5lci9vcHRpbWl6ZXIuZ28=) | `75.82% <55.55%> (+0.61%)` | :arrow_up: |
| [internal/query/query.go](https://codecov.io/gh/genjidb/genji/pull/408/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb#diff-aW50ZXJuYWwvcXVlcnkvcXVlcnkuZ28=) | `52.87% <0.00%> (+20.68%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb). Last update [8812a7a...fdea749](https://codecov.io/gh/genjidb/genji/pull/408?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=genjidb).


Patch:
diff --git a/cmd/genji/go.sum b/cmd/genji/go.sum
index 5ace5946..f2db90fc 100644
--- a/cmd/genji/go.sum
+++ b/cmd/genji/go.sum
@@ -210,6 +210,7 @@ google.golang.org/genproto v0.0.0-20190425155659-357c62f0e4bb/go.mod h1:VzzqZJRn
 google.golang.org/grpc v1.19.0/go.mod h1:mqu4LbDTu4XGKhr4mRzUsmM4RtVoemTSY81AxZiDr8c=
 google.golang.org/grpc v1.20.1/go.mod h1:10oTOabMzJvdu6/UiuZezV6QK5dSlG84ov/aaiqXj38=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15 h1:YR8cESwS4TdDjEe65xsg0ogRM/Nc3DYOhEAlW+xobZo=
 gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/yaml.v2 v2.2.1/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
diff --git a/engine/badgerengine/go.sum b/engine/badgerengine/go.sum
index 1f20516e..a8d35528 100644
--- a/engine/badgerengine/go.sum
+++ b/engine/badgerengine/go.sum
@@ -164,6 +164,7 @@ google.golang.org/genproto v0.0.0-20190425155659-357c62f0e4bb/go.mod h1:VzzqZJRn
 google.golang.org/grpc v1.19.0/go.mod h1:mqu4LbDTu4XGKhr4mRzUsmM4RtVoemTSY81AxZiDr8c=
 google.golang.org/grpc v1.20.1/go.mod h1:10oTOabMzJvdu6/UiuZezV6QK5dSlG84ov/aaiqXj38=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15 h1:YR8cESwS4TdDjEe65xsg0ogRM/Nc3DYOhEAlW+xobZo=
 gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/yaml.v2 v2.2.1/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
diff --git a/go.mod b/go.mod
index 306f85db..50b0125c 100644
--- a/go.mod
+++ b/go.mod
@@ -4,11 +4,14 @@ go 1.16
 
 require (
 	github.com/buger/jsonparser v1.1.1
+	github.com/davecgh/go-spew v1.1.1 // indirect
 	github.com/google/btree v1.0.1
 	github.com/google/go-cmp v0.5.5
+	github.com/kr/pretty v0.1.0 // indirect
 	github.com/stretchr/testify v1.7.0
 	github.com/vmihailenco/msgpack/v5 v5.3.2
 	go.etcd.io/bbolt v1.3.5
 	golang.org/x/sync v0.0.0-20210220032951-036812b2e83c
 	golang.org/x/tools v0.1.1
+	gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127 // indirect
 )
diff --git a/go.sum b/go.sum
index 16e1b4b9..7252b59f 100644
--- a/go.sum
+++ b/go.sum
@@ -1,11 +1,17 @@
 github.com/buger/jsonparser v1.1.1 h1:2PnMjfWD7wBILjqQbt530v576A/cAbQvEW9gGIpYMUs=
 github.com/buger/jsonparser v1.1.1/go.mod h1:6RYKKt7H4d4+iWqouImQ9R2FZql3VbhNgx27UK13J/0=
-github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
 github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/google/btree v1.0.1 h1:gK4Kx5IaGY9CD5sPJ36FHiBJ6ZXl0kilRiiCj+jdYp4=
 github.com/google/btree v1.0.1/go.mod h1:xXMiIv4Fb/0kKde4SpL7qlzvu5cMJDRkFDxJfI9uaxA=
 github.com/google/go-cmp v0.5.5 h1:Khx7svrCpmxxtHBq5j2mp/xVjsi8hQMfNLvJFAlrGgU=
 github.com/google/go-cmp v0.5.5/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
+github.com/kr/pretty v0.1.0 h1:L/CwN0zerZDmRFUapSPitk6f+Q3+0za1rQkzVuMiMFI=
+github.com/kr/pretty v0.1.0/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
+github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
+github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
+github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
 github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
 github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
@@ -48,7 +54,8 @@ golang.org/x/xerrors v0.0.0-20191011141410-1b5146add898/go.mod h1:I/5z698sn9Ka8T
 golang.org/x/xerrors v0.0.0-20191204190536-9bdfabe68543/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
 golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 h1:go1bK/D/BFZV2I8cIQd1NKEZ+0owSTG1fDTci4IqFcE=
 golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
-gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127 h1:qIbj1fsPNlZgppZ+VLlY7N33q108Sa+fhmuc+sWQYwY=
+gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c h1:dUUwHk2QECo/6vqA44rthZ8ie2QXMNeKRTHCNY2nXvo=
 gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/internal/planner/optimizer.go b/internal/planner/optimizer.go
index e0d53de3..1eb92cae 100644
--- a/internal/planner/optimizer.go
+++ b/internal/planner/optimizer.go
@@ -25,6 +25,21 @@ var optimizerRules = []func(s *stream.Stream, tx *database.Transaction) (*stream
 func Optimize(s *stream.Stream, tx *database.Transaction) (*stream.Stream, error) {
 	var err error
 
+	if firstNode, ok := s.First().(*stream.ConcatOperator); ok {
+		// If the first operation is a concat, optimize both streams individually.
+		s1, err := Optimize(firstNode.S1, tx)
+		if err != nil {
+			return nil, err
+		}
+		s2, err := Optimize(firstNode.S2, tx)
+		if err != nil {
+			return nil, err
+		}
+
+		firstNode.S1, firstNode.S2 = s1, s2
+		return s, nil
+	}
+
 	for _, rule := range optimizerRules {
 		s, err = rule(s, tx)
 		if err != nil {
diff --git a/internal/query/statement/select.go b/internal/query/statement/select.go
index 83f94ab7..b68e1721 100644
--- a/internal/query/statement/select.go
+++ b/internal/query/statement/select.go
@@ -20,6 +20,10 @@ type SelectStmt struct {
 	OffsetExpr       expr.Expr
 	LimitExpr        expr.Expr
 	ProjectionExprs  []expr.Expr
+	Union            struct {
+		All        bool
+		SelectStmt *StreamStmt
+	}
 }
 
 func (stmt *SelectStmt) ToStream() (*StreamStmt, error) {
@@ -165,6 +169,10 @@ func (stmt *SelectStmt) ToStream() (*StreamStmt, error) {
 		s = s.Pipe(stream.Take(v.V.(int64)))
 	}
 
+	if stmt.Union.SelectStmt != nil {
+		s = stream.New(stream.Concat(s, stmt.Union.SelectStmt.Stream))
+	}
+
 	return &StreamStmt{
 		Stream:   s,
 		ReadOnly: true,
diff --git a/internal/sql/parser/select.go b/internal/sql/parser/select.go
index 120f76fe..bc325296 100644
--- a/internal/sql/parser/select.go
+++ b/internal/sql/parser/select.go
@@ -63,6 +63,12 @@ func (p *Parser) parseSelectStatement() (*statement.StreamStmt, error) {
 		return nil, err
 	}
 
+	// Parse union: "UNION expr"
+	stmt.Union.SelectStmt, stmt.Union.All, err = p.parseUnion()
+	if err != nil {
+		return nil, err
+	}
+
 	return stmt.ToStream()
 }
 
@@ -154,3 +160,22 @@ func (p *Parser) parseGroupBy() (expr.Expr, error) {
 	e, err := p.ParseExpr()
 	return e, err
 }
+
+func (p *Parser) parseUnion() (*statement.StreamStmt, bool, error) {
+	// Only UNION ALL is supported for the moment
+	if ok, err := p.parseOptional(scanner.UNION, scanner.ALL); !ok || err != nil {
+		return nil, false, err
+	}
+
+	err := p.parseTokens(scanner.SELECT)
+	if err != nil {
+		return nil, false, err
+	}
+
+	otherSelect, err := p.parseSelectStatement()
+	if err != nil {
+		return nil, false, err
+	}
+
+	return otherSelect, false, nil
+}
diff --git a/internal/sql/scanner/token.go b/internal/sql/scanner/token.go
index 8d303ad2..42157440 100644
--- a/internal/sql/scanner/token.go
+++ b/internal/sql/scanner/token.go
@@ -77,6 +77,7 @@ const (
 	keywordBeg
 	// ALL and the following are Genji SQL Keywords
 	ADD_KEYWORD
+	ALL
 	ALTER
 	AS
 	ASC
@@ -123,6 +124,7 @@ const (
 	TABLE
 	TO
 	TRANSACTION
+	UNION
 	UNIQUE
 	UNSET
 	UPDATE
@@ -207,6 +209,7 @@ var tokens = [...]string{
 	DOT:         ".",
 
 	ADD_KEYWORD: "ADD",
+	ALL:         "ALL",
 	ALTER:       "ALTER",
 	AS:          "AS",
 	ASC:         "ASC",
@@ -253,6 +256,7 @@ var tokens = [...]string{
 	TABLE:       "TABLE",
 	TO:          "TO",
 	TRANSACTION: "TRANSACTION",
+	UNION:       "UNION",
 	UNIQUE:      "UNIQUE",
 	UNSET:       "UNSET",
 	UPDATE:      "UPDATE",
diff --git a/internal/stream/concat.go b/internal/stream/concat.go
new file mode 100644
index 00000000..bf3c3457
--- /dev/null
+++ b/internal/stream/concat.go
@@ -0,0 +1,31 @@
+package stream
+
+import (
+	"github.com/genjidb/genji/internal/expr"
+	"github.com/genjidb/genji/internal/stringutil"
+)
+
+// A ConcatOperator concatenates two streams.
+type ConcatOperator struct {
+	baseOperator
+	S1 *Stream
+	S2 *Stream
+}
+
+// Concat turns two individual streams into one.
+func Concat(s1 *Stream, s2 *Stream) *ConcatOperator {
+	return &ConcatOperator{S1: s1, S2: s2}
+}
+
+func (op *ConcatOperator) Iterate(in *expr.Environment, fn func(*expr.Environment) error) error {
+	err := op.S1.Iterate(in, fn)
+	if err != nil {
+		return err
+	}
+
+	return op.S2.Iterate(in, fn)
+}
+
+func (op *ConcatOperator) String() string {
+	return stringutil.Sprintf("concat(%s, %s)", op.S1, op.S2)
+}


Test patch:
diff --git a/internal/planner/optimizer_test.go b/internal/planner/optimizer_test.go
index 3dc46203..0d6272e9 100644
--- a/internal/planner/optimizer_test.go
+++ b/internal/planner/optimizer_test.go
@@ -811,3 +811,121 @@ func TestUseIndexBasedOnSelectionNodeRule_Composite(t *testing.T) {
 		}
 	})
 }
+
+func TestOptimize(t *testing.T) {
+	t.Run("concat operator operands are optimized", func(t *testing.T) {
+		t.Run("PrecalculateExprRule", func(t *testing.T) {
+			_, tx, cleanup := testutil.NewTestTx(t)
+			defer cleanup()
+			testutil.MustExec(t, tx, `
+						CREATE TABLE foo;
+						CREATE TABLE bar;
+			`)
+
+			got, err := planner.Optimize(
+				st.New(st.Concat(
+					st.New(st.SeqScan("foo")).Pipe(st.Filter(parser.MustParseExpr("a = 1 + 2"))),
+					st.New(st.SeqScan("bar")).Pipe(st.Filter(parser.MustParseExpr("b = 1 + 2"))),
+				)),
+				tx)
+
+			want := st.New(st.Concat(
+				st.New(st.SeqScan("foo")).Pipe(st.Filter(parser.MustParseExpr("a = 3"))),
+				st.New(st.SeqScan("bar")).Pipe(st.Filter(parser.MustParseExpr("b = 3"))),
+			))
+
+			require.NoError(t, err)
+			require.Equal(t, want.String(), got.String())
+		})
+
+		t.Run("RemoveUnnecessarySelectionNodesRule", func(t *testing.T) {
+			_, tx, cleanup := testutil.NewTestTx(t)
+			defer cleanup()
+			testutil.MustExec(t, tx, `
+						CREATE TABLE foo;
+						CREATE TABLE bar;
+			`)
+
+			got, err := planner.Optimize(
+				st.New(st.Concat(
+					st.New(st.SeqScan("foo")).Pipe(st.Filter(parser.MustParseExpr("10"))),
+					st.New(st.Concat(
+						st.New(st.SeqScan("bar")).Pipe(st.Filter(parser.MustParseExpr("11"))),
+						st.New(st.SeqScan("bar")).Pipe(st.Filter(parser.MustParseExpr("12"))),
+					)),
+				)),
+				tx)
+
+			want := st.New(st.Concat(
+				st.New(st.SeqScan("foo")),
+				st.New(st.Concat(
+					st.New(st.SeqScan("bar")),
+					st.New(st.SeqScan("bar")),
+				)),
+			))
+
+			require.NoError(t, err)
+			require.Equal(t, want.String(), got.String())
+		})
+
+		t.Run("RemoveUnnecessaryDedupNodeRule", func(t *testing.T) {
+			_, tx, cleanup := testutil.NewTestTx(t)
+			defer cleanup()
+			testutil.MustExec(t, tx, `
+				CREATE TABLE foo(a integer PRIMARY KEY);
+				CREATE TABLE bar(a integer PRIMARY KEY);
+			`)
+
+			got, err := planner.Optimize(
+				st.New(st.Concat(
+					st.New(st.SeqScan("foo")).
+						Pipe(st.Project(parser.MustParseExpr("a"))).
+						Pipe(st.Distinct()),
+					st.New(st.SeqScan("bar")).
+						Pipe(st.Project(parser.MustParseExpr("a"))).
+						Pipe(st.Distinct()),
+				)),
+				tx)
+
+			want := st.New(st.Concat(
+				st.New(st.SeqScan("foo")).
+					Pipe(st.Project(parser.MustParseExpr("a"))),
+				st.New(st.SeqScan("bar")).
+					Pipe(st.Project(parser.MustParseExpr("a"))),
+			))
+
+			require.NoError(t, err)
+			require.Equal(t, want.String(), got.String())
+		})
+	})
+
+	t.Run("UseIndexBasedOnSelectionNodeRule", func(t *testing.T) {
+		_, tx, cleanup := testutil.NewTestTx(t)
+		defer cleanup()
+		testutil.MustExec(t, tx, `
+				CREATE TABLE foo;
+				CREATE TABLE bar;
+				CREATE INDEX idx_foo_a_d ON foo(a, d);
+				CREATE INDEX idx_bar_a_d ON bar(a, d);
+			`)
+
+		got, err := planner.Optimize(
+			st.New(st.Concat(
+				st.New(st.SeqScan("foo")).
+					Pipe(st.Filter(parser.MustParseExpr("a = 1"))).
+					Pipe(st.Filter(parser.MustParseExpr("d = 2"))),
+				st.New(st.SeqScan("bar")).
+					Pipe(st.Filter(parser.MustParseExpr("a = 1"))).
+					Pipe(st.Filter(parser.MustParseExpr("d = 2"))),
+			)),
+			tx)
+
+		want := st.New(st.Concat(
+			st.New(st.IndexScan("idx_foo_a_d", st.IndexRange{Min: testutil.ExprList(t, `[1, 2]`), Exact: true})),
+			st.New(st.IndexScan("idx_bar_a_d", st.IndexRange{Min: testutil.ExprList(t, `[1, 2]`), Exact: true})),
+		))
+
+		require.NoError(t, err)
+		require.Equal(t, want.String(), got.String())
+	})
+}
diff --git a/internal/query/gen_select_with_union_test.go b/internal/query/gen_select_with_union_test.go
new file mode 100644
index 00000000..1c9aad7b
--- /dev/null
+++ b/internal/query/gen_select_with_union_test.go
@@ -0,0 +1,190 @@
+/*
+* CODE GENERATED AUTOMATICALLY WITH github.com/genjidb/genji/dev/gensqltest
+* THIS FILE SHOULD NOT BE EDITED BY HAND
+ */
+package query_test
+
+import (
+	"testing"
+
+	"github.com/genjidb/genji"
+	"github.com/genjidb/genji/internal/testutil"
+	"github.com/stretchr/testify/require"
+)
+
+func TestGenSelectWithUnion(t *testing.T) {
+	setup := func(t *testing.T, db *genji.DB) {
+		t.Helper()
+
+		q := `
+CREATE TABLE foo;
+CREATE TABLE bar;
+CREATE TABLE baz;
+INSERT INTO foo (a,b) VALUES (1.0, 1.0), (2.0, 2.0);
+INSERT INTO bar (a,b) VALUES (3.0, 3.0), (4.0, 4.0);
+INSERT INTO baz (x,y) VALUES ("a", "a"), ("b", "b");
+`
+		err := db.Exec(q)
+		require.NoError(t, err)
+	}
+
+	// --------------------------------------------------------------------------
+	t.Run("basic union all", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM bar;
+`
+			res, err := db.Query(q)
+			require.NoError(t, err)
+			defer res.Close()
+			raw := `
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "a": 3.0, "b": 3.0}
+{ "a": 4.0, "b": 4.0}
+`
+			testutil.RequireStreamEq(t, raw, res)
+		})
+
+	})
+
+	// --------------------------------------------------------------------------
+	t.Run("basic union all with diff fields", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM baz;
+`
+			res, err := db.Query(q)
+			require.NoError(t, err)
+			defer res.Close()
+			raw := `
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "x": "a", "y": "a"}
+{ "x": "b", "y": "b"}
+`
+			testutil.RequireStreamEq(t, raw, res)
+		})
+
+	})
+
+	// --------------------------------------------------------------------------
+	t.Run("union all with conditions", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo WHERE a > 1`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo WHERE a > 1
+UNION ALL
+SELECT * FROM baz WHERE x != "b";
+`
+			res, err := db.Query(q)
+			require.NoError(t, err)
+			defer res.Close()
+			raw := `
+{ "a": 2.0, "b": 2.0}
+{ "x": "a", "y": "a"}
+`
+			testutil.RequireStreamEq(t, raw, res)
+		})
+
+	})
+
+	// --------------------------------------------------------------------------
+	t.Run("self union all", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo WHERE a > 1`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo WHERE a > 1
+UNION ALL
+SELECT * FROM foo WHERE a <= 1;
+`
+			res, err := db.Query(q)
+			require.NoError(t, err)
+			defer res.Close()
+			raw := `
+{ "a": 2.0, "b": 2.0}
+{ "a": 1.0, "b": 1.0}
+`
+			testutil.RequireStreamEq(t, raw, res)
+		})
+
+	})
+
+	// --------------------------------------------------------------------------
+	t.Run("multiple unions all", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM bar
+UNION ALL SELECT * FROM baz;
+`
+			res, err := db.Query(q)
+			require.NoError(t, err)
+			defer res.Close()
+			raw := `
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "a": 3.0, "b": 3.0}
+{ "a": 4.0, "b": 4.0}
+{ "x": "a", "y": "a"}
+{ "x": "b", "y": "b"}
+`
+			testutil.RequireStreamEq(t, raw, res)
+		})
+
+	})
+
+	// --------------------------------------------------------------------------
+	t.Run("basic union", func(t *testing.T) {
+		db, err := genji.Open(":memory:")
+		require.NoError(t, err)
+		defer db.Close()
+
+		setup(t, db)
+
+		t.Run(`SELECT * FROM foo`, func(t *testing.T) {
+			q := `
+SELECT * FROM foo
+UNION
+SELECT * FROM bar;
+`
+			err := db.Exec(q)
+			require.Errorf(t, err, "expected\n%s\nto raise an error but got none", q)
+		})
+
+	})
+
+}
diff --git a/internal/query/gen_select_with_union_test.sql b/internal/query/gen_select_with_union_test.sql
new file mode 100644
index 00000000..3183a82b
--- /dev/null
+++ b/internal/query/gen_select_with_union_test.sql
@@ -0,0 +1,68 @@
+-- setup:
+CREATE TABLE foo;
+CREATE TABLE bar;
+CREATE TABLE baz;
+INSERT INTO foo (a,b) VALUES (1.0, 1.0), (2.0, 2.0);
+INSERT INTO bar (a,b) VALUES (3.0, 3.0), (4.0, 4.0);
+INSERT INTO baz (x,y) VALUES ("a", "a"), ("b", "b");
+
+-- test: basic union all
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM bar;
+/* result:
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "a": 3.0, "b": 3.0}
+{ "a": 4.0, "b": 4.0}
+*/
+
+-- test: basic union all with diff fields
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM baz;
+/* result:
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "x": "a", "y": "a"}
+{ "x": "b", "y": "b"}
+*/
+
+-- test: union all with conditions
+SELECT * FROM foo WHERE a > 1
+UNION ALL
+SELECT * FROM baz WHERE x != "b";
+/* result:
+{ "a": 2.0, "b": 2.0}
+{ "x": "a", "y": "a"}
+*/
+
+-- test: self union all
+SELECT * FROM foo WHERE a > 1
+UNION ALL
+SELECT * FROM foo WHERE a <= 1;
+/* result:
+{ "a": 2.0, "b": 2.0}
+{ "a": 1.0, "b": 1.0}
+*/
+
+-- test: multiple unions all
+SELECT * FROM foo
+UNION ALL
+SELECT * FROM bar
+UNION ALL SELECT * FROM baz;
+/* result:
+{ "a": 1.0, "b": 1.0}
+{ "a": 2.0, "b": 2.0}
+{ "a": 3.0, "b": 3.0}
+{ "a": 4.0, "b": 4.0}
+{ "x": "a", "y": "a"}
+{ "x": "b", "y": "b"}
+*/
+
+-- test: basic union
+SELECT * FROM foo
+UNION
+SELECT * FROM bar;
+-- error:
+-- not implemented for now
diff --git a/internal/sql/parser/select_test.go b/internal/sql/parser/select_test.go
index 644f8085..d50b8b0d 100644
--- a/internal/sql/parser/select_test.go
+++ b/internal/sql/parser/select_test.go
@@ -124,6 +124,31 @@ func TestParserSelect(t *testing.T) {
 				Pipe(stream.HashAggregate(&expr.CountFunc{Wildcard: true})).
 				Pipe(stream.Project(testutil.ParseNamedExpr(t, "COUNT(*)"))),
 			false},
+		{"WithUnionAll", "SELECT * FROM test1 UNION ALL SELECT * FROM test2",
+			stream.New(stream.Concat(
+				stream.New(stream.SeqScan("test1")).Pipe(stream.Project(expr.Wildcard{})),
+				stream.New(stream.SeqScan("test2")).Pipe(stream.Project(expr.Wildcard{})),
+			)),
+			false,
+		},
+		{"CondWithUnionAll", "SELECT * FROM test1 WHERE age = 10 UNION ALL SELECT * FROM test2",
+			stream.New(stream.Concat(
+				stream.New(stream.SeqScan("test1")).
+					Pipe(stream.Filter(parser.MustParseExpr("age = 10"))).
+					Pipe(stream.Project(expr.Wildcard{})),
+				stream.New(stream.SeqScan("test2")).Pipe(stream.Project(expr.Wildcard{})),
+			)),
+			false,
+		},
+		{"WithUnionAllThenUnionAll", "SELECT * FROM test1 UNION ALL SELECT * FROM test2 UNION ALL SELECT * FROM test3",
+			stream.New(stream.Concat(
+				stream.New(stream.SeqScan("test1")).Pipe(stream.Project(expr.Wildcard{})),
+				stream.New(stream.Concat(
+					stream.New(stream.SeqScan("test2")).Pipe(stream.Project(expr.Wildcard{})),
+					stream.New(stream.SeqScan("test3")).Pipe(stream.Project(expr.Wildcard{})),
+				)))),
+			false,
+		},
 	}
 
 	for _, test := range tests {
diff --git a/internal/sql/scanner/scanner_test.go b/internal/sql/scanner/scanner_test.go
index 69db430d..708618b3 100644
--- a/internal/sql/scanner/scanner_test.go
+++ b/internal/sql/scanner/scanner_test.go
@@ -119,6 +119,7 @@ func TestScanner_Scan(t *testing.T) {
 		{s: `ALTER`, tok: ALTER},
 		{s: `AS`, tok: AS},
 		{s: `ASC`, tok: ASC},
+		{s: `ALL`, tok: ALL},
 		{s: `BY`, tok: BY},
 		{s: `BEGIN`, tok: BEGIN},
 		{s: `BETWEEN`, tok: BETWEEN},
@@ -157,6 +158,7 @@ func TestScanner_Scan(t *testing.T) {
 		{s: `TO`, tok: TO},
 		{s: `TRANSACTION`, tok: TRANSACTION},
 		{s: `UPDATE`, tok: UPDATE},
+		{s: `UNION`, tok: UNION},
 		{s: `UNSET`, tok: UNSET},
 		{s: `VALUES`, tok: VALUES},
 		{s: `WHERE`, tok: WHERE},
diff --git a/internal/stream/concat_test.go b/internal/stream/concat_test.go
new file mode 100644
index 00000000..1a3034b7
--- /dev/null
+++ b/internal/stream/concat_test.go
@@ -0,0 +1,39 @@
+package stream_test
+
+import (
+	"testing"
+
+	"github.com/genjidb/genji/document"
+	"github.com/genjidb/genji/internal/expr"
+	"github.com/genjidb/genji/internal/stream"
+	"github.com/genjidb/genji/internal/testutil"
+	"github.com/stretchr/testify/require"
+)
+
+func TestConcatOperator(t *testing.T) {
+	in1 := []document.Document{
+		testutil.MakeDocument(t, `{"a": 10}`),
+		testutil.MakeDocument(t, `{"a": 11}`),
+	}
+	in2 := []document.Document{
+		testutil.MakeDocument(t, `{"a": 12}`),
+		testutil.MakeDocument(t, `{"a": 13}`),
+	}
+
+	s1 := stream.New(stream.Documents(in1...))
+	s2 := stream.New(stream.Documents(in2...))
+	s := stream.Concat(s1, s2)
+
+	var got []document.Document
+	s.Iterate(new(expr.Environment), func(env *expr.Environment) error {
+		d, ok := env.GetDocument()
+		require.True(t, ok)
+		got = append(got, d)
+		return nil
+	})
+
+	want := append(in1, in2...)
+	for i, w := range want {
+		testutil.RequireDocEqual(t, w, got[i])
+	}
+}