ql/ql.go at master · cznic/ql

This repository was archived by the owner on Nov 22, 2018. It is now read-only.
Repository navigation

// Copyright 2014 The ql Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//LATER profile mem
//LATER profile cpu
//LATER coverage
	"math/big"
	"github.com/cznic/strutil"
	crossJoin = iota
// NOTE: all rset implementations must be safe for concurrent use by multiple
// goroutines.  If the do method requires any execution domain local data, they
// must be held out of the implementing instance.
	_ rset = (*distinctRset)(nil)
	_ rset = (*groupByRset)(nil)
	_ rset = (*joinRset)(nil)
	_ rset = (*limitRset)(nil)
	_ rset = (*offsetRset)(nil)
	_ rset = (*orderByRset)(nil)
	_ rset = (*selectRset)(nil)
	_ rset = (*selectStmt)(nil)
	_ rset = (*tableRset)(nil)
	_ rset = (*whereRset)(nil)
	isTesting bool // enables test hook: select from an index
type rset interface {
	plan(ctx *execCtx) (plan, error)
type recordset struct {
	ctx *execCtx
func (r recordset) fieldNames() []interface{} {
	f := r.plan.fieldNames()
	a := make([]interface{}, len(f))
	for i, v := range f {
// Do implements Recordset.
func (r recordset) Do(names bool, f func(data []interface{}) (bool, error)) error {
	if names {
		if more, err := f(r.fieldNames()); err != nil || !more {
			return err
	return r.ctx.db.do(r, f)
// Fields implements Recordset.
func (r recordset) Fields() (names []string, err error) {
	return r.plan.fieldNames(), nil
// FirstRow implements Recordset.
func (r recordset) FirstRow() (row []interface{}, err error) {
	rows, err := r.Rows(1, 0)
	if err != nil {
		return nil, err
	if len(rows) != 0 {
		return rows[0], nil
	return nil, nil
// Rows implements Recordset.
func (r recordset) Rows(limit, offset int) ([][]interface{}, error) {
	var rows [][]interface{}
	if err := r.Do(false, func(row []interface{}) (bool, error) {
		if offset > 0 {
			offset--
			return true, nil
		case limit < 0:
			rows = append(rows, row)
			return true, nil
		case limit == 0:
			return false, nil
		default: // limit > 0
			rows = append(rows, row)
			return limit > 0, nil
	}); err != nil {
		return nil, err
	return rows, nil
// List represents a group of compiled statements.
type List struct {
	l      []stmt
	params int
// String implements fmt.Stringer
func (l List) String() string {
	var b bytes.Buffer
	f := strutil.IndentFormatter(&b, "\t")
	for _, s := range l.l {
		switch s.(type) {
		case beginTransactionStmt:
			f.Format("%s\n%i", s)
		case commitStmt, rollbackStmt:
			f.Format("%u%s\n", s)
			f.Format("%s\n", s)
	return b.String()
// IsExplainStmt reports whether l is a single EXPLAIN statement or a single EXPLAIN
// statement enclosed in a transaction.
func (l List) IsExplainStmt() bool {
	switch len(l.l) {
		_, ok := l.l[0].(*explainStmt)
		return ok
		if _, ok := l.l[0].(beginTransactionStmt); !ok {
			return false
		if _, ok := l.l[1].(*explainStmt); !ok {
			return false
		_, ok := l.l[2].(commitStmt)
		return ok
		return false
type groupByRset struct {
	colNames []string
	src      plan
func (r *groupByRset) plan(ctx *execCtx) (plan, error) {
	fields := r.src.fieldNames()
	for _, v := range r.colNames {
		found := false
		for _, v2 := range fields {
			if v == v2 {
				found = true
		if !found {
			return nil, fmt.Errorf("unknown field %s", v)
	return &groupByDefaultPlan{colNames: r.colNames, src: r.src, fields: fields}, nil
// TCtx represents transaction context. It enables to execute multiple
// statement lists in the same context. The same context guarantees the state
// of the DB cannot change in between the separated executions.
// LastInsertID
// LastInsertID is updated by INSERT INTO statements. The value considers
// performed ROLLBACK statements, if any, even though roll backed IDs are not
// reused. QL clients should treat the field as read only.
// RowsAffected
// RowsAffected is updated by INSERT INTO, DELETE FROM and UPDATE statements.
// The value does not (yet) consider any ROLLBACK statements involved.  QL
// clients should treat the field as read only.
type TCtx struct {
	LastInsertID int64
	RowsAffected int64
// NewRWCtx returns a new read/wr
10BC8
ite transaction context.  NewRWCtx is safe for
// concurrent use by multiple goroutines, every one of them will get a new,
// unique context.
func NewRWCtx() *TCtx { return &TCtx{} }
// Recordset is a result of a select statement. It can call a user function for
// every row (record) in the set using the Do method.
// Recordsets can be safely reused. Evaluation of the rows is performed lazily.
// Every invocation of Do will see the current, potentially actualized data.
// Do will call f for every row (record) in the Recordset.
// If f returns more == false or err != nil then f will not be called for any
// remaining rows in the set and the err value is returned from Do.
// If names == true then f is firstly called with a virtual row
// consisting of field (column) names of the RecordSet.
// Do is executed in a read only context and performs a RLock of the
// database.
// Do is safe for concurrent use by multiple goroutines.
// Fields return a slice of field names of the recordset. The result is computed
// without actually computing the recordset rows.
// FirstRow
// FirstRow will return the first row of the RecordSet or an error, if any. If
// the Recordset has no rows the result is (nil, nil).
// Rows will return rows in Recordset or an error, if any. The semantics of
// limit and offset are the same as of the LIMIT and OFFSET clauses of the
// SELECT statement. To get all rows pass limit < 0. If there are no rows to
// return the result is (nil, nil).
type Recordset interface {
	Do(names bool, f func(data []interface{}) (more bool, err error)) error
	Fields() (names []string, err error)
	FirstRow() (row []interface{}, err error)
	Rows(limit, offset int) (rows [][]interface{}, err error)
type assignment struct {
	colName string
	expr    expression
func (a *assignment) String() string {
	return fmt.Sprintf("%s=%s", a.colName, a.expr)
type distinctRset struct {
func (r *distinctRset) plan(ctx *execCtx) (plan, error) {
	return &distinctDefaultPlan{src: r.src, fields: r.src.fieldNames()}, nil
type orderByRset struct {
	by  []expression
func (r *orderByRset) String() string {
	a := make([]string, len(r.by))
	for i, v := range r.by {
		a[i] = v.String()
	s := strings.Join(a, ", ")
	if !r.asc {
		s += " DESC"
func (r *orderByRset) plan(ctx *execCtx) (plan, error) {
	if _, ok := r.src.(*nullPlan); ok {
		return r.src, nil
	var by []expression
	fields := r.src.fieldNames()
	for _, e := range r.by {
		cols := mentionedColumns(e)
		for k := range cols {
			found := false
			for _, v := range fields {
				if k == v {
					found = true
			if !found {
				return nil, fmt.Errorf("unknown field %s", k)
		if len(cols) == 0 {
			v, err := e.eval(ctx, nil)
			if err != nil {
				by = append(by, e)
				continue
			if isConstValue(v) != nil {
				continue
		by = append(by, e)
	return &orderByDefaultPlan{asc: r.asc, by: by, src: r.src, fields: fields}, nil
type whereRset struct {
	expr   expression
	src    plan
	sel    *selectStmt
	exists bool
func (r *whereRset) String() string {
	if r.sel != nil {
		if !r.exists {
			s += " NOT "
		return fmt.Sprintf("%s EXISTS ( %s )", s, strings.TrimSuffix(r.sel.String(), ";"))
	return r.expr.String()
func (r *whereRset) planBinOp(x *binaryOperation) (plan, error) {
	p := r.src
	ok, cn := isColumnExpression(x.l)
	if ok && cn == "id()" {
		if v := isConstValue(x.r); v != nil {
			v, err := typeCheck1(v, idCol)
			if err != nil {
				return nil, err
			rv := v.(int64)
			switch {
			case p.hasID():
				switch x.op {
				case '<':
					if rv <= 1 {
						return &nullPlan{p.fieldNames()}, nil
				case '>':
					if rv <= 0 {
						return p, nil
				case ge:
					if rv >= 1 {
						return p, nil
				case neq:
					if rv <= 0 {
						return p, nil
				case eq:
					if rv <= 0 {
						return &nullPlan{p.fieldNames()}, nil
				case le:
					if rv <= 0 {
						return &nullPlan{p.fieldNames()}, nil
	var err error
	var p2 plan
	var is []string
	switch x.op {
	case eq, ge, '>', le, '<', neq:
		if p2, is, err = p.filter(x); err != nil {
			return nil, err
		if p2 != nil {
			return p2, nil
	case andand:
		var in []expression
		var f func(expression)
		f = func(e expression) {
			b, ok := e.(*binaryOperation)
			if !ok || b.op != andand {
				in = append(in, e)
		out := []expression{}
		p := r.src
		isNewPlan := false
		for _, e := range in {
			p2, is2, err := p.filter(e)
			if err != nil {
				return nil, err
			if p2 == nil {
				is = append(is, is2...)
				out = append(out, e)
				continue
			isNewPlan = true
		if !isNewPlan {
		if len(out) == 0 {
			return p, nil
		for len(out) > 1 {
			n := len(out)
			e, err := newBinaryOperation(andand, out[n-2], out[n-1])
			if err != nil {
				return nil, err
			out = out[:n-1]
			out[n-2] = e
		return &filterDefaultPlan{p, out[0], is}, nil
	return &filterDefaultPlan{p, x, is}, nil
func (r *whereRset) planIdent(x *ident) (plan, error) {
	p := r.src
	p2, is, err := p.filter(x)
	if err != nil {
		return nil, err
	if p2 != nil {
		return p2, nil
	return &filterDefaultPlan{p, x, is}, nil
func (r *whereRset) planIsNull(x *isNull) (plan, error) {
	p := r.src
	ok, cn := isColumnExpression(x.expr)
		return &filterDefaultPlan{p, x, nil}, nil
	if cn == "id()" {
		case p.hasID():
			switch {
			case x.not: // IS NOT NULL
				return p, nil
			default: // IS NULL
				return &nullPlan{p.fieldNames()}, nil
			switch {
			case x.not: // IS NOT NULL
				return &nullPlan{p.fieldNames()}, nil
			default: // IS NULL
				return p, nil
	p2, is, err := p.filter(x)
	if err != nil {
		return nil, err
	if p2 != nil {
		return p2, nil
	return &filterDefaultPlan{p, x, is}, nil
func (r *whereRset) planUnaryOp(x *unaryOperation) (plan, error) {
	p := r.src
	p2, is, err := p.filter(x)
	if err != nil {
		return nil, err
	if p2 != nil {
		return p2, nil
	return &filterDefaultPlan{p, x, is}, nil
func (r *whereRset) plan(ctx *execCtx) (plan, error) {
	o := r.src
	if r.sel != nil {
		var exists bool
		ctx.mu.RLock()
		m, ok := ctx.cache[r.sel]
		ctx.mu.RUnlock()
			exists = m.(bool)
			p, err := r.sel.plan(ctx)
			if err != nil {
				return nil, err
			err = p.do(ctx, func(i interface{}, data []interface{}) (bool, error) {
				if len(data) > 0 {
					exists = true
				return false, nil
			if err != nil {
				return nil, err
			ctx.mu.Lock()
			ctx.cache[r.sel] = true
			ctx.mu.Unlock()
		if r.exists == exists {
			return o, nil
		return &nullPlan{fields: o.fieldNames()}, nil
	return r.planExpr(ctx)
func (r *whereRset) planExpr(ctx *execCtx) (plan, error) {
	if r.expr == nil {
		return &nullPlan{}, nil
	expr, err := r.expr.clone(ctx.arg)
	if err != nil {
		return nil, err
	switch r.src.(type) {
	case *leftJoinDefaultPlan, *rightJoinDefaultPlan, *fullJoinDefaultPlan:
		return &filterDefaultPlan{r.src, expr, nil}, nil
	switch x := expr.(type) {
	case *binaryOperation:
		return r.planBinOp(x)
	case *ident:
		return r.planIdent(x)
	case *isNull:
		return r.planIsNull(x)
	case *pIn:
		//TODO optimize
		//TODO show plan
	case *pLike:
		//TODO optimize
	case *unaryOperation:
		return r.planUnaryOp(x)
	return &filterDefaultPlan{r.src, expr, nil}, nil
type offsetRset struct {
	expr expression
func (r *offsetRset) plan(ctx *execCtx) (plan, error) {
	return &offsetDefaultPlan{expr: r.expr, src: r.src, fields: r.src.fieldNames()}, nil
type limitRset struct {
	expr expression
func (r *limitRset) plan(ctx *execCtx) (plan, error) {
	return &limitDefaultPlan{expr: r.expr, src: r.src, fields: r.src.fieldNames()}, nil
type selectRset struct {
	flds []*fld
func (r *selectRset) plan(ctx *execCtx) (plan, error) {
	if r.src == nil {
		return nil, nil
	var flds2 []*fld
	if len(r.flds) != 0 {
		m := map[string]struct{}{}
		for _, v := range r.flds {
			mentionedColumns0(v.expr, true, true, m)
		for _, v := range r.src.fieldNames() {
			delete(m, v)
		for k := range m {
			return nil, fmt.Errorf("unknown field %s", k)
		flds2 = append(flds2, r.flds...)
	if x, ok := r.src.(*groupByDefaultPlan); ok {
		if len(r.flds) == 0 {
			fields := x.fieldNames()
			flds := make([]*fld, len(fields))
			for i, v := range fields {
				flds[i] = &fld{&ident{v}, v}
			return &selectFieldsGroupPlan{flds: flds, src: x, fields: fields}, nil
		p := &selectFieldsGroupPlan{flds: flds2, src: x}
		for _, v := range r.flds {
			p.fields = append(p.fields, v.name)
		return p, nil
	if len(r.flds) == 0 {
		return r.src, nil
	f0 := r.src.fieldNames()
	if len(f0) == len(flds2) {
		match := true
		for i, v := range flds2 {
			if x, ok := v.expr.(*ident); ok && x.s == f0[i] && v.name == f0[i] {
				continue
			match = false
		if match {
			return r.src, nil
	src := r.src
	if x, ok := src.(*tableDefaultPlan); ok {
		isconst := true
		for _, v := range flds2 {
			if isConstValue(v.expr) == nil {
				isconst = false
		if isconst { // #250
			src = &tableNilPlan{x.t}
	p := &selectFieldsDefaultPlan{flds: flds2, src: src}
	for _, v := range r.flds {
		p.fields = append(p.fields, v.name)
	return p, nil
type tableRset string
func (r tableRset) plan(ctx *execCtx) (plan, error) {
	switch r {
	case "__Table":
		return &sysTableDefaultPlan{}, nil
	case "__Column":
		return &sysColumnDefaultPlan{}, nil
	case "__Index":
		return &sysIndexDefaultPlan{}, nil
	t, ok := ctx.db.root.tables[string(r)]
	if !ok && isTesting {
		if _, x0 := ctx.db.root.findIndexByName(string(r)); x0 != nil {
			return &selectIndexDefaultPlan{nm: string(r), x: x0}, nil
		return nil, fmt.Errorf("table %s does not exist", r)
	rs := &tableDefaultPlan{t: t}
	for _, col := range t.cols {
		rs.fields = append(rs.fields, col.name)
	return rs, nil
func findFld(fields []*fld, name string) (f *fld) {
	for _, f = range fields {
		if f.name == name {
	return nil
type col struct {
	index      int
	name       string
	typ        int
	constraint *constraint
	dflt       expression
var idCol = &col{name: "id()", typ: qInt64}
func findCol(cols []*col, name string) (c *col) {
	for _, c = range cols {
		if c.name == name {
	return nil
func (f *col) clone() *col {
	r.constraint = f.constraint.clone()
	if f.dflt != nil {
		r.dflt, _ = r.dflt.clone(nil)
func (f *col) typeCheck(x interface{}) (ok bool) { //NTYPE
	switch x.(type) {
		return true
	case bool:
		return f.typ == qBool
	case complex64:
		return f.typ == qComplex64
	case complex128:
		return f.typ == qComplex128
	case float32:
		return f.typ == qFloat32
	case float64:
		return f.typ == qFloat64
	case int8:
		return f.typ == qInt8
	case int16:
		return f.typ == qInt16
	case int32:
		return f.typ == qInt32
	case int64:
		return f.typ == qInt64
	case string:
		return f.typ == qString
	case uint8:
		return f.typ == qUint8
	case uint16:
		return f.typ == qUint16
	case uint32:
		return f.typ == qUint32
	case uint64:
		return f.typ == qUint64
	case []byte:
		return f.typ == qBlob
	case *big.Int:
		return f.typ == qBigInt
	case *big.Rat:
		return f.typ == qBigRat
	case time.Time:
		return f.typ == qTime
	case time.Duration:
		return f.typ == qDuration
	case chunk:
		return true // was checked earlier
func cols2meta(f []*col) (s string) {
	a := []string{}
	for _, f := range f {
		a = append(a, string(f.typ)+f.name)
	return strings.Join(a, "|")
// DB represent the database capable of executing QL statements.
type DB struct {
	cc          *TCtx // Current transaction context
	exprCache   map[string]expression
	exprCacheMu sync.Mutex
	hasIndex2   int // 0: nope, 1: in progress, 2: yes.
	isMem       bool
	mu          sync.Mutex
	queue       []chan struct{}
	root        *root
	rw          bool // DB FSM
	rwmu        sync.RWMutex
	store       storage
	tnl         int // Transaction nesting level
var selIndex2Expr = MustCompile("select Expr from __Index2_Expr where Index2_ID == $1")
func newDB(store storage) (db *DB, err error) {
	db0 := &DB{
		exprCache: map[string]expression{},
		store:     store,
	if db0.root, err = newRoot(store); err != nil {
	ctx := newExecCtx(db0, nil)
	for _, t := range db0.root.tables {
		if err := t.constraintsAndDefaults(ctx); err != nil {
			return nil, err
	if !db0.hasAllIndex2() {
		return db0, nil
	db0.hasIndex2 = 2
	rss, _, err := db0.Run(nil, "select id(), TableName, IndexName, IsUnique, Root from __Index2 where !IsSimple")
	if err != nil {
		return nil, err
	rows, err := rss[0].Rows(-1, 0)
	if err != nil {
		return nil, err
	for _, row := range rows {
		defer func() {
			if e := recover(); e != nil {
				err = fmt.Errorf("error loading DB indices: %v", e)
		id := row[0].(int64)
		tn := row[1].(string)
		xn := row[2].(string)
		unique := row[3].(bool)
		xroot := row[4].(int64)
		t := db0.root.tables[tn]
		if t == nil {
			return nil, fmt.Errorf("DB index refers to nonexistent table: %s", tn)
		x, err := store.OpenIndex(unique, xroot)
		if err != nil {
			return nil, err
		if v := t.indices2[xn]; v != nil {
			return nil, fmt.Errorf("duplicate DB index: %s", xn)
		ix := &index2{
			unique: unique,
			x:      x,
			xroot:  xroot,
		rss, _, err := db0.Execute(nil, selIndex2Expr, id)
		if err != nil {
			return nil, err
		rows, err := rss[0].Rows(-1, 0)
		if err != nil {
			return nil, err
		if len(rows) == 0 {
			return nil, fmt.Errorf("index has no expression: %s", xn)
		var sources []string
		var list []expression
		for _, row := range rows {
			src, ok := row[0].(string)
			if !ok {
				return nil, fmt.Errorf("index %s: expression of type %T", xn, row[0])
			expr, err := db0.str2expr(src)
			if err != nil {
				return nil, fmt.Errorf("index %s: expression error: %v", xn, err)
			sources = append(sources, src)
			list = append(list, expr)
		ix.sources = sources
		ix.exprList = list
		if t.indices2 == nil {
			t.indices2 = map[string]*index2{}
		t.indices2[xn] = ix
	return db0, nil
func (db *DB) deleteIndex2ByIndexName(nm string) error {
	for _, s := range deleteIndex2ByIndexName.l {
		if _, err := s.exec(newExecCtx(db, []interface{}{nm})); err != nil {
			return err
	return nil
func (db *DB) deleteIndex2ByTableName(nm string) error {
	for _, s := range deleteIndex2ByTableName.l {
		if _, err := s.exec(newExecCtx(db, []interface{}{nm})); err != nil {
			return err
	return nil
func (db *DB) createIndex2() error {
	if db.hasIndex2 != 0 {
		return nil
	db.hasIndex2 = 1
	ctx := execCtx{db: db}
	for _, s := range createIndex2.l {
		if _, err := s.exec(&ctx); err != nil {
			db.hasIndex2 = 0
			return err
	for t := db.root.thead; t != nil; t = t.tnext {
		for i, index := range t.indices {
			if index == nil {
				continue
			expr := "id()"
			if i != 0 {
				expr = t.cols0[i-1].name
			if err := db.insertIndex2(t.name, index.name, []string{expr}, index.unique, true, index.xroot); err != nil {
				db.hasIndex2 = 0
				return err
	db.hasIndex2 = 2
	return nil
View remainder of file in raw view
FilesExpand file tree

ql.go

Latest commit

History

ql.go

File metadata and controls
