algorithm

package
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 13, 2026 License: Apache-2.0 Imports: 2 Imported by: 0

Documentation

Overview

Package algorithm holds the parts of lineage analysis that do not depend on the SQL dialect: how a lineage edge is identified for deduplication, how a row-set predicate is attributed to the scope whose rows it decides, and how the arms of a set operation merge. Every dialect analyzer keeps its own syntax tree walk and AST adaptation on top of it.

The split exists because the same mechanism written once per dialect did drift apart: the MySQL family and StarRocks were still dropping a real relation's lineage when a CTE shared its name, losing one of two transformations that reached the same target column, and attributing an unreferenced CTE's WHERE to the statement's result — all three of which PostgreSQL had already fixed in its own copy of the same code.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ArmChain 

func ArmChain(chain []model.Transformation, op model.Transformation) []model.Transformation

ArmChain appends the operation that combines a subtree to the chain of operations already combining it, outermost first.

The chain is kept because a set-operation tree does not bind flatly: INTERSECT binds tighter than UNION and EXCEPT, so `a UNION b INTERSECT c` groups as `a UNION (b INTERSECT c)`. Flattening the tree without the chain labelled every arm with the outermost operation and lost the inner one.

A left-deep tree repeats the same operation (`a UNION b UNION c` nests as `(a UNION b) UNION c`), and that repetition describes one union of three arms rather than a stack of them, so a step already on the end of the chain is not recorded twice.

func FlattenTempSourceLineage 

func FlattenTempSourceLineage(newEdge NewEdgeFunc, sp *scope.Scope, relation *scope.TableRef, columnName, targetTable, targetColumn string, transform []model.Transformation, lineage *[]model.ColumnRelation) bool

FlattenTempSourceLineage appends a query-local relation's lineage, resolved down to stored relations, to a temporary relation's own lineage. It reports whether the source was a query-local relation and was therefore handled.

func FlattenTempSources 

func FlattenTempSources(sp *scope.Scope, ref scope.ColumnRef, relation *scope.TableRef, transform []model.Transformation) []scope.ColumnSource

FlattenTempSources replaces a source that resolved to a query-local relation with the stored relations that relation's own lineage came from, combining the transformations along the way. A query-local relation's name is an alias that exists only in the scope the query wrote it in, so a reference carried into an enclosing scope must not keep it: resolving the alias again there can bind to an unrelated real relation that happens to share the name.

func MergeSetOpColumns 

func MergeSetOpColumns(baseScope *scope.Scope, armColumns [][]scope.OutputColumn, armTransforms [][]model.Transformation)

MergeSetOpColumns merges output columns from multiple set-operation arms positionally, replacing the base scope's columns with the merged ones, and records the operations that produced each arm as the leading transformations of that arm's own sources. That leading transformation is what makes the relation type union/intersect/except instead of direct.

The transformations stay attached to the source they came from: one transformation for the whole merged column would attribute the first arm's expression to every other arm's sources, which is lineage the query does not have.

The first arm's columns are expected to be the base scope's own; the merged list replaces them.

func ResolveOutputColumns 

func ResolveOutputColumns(sp *scope.Scope, cols []scope.OutputColumn) []scope.OutputColumn

ResolveOutputColumns resolves each output column's source references against the scope they were collected in, marking them resolved and replacing a query-local relation with the stored relations behind it. Without this, an arm's reference would be resolved again in the enclosing scope, where the arm's tables no longer exist, and the arm's lineage would be silently dropped.

func TraceThroughTableLineage 

func TraceThroughTableLineage(newEdge NewEdgeFunc, add AddEdgeFunc, tableRef *scope.TableRef, columnName, outputAlias string, transform []model.Transformation)

TraceThroughTableLineage records a query-local relation's own lineage against the statement's result rows, combining each edge's transformations with the ones the reference adds.

func TraceThroughTableLineageToTarget 

func TraceThroughTableLineageToTarget(newEdge NewEdgeFunc, add AddEdgeFunc, tableRef *scope.TableRef, columnName, targetQualifier, targetTable, targetColumn string, transform []model.Transformation)

TraceThroughTableLineageToTarget records a query-local relation's own lineage against a specific real target table, so an edge never names a CTE or a derived-table alias as if it were a stored object.

