Skip to content

Database governance built for humans and agents — controlling changes and access across every major database.

36.5 KB
Raw Blame
package tidb

import (
	"context"
	"strings"

	"github.com/pingcap/tidb/pkg/parser"
	tidbast "github.com/pingcap/tidb/pkg/parser/ast"
	"github.com/pkg/errors"

	"github.com/bytebase/bytebase/backend/plugin/parser/base"
	"github.com/bytebase/bytebase/backend/store/model"
)

// rowIDColumnName is TiDB's hidden row handle: readable on a table without a
// clustered index, listed in no catalog, so never in synced metadata.
// https://docs.pingcap.com/tidb/stable/tidb-rowid/
const rowIDColumnName = "_tidb_rowid"

type querySpanExtractor struct {
	ctx               context.Context
	defaultDatabase   string
	metaCache         map[string]*model.DatabaseMetadata
	gCtx              base.GetQuerySpanContext
	lowerTableViewMap map[string]map[string]bool

	ctes              []*base.PseudoTable
	outerTableSources []base.TableSource
	tableSourcesFrom  []base.TableSource

	// baseTableSources marks the aliases and joins built only from base
	// tables; base.PseudoTable drops that identity.
	baseTableSources map[base.TableSource]bool

	// viewResolutionStack tracks the views currently being expanded so a
	// cyclic view reference (a view that transitively references itself) is
	// reported as an error instead of recursing until the stack overflows.
	viewResolutionStack map[string]bool
}

func newQuerySpanExtractor(defaultDatabase string, gCtx base.GetQuerySpanContext) *querySpanExtractor {
	return &querySpanExtractor{
		defaultDatabase:   defaultDatabase,
		metaCache:         make(map[string]*model.DatabaseMetadata),
		lowerTableViewMap: make(map[string]map[string]bool),
		gCtx:              gCtx,
		baseTableSources:  make(map[base.TableSource]bool),
	}
}

func (q *querySpanExtractor) getQuerySpan(ctx context.Context, statement string) (*base.QuerySpan, error) {
	q.ctx = ctx

	p := parser.New()
	p.EnableWindowFunc(true)
	nodeList, _, err := p.Parse(statement, "", "")
	if err != nil {
		return nil, err
	}
	if len(nodeList) != 1 {
		return nil, errors.Errorf("expecting 1 statement, but got %d", len(nodeList))
	}

	node := nodeList[0]

	accessNode := node
	includeUncached := false
	if explain, ok := node.(*tidbast.ExplainStmt); ok {
		if explain.Stmt == nil {
			return nil, errors.New("EXPLAIN by digest or connection is not supported: referenced tables cannot be determined")
		}
		// A plan carries the tables it reads. System tables are left out: they are
		// not tracked databases, and a plain EXPLAIN may mix them with user tables.
		if !explain.Analyze {
			sourceColumns := q.getAccessTables(explain.Stmt, true)
			for resource := range sourceColumns {
				if isSystemResource(resource) {
					delete(sourceColumns, resource)
				}
			}
			return &base.QuerySpan{Type: base.Explain, Results: []base.QuerySpanResult{}, SourceColumns: sourceColumns}, nil
		}
		accessNode = explain.Stmt
		includeUncached = true
	}
	accessTables := q.getAccessTables(accessNode, includeUncached)
	allSystems, mixed := isMixedQuery(accessTables)
	if mixed {
		return nil, base.MixUserSystemTablesError
	}

	queryType, isExplainAnalyze := getQueryType(node, allSystems)
	if skipQuerySpan(node, queryType) {
		return &base.QuerySpan{
			Type:           queryType,
			ExplainAnalyze: isExplainAnalyze,
			Results:        []base.QuerySpanResult{},
			SourceColumns:  accessTables,
		}, nil
	}

	// For EXPLAIN ANALYZE SELECT, we determine the query type and access tables from the inner SELECT statement.
	if isExplainAnalyze {
		return &base.QuerySpan{
			Type:           queryType,
			ExplainAnalyze: true,
			Results:        []base.QuerySpanResult{},
			SourceColumns:  accessTables,
		}, nil
	}

	tableSource, err := q.extractTableSourceFromNode(node)
	if err != nil {
		// Surface ResourceNotFoundError on the span so the SQL service can resync stale metadata and retry.
		var resourceNotFound *base.ResourceNotFoundError
		if errors.As(err, &resourceNotFound) {
			sourceColumns := make(base.SourceColumnSet, len(accessTables)+1)
			for k := range accessTables {
				sourceColumns[k] = true
			}
			// Add the not-found target only when it carries a distinct ACL/resync anchor.
			// For unqualified column-not-found, target.Table is empty and the FROM tables
			// in accessTables already provide the right table-level ACL keys, so skip.
			target := notFoundSyncTarget(resourceNotFound, q.defaultDatabase)
			if len(sourceColumns) == 0 || target.Table != "" {
				sourceColumns[target] = true
			}
			return &base.QuerySpan{
				Type:          queryType,
				Results:       []base.QuerySpanResult{},
				SourceColumns: sourceColumns,
				NotFoundError: resourceNotFound,
			}, nil
		}
		return nil, err
	}
	if tableSource == nil {
		return &base.QuerySpan{
			Type:          queryType,
			Results:       []base.QuerySpanResult{},
			SourceColumns: accessTables,
		}, nil
	}

	return &base.QuerySpan{
		Type:          queryType,
		Results:       tableSource.GetQuerySpanResult(),
		SourceColumns: accessTables,
	}, nil
}

