physical

package
v3.6.21 Latest Latest
Warning

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

Go to latest
Published: Nov 12, 2026 License: AGPL-3.0 Imports: 15 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func BuildTree

func BuildTree(p *Plan, n Node) *tree.Node

BuildTree converts a physical plan node and its children into a tree structure that can be used for visualization and debugging purposes.

func PrintAsTree

func PrintAsTree(p *Plan) string

PrintAsTree converts a physical Plan into a human-readable tree representation. It processes each root node in the plan graph, and returns the combined string output of all trees joined by newlines.

func WriteMermaidFormat

func WriteMermaidFormat(w io.Writer, p *Plan)

Types

type BinaryExpr

type BinaryExpr struct {
	Left, Right Expression
	Op          types.BinaryOp
}

BinaryExpr is an expression that implements the BinaryExpression interface.

func (*BinaryExpr) Clone

func (e *BinaryExpr) Clone() Expression

Clone returns a copy of the BinaryExpr.

func (*BinaryExpr) String

func (e *BinaryExpr) String() string

func (*BinaryExpr) Type

func (*BinaryExpr) Type() ExpressionType

ID returns the type of the BinaryExpr.

type BinaryExpression

type BinaryExpression interface {
	Expression
	// contains filtered or unexported methods
}

BinaryExpression is the common interface for all binary expressions in a physical plan.

type Catalog

type Catalog interface {
	// ResolveShardDescriptors returns a list of
	// FilteredShardDescriptor objects, which each include:
	// a data object path, a list of stream IDs for
	// each data object path, a list of sections for
	// each data object path, and a time range.
	ResolveShardDescriptors(Expression, time.Time, time.Time) ([]FilteredShardDescriptor, error)
	ResolveShardDescriptorsWithShard(Expression, []Expression, ShardInfo, time.Time, time.Time) ([]FilteredShardDescriptor, error)
}

Catalog is an interface that provides methods for interacting with storage metadata. In traditional database systems there are system tables providing this information (e.g. pg_catalog, ...) whereas in Loki there is the Metastore.

type ColumnCompat

type ColumnCompat struct {

	// TODO(chaudum): These fields are poorly named. Come up with more descriptive names.
	Source      types.ColumnType // column type of the column that may colide with columns of the same name but with collision type
	Destination types.ColumnType // column type of the generated _extracted column (should be same as source)
	Collision   types.ColumnType // column type of the column that a source type column may collide with
	// contains filtered or unexported fields
}

ColumnCompat represents a compactibilty operation in the physical plan that moves a values from a conflicting metadata column with a label column into a new column suffixed with `_extracted`.

func (*ColumnCompat) Accept

func (m *ColumnCompat) Accept(v Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*ColumnCompat) Clone

func (m *ColumnCompat) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*ColumnCompat) ID

func (m *ColumnCompat) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*ColumnCompat) Type

func (m *ColumnCompat) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type ColumnExpr

type ColumnExpr struct {
	Ref types.ColumnRef
}

ColumnExpr is an expression that implements the ColumnExpr interface.

func (*ColumnExpr) Clone

func (e *ColumnExpr) Clone() Expression

Clone returns a copy of the ColumnExpr.

func (*ColumnExpr) String

func (e *ColumnExpr) String() string

String returns the string representation of the column expression. It contains of the name of the column and its type, joined by a dot (`.`).

func (*ColumnExpr) Type

func (e *ColumnExpr) Type() ExpressionType

ID returns the type of the ColumnExpr.

type ColumnExpression

type ColumnExpression interface {
	Expression
	// contains filtered or unexported methods
}

ColumnExpression is the common interface for all column expressions in a physical plan.

type Context

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

Context carries planning state that needs to be propagated down the plan tree. This enables each branch to have independent context, which is essential for complex queries: - Binary operations with different [$range] intervals, offsets or @timestamp.

Propagation: - Each process() method passes context to children. - Context can be cloned and modified by nodes (ex: RangeAggregation sets rangeInterval) that gets inherited by all descendants.

func NewContext

func NewContext(from, through time.Time) *Context

func (*Context) Clone

func (pc *Context) Clone() *Context

func (*Context) GetResolveTimeRange

func (pc *Context) GetResolveTimeRange() (from, through time.Time)

func (*Context) WithDirection

func (pc *Context) WithDirection(direction SortOrder) *Context

func (*Context) WithRangeInterval

func (pc *Context) WithRangeInterval(rangeInterval time.Duration) *Context