Types

type AddEdgeFunc 

type AddEdgeFunc func(model.ColumnRelation)

AddEdgeFunc records one edge in the graph being built.

type Diagnostics 

type Diagnostics struct {
	// contains filtered or unexported fields
}

Diagnostics collects what an analysis could not represent. A caller records the notes beside the edges it did find — the runner stores them on the lineage version — which is what makes a partial result distinguishable from a complete one: the edges alone cannot say whether an edge is missing because the SQL never had it or because the analyzer dropped it.

A note is a model.Diagnostic rather than a sentence, so a caller can act on the category and point at the reference instead of re-reading its own message.

func NewDiagnostics 

func NewDiagnostics() *Diagnostics

NewDiagnostics creates an empty note store.

func (*Diagnostics) Ambiguous 

func (d *Diagnostics) Ambiguous(clause string, ref scope.ColumnRef)

Ambiguous reports a reference a single-valued position could not choose between, which is an unqualified name several relations in scope own.

func (*Diagnostics) AppendTo 

func (d *Diagnostics) AppendTo(reasons []string) []string

AppendTo adds the notes to a caller's own failure reasons, so a statement that fails whole does not hide what the analysis learned before it failed.

func (*Diagnostics) CatalogUnavailable 

func (d *Diagnostics) CatalogUnavailable(relation string, err error)

CatalogUnavailable reports a metadata lookup that failed. The analysis carries on with the relation's columns unknown, which is what makes a wildcard fall back to a bulk edge, so the note is what keeps a catalog outage from reading as a complete analysis: the edges of a degraded result and of a good one look alike.

func (*Diagnostics) NotModelled 

func (d *Diagnostics) NotModelled(subject, detail string)

NotModelled reports a statement or clause shape the analyzer does not model. detail carries the cause when the shape needs one — the parser defect behind a skipped clause — and is empty for a shape that speaks for itself.

func (*Diagnostics) Notes 

func (d *Diagnostics) Notes() ([]model.Diagnostic, int)

Notes returns the notes in the order they were first reported, and how many the limit left out. It returns nil when nothing was dropped, which is the signal a caller reads as "this analysis is complete".

func (*Diagnostics) Unresolved 

func (d *Diagnostics) Unresolved(clause string, ref scope.ColumnRef)

Unresolved reports a reference that resolved to nothing, together with the clause it was written in.

func (*Diagnostics) UnresolvedQualifier 

func (d *Diagnostics) UnresolvedQualifier(clause, qualifier string)

UnresolvedQualifier reports a wildcard whose qualifier names no relation in scope. There is no column to name, so the note names the qualifier.

type EdgeSet 

type EdgeSet struct {
	// contains filtered or unexported fields
}

EdgeSet accumulates column lineage edges, dropping duplicates.

An edge's identity is its endpoints together with the transformations that produced it. The endpoints alone are not enough: one column can reach the same target column through two different expressions (`SELECT x + 1 AS a, x + 2 AS a FROM t`), and a column can both be projected into a target and decide which rows reach it.

Endpoints are compared as identifier values and transformations are compared field by field, never through a rendering of either. Joining the fields into a string to get one comparable key cannot tell an identifier that contains the separator from two identifiers around it.

func NewEdgeSet 

func NewEdgeSet() *EdgeSet

NewEdgeSet creates an empty edge set.

func (*EdgeSet) Add 

func (s *EdgeSet) Add(relation model.ColumnRelation)

Add records one edge unless an edge with the same identity is already there.

func (*EdgeSet) Edges 

func (s *EdgeSet) Edges() []model.ColumnRelation

Edges returns the distinct edges in the order they were added.

func (*EdgeSet) Len 

func (s *EdgeSet) Len() int

Len returns the number of distinct edges recorded.

type Emitter 

type Emitter struct {
	// Trace expands a reference that resolved to a query-local relation, so the
	// edge names the stored relation behind it rather than the CTE or alias.
	Trace func(relation *scope.TableRef, column, targetQualifier, targetTable, targetColumn string, transform []model.Transformation)
	// AddEdge records one edge.
	AddEdge func(model.ColumnRelation)
	// NewEdge builds an edge whose source is a stored relation.
	NewEdge NewEdgeFunc
}