// notFoundSyncTarget derives a sync target for the resync loop, falling back to defaultDatabase when the error lacks one.
func notFoundSyncTarget(e *base.ResourceNotFoundError, defaultDatabase string) base.ColumnResource {
	r := base.ColumnResource{Database: defaultDatabase}
	if e.Database != nil && *e.Database != "" {
		r.Database = *e.Database
	}
	if e.Schema != nil {
		r.Schema = *e.Schema
	}
	if e.Table != nil {
		r.Table = *e.Table
	}
	if e.Column != nil {
		r.Column = *e.Column
	}
	return r
}

func skipQuerySpan(node tidbast.Node, queryType base.QueryType) bool {
	if queryType == base.Select {
		return false
	}

	// This is for internal view in a SELECT statement.
	if _, ok := node.(*tidbast.CreateViewStmt); ok {
		return false
	}

	return true
}

func isMixedQuery(m base.SourceColumnSet) (bool, bool) {
	hasSystem, hasUser := false, false

	for table := range m {
		if isSystemResource(table) {
			hasSystem = true
		} else {
			hasUser = true
		}
	}

	if hasSystem && hasUser {
		return false, true
	}

	return !hasUser && hasSystem, false
}

func isSystemResource(resource base.ColumnResource) bool {
	database := resource.Database
	database = strings.ToLower(database)
	return systemDatabases[database]
}

var systemDatabases = map[string]bool{
	"information_schema": true,
	"mysql":              true,
	"performance_schema": true,
	"sys":                true,
	// TiDB only
	"metrics_schema": true,
}

func (q *querySpanExtractor) getAccessTables(node tidbast.Node, includeUncached bool) base.SourceColumnSet {
	accessesMap := make(base.SourceColumnSet)
	// ANALYZE executes before metadata can be refreshed. Keep every physical
	// target for authorization, excluding only references to in-scope CTEs.
	v := &accessTableVisitor{resolveCTEs: includeUncached}
	node.Accept(v)
	for _, table := range v.tables {
		databaseName := table.Schema.O
		if databaseName == "" {
			databaseName = q.defaultDatabase
		}

		// This is a false-positive behavior, the table we found may not be the table the query actually accesses.
		// For example, the query is `WITH t1 AS (SELECT 1) SELECT * FROM t1` and we have a physical table `t1` in the database exactly,
		// what we found is the physical table `t1`, but the query actually accesses the CTE `t1`.
		// We do this because we do not have too much time to implement the real behavior.
		// XXX(rebelice/zp): Can we pass more information here to make this function know the context and then
		// figure out whether the table is the table the query actually accesses
		if !includeUncached && !q.existsTableMetadata(databaseName, table.Name.O) {
			continue
		}

		resource := base.ColumnResource{
			Database: databaseName,
			Table:    table.Name.O,
		}
		accessesMap[resource] = true
	}
	return accessesMap
}

func (q *querySpanExtractor) existsTableMetadata(databaseName string, tableName string) bool {
	if databaseName == "" {
		databaseName = q.defaultDatabase
	}

	if q.lowerTableViewMap[databaseName] != nil {
		return q.lowerTableViewMap[databaseName][strings.ToLower(tableName)]
	}

	databaseMetadata, err := q.getDatabaseMetadata(databaseName)
	if err != nil {
		return false
	}

	if databaseMetadata == nil {
		return false
	}
	schemaMetadata := databaseMetadata.GetSchemaMetadata("")
	if schemaMetadata == nil {
		return false
	}

	tableViewMap := make(map[string]bool)
	for _, table := range schemaMetadata.ListTableNames() {
		tableViewMap[strings.ToLower(table)] = true
	}
	for _, view := range schemaMetadata.ListViewNames() {
		tableViewMap[strings.ToLower(view)] = true
	}
	q.lowerTableViewMap[databaseName] = tableViewMap

	return q.lowerTableViewMap[databaseName][strings.ToLower(tableName)]
}

func (q *querySpanExtractor) extractTableSourceFromNode(node tidbast.Node) (base.TableSource, error) {
	if node == nil {
		return nil, nil
	}
	switch node := node.(type) {
	case *tidbast.SelectStmt:
		return q.extractSelect(node)
	case *tidbast.Join:
		return q.extractJoin(node)
	case *tidbast.TableSource:
		return q.extractTableSource(node)
	case *tidbast.TableName:
		return q.extractTableName(node)
	case *tidbast.SetOprStmt:
		return q.extractSetOpr(node)
	case *tidbast.SetOprSelectList:
		return q.extractSetOprSelectList(node)
	case *tidbast.CreateViewStmt:
		tableSource, err := q.extractTableSourceFromNode(node.Select)
		if err != nil {
			return nil, err
		}
		querySpanResult := tableSource.GetQuerySpanResult()

		if len(node.Cols) == 0 {
			return base.NewPseudoTable(node.ViewName.Name.O, querySpanResult), nil
		}

		if len(node.Cols) != len(querySpanResult) {
			return nil, errors.Errorf("The used SELECT statements have a different number of columns for view %s", node.ViewName.Name.O)
		}

		var columns []base.QuerySpanResult
		for i, item := range querySpanResult {
			columns = append(columns, base.QuerySpanResult{
				Name:          node.Cols[i].L,
				SourceColumns: item.SourceColumns,
			})
		}
		return base.NewPseudoTable(node.ViewName.Name.O, columns), nil
	}
	return nil, nil
}