func (*Context) WithTimeRange

func (pc *Context) WithTimeRange(from, through time.Time) *Context

type DataObjLocation

type DataObjLocation string

DataObjLocation is a string that uniquely indentifies a data object location in object storage.

type DataObjScan

type DataObjScan struct {

	// Location is the unique name of the data object that is used as source for
	// reading streams.
	Location DataObjLocation
	// Section is the section index inside the data object to scan.
	Section int
	// StreamIDs is a set of stream IDs inside the data object. These IDs are
	// only unique in the context of a single data object.
	StreamIDs []int64
	// Projections are used to limit the columns that are read to the ones
	// provided in the column expressions to reduce the amount of data that needs
	// to be processed.
	Projections []ColumnExpression
	// Predicates are used to filter rows to reduce the amount of rows that are
	// returned. Predicates would almost always contain a time range filter to
	// only read the logs for the requested time range.
	Predicates []Expression
	// contains filtered or unexported fields
}

DataObjScan represents a physical plan operation for reading data objects. It contains information about the object location, stream IDs, projections, predicates for reading data from a data object.

func (*DataObjScan) Accept

func (s *DataObjScan) Accept(v Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*DataObjScan) Clone

func (s *DataObjScan) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*DataObjScan) ID

func (s *DataObjScan) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*DataObjScan) Type

func (*DataObjScan) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type Expression

type Expression interface {
	fmt.Stringer
	Clone() Expression
	Type() ExpressionType
	// contains filtered or unexported methods
}

Expression is the common interface for all expressions in a physical plan.

type ExpressionType

type ExpressionType uint32

ExpressionType represents the type of expression in the physical plan.

const (
	ExprTypeUnary ExpressionType
	ExprTypeBinary
	ExprTypeLiteral
	ExprTypeColumn
)

func (ExpressionType) String

func (t ExpressionType) String() string

String returns the string representation of the ExpressionType.

type Filter

type Filter struct {

	// Predicates is a list of filter expressions that are used to discard not
	// matching rows during execution.
	Predicates []Expression
	// contains filtered or unexported fields
}

Filter represents a filtering operation in the physical plan. It contains a list of predicates (conditional expressions) that are later evaluated against the input columns and produce a result that only contains rows that match the given conditions. The list of expressions are chained with a logical AND.

func (*Filter) Accept

func (f *Filter) Accept(v Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*Filter) Clone

func (f *Filter) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*Filter) ID

func (f *Filter) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*Filter) Type

func (*Filter) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type FilteredShardDescriptor

type FilteredShardDescriptor struct {
	Location  DataObjLocation
	Streams   []int64
	Sections  []int
	TimeRange TimeRange
}

type Limit

type Limit struct {

	// Skip specifies how many initial rows should be skipped.
	Skip uint32
	// Fetch specifies how many rows should be returned in total.
	Fetch uint32
	// contains filtered or unexported fields
}

Limit represents a limiting operation in the physical plan that applies offset and limit to the result set. The offset specifies how many rows to skip before starting to return results, while limit specifies the maximum number of rows to return.

func (*Limit) Accept

func (l *Limit) Accept(v Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*Limit) Clone

func (l *Limit) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*Limit) ID

func (l *Limit) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*Limit) Type

func (*Limit) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type LiteralExpr

type LiteralExpr struct {
	types.Literal
}

LiteralExpr is an expression that implements the LiteralExpression interface.

func NewLiteral

func NewLiteral(value types.LiteralType) *LiteralExpr

func (*LiteralExpr) Clone

func (e *LiteralExpr) Clone() Expression

Clone returns a copy of the LiteralExpr.

func (*LiteralExpr) String

func (e *LiteralExpr) String() string

String returns the string representation of the literal value.

func (*LiteralExpr) Type

func (*LiteralExpr) Type() ExpressionType

ID returns the type of the LiteralExpr.

func (*LiteralExpr) ValueType

func (e *LiteralExpr) ValueType() types.DataType

ValueType returns the kind of value represented by the literal.

type LiteralExpression

type LiteralExpression interface {
	Expression
	ValueType() types.DataType
	// contains filtered or unexported methods
}

LiteralExpression is the common interface for all literal expressions in a physical plan.

type MetastoreCatalog

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

MetastoreCatalog is the default implementation of Catalog.

func NewMetastoreCatalog

func NewMetastoreCatalog(ctx context.Context, ms metastore.Metastore) *MetastoreCatalog