Emitter receives the edges a predicate influence produces. Tracing a query-local relation has to go through the dialect, because only it knows the lineage recorded for that relation.

type Influence 

type Influence struct {
	// Relation is the query-local relation the column resolved to, whose lineage
	// is traced instead. It is nil when the column resolved to a stored relation,
	// which Key then names.
	Relation *scope.TableRef
	Column   string
	// Key names the stored relation the column resolved to.
	Key       PredicateKey
	Transform model.Transformation
}

Influence is one column a WHERE, HAVING or ON predicate depends on, together with the clause that makes it an influence.

type Influences 

type Influences struct {
	// contains filtered or unexported fields
}

Influences holds the row-set influences collected while a scope was current. They belong to the rows that scope produces and are inherited by whatever consumes them, so a scope whose rows reach no output cannot influence the statement's result.

The influences used to sit in one statement-wide list that the last emitter drained. That attributed an unreferenced CTE's WHERE to a result it never reached — `WITH unused AS (SELECT id FROM t WHERE x = 1) SELECT 1` recorded `t.x -> __result__` — and silently dropped an UPDATE's WHERE, which nothing consumed.

func NewInfluences 

func NewInfluences(notes *Diagnostics) *Influences

NewInfluences creates an empty influence store. A nil notes store drops unresolvable predicate columns silently, which is what a caller that only wants the edges asks for.

func (*Influences) Add 

func (s *Influences) Add(sp *scope.Scope, influence Influence)

Add records one influence against the scope whose rows it decides.

func (*Influences) BindCTE 

func (s *Influences) BindCTE(cte *scope.CTEDefinition, from *scope.Scope)

BindCTE holds the influences a CTE body produced against the definition they belong to. They reach the query only if it references the CTE.

func (*Influences) Emit 

func (s *Influences) Emit(sp *scope.Scope, targetQualifier, targetTable string, isTemp bool, e Emitter)

Emit adds one edge per predicate column of sp to the rows the statement produces, and forgets them. The target column is empty: a predicate decides which rows are emitted, not the value of any one column.

func (*Influences) Inherit 

func (s *Influences) Inherit(from, to *scope.Scope)

Inherit moves the influences collected in from into to. A construct that consumes from's rows carries the predicates that shaped them, so a derived table or an expression subquery passes its WHERE to the query that reads it. A scope whose rows are never consumed keeps its influences instead: they are dropped with the statement rather than attributed to a result they do not reach, which is what an unreferenced CTE is.

func (*Influences) InheritCTE 

func (s *Influences) InheritCTE(sp *scope.Scope, cte *scope.CTEDefinition)

InheritCTE hands a referenced CTE's influences to the scope that reads it. The entry is kept rather than moved because one CTE can be referenced from several places, and the emitted edges are deduplicated anyway.

func (*Influences) Resolve 

func (s *Influences) Resolve(sp *scope.Scope, ref scope.ColumnRef, transform model.Transformation, resolveAliases bool)

Resolve records one predicate column. An unresolvable column is dropped, the same way an unresolvable source column is, so a predicate never invents a relation.

A select-list alias is not a column of any relation. The clause influences the rows the aggregate behind the alias produced, so the influence belongs to that output column's own sources; resolveAliases is set for a clause that may name one, as HAVING does.

type NewEdgeFunc 

type NewEdgeFunc func(fromQualifier, fromTable, fromField, toQualifier, toTable, toField string, transform []model.Transformation, isTemp bool) model.ColumnRelation

NewEdgeFunc builds an edge from its endpoints. The dialects differ in where they record a reference's qualifier — the MySQL family and StarRocks name a database, PostgreSQL a schema — so each one passes the constructor it records with.

type PredicateKey 

type PredicateKey struct {
	// Qualifier is the database (MySQL family, StarRocks) or schema (PostgreSQL)
	// the relation was named with, and is empty when the query does not name one.
	Qualifier string
	Table     string
	Column    string
}

PredicateKey identifies a stored relation's column, so a column used by several clauses collapses to the one edge the deduplication keeps.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.