sqlvm: planner: wip

7 files changed, 1671 insertions, 0 deletions

diff --git a/core/vm/sqlvm/errors/errors.go b/core/vm/sqlvm/errors/errors.go
index 6f2b8ad93..ad00e5bb0 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
 	ErrorCodeInvalidDataType
 	ErrorCodeOverflow
@@ -141,6 +145,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
 	ErrorCodeInvalidDataType:    "invalid data type",
 	ErrorCodeOverflow:           "overflow",
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..5f2f06e25
--- /dev/null
+++ b/core/vm/sqlvm/planner/planner.go
@@ -0,0 +1,494 @@
+package planner
+
+import (
+	"github.com/shopspring/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 (planner *planner) planInsert(stmt *ast.InsertStmtNode) (PlanStep, error) {
+	tableIdx, ok := findTableIdxByName(planner.schema, stmt.Table.Name)
+	if !ok {
+		panic("Invalid table name.")
+	}
+	planner.tableRef = tableIdx
+	planner.table = &planner.schema[tableIdx]
+
+	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 {
+			columnIdx, ok := findColumnIdxByName(planner.table, node.Name)
+			if !ok {
+				panic("Invalid column name.")
+			}
+			plan.Columns[i] = columnIdx
+		}
+		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) && leftCols[i] == cl.ColumnSet[k]:
+			leftColMap[i] = k
+			i++
+		case j < len(rightCols) && rightCols[j] == cl.ColumnSet[k]:
+			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.
+		// TODO(yenlin): bool column is directly enumerable.
+		colIdx, ok := findColumnIdxByName(planner.table, op.Name)
+		if !ok {
+			// This is function name.
+			// TODO(yenlin): distinguish function name from column names.
+			break
+		}
+		cl.ColumnSet = []schema.ColumnRef{colIdx}
+		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
+
+			// NOTICE: we need the index.Columns in ascending order.
+			columnSet := (ColumnSet)(index.Columns)
+			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)
+	}
+	tableIdx, ok := findTableIdxByName(planner.schema, stmt.Table.Name)
+	if !ok {
+		panic("Invalid table name.")
+	}
+	planner.tableRef = tableIdx
+	planner.table = &planner.schema[tableIdx]
+
+	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) {
+	tableIdx, ok := findTableIdxByName(planner.schema, stmt.Table.Name)
+	if !ok {
+		panic("Invalid table name.")
+	}
+	planner.tableRef = tableIdx
+	planner.table = &planner.schema[tableIdx]
+
+	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
+		}
+		columnIdx, ok := findColumnIdxByName(planner.table, as.Column.Name)
+		if !ok {
+			panic("Invalid column name.")
+		}
+		plan.Columns[i] = columnIdx
+		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) {
+	tableIdx, ok := findTableIdxByName(planner.schema, stmt.Table.Name)
+	if !ok {
+		panic("Invalid table name.")
+	}
+	planner.tableRef = tableIdx
+	planner.table = &planner.schema[tableIdx]
+
+	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..a1065db1e
--- /dev/null
+++ b/core/vm/sqlvm/planner/planner_test.go
@@ -0,0 +1,712 @@
+package planner
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/shopspring/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")},
+			Insert: &ast.InsertWithColumnOptionNode{
+				Column: []*ast.IdentifierNode{
+					&ast.IdentifierNode{Name: []byte("a")},
+					&ast.IdentifierNode{Name: []byte("b")},
+				},
+				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")},
+				Subject: &ast.IdentifierNode{Name: []byte("b")},
+			},
+		}
+		stmt := &ast.UpdateStmtNode{
+			Table: &ast.IdentifierNode{Name: []byte("table1")},
+			Assignment: []*ast.AssignOperatorNode{
+				&ast.AssignOperatorNode{
+					Column: &ast.IdentifierNode{Name: []byte("a")},
+					Expr:   expr,
+				},
+			},
+		}
+		expectedPlan := &UpdateStep{
+			Table:     0,
+			ColumnSet: ColumnSet{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")},
+				&ast.IdentifierNode{Name: []byte("b")},
+			},
+			Table: &ast.IdentifierNode{Name: []byte("table1")},
+			Where: &ast.WhereOptionNode{
+				Condition: &ast.EqualOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("b")},
+						Subject: &ast.BytesValueNode{V: []byte("valB")},
+					},
+				},
+			},
+			Order: []*ast.OrderOptionNode{
+				&ast.OrderOptionNode{
+					Expr: &ast.IdentifierNode{Name: []byte("c")},
+				},
+			},
+			Limit: &ast.LimitOptionNode{
+				Value: &ast.IntegerValueNode{
+					V: limit,
+				},
+			},
+			Offset: &ast.OffsetOptionNode{
+				Value: &ast.IntegerValueNode{
+					V: offset,
+				},
+			},
+		}
+		expectedPlan := &SelectStep{
+			Table:     0,
+			ColumnSet: ColumnSet{0, 1, 2},
+			Columns: []ast.ExprNode{
+				&ast.IdentifierNode{Name: []byte("a")},
+				&ast.IdentifierNode{Name: []byte("b")},
+			},
+			Order: []*ast.OrderOptionNode{
+				&ast.OrderOptionNode{
+					Expr: &ast.IdentifierNode{Name: []byte("c")},
+				},
+			},
+			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")},
+			Where: &ast.WhereOptionNode{
+				Condition: &ast.GreaterOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("b")},
+						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")},
+								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: []schema.ColumnRef{0, 1, 2},
+			Attr:      clauseAttrAnd | clauseAttrEnumerable,
+			SubCls: []*clause{
+				&clause{
+					ColumnSet: []schema.ColumnRef{0, 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: []schema.ColumnRef{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: []schema.ColumnRef{0, 1, 2},
+			Attr:      clauseAttrAnd | clauseAttrEnumerable,
+			SubCls: []*clause{
+				&clause{
+					ColumnSet: []schema.ColumnRef{0, 2},
+					Attr:      clauseAttrEnumerable,
+					HashKeys:  [][]ast.Valuer{},
+				},
+				&clause{
+					ColumnSet: []schema.ColumnRef{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: []schema.ColumnRef{0, 1, 2},
+			Attr:      clauseAttrAnd | clauseAttrEnumerable,
+			SubCls: []*clause{
+				&clause{
+					ColumnSet: []schema.ColumnRef{0, 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: []schema.ColumnRef{1},
+					Attr:      clauseAttrEnumerable,
+					HashKeys:  [][]ast.Valuer{},
+				},
+			},
+		}
+		planner.mergeAndHashKeys(cl)
+		expectedKeys = [][]ast.Valuer{}
+		s.Require().Equal(expectedKeys, cl.HashKeys)
+	}
+	{
+		// Test OR merge.
+		cl := &clause{
+			ColumnSet: []schema.ColumnRef{0, 2},
+			Attr:      clauseAttrOr | clauseAttrEnumerable,
+			SubCls: []*clause{
+				&clause{
+					ColumnSet: []schema.ColumnRef{0, 2},
+					Attr:      clauseAttrEnumerable,
+					HashKeys: [][]ast.Valuer{
+						genCombination([]schema.ColumnRef{0, 2}, []int{0, 0}),
+						genCombination([]schema.ColumnRef{0, 2}, []int{1, 1}),
+					},
+				},
+				&clause{
+					ColumnSet: []schema.ColumnRef{0, 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 schema 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: schema,
+		table:  &schema[0],
+	}
+
+	{
+		node := &ast.IdentifierNode{Name: []byte("a")}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Equal(clauseAttrColumn, cl.Attr)
+		s.Require().Equal(ColumnSet{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")},
+				Subject: valA,
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Equal(clauseAttrEnumerable, cl.Attr)
+		s.Require().Equal(ColumnSet{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")},
+				Subject: &ast.BytesValueNode{V: []byte("valA")},
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Zero(cl.Attr)
+		s.Require().Equal(ColumnSet{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")},
+						Subject: valB,
+					},
+				},
+				Subject: &ast.EqualOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("a")},
+						Subject: valA,
+					},
+				},
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Equal(clauseAttrEnumerable|clauseAttrAnd, cl.Attr)
+		s.Require().Equal(ColumnSet{0, 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")},
+						Subject: &ast.BytesValueNode{V: []byte("valA")},
+					},
+				},
+				Subject: &ast.EqualOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("b")},
+						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{0, 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")},
+						Subject: valA,
+					},
+				},
+				Subject: &ast.EqualOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("b")},
+						Subject: valB,
+					},
+				},
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Equal(clauseAttrOr|clauseAttrEnumerable, cl.Attr)
+		s.Require().Equal(ColumnSet{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")},
+					Subject: valA,
+				},
+			},
+			Right: []ast.ExprNode{
+				&ast.EqualOperatorNode{
+					BinaryOperatorNode: ast.BinaryOperatorNode{
+						Object:  &ast.IdentifierNode{Name: []byte("b")},
+						Subject: valB,
+					},
+				},
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Zero(cl.Attr)
+		s.Require().Equal(ColumnSet{0, 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")},
+			Right: []ast.ExprNode{
+				valA, valB,
+			},
+		}
+		cl, err := planner.parseClause(node)
+		s.Require().Nil(err)
+		s.Require().Equal(clauseAttrEnumerable, cl.Attr)
+		s.Require().Equal(ColumnSet{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")},
+					Subject: &ast.IdentifierNode{Name: []byte("b")},
+				},
+			},
+			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{0, 1}, cl.ColumnSet)
+		s.Require().Zero(cl.HashKeys)
+	}
+	{
+		node := &ast.EqualOperatorNode{
+			BinaryOperatorNode: ast.BinaryOperatorNode{
+				Object: &ast.IdentifierNode{Name: []byte("a")},
+				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{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..eb5c4f3a0
--- /dev/null
+++ b/core/vm/sqlvm/planner/types.go
@@ -0,0 +1,166 @@
+package planner
+
+import (
+	"github.com/shopspring/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..e1aad047a
--- /dev/null
+++ b/core/vm/sqlvm/planner/utils.go
@@ -0,0 +1,113 @@
+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.ColumnRef
+
+// Join creates a new set which is the union of c and other.
+func (c ColumnSet) Join(other ColumnSet) ColumnSet {
+	ret := make([]schema.ColumnRef, 0, len(c)+len(other))
+	i, j := 0, 0
+	for i != len(c) && j != len(other) {
+		if c[i] == other[j] {
+			ret = append(ret, c[i])
+			i++
+			j++
+		} else if c[i] > other[j] {
+			ret = append(ret, other[j])
+			j++
+		} else {
+			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 c[i] != other[i] {
+			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) {
+		if c[i] == other[j] {
+			return false
+		}
+		if c[i] > other[j] {
+			j++
+		} else {
+			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) {
+		if c[i] > other[j] {
+			// Found some item not in c.
+			return false
+		}
+		if c[i] == other[j] {
+			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..3e3d90a8d
--- /dev/null
+++ b/core/vm/sqlvm/planner/utils_test.go
@@ -0,0 +1,101 @@
+package planner
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/suite"
+)
+
+type PlannerUtilsTestSuite struct{ suite.Suite }
+
+func (s *PlannerUtilsTestSuite) TestColumnSet() {
+	{
+		// Join.
+		var columns, expected ColumnSet
+		columns = ColumnSet{1, 3, 5}.Join(ColumnSet{0, 1, 2, 4, 6})
+		expected = ColumnSet{0, 1, 2, 3, 4, 5, 6}
+		s.Require().Equal(expected, columns)
+		columns = ColumnSet{1, 3, 5}.Join(ColumnSet{3, 5})
+		expected = ColumnSet{1, 3, 5}
+		s.Require().Equal(expected, columns)
+		columns = ColumnSet{}.Join(ColumnSet{0})
+		expected = ColumnSet{0}
+		s.Require().Equal(expected, columns)
+		columns = ColumnSet{1}.Join(ColumnSet{1, 3})
+		expected = ColumnSet{1, 3}
+		s.Require().Equal(expected, columns)
+		columns = ColumnSet{5}.Join(ColumnSet{1, 3})
+		expected = ColumnSet{1, 3, 5}
+		s.Require().Equal(expected, columns)
+	}
+	{
+		// Equal.
+		var equal bool
+		// True cases.
+		equal = ColumnSet{}.Equal(ColumnSet{})
+		s.Require().True(equal)
+		equal = ColumnSet{1, 2}.Equal(ColumnSet{1, 2})
+		s.Require().True(equal)
+		// False cases.
+		equal = ColumnSet{}.Equal(ColumnSet{1, 2})
+		s.Require().False(equal)
+		equal = ColumnSet{1, 2}.Equal(ColumnSet{})
+		s.Require().False(equal)
+		equal = ColumnSet{2}.Equal(ColumnSet{1})
+		s.Require().False(equal)
+		equal = ColumnSet{2}.Equal(ColumnSet{1, 3})
+		s.Require().False(equal)
+		equal = ColumnSet{1, 3}.Equal(ColumnSet{2})
+		s.Require().False(equal)
+	}
+	{
+		// Contains.
+		var contains bool
+		// True cases.
+		contains = ColumnSet{}.Contains(ColumnSet{})
+		s.Require().True(contains)
+		contains = ColumnSet{1, 2}.Contains(ColumnSet{})
+		s.Require().True(contains)
+		contains = ColumnSet{1, 2}.Contains(ColumnSet{2})
+		s.Require().True(contains)
+		contains = ColumnSet{1, 2}.Contains(ColumnSet{1})
+		s.Require().True(contains)
+		contains = ColumnSet{1, 2, 3}.Contains(ColumnSet{1, 2})
+		s.Require().True(contains)
+		// False cases.
+		contains = ColumnSet{1}.Contains(ColumnSet{2})
+		s.Require().False(contains)
+		contains = ColumnSet{2}.Contains(ColumnSet{1, 2})
+		s.Require().False(contains)
+		contains = ColumnSet{1}.Contains(ColumnSet{1, 2})
+		s.Require().False(contains)
+		contains = ColumnSet{1, 3, 5}.Contains(ColumnSet{4})
+		s.Require().False(contains)
+	}
+	{
+		// IsDisjoint.
+		var disjoin bool
+		// True cases.
+		disjoin = ColumnSet{}.IsDisjoint(ColumnSet{})
+		s.Require().True(disjoin)
+		disjoin = ColumnSet{}.IsDisjoint(ColumnSet{1})
+		s.Require().True(disjoin)
+		disjoin = ColumnSet{1}.IsDisjoint(ColumnSet{})
+		s.Require().True(disjoin)
+		disjoin = ColumnSet{1}.IsDisjoint(ColumnSet{2})
+		s.Require().True(disjoin)
+		// False cases.
+		disjoin = ColumnSet{1, 2}.IsDisjoint(ColumnSet{2})
+		s.Require().False(disjoin)
+		disjoin = ColumnSet{1, 2}.IsDisjoint(ColumnSet{1})
+		s.Require().False(disjoin)
+		disjoin = ColumnSet{1, 2}.IsDisjoint(ColumnSet{0, 2})
+		s.Require().False(disjoin)
+		disjoin = ColumnSet{1, 7}.IsDisjoint(ColumnSet{5, 6, 7})
+		s.Require().False(disjoin)
+	}
+}
+
+func TestPlannerUtils(t *testing.T) {
+	suite.Run(t, new(PlannerUtilsTestSuite))
+}