Database governance built for humans and agents — controlling changes and access across every major database.
Go cicddata-governancedata-maskingdata-securitydatabase-accessdatabase-governancedevopsdevsecopsflywaygitopsliquibasemongodbmysqloraclepostgresqlschema-migrationssecuritysql-clientsqlservertidb
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
}