func (q *querySpanExtractor) extractNonRecursiveCTE(node *tidbast.CommonTableExpression) (*base.PseudoTable, error) {
	tableSource, err := q.extractTableSourceFromNode(node.Query.Query)
	if err != nil {
		return nil, errors.Wrap(err, "failed to extract table source from CTE query")
	}
	querySpanResults := tableSource.GetQuerySpanResult()
	if len(node.ColNameList) > 0 {
		if len(node.ColNameList) != len(querySpanResults) {
			return nil, errors.Errorf("cte table expr has %d columns, but alias has %d columns", len(querySpanResults), len(node.ColNameList))
		}
		for i, name := range node.ColNameList {
			// The column name for MySQL is case insensitive.
			querySpanResults[i].Name = name.L
		}
	}

	return &base.PseudoTable{
		Name:    node.Name.O,
		Columns: querySpanResults,
	}, nil
}

func (q *querySpanExtractor) extractRecursiveCTE(node *tidbast.CommonTableExpression) (*base.PseudoTable, error) {
	switch x := node.Query.Query.(type) {
	case *tidbast.SetOprStmt:
		if x.With != nil {
			previousCteOuterLength := len(q.ctes)
			defer func() {
				q.ctes = q.ctes[:previousCteOuterLength]
			}()
			for _, cte := range x.With.CTEs {
				cteTableSource, err := q.extractCTE(cte)
				if err != nil {
					return nil, err
				}
				q.ctes = append(q.ctes, cteTableSource)
			}

			for i := previousCteOuterLength; i < len(q.ctes); i++ {
				cteTableSource := q.ctes[i]
				if strings.EqualFold(cteTableSource.Name, node.Name.O) {
					// It means this recursive CTE will be hidden by the inner CTE with the same name.
					// In other words, this recursive CTE will be not references by itself sub-query.
					// So, we can build it as non-recursive CTE
					return q.extractNonRecursiveCTE(node)
				}
			}
		}

		initialPart, recursivePart := splitInitialAndRecursivePart(x, node.Name.O)
		if len(initialPart) == 0 {
			return nil, errors.Errorf("Failed to find initial part for recursive common table expression")
		}
		if len(recursivePart) == 0 {
			return q.extractNonRecursiveCTE(node)
		}

		initialTableSource, err := q.extractTableSourceFromNode(&tidbast.SetOprStmt{
			SelectList: &tidbast.SetOprSelectList{
				Selects: initialPart,
			},
		})
		if err != nil {
			return nil, errors.Wrap(err, "failed to extract table source from initial part of recursive CTE")
		}
		initialQuerySpanResult := initialTableSource.GetQuerySpanResult()
		if len(node.ColNameList) > 0 {
			if len(node.ColNameList) != len(initialQuerySpanResult) {
				return nil, errors.Errorf("cte table expr has %d columns, but alias has %d columns", len(initialQuerySpanResult), len(node.ColNameList))
			}
			for i, name := range node.ColNameList {
				// The column name for MySQL is case insensitive.
				initialQuerySpanResult[i].Name = name.L
			}
		}

		cteTableResource := &base.PseudoTable{
			Name:    node.Name.O,
			Columns: initialQuerySpanResult,
		}

		// Compute dependent closures.
		// There are two ways to compute dependent closures:
		//   1. find the all dependent edges, then use graph theory traversal to find the closure.
		//   2. Iterate to simulate the CTE recursive process, each turn check whether the Sensitive state has changed, and stop if no change.
		//
		// Consider the option 2 can easy to implementation, because the simulate process has been written.
		// On the other hand, the number of iterations of the entire algorithm will not exceed the length of fields.
		// In actual use, the length of fields will not be more than 20 generally.
		// So I think it's OK for now.
		// If any performance issues in use, optimize here.
		q.ctes = append(q.ctes, cteTableResource)
		defer func() {
			q.ctes = q.ctes[:len(q.ctes)-1]
		}()
		for {
			recursiveTableSource, err := q.extractTableSourceFromNode(&tidbast.SetOprStmt{
				SelectList: &tidbast.SetOprSelectList{
					Selects: recursivePart,
				},
			})
			if err != nil {
				return nil, errors.Wrap(err, "failed to extract table source from recursive part of recursive CTE")
			}
			recursiveQuerySpanResult := recursiveTableSource.GetQuerySpanResult()
			if len(recursiveQuerySpanResult) != len(initialQuerySpanResult) {
				return nil, errors.Errorf("cte table expr has %d columns, but recursive part has %d columns", len(initialQuerySpanResult), len(recursiveQuerySpanResult))
			}

			changed := false
			for i, spanQueryResult := range recursiveQuerySpanResult {
				newResourceColumns, hasDiff := base.MergeSourceColumnSet(initialQuerySpanResult[i].SourceColumns, spanQueryResult.SourceColumns)
				if hasDiff {
					changed = true
					initialQuerySpanResult[i].SourceColumns = newResourceColumns
				}
			}

			if !changed {
				break
			}
			q.ctes[len(q.ctes)-1].Columns = initialQuerySpanResult
		}
		return cteTableResource, nil
	default:
		return q.extractNonRecursiveCTE(node)
	}
}

