aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/vm/sqlvm/errors/errors.go7
-rw-r--r--core/vm/sqlvm/planner/plan.go78
-rw-r--r--core/vm/sqlvm/planner/planner.go488
-rw-r--r--core/vm/sqlvm/planner/planner_test.go878
-rw-r--r--core/vm/sqlvm/planner/types.go166
-rw-r--r--core/vm/sqlvm/planner/utils.go149
-rw-r--r--core/vm/sqlvm/planner/utils_test.go128
7 files changed, 1894 insertions, 0 deletions
diff --git a/core/vm/sqlvm/errors/errors.go b/core/vm/sqlvm/errors/errors.go
index b6c3909af..9a22bf453 100644
--- a/core/vm/sqlvm/errors/errors.go
+++ b/core/vm/sqlvm/errors/errors.go
@@ -71,6 +71,7 @@ const (
ErrorCategoryLimit
ErrorCategoryGrammar
ErrorCategorySemantic
+ ErrorCategoryPlanner
ErrorCategoryRuntime
)
@@ -78,6 +79,7 @@ var errorCategoryMap = [...]string{
ErrorCategoryLimit: "limit",
ErrorCategoryGrammar: "grammar",
ErrorCategorySemantic: "semantic",
+ ErrorCategoryPlanner: "planner",
ErrorCategoryRuntime: "runtime",
}
@@ -111,6 +113,8 @@ const (
ErrorCodeDecimalEncode
ErrorCodeDecimalDecode
+ // Planner Error
+ ErrorCodePlanner
// Runtime Error
ErrorCodeInvalidOperandNum
ErrorCodeInvalidDataType
@@ -145,6 +149,9 @@ var errorCodeMap = [...]string{
ErrorCodeInvalidUfixedFractionalDigits: "invalid ufixed fractional digits",
ErrorCodeDecimalEncode: "decimal encode failed",
ErrorCodeDecimalDecode: "decimal decode failed",
+
+ // Planner Error
+ ErrorCodePlanner: "planner failure", // TODO: fix the message.
// Runtime Error
ErrorCodeInvalidOperandNum: "invalid operand number",
ErrorCodeInvalidDataType: "invalid data type",
diff --git a/core/vm/sqlvm/planner/plan.go b/core/vm/sqlvm/planner/plan.go
new file mode 100644
index 000000000..a900fa51c
--- /dev/null
+++ b/core/vm/sqlvm/planner/plan.go
@@ -0,0 +1,78 @@
+package planner
+
+import (
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/ast"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+)
+
+// Collect common plan step constructors here, so that the cost calculation
+// can be viewed at once.
+
+func (planner *planner) newScanTable(
+ tableRef schema.TableRef,
+ condition *clause,
+) PlanStep {
+ p := &ScanTable{}
+ p.Table = planner.tableRef
+ if condition != nil {
+ p.ColumnSet = condition.ColumnSet
+ p.Condition = condition.OriginAst
+ }
+ p.Cost = 10 // TODO(yenlin): calculate cost.
+ return p
+}
+
+func (planner *planner) newScanIndices(
+ tableRef schema.TableRef,
+ indexRef schema.IndexRef,
+ hashKeys [][]ast.Valuer,
+) PlanStep {
+ p := &ScanIndices{}
+ p.Cost = 0 // TODO(yenlin): calculate cost.
+ p.Table = tableRef
+ p.Index = indexRef
+ p.Values = hashKeys
+ return p
+}
+
+func (planner *planner) newScanIndexValues(
+ tableRef schema.TableRef,
+ indexRef schema.IndexRef,
+ condition *clause,
+) PlanStep {
+ index := planner.table.Indices[indexRef]
+ p := &ScanIndexValues{}
+ p.Table = tableRef
+ p.Index = indexRef
+ p.Condition = condition.OriginAst
+ // TODO(yenlin): calculate cost.
+ p.Cost = uint64(len(index.Columns) - len(condition.ColumnSet))
+ return p
+}
+
+func (planner *planner) newFilterStep(
+ condition *clause,
+ tableRef schema.TableRef,
+ source PlanStep,
+) PlanStep {
+ p := &FilterStep{
+ Table: tableRef,
+ ColumnSet: condition.ColumnSet,
+ Condition: condition.OriginAst,
+ }
+ p.Operands = []PlanStep{source}
+ p.Cost = source.GetCost() // TODO(yenlin): calculate cost.
+ return p
+}
+
+func (planner *planner) newUnionStep(
+ subPlans []PlanStep,
+) PlanStep {
+ p := &UnionStep{}
+ p.Cost = 1 // TODO(yenlin): calculate cost.
+ for _, subPlan := range subPlans {
+ p.Cost += subPlan.GetCost()
+ }
+ p.Operands = subPlans
+ return p
+}
diff --git a/core/vm/sqlvm/planner/planner.go b/core/vm/sqlvm/planner/planner.go
new file mode 100644
index 000000000..bf594403b
--- /dev/null
+++ b/core/vm/sqlvm/planner/planner.go
@@ -0,0 +1,488 @@
+package planner
+
+import (
+ "github.com/dexon-foundation/decimal"
+
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/ast"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/common"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/errors"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+)
+
+const (
+ maxHashKeySize = 64
+ maxPlanDepth = 5
+)
+
+type planner struct {
+ context *common.Context
+ schema schema.Schema
+ tableRef schema.TableRef
+ table *schema.Table
+}
+
+func idNodeToTable(node *ast.IdentifierNode) schema.TableRef {
+ return node.Desc.(*schema.TableDescriptor).Table
+}
+
+func idNodeToColumn(node *ast.IdentifierNode) (schema.TableRef, schema.ColumnRef) {
+ desc := node.Desc.(*schema.ColumnDescriptor)
+ return desc.Table, desc.Column
+}
+
+func (planner *planner) planInsert(stmt *ast.InsertStmtNode) (PlanStep, error) {
+ planner.tableRef = idNodeToTable(stmt.Table)
+ planner.table = &planner.schema[planner.tableRef]
+
+ plan := &InsertStep{}
+ plan.Table = planner.tableRef
+
+ switch node := stmt.Insert.(type) {
+ case *ast.InsertWithColumnOptionNode:
+ plan.Columns = make([]schema.ColumnRef, len(node.Column))
+ for i, node := range node.Column {
+ _, plan.Columns[i] = idNodeToColumn(node)
+ }
+ plan.Values = node.Value
+ case *ast.InsertWithDefaultOptionNode:
+ plan.Values = [][]ast.ExprNode{[]ast.ExprNode{}}
+ }
+ return plan, nil
+}
+
+func (planner *planner) mergeAndHashKeys(cl *clause) {
+ // Merge hash keys from sub-clause in disjoint AND.
+ colNum := len(cl.ColumnSet)
+ leftLen := len(cl.SubCls[0].HashKeys)
+ rightLen := len(cl.SubCls[1].HashKeys)
+ totalLen := leftLen * rightLen
+ // Ignore enumerable if the hask key size is too big.
+ if totalLen > maxHashKeySize {
+ cl.Attr = cl.Attr &^ clauseAttrEnumerable
+ return
+ }
+ // Prepare columns idx mapping.
+ leftCols := cl.SubCls[0].ColumnSet
+ leftColMap := make([]int, len(cl.SubCls[0].ColumnSet))
+ rightCols := cl.SubCls[1].ColumnSet
+ rightColMap := make([]int, len(cl.SubCls[1].ColumnSet))
+ for i, j, k := 0, 0, 0; k < colNum; {
+ switch {
+ case i < len(leftCols) &&
+ compareColumn(leftCols[i], cl.ColumnSet[k]) == 0:
+ leftColMap[i] = k
+ i++
+ case j < len(rightCols) &&
+ compareColumn(rightCols[j], cl.ColumnSet[k]) == 0:
+ rightColMap[j] = k
+ j++
+ default:
+ panic("Merging hash keys of invalid clauses.")
+ }
+ k++
+ }
+ cl.HashKeys = make([][]ast.Valuer, totalLen)
+ for i := 0; i < totalLen; i++ {
+ row := make([]ast.Valuer, colNum)
+ for j, colIdx := range leftColMap {
+ row[colIdx] = cl.SubCls[0].HashKeys[i%leftLen][j]
+ }
+ for j, colIdx := range rightColMap {
+ row[colIdx] = cl.SubCls[1].HashKeys[i/leftLen][j]
+ }
+ cl.HashKeys[i] = row
+ }
+}
+
+func (planner *planner) mergeOrHashKeys(cl *clause) {
+ // Merge hash keys from sub-clause with same ColumnSet in OR.
+ totalLen := len(cl.SubCls[0].HashKeys)
+ totalLen += len(cl.SubCls[1].HashKeys)
+ // Ignore enumerable if the hask key size is too big.
+ if totalLen > maxHashKeySize {
+ cl.Attr = cl.Attr &^ clauseAttrEnumerable
+ return
+ }
+ cl.HashKeys = make([][]ast.Valuer, totalLen)
+ i := 0
+ for _, keys := range cl.SubCls[0].HashKeys {
+ cl.HashKeys[i] = keys
+ i++
+ }
+ for _, keys := range cl.SubCls[1].HashKeys {
+ cl.HashKeys[i] = keys
+ i++
+ }
+}
+
+func (planner *planner) parseClause(node ast.ExprNode) (*clause, error) {
+ // General parsing.
+ cl := &clause{
+ OriginAst: node,
+ }
+ children := node.GetChildren()
+ // Parse sub expressions.
+ for _, c := range children {
+ child, ok := c.(ast.ExprNode)
+ if !ok {
+ continue
+ }
+ subCl, err := planner.parseClause(child)
+ if err != nil {
+ return nil, err
+ }
+ cl.SubCls = append(cl.SubCls, subCl)
+ cl.ColumnSet = cl.ColumnSet.Join(subCl.ColumnSet)
+ // General attributes.
+ cl.Attr |= subCl.Attr & clauseAttrForceScan
+ }
+
+ // Special attributes.
+ switch op := node.(type) {
+ case *ast.IdentifierNode:
+ // Column.
+ switch desc := op.Desc.(type) {
+ case *schema.ColumnDescriptor:
+ cl.ColumnSet = []*schema.ColumnDescriptor{desc}
+ default:
+ // This is function name.
+ // TODO(yenlin): distinguish function name from column names.
+ break
+ }
+ // TODO(yenlin): bool column is directly enumerable.
+ cl.Attr |= clauseAttrColumn
+ case ast.Valuer:
+ // Constant value.
+ if node.IsConstant() {
+ cl.Attr |= clauseAttrConst
+ cl.HashKeys = [][]ast.Valuer{[]ast.Valuer{op}}
+ }
+ case ast.UnaryOperator:
+ // Unary op.
+ // TODO(yenlin): negation of bool column is still enumerable.
+ case ast.BinaryOperator:
+ // Binary op.
+ if cl.Attr&clauseAttrForceScan != 0 {
+ // No need of optimization.
+ break
+ }
+ // Set optimization attributes by detailed type.
+ switch node.(type) {
+ case *ast.AndOperatorNode:
+ cl.Attr |= clauseAttrAnd
+ if cl.SubCls[0].ColumnSet.IsDisjoint(cl.SubCls[1].ColumnSet) &&
+ (cl.SubCls[0].Attr&clauseAttrEnumerable != 0) &&
+ (cl.SubCls[1].Attr&clauseAttrEnumerable != 0) {
+ cl.Attr |= clauseAttrEnumerable
+ planner.mergeAndHashKeys(cl)
+ }
+ case *ast.OrOperatorNode:
+ cl.Attr |= clauseAttrOr
+ if cl.SubCls[0].ColumnSet.Equal(cl.SubCls[1].ColumnSet) &&
+ (cl.SubCls[0].Attr&clauseAttrEnumerable != 0) &&
+ (cl.SubCls[1].Attr&clauseAttrEnumerable != 0) {
+ cl.Attr |= clauseAttrEnumerable
+ planner.mergeOrHashKeys(cl)
+ }
+ case *ast.EqualOperatorNode:
+ hashableAttr := clauseAttrConst | clauseAttrColumn
+ attrs := (cl.SubCls[0].Attr | cl.SubCls[1].Attr)
+ attrs &= hashableAttr
+ if attrs == hashableAttr {
+ cl.Attr |= clauseAttrEnumerable
+ if cl.SubCls[0].Attr&clauseAttrConst != 0 {
+ cl.HashKeys = cl.SubCls[0].HashKeys
+ } else {
+ cl.HashKeys = cl.SubCls[1].HashKeys
+ }
+ }
+ }
+ case *ast.InOperatorNode:
+ if cl.Attr&clauseAttrForceScan != 0 {
+ // No need of optimization.
+ break
+ }
+ left := cl.SubCls[0]
+ enumerable := (left.Attr & clauseAttrColumn) != 0
+ hashKeys := make([][]ast.Valuer, len(cl.SubCls)-1)
+ for i, right := range cl.SubCls[1:] {
+ if !enumerable {
+ break
+ }
+ if right.Attr&clauseAttrConst == 0 {
+ enumerable = false
+ break
+ }
+ hashKeys[i] = right.HashKeys[0]
+ }
+ if enumerable {
+ cl.Attr |= clauseAttrEnumerable
+ cl.HashKeys = hashKeys
+ }
+ case *ast.CastOperatorNode:
+ // No optimization can be done.
+ case *ast.FunctionOperatorNode:
+ // TODO(yenlin): enumerate the force scan function calls. (e.g. rand)
+ cl.Attr |= clauseAttrForceScan
+ default:
+ err := errors.Error{
+ Position: node.GetPosition(),
+ Category: errors.ErrorCategoryPlanner,
+ Code: errors.ErrorCodePlanner,
+ Message: "Unsupported node type",
+ }
+ return nil, err
+ }
+ return cl, nil
+}
+
+func (planner *planner) parseWhere(
+ whereNode *ast.WhereOptionNode,
+) (*clause, error) {
+ if whereNode == nil {
+ return nil, nil
+ }
+ return planner.parseClause(whereNode.Condition)
+}
+
+func (planner *planner) planWhereclause(
+ clause *clause,
+ depth int,
+) (PlanStep, error) {
+ // TOOD(yenlin): recursion depth limit.
+ var curPlan PlanStep
+ checkPlan := func(newPlan PlanStep) {
+ if curPlan == nil {
+ curPlan = newPlan
+ }
+ if newPlan != nil && curPlan.GetCost() > newPlan.GetCost() {
+ // Found a better plan, replace the old one.
+ curPlan = newPlan
+ }
+ }
+
+ // Basic brute force plan.
+ p := planner.newScanTable(planner.tableRef, clause)
+ checkPlan(p)
+
+ if clause == nil {
+ // No where specified, return ScanTable directly.
+ return curPlan, nil
+ }
+
+ // If not forced scan.
+ if clause.Attr&clauseAttrForceScan == 0 {
+ // Plan on the whole clause.
+ for i, index := range planner.table.Indices {
+ var plan PlanStep
+
+ var columnSet ColumnSet
+ columnSet = make([]*schema.ColumnDescriptor, len(index.Columns))
+ for i := range columnSet {
+ columnSet[i] = &schema.ColumnDescriptor{
+ Table: planner.tableRef,
+ Column: index.Columns[i],
+ }
+ }
+ if clause.Attr&clauseAttrEnumerable != 0 &&
+ columnSet.Equal(clause.ColumnSet) {
+ // Values are known for hash.
+ plan = planner.newScanIndices(planner.tableRef, schema.IndexRef(i),
+ clause.HashKeys)
+ } else if columnSet.Contains(clause.ColumnSet) {
+ plan = planner.newScanIndexValues(planner.tableRef,
+ schema.IndexRef(i), clause)
+ }
+ checkPlan(plan)
+ }
+ }
+
+ if depth >= maxPlanDepth {
+ // Maximum plan depth reached, just current best plan.
+ return curPlan, nil
+ }
+ // Plan on sub-clauses.
+ switch {
+ case clause.Attr&clauseAttrAnd != 0:
+ // It's an AND condition. Try to find a better plan by index on one
+ // sub-clause and filter the other sub-clause.
+ for i, subCl := range clause.SubCls {
+ plan, err := planner.planWhereclause(subCl, depth+1)
+ if err != nil {
+ return nil, err
+ }
+ if plan == nil {
+ continue
+ }
+ for j, filterCl := range clause.SubCls {
+ if j != i {
+ plan = planner.newFilterStep(
+ filterCl, planner.tableRef, plan)
+ }
+ }
+ checkPlan(plan)
+ }
+ case clause.Attr&clauseAttrOr != 0:
+ // It's an OR condition. Try union from sub-clauses.
+ subPlans := make([]PlanStep, len(clause.SubCls))
+ for i, subCl := range clause.SubCls {
+ subPlan, err := planner.planWhereclause(subCl, depth+1)
+ if err != nil {
+ return nil, err
+ }
+ subPlans[i] = subPlan
+ }
+ plan := planner.newUnionStep(subPlans)
+ checkPlan(plan)
+ }
+ // Cleanup SubCls as they are no longer needed.
+ return curPlan, nil
+}
+
+func (planner *planner) planWhere(
+ whereNode *ast.WhereOptionNode,
+) (PlanStep, error) {
+ whereclause, err := planner.parseWhere(whereNode)
+ if err != nil {
+ return nil, err
+ }
+ return planner.planWhereclause(whereclause, 0)
+}
+
+func (planner *planner) planSelectWithoutTable(stmt *ast.SelectStmtNode) (
+ PlanStep, error) {
+
+ plan := &SelectWithoutTable{
+ Columns: stmt.Column,
+ }
+ if stmt.Where != nil {
+ plan.Condition = stmt.Where.Condition
+ }
+ if stmt.Offset != nil {
+ plan.Offset = &decimal.Decimal{}
+ *plan.Offset = stmt.Offset.Value.Value().(decimal.Decimal)
+ }
+ if stmt.Limit != nil {
+ plan.Limit = &decimal.Decimal{}
+ *plan.Limit = stmt.Limit.Value.Value().(decimal.Decimal)
+ }
+ return plan, nil
+}
+
+func (planner *planner) planSelect(stmt *ast.SelectStmtNode) (PlanStep, error) {
+ if stmt.Table == nil {
+ return planner.planSelectWithoutTable(stmt)
+ }
+ planner.tableRef = idNodeToTable(stmt.Table)
+ planner.table = &planner.schema[planner.tableRef]
+
+ wherePlan, err := planner.planWhere(stmt.Where)
+ if err != nil {
+ return nil, err
+ }
+ plan := &SelectStep{}
+ plan.Table = planner.tableRef
+ if stmt.Offset != nil {
+ plan.Offset = &decimal.Decimal{}
+ *plan.Offset = stmt.Offset.Value.Value().(decimal.Decimal)
+ }
+ if stmt.Limit != nil {
+ plan.Limit = &decimal.Decimal{}
+ *plan.Limit = stmt.Limit.Value.Value().(decimal.Decimal)
+ }
+ // TODO(yenlin): we may expect there's a columnset struct in every node.
+ // use clause for current development.
+ plan.Columns = stmt.Column
+ for _, col := range plan.Columns {
+ cl, err := planner.parseClause(col)
+ if err != nil {
+ return nil, err
+ }
+ plan.ColumnSet = plan.ColumnSet.Join(cl.ColumnSet)
+ }
+ plan.Order = stmt.Order
+ for i := range plan.Order {
+ cl, err := planner.parseClause(plan.Order[i].Expr)
+ if err != nil {
+ return nil, err
+ }
+ plan.ColumnSet = plan.ColumnSet.Join(cl.ColumnSet)
+ }
+ plan.Operands = []PlanStep{wherePlan}
+ return plan, nil
+}
+
+func (planner *planner) planUpdate(stmt *ast.UpdateStmtNode) (PlanStep, error) {
+ planner.tableRef = idNodeToTable(stmt.Table)
+ planner.table = &planner.schema[planner.tableRef]
+
+ wherePlan, err := planner.planWhere(stmt.Where)
+ if err != nil {
+ return nil, err
+ }
+ plan := &UpdateStep{}
+ plan.Table = planner.tableRef
+ // Parse assignment.
+ plan.Columns = make([]schema.ColumnRef, len(stmt.Assignment))
+ plan.Values = make([]ast.ExprNode, len(stmt.Assignment))
+ for i, as := range stmt.Assignment {
+ cl, err := planner.parseClause(as.Expr)
+ if err != nil {
+ return nil, err
+ }
+ _, plan.Columns[i] = idNodeToColumn(as.Column)
+ plan.Values[i] = as.Expr
+ plan.ColumnSet = plan.ColumnSet.Join(cl.ColumnSet)
+ }
+ plan.Operands = []PlanStep{wherePlan}
+ return plan, nil
+}
+
+func (planner *planner) planDelete(stmt *ast.DeleteStmtNode) (PlanStep, error) {
+ planner.tableRef = idNodeToTable(stmt.Table)
+ planner.table = &planner.schema[planner.tableRef]
+
+ wherePlan, err := planner.planWhere(stmt.Where)
+ if err != nil {
+ return nil, err
+ }
+ plan := &DeleteStep{}
+ plan.Table = planner.tableRef
+ plan.Operands = []PlanStep{wherePlan}
+ return plan, nil
+}
+
+// Plan the steps to achieve the sql statement in stmt.
+func Plan(
+ context *common.Context,
+ schema schema.Schema,
+ stmt ast.Node,
+) (PlanStep, error) {
+ planner := planner{
+ context: context,
+ schema: schema,
+ }
+
+ var plan PlanStep
+ var err error
+ // Handle the action.
+ switch st := stmt.(type) {
+ case *ast.InsertStmtNode:
+ plan, err = planner.planInsert(st)
+ case *ast.SelectStmtNode:
+ plan, err = planner.planSelect(st)
+ case *ast.UpdateStmtNode:
+ plan, err = planner.planUpdate(st)
+ case *ast.DeleteStmtNode:
+ plan, err = planner.planDelete(st)
+ default:
+ err = errors.Error{
+ Position: stmt.GetPosition(),
+ Category: errors.ErrorCategoryPlanner,
+ Code: errors.ErrorCodePlanner,
+ Message: "Unsupported statement type",
+ }
+ }
+
+ return plan, err
+}
diff --git a/core/vm/sqlvm/planner/planner_test.go b/core/vm/sqlvm/planner/planner_test.go
new file mode 100644
index 000000000..a13659a1d
--- /dev/null
+++ b/core/vm/sqlvm/planner/planner_test.go
@@ -0,0 +1,878 @@
+package planner
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/dexon-foundation/decimal"
+ "github.com/stretchr/testify/suite"
+
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/ast"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+)
+
+type PlannerTestSuite struct{ suite.Suite }
+
+// utility functions.
+// cleanPlanCost clean up cost and out num recursively.
+func cleanPlanCost(plan PlanStep) {
+ plan.SetCost(0)
+ plan.SetOutNum(0)
+ for _, p := range plan.GetOperands() {
+ cleanPlanCost(p)
+ }
+}
+
+func (s *PlannerTestSuite) assertPlanEqual(
+ expected, actual PlanStep,
+ compareCost bool,
+) {
+ if !compareCost {
+ cleanPlanCost(expected)
+ cleanPlanCost(actual)
+ }
+ s.Require().Equal(expected, actual)
+}
+
+// createTable with given name, column names, column ids in every indices.
+func (s *PlannerTestSuite) createTable(
+ name []byte,
+ columns [][]byte,
+ indices [][]schema.ColumnRef,
+) schema.Table {
+ table := schema.Table{
+ Name: name,
+ }
+ table.Columns = make([]schema.Column, len(columns))
+ for i, cname := range columns {
+ col := schema.Column{}
+ col.Name = cname
+ table.Columns[i] = col
+ }
+ table.Indices = make([]schema.Index, len(indices))
+ for i, cols := range indices {
+ table.Indices[i] = schema.Index{
+ Name: []byte(fmt.Sprintf("index%d", i)),
+ Columns: cols,
+ }
+ }
+ return table
+}
+
+func (s *PlannerTestSuite) TestBasic() {
+ var tables schema.Schema = []schema.Table{
+ s.createTable(
+ []byte("table1"),
+ [][]byte{
+ []byte("a"),
+ []byte("b"),
+ []byte("c"),
+ },
+ [][]schema.ColumnRef{
+ []schema.ColumnRef{0},
+ []schema.ColumnRef{1},
+ []schema.ColumnRef{0, 1, 2},
+ },
+ ),
+ }
+ {
+ stmt := &ast.InsertStmtNode{
+ Table: &ast.IdentifierNode{
+ Name: []byte("table1"),
+ Desc: &schema.TableDescriptor{Table: 0},
+ },
+ Insert: &ast.InsertWithColumnOptionNode{
+ Column: []*ast.IdentifierNode{
+ &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ },
+ Value: [][]ast.ExprNode{
+ []ast.ExprNode{
+ &ast.BytesValueNode{V: []byte("valA")},
+ &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ }
+ expectedPlan := &InsertStep{
+ Table: 0,
+ Columns: []schema.ColumnRef{0, 1},
+ Values: [][]ast.ExprNode{
+ []ast.ExprNode{
+ &ast.BytesValueNode{V: []byte("valA")},
+ &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ }
+ plan, err := Plan(nil, tables, stmt)
+ s.Require().Nil(err)
+ s.Require().NotNil(plan)
+ s.assertPlanEqual(expectedPlan, plan, false)
+ }
+ {
+ expr := &ast.AddOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ },
+ }
+ stmt := &ast.UpdateStmtNode{
+ Table: &ast.IdentifierNode{
+ Name: []byte("table1"),
+ Desc: &schema.TableDescriptor{Table: 0},
+ },
+ Assignment: []*ast.AssignOperatorNode{
+ &ast.AssignOperatorNode{
+ Column: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Expr: expr,
+ },
+ },
+ }
+ expectedPlan := &UpdateStep{
+ Table: 0,
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Columns: []schema.ColumnRef{0},
+ Values: []ast.ExprNode{expr},
+ // Children.
+ PlanStepBase: PlanStepBase{
+ Operands: []PlanStep{
+ &ScanTable{
+ Table: 0,
+ Condition: nil,
+ },
+ },
+ },
+ }
+ plan, err := Plan(nil, tables, stmt)
+ s.Require().Nil(err)
+ s.Require().NotNil(plan)
+ s.assertPlanEqual(expectedPlan, plan, false)
+ }
+ {
+ // Test a index scan select.
+ // TODO(yenlin): test more on planning.
+ limit := decimal.New(10, 0)
+ offset := decimal.New(20, 0)
+ stmt := &ast.SelectStmtNode{
+ Column: []ast.ExprNode{
+ &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ },
+ Table: &ast.IdentifierNode{
+ Name: []byte("table1"),
+ Desc: &schema.TableDescriptor{Table: 0},
+ },
+ Where: &ast.WhereOptionNode{
+ Condition: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ Order: []*ast.OrderOptionNode{
+ &ast.OrderOptionNode{
+ Expr: &ast.IdentifierNode{
+ Name: []byte("c"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ },
+ },
+ Limit: &ast.LimitOptionNode{
+ Value: &ast.IntegerValueNode{
+ V: limit,
+ },
+ },
+ Offset: &ast.OffsetOptionNode{
+ Value: &ast.IntegerValueNode{
+ V: offset,
+ },
+ },
+ }
+ expectedPlan := &SelectStep{
+ Table: 0,
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Columns: []ast.ExprNode{
+ &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ },
+ Order: []*ast.OrderOptionNode{
+ &ast.OrderOptionNode{
+ Expr: &ast.IdentifierNode{
+ Name: []byte("c"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ },
+ },
+ Limit: &limit,
+ Offset: &offset,
+
+ // Children.
+ PlanStepBase: PlanStepBase{
+ Operands: []PlanStep{
+ &ScanIndices{
+ Table: 0,
+ Index: 1,
+ Values: [][]ast.Valuer{
+ []ast.Valuer{
+ &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ },
+ },
+ }
+ plan, err := Plan(nil, tables, stmt)
+ s.Require().Nil(err)
+ s.Require().NotNil(plan)
+ s.assertPlanEqual(expectedPlan, plan, false)
+ }
+ {
+ // Test select without table.
+ limit := decimal.New(10, 0)
+ offset := decimal.New(20, 0)
+ stmt := &ast.SelectStmtNode{
+ Column: []ast.ExprNode{
+ &ast.FunctionOperatorNode{
+ Name: &ast.IdentifierNode{
+ Name: []byte("rand"),
+ },
+ },
+ &ast.BytesValueNode{V: []byte("valB")},
+ },
+ Where: &ast.WhereOptionNode{
+ Condition: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.FunctionOperatorNode{
+ Name: &ast.IdentifierNode{
+ Name: []byte("rand"),
+ },
+ },
+ Subject: &ast.DecimalValueNode{V: decimal.New(1, 0)},
+ },
+ },
+ },
+ Limit: &ast.LimitOptionNode{
+ Value: &ast.IntegerValueNode{
+ V: limit,
+ },
+ },
+ Offset: &ast.OffsetOptionNode{
+ Value: &ast.IntegerValueNode{
+ V: offset,
+ },
+ },
+ }
+ expectedPlan := &SelectWithoutTable{
+ Columns: []ast.ExprNode{
+ &ast.FunctionOperatorNode{
+ Name: &ast.IdentifierNode{
+ Name: []byte("rand"),
+ },
+ },
+ &ast.BytesValueNode{V: []byte("valB")},
+ },
+ Condition: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.FunctionOperatorNode{
+ Name: &ast.IdentifierNode{
+ Name: []byte("rand"),
+ },
+ },
+ Subject: &ast.DecimalValueNode{V: decimal.New(1, 0)},
+ },
+ },
+ Limit: &limit,
+ Offset: &offset,
+ }
+ plan, err := Plan(nil, tables, stmt)
+ s.Require().Nil(err)
+ s.Require().NotNil(plan)
+ s.assertPlanEqual(expectedPlan, plan, false)
+ }
+ {
+ stmt := &ast.DeleteStmtNode{
+ Table: &ast.IdentifierNode{
+ Name: []byte("table1"),
+ Desc: &schema.TableDescriptor{Table: 0},
+ },
+ Where: &ast.WhereOptionNode{
+ Condition: &ast.GreaterOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ }
+ expectedPlan := &DeleteStep{
+ Table: 0,
+ // Children.
+ PlanStepBase: PlanStepBase{
+ Operands: []PlanStep{
+ &ScanIndexValues{
+ Table: 0,
+ Index: 1,
+ Condition: &ast.GreaterOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ },
+ },
+ }
+ plan, err := Plan(nil, tables, stmt)
+ s.Require().Nil(err)
+ s.Require().NotNil(plan)
+ s.assertPlanEqual(expectedPlan, plan, false)
+ }
+}
+
+func (s *PlannerTestSuite) TestHashKeys() {
+ var tableSchema schema.Schema = []schema.Table{
+ s.createTable(
+ []byte("table1"),
+ [][]byte{
+ []byte("a"),
+ []byte("b"),
+ []byte("c"),
+ },
+ [][]schema.ColumnRef{
+ []schema.ColumnRef{0},
+ []schema.ColumnRef{1},
+ []schema.ColumnRef{0, 1, 2},
+ },
+ ),
+ }
+ planner := planner{
+ schema: tableSchema,
+ }
+ // Pre-define possible values in every columns.
+ consts := [][]ast.Valuer{
+ []ast.Valuer{
+ &ast.BytesValueNode{V: []byte("val1")},
+ &ast.BytesValueNode{V: []byte("val2")},
+ &ast.BytesValueNode{V: []byte("val3")},
+ },
+ []ast.Valuer{
+ &ast.BytesValueNode{V: []byte("val4")},
+ &ast.BytesValueNode{V: []byte("val5")},
+ &ast.BytesValueNode{V: []byte("val6")},
+ },
+ []ast.Valuer{
+ &ast.BytesValueNode{V: []byte("val7")},
+ &ast.BytesValueNode{V: []byte("val8")},
+ &ast.BytesValueNode{V: []byte("val9")},
+ },
+ }
+ genCombination := func(columns []schema.ColumnRef, values []int) []ast.Valuer {
+ s.Require().Equal(len(columns), len(values))
+ s.Require().True(len(columns) <= len(consts))
+
+ ret := make([]ast.Valuer, len(columns))
+ for i := range ret {
+ colIdx := columns[i]
+ valIdx := values[i]
+ s.Require().True(int(colIdx) < len(consts))
+ s.Require().True(valIdx < len(consts[colIdx]))
+ ret[i] = consts[colIdx][valIdx]
+ }
+
+ return ret
+ }
+
+ {
+ // Test AND merge.
+ cl := &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrAnd | clauseAttrEnumerable,
+ SubCls: []*clause{
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 2}, []int{0, 0}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 1}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 2}),
+ },
+ },
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{1}, []int{0}),
+ genCombination([]schema.ColumnRef{1}, []int{1}),
+ },
+ },
+ },
+ }
+ planner.mergeAndHashKeys(cl)
+ expectedKeys := [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{0, 0, 0}),
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{1, 0, 1}),
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{1, 0, 2}),
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{0, 1, 0}),
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{1, 1, 1}),
+ genCombination([]schema.ColumnRef{0, 1, 2}, []int{1, 1, 2}),
+ }
+ s.Require().Equal(expectedKeys, cl.HashKeys)
+ }
+ {
+ // Test AND merge boundary with one size empty.
+ cl := &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrAnd | clauseAttrEnumerable,
+ SubCls: []*clause{
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{},
+ },
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{1}, []int{0}),
+ genCombination([]schema.ColumnRef{1}, []int{1}),
+ },
+ },
+ },
+ }
+ planner.mergeAndHashKeys(cl)
+ expectedKeys := [][]ast.Valuer{}
+ s.Require().Equal(expectedKeys, cl.HashKeys)
+ cl = &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrAnd | clauseAttrEnumerable,
+ SubCls: []*clause{
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 2}, []int{0, 0}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 1}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 2}),
+ },
+ },
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{},
+ },
+ },
+ }
+ planner.mergeAndHashKeys(cl)
+ expectedKeys = [][]ast.Valuer{}
+ s.Require().Equal(expectedKeys, cl.HashKeys)
+ }
+ {
+ // Test OR merge.
+ cl := &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrOr | clauseAttrEnumerable,
+ SubCls: []*clause{
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 2}, []int{0, 0}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 1}),
+ },
+ },
+ &clause{
+ ColumnSet: ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 2},
+ },
+ Attr: clauseAttrEnumerable,
+ HashKeys: [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 2}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{2, 1}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{2, 2}),
+ },
+ },
+ },
+ }
+ planner.mergeOrHashKeys(cl)
+ expectedKeys := [][]ast.Valuer{
+ genCombination([]schema.ColumnRef{0, 2}, []int{0, 0}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 1}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{1, 2}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{2, 1}),
+ genCombination([]schema.ColumnRef{0, 2}, []int{2, 2}),
+ }
+ s.Require().Equal(expectedKeys, cl.HashKeys)
+ }
+}
+
+func (s *PlannerTestSuite) TestClauseAttr() {
+ var dbSchema schema.Schema = []schema.Table{
+ s.createTable(
+ []byte("table1"),
+ [][]byte{
+ []byte("a"),
+ []byte("b"),
+ []byte("c"),
+ },
+ [][]schema.ColumnRef{
+ []schema.ColumnRef{0},
+ []schema.ColumnRef{1},
+ []schema.ColumnRef{0, 1, 2},
+ },
+ ),
+ }
+ planner := planner{
+ schema: dbSchema,
+ table: &dbSchema[0],
+ tableRef: 0,
+ }
+
+ {
+ node := &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrColumn, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+ {
+ node := &ast.BytesValueNode{V: []byte("valA")}
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrConst, cl.Attr)
+ s.Require().Zero(cl.ColumnSet)
+ s.Require().Equal([][]ast.Valuer{[]ast.Valuer{node}}, cl.HashKeys)
+ }
+ {
+ valA := &ast.BytesValueNode{V: []byte("valA")}
+ node := &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: valA,
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrEnumerable, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }, cl.ColumnSet)
+ s.Require().Equal([][]ast.Valuer{[]ast.Valuer{valA}}, cl.HashKeys)
+ }
+ {
+ node := &ast.GreaterOrEqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valA")},
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Zero(cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+ {
+ valA := &ast.BytesValueNode{V: []byte("valA")}
+ valB := &ast.BytesValueNode{V: []byte("valB")}
+ node := &ast.AndOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: valB,
+ },
+ },
+ Subject: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: valA,
+ },
+ },
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrEnumerable|clauseAttrAnd, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ }, cl.ColumnSet)
+ s.Require().Equal([][]ast.Valuer{
+ []ast.Valuer{valA, valB},
+ }, cl.HashKeys)
+ }
+ {
+ node := &ast.OrOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valA")},
+ },
+ },
+ Subject: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: &ast.BytesValueNode{V: []byte("valB")},
+ },
+ },
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrOr, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+ {
+ valA := &ast.BytesValueNode{V: []byte("valA")}
+ valB := &ast.BytesValueNode{V: []byte("valB")}
+ node := &ast.OrOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: valA,
+ },
+ },
+ Subject: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: valB,
+ },
+ },
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrOr|clauseAttrEnumerable, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ }, cl.ColumnSet)
+ s.Require().Equal([][]ast.Valuer{
+ []ast.Valuer{valA},
+ []ast.Valuer{valB},
+ }, cl.HashKeys)
+ }
+ {
+ valA := &ast.BytesValueNode{V: []byte("valA")}
+ valB := &ast.BytesValueNode{V: []byte("valB")}
+ node := &ast.InOperatorNode{
+ Left: &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: valA,
+ },
+ },
+ Right: []ast.ExprNode{
+ &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ Subject: valB,
+ },
+ },
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Zero(cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+ {
+ valA := &ast.BytesValueNode{V: []byte("valA")}
+ valB := &ast.BytesValueNode{V: []byte("valB")}
+ node := &ast.InOperatorNode{
+ Left: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Right: []ast.ExprNode{
+ valA, valB,
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrEnumerable, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }, cl.ColumnSet)
+ s.Require().Equal([][]ast.Valuer{
+ []ast.Valuer{valA},
+ []ast.Valuer{valB},
+ }, cl.HashKeys)
+ }
+ {
+ node := &ast.CastOperatorNode{
+ SourceExpr: &ast.AddOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: &ast.IdentifierNode{
+ Name: []byte("b"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 1},
+ },
+ },
+ },
+ TargetType: &ast.IntTypeNode{
+ Unsigned: true,
+ Size: 32,
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Zero(cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ &schema.ColumnDescriptor{Table: 0, Column: 1},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+ {
+ node := &ast.EqualOperatorNode{
+ BinaryOperatorNode: ast.BinaryOperatorNode{
+ Object: &ast.IdentifierNode{
+ Name: []byte("a"),
+ Desc: &schema.ColumnDescriptor{Table: 0, Column: 0},
+ },
+ Subject: &ast.FunctionOperatorNode{
+ Name: &ast.IdentifierNode{Name: []byte("RAND")},
+ },
+ },
+ }
+ cl, err := planner.parseClause(node)
+ s.Require().Nil(err)
+ s.Require().Equal(clauseAttrForceScan, cl.Attr)
+ s.Require().Equal(ColumnSet{
+ &schema.ColumnDescriptor{Table: 0, Column: 0},
+ }, cl.ColumnSet)
+ s.Require().Zero(cl.HashKeys)
+ }
+}
+
+func TestPlanner(t *testing.T) {
+ suite.Run(t, new(PlannerTestSuite))
+}
diff --git a/core/vm/sqlvm/planner/types.go b/core/vm/sqlvm/planner/types.go
new file mode 100644
index 000000000..d93c3e850
--- /dev/null
+++ b/core/vm/sqlvm/planner/types.go
@@ -0,0 +1,166 @@
+package planner
+
+import (
+ "github.com/dexon-foundation/decimal"
+
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/ast"
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+)
+
+// clause types.
+
+// clauseAttr is the attribute bitmap for every clause.
+type clauseAttr uint64
+
+// clauseAttr enums.
+const (
+ clauseAttrConst clauseAttr = 1 << iota
+ clauseAttrColumn
+ clauseAttrEnumerable
+ clauseAttrForceScan
+ clauseAttrAnd
+ clauseAttrOr
+)
+
+// clause contains metadata used by planner about operation nodes.
+type clause struct {
+ ColumnSet ColumnSet
+ Attr clauseAttr
+ HashKeys [][]ast.Valuer
+ OriginAst ast.ExprNode
+ SubCls []*clause `print:"-"`
+}
+
+// Plan types.
+
+// PlanStep is the interface for all plan or sub-plans.
+type PlanStep interface {
+ GetCost() uint64
+ SetCost(uint64)
+ GetOutNum() uint64
+ SetOutNum(uint64)
+ GetOperands() []PlanStep
+}
+
+// PlanStepBase implements PlanStep interface.
+type PlanStepBase struct {
+ Cost uint64
+ OutNum uint64
+ Operands []PlanStep
+}
+
+// GetCost gets the cost of the plan.
+func (b PlanStepBase) GetCost() uint64 {
+ return b.Cost
+}
+
+// SetCost sets the cost of the plan.
+func (b *PlanStepBase) SetCost(c uint64) {
+ b.Cost = c
+}
+
+// GetOutNum gets the estimated output row count of the plan.
+func (b PlanStepBase) GetOutNum() uint64 {
+ return b.OutNum
+}
+
+// SetOutNum sets the estimated output row count of the plan.
+func (b *PlanStepBase) SetOutNum(n uint64) {
+ b.OutNum = n
+}
+
+// GetOperands gets the sub-plans to generate the operands of this plan.
+func (b PlanStepBase) GetOperands() []PlanStep {
+ return b.Operands
+}
+
+var _ PlanStep = (*PlanStepBase)(nil)
+
+// Plan step types.
+
+// ScanTable means to scan whole table.
+type ScanTable struct {
+ PlanStepBase
+ Table schema.TableRef
+ ColumnSet ColumnSet
+ Condition ast.ExprNode
+}
+
+// ScanIndices means to scan known hash keys on a index.
+type ScanIndices struct {
+ PlanStepBase
+ Table schema.TableRef
+ Index schema.IndexRef
+ Values [][]ast.Valuer
+}
+
+// ScanIndexValues means to scan all possible values on a index.
+type ScanIndexValues struct {
+ PlanStepBase
+ Table schema.TableRef
+ Index schema.IndexRef
+ Condition ast.ExprNode
+}
+
+// FilterStep means to further filter the rows in Operands[0].
+type FilterStep struct {
+ PlanStepBase
+ Table schema.TableRef
+ ColumnSet ColumnSet
+ Condition ast.ExprNode
+}
+
+// UnionStep means to take union the results from Operands.
+type UnionStep struct {
+ PlanStepBase
+}
+
+// IntersectStep means to take intersect of the result from Operands.
+type IntersectStep struct {
+ PlanStepBase
+}
+
+// InsertStep inserts rows (with Columns = Values) into Table.
+type InsertStep struct {
+ PlanStepBase
+ Table schema.TableRef
+ Columns []schema.ColumnRef
+ Values [][]ast.ExprNode
+}
+
+// SelectStep select Columns from the rows in the result of Operands[0].
+type SelectStep struct {
+ PlanStepBase
+ Table schema.TableRef
+ ColumnSet ColumnSet
+ Columns []ast.ExprNode
+ Order []*ast.OrderOptionNode
+ Offset *decimal.Decimal
+ Limit *decimal.Decimal
+}
+
+// SelectWithoutTable is a special case of select when table is nil.
+// In this case, we should output 1 or 0 row data depending on whether the
+// condition is true.
+type SelectWithoutTable struct {
+ PlanStepBase
+ Columns []ast.ExprNode
+ Condition ast.ExprNode
+ Offset *decimal.Decimal
+ Limit *decimal.Decimal
+}
+
+// UpdateStep does the assignment to the rows in the result of Operands[0].
+type UpdateStep struct {
+ PlanStepBase
+ Table schema.TableRef
+ ColumnSet ColumnSet
+ Columns []schema.ColumnRef
+ Values []ast.ExprNode
+}
+
+// DeleteStep deletes the rows in the result of Operands[0] from the table.
+type DeleteStep struct {
+ PlanStepBase
+ Table schema.TableRef
+}
diff --git a/core/vm/sqlvm/planner/utils.go b/core/vm/sqlvm/planner/utils.go
new file mode 100644
index 000000000..912f32346
--- /dev/null
+++ b/core/vm/sqlvm/planner/utils.go
@@ -0,0 +1,149 @@
+package planner
+
+import "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+
+func bytesEq(a []byte, b []byte) bool {
+ if len(a) != len(b) {
+ return false
+ }
+ for i := range a {
+ if a[i] != b[i] {
+ return false
+ }
+ }
+ return true
+}
+
+func findTableIdxByName(tables schema.Schema, name []byte) (
+ schema.TableRef, bool) {
+
+ for i, table := range tables {
+ if bytesEq(name, table.Name) {
+ return schema.TableRef(i), true
+ }
+ }
+ return 0, false
+}
+
+func findColumnIdxByName(table *schema.Table, name []byte) (
+ schema.ColumnRef, bool) {
+
+ for i, c := range table.Columns {
+ if bytesEq(name, c.Name) {
+ return schema.ColumnRef(i), true
+ }
+ }
+ return 0, false
+}
+
+// ColumnSet is a sorted slice of column idxs.
+type ColumnSet []*schema.ColumnDescriptor
+
+func compareTableRef(a, b schema.TableRef) int {
+ switch {
+ case a > b:
+ return 1
+ case a == b:
+ return 0
+ default:
+ return -1
+ }
+}
+
+func compareColumnRef(a, b schema.ColumnRef) int {
+ switch {
+ case a > b:
+ return 1
+ case a == b:
+ return 0
+ default:
+ return -1
+ }
+}
+
+func compareColumn(a, b *schema.ColumnDescriptor) int {
+ comp := compareTableRef(a.Table, b.Table)
+ switch comp {
+ case 0:
+ return compareColumnRef(a.Column, b.Column)
+ default:
+ return comp
+ }
+}
+
+// Join creates a new set which is the union of c and other.
+func (c ColumnSet) Join(other ColumnSet) ColumnSet {
+ ret := make([]*schema.ColumnDescriptor, 0, len(c)+len(other))
+ i, j := 0, 0
+ for i != len(c) && j != len(other) {
+ comp := compareColumn(c[i], other[j])
+ switch comp {
+ case 0:
+ ret = append(ret, c[i])
+ i++
+ j++
+ case 1:
+ ret = append(ret, other[j])
+ j++
+ case -1:
+ ret = append(ret, c[i])
+ i++
+ }
+ }
+ for i != len(c) {
+ ret = append(ret, c[i])
+ i++
+ }
+ for j != len(other) {
+ ret = append(ret, other[j])
+ j++
+ }
+ return ret
+}
+
+// Equal compares the two sets.
+func (c ColumnSet) Equal(other ColumnSet) bool {
+ if len(c) != len(other) {
+ return false
+ }
+ for i := range c {
+ if compareColumn(c[i], other[i]) != 0 {
+ return false
+ }
+ }
+ return true
+}
+
+// IsDisjoint checks if the two sets are disjoint.
+func (c ColumnSet) IsDisjoint(other ColumnSet) bool {
+ i, j := 0, 0
+ for i != len(c) && j != len(other) {
+ comp := compareColumn(c[i], other[j])
+ switch comp {
+ case 0:
+ return false
+ case 1:
+ j++
+ case -1:
+ i++
+ }
+ }
+ return true
+}
+
+// Contains checks if other is a subset of c.
+func (c ColumnSet) Contains(other ColumnSet) bool {
+ i, j := 0, 0
+ for i != len(c) && j != len(other) {
+ comp := compareColumn(c[i], other[j])
+ switch comp {
+ case 1:
+ // Found some item not in c.
+ return false
+ case 0:
+ j++
+ }
+ i++
+ }
+ return j == len(other)
+}
diff --git a/core/vm/sqlvm/planner/utils_test.go b/core/vm/sqlvm/planner/utils_test.go
new file mode 100644
index 000000000..6053a3180
--- /dev/null
+++ b/core/vm/sqlvm/planner/utils_test.go
@@ -0,0 +1,128 @@
+package planner
+
+import (
+ "testing"
+
+ "github.com/stretchr/testify/suite"
+
+ "github.com/dexon-foundation/dexon/core/vm/sqlvm/schema"
+)
+
+type PlannerUtilsTestSuite struct{ suite.Suite }
+
+func makeColumnSet(cols []uint8) ColumnSet {
+ var ret ColumnSet = make([]*schema.ColumnDescriptor, len(cols))
+ for i := range ret {
+ ret[i] = &schema.ColumnDescriptor{
+ Table: 0,
+ Column: schema.ColumnRef(cols[i]),
+ }
+ }
+ return ret
+}
+
+func (s *PlannerUtilsTestSuite) TestColumnSet() {
+ {
+ // Join.
+ var columns, expected ColumnSet
+ columns = makeColumnSet([]uint8{1, 3, 5}).Join(
+ makeColumnSet([]uint8{0, 1, 2, 4, 6}))
+ expected = makeColumnSet([]uint8{0, 1, 2, 3, 4, 5, 6})
+ s.Require().Equal(expected, columns)
+ columns = makeColumnSet([]uint8{1, 3, 5}).Join(
+ makeColumnSet([]uint8{3, 5}))
+ expected = makeColumnSet([]uint8{1, 3, 5})
+ s.Require().Equal(expected, columns)
+ columns = ColumnSet{}.Join(makeColumnSet([]uint8{0}))
+ expected = makeColumnSet([]uint8{0})
+ s.Require().Equal(expected, columns)
+ columns = makeColumnSet([]uint8{1}).Join(
+ makeColumnSet([]uint8{1, 3}))
+ expected = makeColumnSet([]uint8{1, 3})
+ s.Require().Equal(expected, columns)
+ columns = makeColumnSet([]uint8{5}).Join(makeColumnSet([]uint8{1, 3}))
+ expected = makeColumnSet([]uint8{1, 3, 5})
+ s.Require().Equal(expected, columns)
+ }
+ {
+ // Equal.
+ var equal bool
+ // True cases.
+ equal = ColumnSet{}.Equal(ColumnSet{})
+ s.Require().True(equal)
+ equal = makeColumnSet([]uint8{1, 2}).Equal(makeColumnSet([]uint8{1, 2}))
+ s.Require().True(equal)
+ // False cases.
+ equal = ColumnSet{}.Equal(makeColumnSet([]uint8{1, 2}))
+ s.Require().False(equal)
+ equal = makeColumnSet([]uint8{1, 2}).Equal(ColumnSet{})
+ s.Require().False(equal)
+ equal = makeColumnSet([]uint8{2}).Equal(makeColumnSet([]uint8{1}))
+ s.Require().False(equal)
+ equal = makeColumnSet([]uint8{2}).Equal(makeColumnSet([]uint8{1, 3}))
+ s.Require().False(equal)
+ equal = makeColumnSet([]uint8{1, 3}).Equal(makeColumnSet([]uint8{2}))
+ s.Require().False(equal)
+ }
+ {
+ // Contains.
+ var contains bool
+ // True cases.
+ contains = ColumnSet{}.Contains(ColumnSet{})
+ s.Require().True(contains)
+ contains = makeColumnSet([]uint8{1, 2}).Contains(ColumnSet{})
+ s.Require().True(contains)
+ contains = makeColumnSet([]uint8{1, 2}).Contains(
+ makeColumnSet([]uint8{2}))
+ s.Require().True(contains)
+ contains = makeColumnSet([]uint8{1, 2}).Contains(
+ makeColumnSet([]uint8{1}))
+ s.Require().True(contains)
+ contains = makeColumnSet([]uint8{1, 2, 3}).Contains(
+ makeColumnSet([]uint8{1, 2}))
+ s.Require().True(contains)
+ // False cases.
+ contains = makeColumnSet([]uint8{1}).Contains(makeColumnSet([]uint8{2}))
+ s.Require().False(contains)
+ contains = makeColumnSet([]uint8{2}).Contains(
+ makeColumnSet([]uint8{1, 2}))
+ s.Require().False(contains)
+ contains = makeColumnSet([]uint8{1}).Contains(
+ makeColumnSet([]uint8{1, 2}))
+ s.Require().False(contains)
+ contains = makeColumnSet([]uint8{1, 3, 5}).Contains(
+ makeColumnSet([]uint8{4}))
+ s.Require().False(contains)
+ }
+ {
+ // IsDisjoint.
+ var disjoin bool
+ // True cases.
+ disjoin = ColumnSet{}.IsDisjoint(ColumnSet{})
+ s.Require().True(disjoin)
+ disjoin = ColumnSet{}.IsDisjoint(makeColumnSet([]uint8{1}))
+ s.Require().True(disjoin)
+ disjoin = makeColumnSet([]uint8{1}).IsDisjoint(ColumnSet{})
+ s.Require().True(disjoin)
+ disjoin = makeColumnSet([]uint8{1}).IsDisjoint(
+ makeColumnSet([]uint8{2}))
+ s.Require().True(disjoin)
+ // False cases.
+ disjoin = makeColumnSet([]uint8{1, 2}).IsDisjoint(
+ makeColumnSet([]uint8{2}))
+ s.Require().False(disjoin)
+ disjoin = makeColumnSet([]uint8{1, 2}).IsDisjoint(
+ makeColumnSet([]uint8{1}))
+ s.Require().False(disjoin)
+ disjoin = makeColumnSet([]uint8{1, 2}).IsDisjoint(
+ makeColumnSet([]uint8{0, 2}))
+ s.Require().False(disjoin)
+ disjoin = makeColumnSet([]uint8{1, 7}).IsDisjoint(
+ makeColumnSet([]uint8{5, 6, 7}))
+ s.Require().False(disjoin)
+ }
+}
+
+func TestPlannerUtils(t *testing.T) {
+ suite.Run(t, new(PlannerUtilsTestSuite))
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-25 15:43:47 +0800