NewMetastoreCatalog creates a new instance of MetastoreCatalog for query planning.

func (*MetastoreCatalog) ResolveShardDescriptors

func (c *MetastoreCatalog) ResolveShardDescriptors(selector Expression, from, through time.Time) ([]FilteredShardDescriptor, error)

ResolveShardDescriptors resolves an array of FilteredShardDescriptor objects based on a given Expression. The expression is required to be a (tree of) BinaryExpression with a ColumnExpression on the left and a LiteralExpression on the right.

func (*MetastoreCatalog) ResolveShardDescriptorsWithShard

func (c *MetastoreCatalog) ResolveShardDescriptorsWithShard(selector Expression, predicates []Expression, shard ShardInfo, from, through time.Time) ([]FilteredShardDescriptor, error)

type Node

type Node interface {
	// ID returns a string that uniquely identifies a node in the plan
	ID() string
	// Type returns the node type
	Type() NodeType
	// Clone creates a deep copy of the Node. Cloned nodes do not retain the
	// same ID.
	Clone() Node
	// Accept allows the object to be visited by a [Visitor] as part of the
	// visitor pattern. It typically calls back to the appropriate Visit method
	// on the Visitor for the concrete type being visited.
	Accept(Visitor) error
	// contains filtered or unexported methods
}

Node represents a single operation in a physical execution plan. It defines the core interface that all physical plan nodes must implement. Each node represents a specific operation like scanning, filtering, or transforming data. Nodes can be connected to form a directed acyclic graph (DAG) representing the complete execution plan.

type NodeType

type NodeType uint32
const (
	NodeTypeDataObjScan NodeType = iota
	NodeTypeSortMerge
	NodeTypeProjection
	NodeTypeFilter
	NodeTypeLimit
	NodeTypeRangeAggregation
	NodeTypeVectorAggregation
	NodeTypeMerge
	NodeTypeParse
	NodeTypeCompat
	NodeTypeTopK
	NodeTypeParallelize
	NodeTypeScanSet
)

func (NodeType) String

func (t NodeType) String() string

type Parallelize

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

Parallelize represents a hint to the engine to partition and parallelize the children branches of the Parallelize and emit results as a single sequence with no guaranteed order.

func (*Parallelize) Accept

func (p *Parallelize) Accept(v Visitor) error

Accept implements the Node interface, dispatching itself to v.

func (*Parallelize) Clone

func (p *Parallelize) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*Parallelize) ID

func (p *Parallelize) ID() string

ID returns a string that uniquely identifies the node in the plan.

func (*Parallelize) Type

func (p *Parallelize) Type() NodeType

Type returns NodeTypeParallelize.

type ParseNode

type ParseNode struct {
	Kind          ParserKind
	RequestedKeys []string
	// contains filtered or unexported fields
}

ParseNode represents a parsing operation in the physical plan. It extracts structured fields from log lines using the specified parser.

func (*ParseNode) Accept

func (n *ParseNode) Accept(v Visitor) error

Accept allows the ParseNode to be visited by a Visitor

func (*ParseNode) Clone

func (n *ParseNode) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*ParseNode) ID

func (n *ParseNode) ID() string

ID returns a unique identifier for this ParseNode

func (*ParseNode) Type

func (n *ParseNode) Type() NodeType

Type returns the node type

type ParserKind

type ParserKind int

ParserKind represents the type of parser to use

const (
	ParserInvalid ParserKind = iota
	ParserLogfmt
	ParserJSON
)

func (ParserKind) String

func (p ParserKind) String() string

type Plan

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

Plan represents a physical execution plan as a directed acyclic graph (DAG). It maintains the relationships between nodes, tracking parent-child connections and providing methods for graph traversal and manipulation.

The plan structure supports operations like adding nodes and edges, retrieving nodes by ID, retrieving parents and children of nodes, and walking the graph in different orders using the depth-first-search algorithm.

func (*Plan) Children

func (p *Plan) Children(n Node) []Node

Children returns all child nodes of the given node.

func (*Plan) DFSWalk

func (p *Plan) DFSWalk(n Node, v Visitor, order WalkOrder) error

DFSWalk performs a depth-first traversal of the plan starting from node n. It applies the visitor v to each node according to the specified walk order. The order parameter determines if nodes are visited before their children (PreOrderWalk) or after their children (PostOrderWalk).

func (*Plan) Leaves

func (p *Plan) Leaves() []Node

Leaves returns all nodes that have no children.

func (*Plan) Len