func (q *querySpanExtractor) extractCTE(node *tidbast.CommonTableExpression) (*base.PseudoTable, error) {
	if node.IsRecursive {
		return q.extractRecursiveCTE(node)
	}
	return q.extractNonRecursiveCTE(node)
}

func (q *querySpanExtractor) extractSelect(node *tidbast.SelectStmt) (base.TableSource, error) {
	if node.With != nil {
		previousCteOuterLength := len(q.ctes)
		defer func() {
			q.ctes = q.ctes[:previousCteOuterLength]
		}()
		for _, cte := range node.With.CTEs {
			cteTableSource, err := q.extractCTE(cte)
			if err != nil {
				return nil, err
			}
			q.ctes = append(q.ctes, cteTableSource)
		}
	}

	var fromFieldList []base.TableSource
	if node.From != nil {
		tableSource, err := q.extractTableSourceFromNode(node.From.TableRefs)
		if err != nil {
			return nil, errors.Wrap(err, "failed to extract table source from FROM clause")
		}
		previousTableSourcesFromLength := len(q.tableSourcesFrom)
		defer func() {
			q.tableSourcesFrom = q.tableSourcesFrom[:previousTableSourcesFromLength]
		}()
		q.tableSourcesFrom = append(q.tableSourcesFrom, tableSource)
		fromFieldList = append(fromFieldList, tableSource)
	}

	result := new(base.PseudoTable)
	if node.Fields != nil {
		for _, field := range node.Fields.Fields {
			if field.WildCard != nil {
				if field.WildCard.Table.O == "" {
					var columns []base.QuerySpanResult
					for _, tableSource := range fromFieldList {
						columns = append(columns, tableSource.GetQuerySpanResult()...)
					}
					result.Columns = append(result.Columns, columns...)
				} else {
					for _, tableSource := range fromFieldList {
						sameDatabase := (strings.EqualFold(field.WildCard.Schema.O, tableSource.GetDatabaseName()) || (field.WildCard.Schema.O == "" && strings.EqualFold(tableSource.GetDatabaseName(), q.defaultDatabase)))
						sameTable := strings.EqualFold(field.WildCard.Table.O, tableSource.GetTableName())
						find := false
						if sameDatabase && sameTable {
							result.Columns = append(result.Columns, tableSource.GetQuerySpanResult()...)
							find = true
							break
						}
						if !find {
							sources, ok := q.getAllTableColumnSources(field.WildCard.Schema.O, field.WildCard.Table.O)
							if ok {
								result.Columns = append(result.Columns, sources...)
								find = true
							}
						}
						if !find {
							return nil, &base.ResourceNotFoundError{
								Err:      errors.New("failed to find table to calculate asterisk"),
								Database: &field.WildCard.Schema.O,
								Table:    &field.WildCard.Table.O,
							}
						}
					}
				}
			} else {
				sourceColumnSet, err := q.extractSourceColumnSetFromExpression(field.Expr)
				if err != nil {
					return nil, err
				}
				fieldName := extractFieldName(field)
				result.Columns = append(result.Columns, base.QuerySpanResult{
					Name:          fieldName,
					SourceColumns: sourceColumnSet,
				})
			}
		}
	}

	return result, nil
}

func (q *querySpanExtractor) extractSourceColumnSetFromExpressionList(list []tidbast.ExprNode) (base.SourceColumnSet, error) {
	result := make(base.SourceColumnSet)
	for _, node := range list {
		sourceColumnSet, err := q.extractSourceColumnSetFromExpression(node)
		if err != nil {
			return nil, err
		}
		result, _ = base.MergeSourceColumnSet(result, sourceColumnSet)
	}
	return result, nil
}

func (q *querySpanExtractor) extractSourceColumnSetFromExpression(in tidbast.ExprNode) (base.SourceColumnSet, error) {
	if in == nil {
		return base.SourceColumnSet{}, nil
	}

	switch node := in.(type) {
	case *tidbast.ColumnNameExpr:
		database, table, column := node.Name.Schema.O, node.Name.Table.O, node.Name.Name.O
		sources, ok := q.getFieldColumnSource(database, table, column)
		if ok {
			return sources, nil
		}
		// The row handle carries no column data, hence no lineage.
		if q.isRowIDReference(database, table, column) {
			return base.SourceColumnSet{}, nil
		}
		return base.SourceColumnSet{}, &base.ResourceNotFoundError{
			Err:      errors.New("cannot find the column ref"),
			Database: &database,
			Table:    &table,
			Column:   &column,
		}
	case *tidbast.BinaryOperationExpr:
		return q.extractSourceColumnSetFromExpressionList([]tidbast.ExprNode{node.L, node.R})
	case *tidbast.UnaryOperationExpr:
		return q.extractSourceColumnSetFromExpression(node.V)
	case *tidbast.FuncCallExpr:
		return q.extractSourceColumnSetFromExpressionList(node.Args)
	case *tidbast.FuncCastExpr:
		return q.extractSourceColumnSetFromExpression(node.Expr)
	case *tidbast.AggregateFuncExpr:
		return q.extractSourceColumnSetFromExpressionList(node.Args)
	case *tidbast.PatternInExpr:
		nodeList := []tidbast.ExprNode{}
		nodeList = append(nodeList, node.Expr)
		nodeList = append(nodeList, node.List...)
		nodeList = append(nodeList, node.Sel)
		return q.extractSourceColumnSetFromExpressionList(nodeList)
	case *tidbast.PatternLikeOrIlikeExpr:
		return q.extractSourceColumnSetFromExpressionList([]tidbast.ExprNode{node.Expr, node.Pattern})
	case *tidbast.PatternRegexpExpr:
		return q.extractSourceColumnSetFromExpressionList([]tidbast.ExprNode{node.Expr, node.Pattern})
	case *tidbast.SubqueryExpr:
		// Subquery in SELECT fields is special.
		// It can be the non-associated or associated subquery.
		// For associated subquery, we should set the fromFieldList as the outerSchemaInfo.
		// So that the subquery can access the outer schema.
		// The reason for new q is that we still need the current fromFieldList, overriding it is not expected.
		subqueryExtractor := &querySpanExtractor{
			ctx:                 q.ctx,
			defaultDatabase:     q.defaultDatabase,
			metaCache:           q.metaCache,
			gCtx:                q.gCtx,
			ctes:                q.ctes,
			outerTableSources:   append(q.outerTableSources, q.tableSourcesFrom...),
			tableSourcesFrom:    []base.TableSource{},
			baseTableSources:    q.baseTableSources,
			viewResolutionStack: cloneViewResolutionStack(q.viewResolutionStack),
		}
		tableSource, err := subqueryExtractor.extractTableSourceFromNode(node.Query)
		if err != nil {
			return base.SourceColumnSet{}, errors.Wrap(err, "failed to extract table source from subquery")
		}
		spanResult := tableSource.GetQuerySpanResult()
		sourceColumnSet := base.SourceColumnSet{}

		for _, field := range spanResult {
			sourceColumnSet, _ = base.MergeSourceColumnSet(sourceColumnSet, field.SourceColumns)
		}
		return sourceColumnSet, nil
	case *tidbast.CompareSubqueryExpr:
		return q.extractSourceColumnSetFromExpressionList([]tidbast.ExprNode{node.L, node.R})
	case *tidbast.ExistsSubqueryExpr:
		return q.extractSourceColumnSetFromExpression(node.Sel)
	case *tidbast.IsNullExpr:
		return q.extractSourceColumnSetFromExpression(node.Expr)
	case *tidbast.IsTruthExpr:
		return q.extractSourceColumnSetFromExpression(node.Expr)
	case *tidbast.BetweenExpr:
		return q.extractSourceColumnSetFromExpressionList([]tidbast.ExprNode{node.Expr, node.Left, node.Right})
	case *tidbast.CaseExpr:
		nodeList := []tidbast.ExprNode{}
		nodeList = append(nodeList, node.Value)
		nodeList = append(nodeList, node.ElseClause)
		for _, whenClause := range node.WhenClauses {
			nodeList = append(nodeList, whenClause.Expr)
			nodeList = append(nodeList, whenClause.Result)
		}
		return q.extractSourceColumnSetFromExpressionList(nodeList)
	case *tidbast.ParenthesesExpr:
		return q.extractSourceColumnSetFromExpression(node.Expr)
	case *tidbast.RowExpr:
		return q.extractSourceColumnSetFromExpressionList(node.Values)
	case *tidbast.VariableExpr:
		return q.extractSourceColumnSetFromExpression(node.Value)
	case *tidbast.PositionExpr:
		return q.extractSourceColumnSetFromExpression(node.P)
	case *tidbast.MatchAgainst:
		return q.extractSourceColumnSetFromExpression(node.Against)
	case *tidbast.WindowFuncExpr:
		return q.extractSourceColumnSetFromExpressionList(node.Args)
	case *tidbast.ValuesExpr,
		*tidbast.TableNameExpr,
		*tidbast.MaxValueExpr,
		*tidbast.SetCollationExpr,
		*tidbast.TrimDirectionExpr,
		*tidbast.TimeUnitExpr,
		*tidbast.GetFormatSelectorExpr,
		*tidbast.DefaultExpr:
		// No expression need to extract.
	default:
	}
	return base.SourceColumnSet{}, nil
}

func (q *querySpanExtractor) getAllTableColumnSources(databaseName, tableName string) ([]base.QuerySpanResult, bool) {
	findInTableSource := func(tableSource base.TableSource) ([]base.QuerySpanResult, bool) {
		if databaseName != "" && !strings.EqualFold(databaseName, tableSource.GetDatabaseName()) {
			return nil, false
		}
		if databaseName == "" && tableSource.GetDatabaseName() != "" && !strings.EqualFold(tableSource.GetDatabaseName(), q.defaultDatabase) {
			return nil, false
		}
		if tableName != "" && !strings.EqualFold(tableName, tableSource.GetTableName()) {
			return nil, false
		}
		// If the table name is empty, we should check if there are ambiguous fields,
		// but we delegate this responsibility to the db-server, we do the fail-open strategy here.

		return tableSource.GetQuerySpanResult(), true
	}

	// One sub-query may have multi-outer schemas and the multi-outer schemas can use the same name, such as:
	//
	//  select (
	//    select (
	//      select max(a) > x1.a from t
	//    )
	//    from t1 as x1
	//    limit 1
	//  )
	//  from t as x1;
	//
	// This query has two tables can be called `x1`, and the expression x1.a uses the closer x1 table.
	// This is the reason we loop the slice in reversed order.
	//
	// The statement's own FROM is searched first, as in candidateTableSources.

	for _, tableSource := range q.tableSourcesFrom {
		if sourceColumnSet, ok := findInTableSource(tableSource); ok {
			return sourceColumnSet, true
		}
	}

	for i := len(q.outerTableSources) - 1; i >= 0; i-- {
		tableSource := q.outerTableSources[i]
		if sourceColumnSet, ok := findInTableSource(tableSource); ok {
			return sourceColumnSet, true
		}
	}

	return nil, false
}

func (q *querySpanExtractor) getFieldColumnSource(databaseName, tableName, fieldName string) (base.SourceColumnSet, bool) {
	// If the table name is empty, we should check if there are ambiguous fields,
	// but we delegate this responsibility to the db-server, we do the fail-open strategy here.
	for _, tableSource := range q.candidateTableSources(databaseName, tableName) {
		for _, field := range tableSource.GetQuerySpanResult() {
			if strings.EqualFold(field.Name, fieldName) {
				return field.SourceColumns, true
			}
		}
	}
	return base.SourceColumnSet{}, false
}

// isRowIDReference reports whether an unresolved column reference is the row
// handle. Every table source it can bind to must be built from base tables,
// where TiDB rejects this name for a real column (ERROR 1166). A view or
// subquery can own one that cached metadata lacks, and only the not-found
// error triggers the resync that finds it: on TiDB 8.5,
// `SELECT _tidb_rowid FROM clustered_tbl, such_view` reads the view's column.
func (q *querySpanExtractor) isRowIDReference(databaseName, tableName, fieldName string) bool {
	if !strings.EqualFold(fieldName, rowIDColumnName) {
		return false
	}
	candidates := q.candidateTableSources(databaseName, tableName)
	for _, tableSource := range candidates {
		if !q.isBaseTableSource(tableSource) {
			return false
		}
	}
	return len(candidates) > 0
}

func (q *querySpanExtractor) isBaseTableSource(tableSource base.TableSource) bool {
	if _, ok := tableSource.(*base.PhysicalTable); ok {
		return true
	}
	return q.baseTableSources[tableSource]
}

// candidateTableSources returns the table sources a column reference with the
// given qualifiers can bind to, in resolution order.
func (q *querySpanExtractor) candidateTableSources(databaseName, tableName string) []base.TableSource {
	var candidates []base.TableSource
	appendIfMatch := func(tableSource base.TableSource) {
		if databaseName != "" && !strings.EqualFold(databaseName, tableSource.GetDatabaseName()) {
			return
		}
		if tableName != "" && !strings.EqualFold(tableName, tableSource.GetTableName()) {
			return
		}
		candidates = append(candidates, tableSource)
	}

	// One sub-query may have multi-outer schemas and the multi-outer schemas can use the same name, such as:
	//
	//  select (
	//    select (
	//      select max(a) > x1.a from t
	//    )
	//    from t1 as x1
	//    limit 1
	//  )
	//  from t as x1;
	//
	// This query has two tables can be called `x1`, and the expression x1.a uses the closer x1 table.
	// This is the reason we loop the slice in reversed order.
	//
	// The statement's own FROM is closer than any enclosing query, so it is
	// searched first. Otherwise a column the subquery reads is traced to a
	// same-named column of an outer table.

	for _, tableSource := range q.tableSourcesFrom {
		appendIfMatch(tableSource)
	}
	for i := len(q.outerTableSources) - 1; i >= 0; i-- {
		appendIfMatch(q.outerTableSources[i])
	}
	return candidates
}

func (q *querySpanExtractor) extractJoin(node *tidbast.Join) (base.TableSource, error) {
	if node.Right == nil {
		// This case is no Join.
		return q.extractTableSourceFromNode(node.Left)
	}
	leftTableSource, err := q.extractTableSourceFromNode(node.Left)
	if err != nil {
		return nil, errors.Wrap(err, "failed to extract table source from left table")
	}
	q.tableSourcesFrom = append(q.tableSourcesFrom, leftTableSource)
	rightTableSource, err := q.extractTableSourceFromNode(node.Right)
	if err != nil {
		return nil, errors.Wrap(err, "failed to extract table source from right table")
	}
	q.tableSourcesFrom = append(q.tableSourcesFrom, rightTableSource)
	q.tableSourcesFrom = append(q.tableSourcesFrom, rightTableSource)
	joined := q.mergeJoinTableSource(node, leftTableSource, rightTableSource)
	if q.isBaseTableSource(leftTableSource) && q.isBaseTableSource(rightTableSource) {
		q.baseTableSources[joined] = true
	}
	return joined, nil
}