func (p *Plan) Len() int

Len returns the number of nodes in the graph.

func (*Plan) Parent

func (p *Plan) Parent(n Node) []Node

Parent returns the parents of the given node.

func (*Plan) Root

func (p *Plan) Root() (Node, error)

Root returns the root node that have no parents. It returns an error if the plan has no or multiple root nodes.

func (*Plan) Roots

func (p *Plan) Roots() []Node

Roots returns all nodes that have no parents.

type Planner

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

Planner creates an executable physical plan from a logical plan. Planning is done in two steps:

  1. Convert Instructions from the logical plan are converted into Nodes in the physical plan. Most instructions can be translated into a single Node. However, MakeTable translates into multiple DataObjScan nodes.
  2. Pushdown a) Push down the limit of the Limit node to the DataObjScan nodes. b) Push down the predicate from the Filter node to the DataObjScan nodes.

func NewPlanner

func NewPlanner(ctx *Context, catalog Catalog) *Planner

NewPlanner creates a new planner instance with the given context.

func (*Planner) Build

func (p *Planner) Build(lp *logical.Plan) (*Plan, error)

Build converts a given logical plan into a physical plan and returns an error if the conversion fails. The resulting plan can be accessed using [Planner.Plan].

func (*Planner) Optimize

func (p *Planner) Optimize(plan *Plan) (*Plan, error)

Optimize runs optimization passes over the plan, modifying it if any optimizations can be applied.

type Projection

type Projection struct {

	// Expressions is a set of column expressions that are used to drop not needed
	// columns that match the column expression, or to expand columns that result
	// from the expressions.
	Expressions []Expression

	All    bool // Marker for projecting all columns of input relation (similar to SQL `SELECT *`)
	Expand bool // Indicates that projected columns should be added to input relation
	Drop   bool // Indicates that projected columns should be dropped from input Relation
	// contains filtered or unexported fields
}

Projection represents a column selection operation in the physical plan. It contains a list of columns (column expressions) that are later evaluated against the input columns to remove unnecessary colums from the intermediate result.

func (*Projection) Accept

func (p *Projection) Accept(v Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*Projection) Clone

func (p *Projection) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*Projection) ID

func (p *Projection) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*Projection) Type

func (*Projection) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type RangeAggregation

type RangeAggregation struct {
	PartitionBy []ColumnExpression // Columns to partition the data by.

	Operation types.RangeAggregationType
	Start     time.Time
	End       time.Time
	Step      time.Duration // optional for instant queries
	Range     time.Duration
	// contains filtered or unexported fields
}

TODO: Rename based on the actual implementation.

func (*RangeAggregation) Accept

func (r *RangeAggregation) Accept(v Visitor) error

func (*RangeAggregation) Clone

func (r *RangeAggregation) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*RangeAggregation) ID

func (r *RangeAggregation) ID() string

func (*RangeAggregation) Type

func (r *RangeAggregation) Type() NodeType

type ScanSet

type ScanSet struct {

	// Targets to scan.
	Targets []*ScanTarget

	// Projections are used to limit the columns that are read to the ones
	// provided in the column expressions to reduce the amount of data that
	// needs to be processed.
	Projections []ColumnExpression

	// Predicates are used to filter rows to reduce the amount of rows that are
	// returned. Predicates would almost always contain a time range filter to
	// only read the logs for the requested time range.
	Predicates []Expression
	// contains filtered or unexported fields
}

ScanSet represents a physical plan operation for reading data from targets.

func (*ScanSet) Accept

func (s *ScanSet) Accept(v Visitor) error

Accept dispatches s to the provided Visitor v.

func (*ScanSet) Clone

func (s *ScanSet) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*ScanSet) ID

func (s *ScanSet) ID() string

ID returns a string that uniquely identifies the node in the plan.

func (*ScanSet) Type

func (s *ScanSet) Type() NodeType

Type returns NodeTypeScanSet.

type ScanTarget

type ScanTarget struct {
	Type ScanType

	// DataObj is non-nil if Type is [ScanTypeDataObject]. Despite DataObjScan
	// implementing [Node], the value is not inserted into the graph as a node.
	DataObject *DataObjScan
}

ScanTarget represents a target of a ScanSet.

func (*ScanTarget) Clone

func (t *ScanTarget) Clone() *ScanTarget

Clone returns a copy of the scan target.

type ScanType

type ScanType int

ScanType represents the data being scanned in a target of a ScanSet.