func (*querySpanExtractor) mergeJoinTableSource(node *tidbast.Join, leftTableSource, rightTableSource base.TableSource) *base.PseudoTable {
	leftSpanResult, rightSpanResult := leftTableSource.GetQuerySpanResult(), rightTableSource.GetQuerySpanResult()

	result := new(base.PseudoTable)

	leftSpanResultIdx, rightSpanResultIdx := make(map[string]int), make(map[string]int)
	for i, spanResult := range leftSpanResult {
		// Column name in TiDB is case insensitive.
		leftSpanResultIdx[strings.ToLower(spanResult.Name)] = i
	}
	for i, spanResult := range rightSpanResult {
		// Column name in TiDB is case insensitive.
		rightSpanResultIdx[strings.ToLower(spanResult.Name)] = i
	}

	if node.NaturalJoin {
		// Natural Join will merge the same column name field.
		for _, spanResult := range leftSpanResult {
			if rightIdx, exists := rightSpanResultIdx[strings.ToLower(spanResult.Name)]; exists {
				spanResult.SourceColumns, _ = base.MergeSourceColumnSet(spanResult.SourceColumns, rightSpanResult[rightIdx].SourceColumns)
			}
			result.Columns = append(result.Columns, spanResult)
		}
		for _, spanResult := range rightSpanResult {
			if _, exists := leftSpanResultIdx[strings.ToLower(spanResult.Name)]; !exists {
				result.Columns = append(result.Columns, spanResult)
			}
		}
	} else {
		if len(node.Using) != 0 {
			// ... JOIN ... USING (...) will merge the column in USING.
			usingMap := make(map[string]bool)
			for _, column := range node.Using {
				// Column name in TiDB is case insensitive.
				usingMap[column.Name.L] = true
			}

			for _, spanResult := range leftSpanResult {
				_, existsInUsingMap := usingMap[strings.ToLower(spanResult.Name)]
				rightIdx, existsInRightField := rightSpanResultIdx[strings.ToLower(spanResult.Name)]
				// Merge column in USING.
				if existsInUsingMap && existsInRightField {
					rightSpanResult[rightIdx].SourceColumns, _ = base.MergeSourceColumnSet(spanResult.SourceColumns, rightSpanResult[rightIdx].SourceColumns)
				}
				result.Columns = append(result.Columns, spanResult)
			}

			for _, spanResult := range rightSpanResult {
				_, existsInUsing := usingMap[strings.ToLower(spanResult.Name)]
				_, existsInLeftField := leftSpanResultIdx[strings.ToLower(spanResult.Name)]
				if existsInUsing && existsInLeftField {
					continue
				}
				result.Columns = append(result.Columns, spanResult)
			}
		} else {
			result.Columns = append(result.Columns, leftSpanResult...)
			result.Columns = append(result.Columns, rightSpanResult...)
		}
	}

	return result
}

func (q *querySpanExtractor) extractTableSource(node *tidbast.TableSource) (base.TableSource, error) {
	tableSource, err := q.extractTableSourceFromNode(node.Source)
	if err != nil {
		return nil, err
	}
	if node.AsName.O != "" {
		aliased := base.NewPseudoTable(node.AsName.O, tableSource.GetQuerySpanResult())
		if q.isBaseTableSource(tableSource) {
			q.baseTableSources[aliased] = true
		}
		return aliased, nil
	}
	return tableSource, nil
}

func (q *querySpanExtractor) findTableSchema(databaseName string, tableName string) (base.TableSource, error) {
	// Each CTE name in one WITH clause must be unique, but we can use the same name in the different level CTE, such as:
	//
	//  with tt2 as (
	//    with tt2 as (select * from t)
	//    select max(a) from tt2)
	//  select * from tt2
	//
	// This query has two CTE can be called `tt2`, and the FROM clause 'from tt2' uses the closer tt2 CTE.
	// This is the reason we loop the slice in reversed order.
	if databaseName == "" {
		for i := len(q.ctes) - 1; i >= 0; i-- {
			cte := q.ctes[i]
			// TiDB fixes lower_case_table_names at 2, so `FROM c` reads CTE `C`
			// even when a base table `c` exists. Matching by case would trace
			// the CTE's columns to that table and apply its masking policy.
			if strings.EqualFold(cte.Name, tableName) {
				return cte, nil
			}
		}
	}

	if databaseName == "" {
		databaseName = q.defaultDatabase
	}

	dbMetadata, err := q.getDatabaseMetadata(databaseName)
	if err != nil {
		return nil, errors.Wrapf(err, "failed to get database metadata for %q", databaseName)
	}
	if dbMetadata == nil {
		return nil, &base.ResourceNotFoundError{
			Database: &databaseName,
		}
	}
	emptySchema := ""
	schema := dbMetadata.GetSchemaMetadata("")
	if schema == nil {
		return nil, &base.ResourceNotFoundError{
			Database: &databaseName,
			Schema:   &emptySchema,
		}
	}
	lowerTableName := strings.ToLower(tableName)
	for _, table := range schema.ListTableNames() {
		if lowerTableName == strings.ToLower(table) {
			var columns []string
			tableMeta := schema.GetTable(table)
			if tableMeta != nil {
				for _, column := range tableMeta.GetProto().GetColumns() {
					columns = append(columns, column.Name)
				}
				return &base.PhysicalTable{
					Database: databaseName,
					Name:     tableMeta.GetProto().Name,
					Columns:  columns,
				}, nil
			}
		}
	}

	for _, view := range schema.ListViewNames() {
		if lowerTableName == strings.ToLower(view) {
			viewMeta := schema.GetView(view)
			if viewMeta != nil {
				columns, err := q.getColumnsForView(databaseName, viewMeta.Name, viewMeta.Definition)
				if err != nil {
					return nil, err
				}
				return &base.PhysicalView{
					Database: databaseName,
					Name:     viewMeta.Name,
					Columns:  columns,
				}, nil
			}
		}
	}

	return nil, &base.ResourceNotFoundError{
		Database: &databaseName,
		Schema:   &emptySchema,
		Table:    &tableName,
	}
}

func (q *querySpanExtractor) getColumnsForView(databaseName, viewName, definition string) ([]base.QuerySpanResult, error) {
	key := viewResolutionKey(databaseName, viewName)
	if q.viewResolutionStack[key] {
		return nil, errors.Errorf("cyclic view reference detected while resolving %q", viewName)
	}
	newQ := newQuerySpanExtractor(q.defaultDatabase, q.gCtx)
	newQ.viewResolutionStack = cloneViewResolutionStack(q.viewResolutionStack)
	newQ.viewResolutionStack[key] = true
	span, err := newQ.getQuerySpan(q.ctx, definition)
	if err != nil {
		return nil, err
	}
	if span.NotFoundError != nil {
		return nil, span.NotFoundError
	}
	return span.Results, nil
}

func viewResolutionKey(databaseName, viewName string) string {
	return databaseName + "\x00" + viewName
}

func cloneViewResolutionStack(in map[string]bool) map[string]bool {
	out := make(map[string]bool, len(in))
	for k, v := range in {
		out[k] = v
	}
	return out
}

func (q *querySpanExtractor) getDatabaseMetadata(databaseName string) (*model.DatabaseMetadata, error) {
	if meta, ok := q.metaCache[databaseName]; ok {
		return meta, nil
	}
	_, meta, err := q.gCtx.GetDatabaseMetadataFunc(q.ctx, q.gCtx.InstanceID, databaseName)
	if err != nil {
		return nil, err
	}
	q.metaCache[databaseName] = meta
	return meta, nil
}

func (q *querySpanExtractor) extractTableName(node *tidbast.TableName) (base.TableSource, error) {
	return q.findTableSchema(node.Schema.O, node.Name.O)
}

func (q *querySpanExtractor) extractSetOpr(node *tidbast.SetOprStmt) (base.TableSource, error) {
	if node.With != nil {
		previousCteOuterLength := len(q.ctes)
		defer func() {
			q.ctes = q.ctes[:previousCteOuterLength]
		}()
		for _, cte := range node.With.CTEs {
			cteTableSource, err := q.extractCTE(cte)
			if err != nil {
				return nil, err
			}
			q.ctes = append(q.ctes, cteTableSource)
		}
	}

	return q.extractTableSourceFromNode(node.SelectList)
}

func mergeTableSource(left, right base.TableSource) (base.TableSource, error) {
	leftSpanResult, rightSpanResult := left.GetQuerySpanResult(), right.GetQuerySpanResult()

	if len(leftSpanResult) != len(rightSpanResult) {
		return nil, errors.Errorf("left table source has %d columns, but right table source has %d columns", len(leftSpanResult), len(rightSpanResult))
	}

	var result []base.QuerySpanResult
	for i, leftResult := range leftSpanResult {
		rightResult := rightSpanResult[i]
		newResourceColumns, _ := base.MergeSourceColumnSet(leftResult.SourceColumns, rightResult.SourceColumns)
		result = append(result, base.QuerySpanResult{
			Name:          leftResult.Name,
			SourceColumns: newResourceColumns,
		})
	}
	return &base.PseudoTable{
		Name:    "",
		Columns: result,
	}, nil
}

func (q *querySpanExtractor) extractSetOprSelectList(node *tidbast.SetOprSelectList) (base.TableSource, error) {
	if node.With != nil {
		previousCteOuterLength := len(q.ctes)
		defer func() {
			q.ctes = q.ctes[:previousCteOuterLength]
		}()
		for _, cte := range node.With.CTEs {
			cteTableSource, err := q.extractCTE(cte)
			if err != nil {
				return nil, err
			}
			q.ctes = append(q.ctes, cteTableSource)
		}
	}

	var result base.TableSource
	for i, selectStmt := range node.Selects {
		tableSource, err := q.extractTableSourceFromNode(selectStmt)
		if err != nil {
			return nil, err
		}
		if i == 0 {
			result = tableSource
		} else {
			result, err = mergeTableSource(result, tableSource)
			if err != nil {
				return nil, errors.Wrapf(err, "failed to merge table source for %dth select statement", i)
			}
		}
	}
	return result, nil
}