const (
	ScanTypeInvalid ScanType = iota
	ScanTypeDataObject
)

func (ScanType) String

func (ty ScanType) String() string

String returns a string representation of the scan type.

type ShardInfo

type ShardInfo struct {
	Shard uint32
	Of    uint32
}

func (ShardInfo) String

func (s ShardInfo) String() string

type SortOrder

type SortOrder uint8
const (
	UNSORTED SortOrder = iota
	ASC
	DESC
)

func (SortOrder) String

func (o SortOrder) String() string

String returns the string representation of the SortOrder.

type TimeRange

type TimeRange struct {
	Start time.Time
	End   time.Time
}

Start and End are inclusive.

func (*TimeRange) Merge

func (t *TimeRange) Merge(secondRange TimeRange) TimeRange

func (*TimeRange) Overlaps

func (t *TimeRange) Overlaps(secondRange TimeRange) bool

type TopK

type TopK struct {

	// SortBy is the column to sort by.
	SortBy     ColumnExpression
	Ascending  bool // Sort lines in ascending order if true.
	NullsFirst bool // When true, considers NULLs < non-NULLs when sorting.
	K          int  // Number of top rows to return.
	// contains filtered or unexported fields
}

TopK represents a physical plan node that performs topK operation. It sorts rows based on sort expressions and limits the result to the top K rows. This is equivalent to a SORT followed by a LIMIT operation.

func (*TopK) Accept

func (t *TopK) Accept(visitor Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*TopK) Clone

func (t *TopK) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*TopK) ID

func (t *TopK) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*TopK) Type

func (*TopK) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type UnaryExpr

type UnaryExpr struct {
	// Left is the expression being operated on
	Left Expression
	// Op is the unary operator to apply to the expression
	Op types.UnaryOp
}

UnaryExpr is an expression that implements the UnaryExpression interface.

func (*UnaryExpr) Clone

func (e *UnaryExpr) Clone() Expression

Clone returns a copy of the UnaryExpr.

func (*UnaryExpr) String

func (e *UnaryExpr) String() string

func (*UnaryExpr) Type

func (*UnaryExpr) Type() ExpressionType

ID returns the type of the UnaryExpr.

type UnaryExpression

type UnaryExpression interface {
	Expression
	// contains filtered or unexported methods
}

UnaryExpression is the common interface for all unary expressions in a physical plan.

type VectorAggregation

type VectorAggregation struct {

	// GroupBy defines the columns to group by. If empty, all rows are aggregated into a single result.
	GroupBy []ColumnExpression

	// Operation defines the type of aggregation operation to perform (e.g., sum, min, max)
	Operation types.VectorAggregationType
	// contains filtered or unexported fields
}

VectorAggregation represents a physical plan node that performs vector aggregations. It computes aggregations over time series data at each timestamp instant, grouping results by specified dimensions.

func (*VectorAggregation) Accept

func (v *VectorAggregation) Accept(visitor Visitor) error

Accept implements the Node interface. Dispatches itself to the provided Visitor v

func (*VectorAggregation) Clone

func (v *VectorAggregation) Clone() Node

Clone returns a deep copy of the node (minus its ID).

func (*VectorAggregation) ID

func (v *VectorAggregation) ID() string

ID implements the Node interface. Returns a string that uniquely identifies the node in the plan.

func (*VectorAggregation) Type

func (*VectorAggregation) Type() NodeType

Type implements the Node interface. Returns the type of the node.

type Visitor

type Visitor interface {
	VisitDataObjScan(*DataObjScan) error
	VisitProjection(*Projection) error
	VisitRangeAggregation(*RangeAggregation) error
	VisitFilter(*Filter) error
	VisitLimit(*Limit) error
	VisitVectorAggregation(*VectorAggregation) error
	VisitParse(*ParseNode) error
	VisitCompat(*ColumnCompat) error
	VisitTopK(*TopK) error
	VisitParallelize(*Parallelize) error
	VisitScanSet(*ScanSet) error
}

Visitor defines the interface for objects that can visit each type of physical plan node. It implements the Visitor pattern, providing type-specific visit methods for each concrete node type in the physical plan.

type WalkOrder

type WalkOrder uint8

WalkOrder defines the order for how a node and its children are visited.

const (
	// PreOrderWalk processes the current vertex before visiting any of its
	// children.
	PreOrderWalk WalkOrder = iota

	// PostOrderWalk processes the current vertex after visiting all of its
	// children.
	PostOrderWalk
)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL