optimize

package
v0.9.3 Latest Latest
Warning

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

 Go to latest Published: Oct 15, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	LoweringProjectionPruning         = "ProjectionPruning"
	LoweringLatePathMaterialization   = "LatePathMaterialization"
	LoweringExpandIntoDetection       = "ExpandIntoDetection"
	LoweringTraversalDirection        = "TraversalDirectionSelection"
	LoweringShortestPathStrategy      = "ShortestPathStrategySelection"
	LoweringShortestPathFilter        = "ShortestPathFilterMaterialization"
	LoweringLimitPushdown             = "LimitPushdown"
	LoweringExpansionSuffixPushdown   = "ExpansionSuffixPushdown"
	LoweringPredicatePlacement        = "PredicatePlacement"
	LoweringCountStoreFastPath        = "CountStoreFastPath"
	LoweringCollectIDMembership       = "CollectIDMembership"
	LoweringAggregateTraversalCount   = "AggregateTraversalCount"
	LoweringExactRangeExpansion       = "ExactRangeExpansion"
	LoweringPathRelationshipPredicate = "PathRelationshipPredicate"
)

Variables

This section is empty.

Functions

func AddFromClauseBindings 

func AddFromClauseBindings(localScope *pgsql.IdentifierSet, fromClauses []pgsql.FromClause)

func AddFromExpressionBinding 

func AddFromExpressionBinding(localScope *pgsql.IdentifierSet, expression pgsql.Expression)

func ExactPatternRangeDepth added in v0.7.0 

func ExactPatternRangeDepth(patternRange *cypher.PatternRange) int64

func ExpressionReferencesOnlyLocalIdentifiers 

func ExpressionReferencesOnlyLocalIdentifiers(expression pgsql.Expression, localScope *pgsql.IdentifierSet) bool

ExpressionReferencesOnlyLocalIdentifiers returns true only when every binding reference found in the expression is a member of localScope.

func FlattenConjunction 

func FlattenConjunction(expr pgsql.Expression) []pgsql.Expression

FlattenConjunction collects the leaf operands of a left-recursive AND chain.

func FromExpressionReferencesOnlyLocalIdentifiers 

func FromExpressionReferencesOnlyLocalIdentifiers(expression pgsql.Expression, localScopes ...*pgsql.IdentifierSet) bool

func IndexPatternPredicateTargets 

func IndexPatternPredicateTargets(query *cypher.RegularQuery) map[*cypher.PatternPredicate]PatternTarget

func IndexPatternTargets 

func IndexPatternTargets(query *cypher.RegularQuery) map[*cypher.PatternPart]PatternTarget

func IsBidirectionalSearchAnchor 

func IsBidirectionalSearchAnchor(selectivity int) bool

func IsLocalToScope 

func IsLocalToScope(expression pgsql.Expression, localScope *pgsql.IdentifierSet) bool

func MeasureSelectivity 

func MeasureSelectivity(bindings BindingLookup, expression pgsql.Expression) (int, error)

func PartitionConstraintByLocality 

func PartitionConstraintByLocality(expression pgsql.Expression, localScope *pgsql.IdentifierSet) (pgsql.Expression, pgsql.Expression)

PartitionConstraintByLocality splits a conjunction (A AND B AND ...) into two expressions: one whose every binding reference is contained in localScope (safe for JOIN ON), and one that references outside identifiers (must stay in WHERE).

Only top-level AND operands are split. If an expression is not a BinaryExpression with OperatorAnd, the whole expression is tested as a unit.

func QueryReferencesOnlyLocalIdentifiers 

func QueryReferencesOnlyLocalIdentifiers(query pgsql.Query, localScope *pgsql.IdentifierSet) bool

func SelectReferencesOnlyLocalIdentifiers 

func SelectReferencesOnlyLocalIdentifiers(selectBody pgsql.Select, localScope *pgsql.IdentifierSet) bool

func SubqueryReferencesOnlyLocalIdentifiers 

func SubqueryReferencesOnlyLocalIdentifiers(subquery pgsql.Subquery, localScope *pgsql.IdentifierSet) bool

Types

type AggregateTraversalCountDecision 

type AggregateTraversalCountDecision struct {
	QueryPartIndex int                 `json:"query_part_index"`
	SourceSymbol   string              `json:"source_symbol"`
	TerminalSymbol string              `json:"terminal_symbol"`
	CountAlias     string              `json:"count_alias"`
	Limit          int64               `json:"limit,omitempty"`
	Target         TraversalStepTarget `json:"target"`
}

type AggregateTraversalCountShape 

type AggregateTraversalCountShape struct {
	QueryPartIndex    int
	SourceSymbol      string
	TerminalSymbol    string
	CountAlias        string
	ReturnSourceAlias string
	ReturnCountAlias  string
	ReturnCount       bool
	Limit             int64
	SourceMatch       *cypher.Match
	TerminalMatch     *cypher.Match
	SourceKinds       graph.Kinds
	TerminalKinds     graph.Kinds
	RelationshipKinds graph.Kinds
	Direction         graph.Direction
	MinDepth          int64
	MaxDepth          int64
	Target            TraversalStepTarget
}

func AggregateTraversalCountShapeForQuery 

func AggregateTraversalCountShapeForQuery(query *cypher.RegularQuery) (AggregateTraversalCountShape, bool)

type Analysis 

type Analysis struct {
	QueryParts []QueryPart
}

func Analyze 

func Analyze(query *cypher.RegularQuery) Analysis

func (Analysis) Diagnostics 

func (s Analysis) Diagnostics() []string

func (Analysis) String 

func (s Analysis) String() string

type Barrier 

type Barrier struct {
	QueryPartIndex int
	ClauseIndex    int
	Kind           BarrierKind
	Dependencies   []string
}

type BarrierKind 

type BarrierKind string
const (
	BarrierKindReturn        BarrierKind = "return"
	BarrierKindWith          BarrierKind = "with"
	BarrierKindUnwind        BarrierKind = "unwind"
	BarrierKindOptionalMatch BarrierKind = "optional_match"
	BarrierKindUpdate        BarrierKind = "update"
)

type Binding 

type Binding struct {
	Symbol       string
	Kind         BindingKind
	ClauseIndex  int
	PatternIndex int
}

type BindingKind 

type BindingKind string
const (
	BindingKindNode         BindingKind = "node"
	BindingKindRelationship BindingKind = "relationship"
	BindingKindPath         BindingKind = "path"
)

type BindingLookup 

type BindingLookup interface {
	LookupDataType(identifier pgsql.Identifier) (pgsql.DataType, bool)
}

type ConservativePatternReorderingRule 

type ConservativePatternReorderingRule struct{}

ConservativePatternReorderingRule reorders reading clauses within a dependency-safe region so that more selective anchors are scheduled earlier, driving traversals from the endpoints expected to prune the search soonest. It reorders whole clauses relative to one another without mutating the internals of any pattern; a clause is only moved when its dependencies remain satisfied by the clauses that precede it in the new order.

func (ConservativePatternReorderingRule) Apply 

func (s ConservativePatternReorderingRule) Apply(plan *Plan) (bool, error)

func (ConservativePatternReorderingRule) Name 

func (s ConservativePatternReorderingRule) Name() string

type CountStoreFastPathDecision 

type CountStoreFastPathDecision struct {
	QueryPartIndex int                      `json:"query_part_index"`
	ClauseIndex    int                      `json:"clause_index"`
	PatternIndex   int                      `json:"pattern_index"`
	BindingSymbol  string                   `json:"binding_symbol,omitempty"`
	Target         CountStoreFastPathTarget `json:"target"`
	KindSymbols    []string                 `json:"kind_symbols,omitempty"`
}

type CountStoreFastPathTarget 

type CountStoreFastPathTarget string
const (
	CountStoreFastPathNode CountStoreFastPathTarget = "node"
	CountStoreFastPathEdge CountStoreFastPathTarget = "edge"
)

type ExactRangeExpansionDecision added in v0.7.0 

type ExactRangeExpansionDecision struct {
	Target TraversalStepTarget `json:"target"`
	Depth  int64               `json:"depth"`
}

type ExpandIntoDecision 

type ExpandIntoDecision struct {
	Target TraversalStepTarget `json:"target"`
}

type ExpansionSuffixPushdownDecision 

type ExpansionSuffixPushdownDecision struct {
	Target               TraversalStepTarget   `json:"target"`
	SuffixLength         int                   `json:"suffix_length"`
	SuffixStartStep      int                   `json:"suffix_start_step"`
	SuffixEndStep        int                   `json:"suffix_end_step"`
	PredicateAttachments []PredicateAttachment `json:"predicate_attachments,omitempty"`
}

type InboundTraversalReversalRule added in v0.7.1 

type InboundTraversalReversalRule struct{}

InboundTraversalReversalRule reverses a qualifying multi-step traversal pattern so that the search is driven from the more selective terminal endpoint inward, rather than expanding outward from an unconstrained source through a leading unbounded variable-length expansion.

A pattern such as: 

MATCH p = (s:User)-[:MemberOf*0..]->(:Group)-[:AdminTo]->(d:Computer)
WHERE s.samaccountname =~ '(?i).*[ge]$' AND d.operatingsystem CONTAINS "WINDOWS SERVER"
RETURN p

is rewritten to drive from d:Computer inbound toward s:User by reversing the pattern element order and each relationship direction. The reversed pattern is flagged via PatternPart.PathDirectionReversed so path materialization can restore the original left-to-right order for RETURN p.

func (InboundTraversalReversalRule) Apply added in v0.7.1 

func (s InboundTraversalReversalRule) Apply(plan *Plan) (bool, error)

func (InboundTraversalReversalRule) Name added in v0.7.1 

func (s InboundTraversalReversalRule) Name() string

type LatePathMaterializationDecision 

type LatePathMaterializationDecision struct {
	Target TraversalStepTarget         `json:"target"`
	Mode   LatePathMaterializationMode `json:"mode"`
}

type LatePathMaterializationMode 

type LatePathMaterializationMode string
const (
	LatePathMaterializationPathEdgeID    LatePathMaterializationMode = "path_edge_id"
	LatePathMaterializationExpansionPath LatePathMaterializationMode = "expansion_path"
	LatePathMaterializationEdgeComposite LatePathMaterializationMode = "edge_composite"
)

type LimitPushdownDecision 

type LimitPushdownDecision struct {
	Target TraversalStepTarget `json:"target"`
	Mode   LimitPushdownMode   `json:"mode"`
}

type LimitPushdownMode 

type LimitPushdownMode string
const (
	LimitPushdownTraversalCTE        LimitPushdownMode = "traversal_cte"
	LimitPushdownShortestPathHarness LimitPushdownMode = "shortest_path_harness"
)

type LoweringDecision 

type LoweringDecision struct {
	Name string `json:"name"`
}

type LoweringPlan 

type LoweringPlan struct {
	ProjectionPruning         []ProjectionPruningDecision         `json:"projection_pruning,omitempty"`
	LatePathMaterialization   []LatePathMaterializationDecision   `json:"late_path_materialization,omitempty"`
	ExpandInto                []ExpandIntoDecision                `json:"expand_into,omitempty"`
	TraversalDirection        []TraversalDirectionDecision        `json:"traversal_direction,omitempty"`
	ShortestPathStrategy      []ShortestPathStrategyDecision      `json:"shortest_path_strategy,omitempty"`
	ShortestPathFilter        []ShortestPathFilterDecision        `json:"shortest_path_filter,omitempty"`
	LimitPushdown             []LimitPushdownDecision             `json:"limit_pushdown,omitempty"`
	ExpansionSuffixPushdown   []ExpansionSuffixPushdownDecision   `json:"expansion_suffix_pushdown,omitempty"`
	PredicatePlacement        []PredicatePlacementDecision        `json:"predicate_placement,omitempty"`
	PatternPredicate          []PatternPredicatePlacementDecision `json:"pattern_predicate_placement,omitempty"`
	CountStoreFastPath        []CountStoreFastPathDecision        `json:"count_store_fast_path,omitempty"`
	ExactRangeExpansion       []ExactRangeExpansionDecision       `json:"exact_range_expansion,omitempty"`
	PathRelationshipPredicate []PathRelationshipPredicateDecision `json:"path_relationship_predicate,omitempty"`
	AggregateTraversalCount   []AggregateTraversalCountDecision   `json:"aggregate_traversal_count,omitempty"`
}

func BuildLoweringPlan 

func BuildLoweringPlan(query *cypher.RegularQuery, predicateAttachments []PredicateAttachment) (LoweringPlan, error)

func (LoweringPlan) Decisions 

func (s LoweringPlan) Decisions() []LoweringDecision

func (LoweringPlan) Empty 

func (s LoweringPlan) Empty() bool

type MatchClause 

type MatchClause struct {
	Index           int
	PatternCount    int
	WherePredicates int
}

type Optimizer 

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

func NewOptimizer 

func NewOptimizer(rules ...Rule) Optimizer

func (Optimizer) Optimize 

func (s Optimizer) Optimize(query *cypher.RegularQuery) (Plan, error)

Optimize preserves the historical ownership contract: the returned plan always owns its query independently of the caller's input.

func (Optimizer) OptimizeBorrowed added in v0.8.0 

func (s Optimizer) OptimizeBorrowed(query *cypher.RegularQuery) (Plan, error)

OptimizeBorrowed applies the optimizer without copying query until a rule needs to mutate it. See OptimizeBorrowed for ownership details.

type PathRelationshipPredicateDecision added in v0.7.0 

type PathRelationshipPredicateDecision struct {
	Target        QuantifierTarget `json:"target"`
	PathSymbol    string           `json:"path_symbol"`
	BindingSymbol string           `json:"binding_symbol"`
}

type PathVariable 

type PathVariable struct {
	Symbol            string
	ClauseIndex       int
	PatternIndex      int
	NodeCount         int
	RelationshipCount int
	VariableLength    bool
	Dependencies      []string
}

type PatternPredicatePlacementDecision 

type PatternPredicatePlacementDecision struct {
	Target TraversalStepTarget           `json:"target"`
	Mode   PatternPredicatePlacementMode `json:"mode"`
}

type PatternPredicatePlacementMode 

type PatternPredicatePlacementMode string
const (
	PatternPredicatePlacementExistence PatternPredicatePlacementMode = "existence"
)

type PatternTarget 

type PatternTarget struct {
	QueryPartIndex int  `json:"query_part_index"`
	ClauseIndex    int  `json:"clause_index"`
	PatternIndex   int  `json:"pattern_index"`
	Predicate      bool `json:"predicate,omitempty"`
	PredicateIndex int  `json:"predicate_index,omitempty"`
}

func (PatternTarget) TraversalStep 

func (s PatternTarget) TraversalStep(stepIndex int) TraversalStepTarget

type Plan 

type Plan struct {
	Query                *cypher.RegularQuery
	Analysis             Analysis
	LoweringPlan         LoweringPlan
	Rules                []RuleResult
	PredicateAttachments []PredicateAttachment
	// contains filtered or unexported fields
}

func Optimize 

func Optimize(query *cypher.RegularQuery) (Plan, error)

func OptimizeBorrowed added in v0.8.0 

func OptimizeBorrowed(query *cypher.RegularQuery) (Plan, error)

OptimizeBorrowed optimizes query without copying it up front. The returned plan aliases query when no rewrite applies; rules must call EnsureMutable before modifying the tree. It is intended for callers that already own the input tree and can treat the returned plan as read-only.

func (*Plan) EnsureMutable added in v0.8.0 

func (s *Plan) EnsureMutable() *cypher.RegularQuery

EnsureMutable gives a rule an owned query before it changes the AST. It is intentionally idempotent so multiple applied rules share one copy.

type Predicate 

type Predicate struct {
	ClauseIndex     int
	ExpressionIndex int
	Dependencies    []string
}

type PredicateAttachment 

type PredicateAttachment struct {
	QueryPartIndex  int                      `json:"query_part_index"`
	RegionIndex     int                      `json:"region_index"`
	ClauseIndex     int                      `json:"clause_index"`
	ExpressionIndex int                      `json:"expression_index"`
	Scope           PredicateAttachmentScope `json:"scope"`
	BindingSymbols  []string                 `json:"binding_symbols"`
	Dependencies    []string                 `json:"dependencies"`
}

func AttachPredicates 

func AttachPredicates(analysis Analysis) []PredicateAttachment

type PredicateAttachmentRule 

type PredicateAttachmentRule struct{}

func (PredicateAttachmentRule) Apply 

func (s PredicateAttachmentRule) Apply(plan *Plan) (bool, error)

func (PredicateAttachmentRule) Name 

func (s PredicateAttachmentRule) Name() string

type PredicateAttachmentScope 

type PredicateAttachmentScope string
const (
	PredicateAttachmentScopeBinding PredicateAttachmentScope = "binding"
	PredicateAttachmentScopeRegion  PredicateAttachmentScope = "region"
)

type PredicatePlacementDecision 

type PredicatePlacementDecision struct {
	Target     TraversalStepTarget      `json:"target"`
	Attachment PredicateAttachment      `json:"attachment"`
	Placement  PredicateAttachmentScope `json:"placement"`
}

type ProjectionPruningDecision 

type ProjectionPruningDecision struct {
	Target                   TraversalStepTarget `json:"target"`
	ReferencedSymbols        []string            `json:"referenced_symbols,omitempty"`
	PatternBindingReferenced bool                `json:"pattern_binding_referenced,omitempty"`
	OmitLeftNode             bool                `json:"omit_left_node,omitempty"`
	OmitRelationship         bool                `json:"omit_relationship,omitempty"`
	OmitRightNode            bool                `json:"omit_right_node,omitempty"`
	OmitPathBinding          bool                `json:"omit_path_binding,omitempty"`
}

type QuantifierTarget added in v0.7.0 

type QuantifierTarget struct {
	QueryPartIndex  int `json:"query_part_index"`
	QuantifierIndex int `json:"quantifier_index"`
}

type QueryPart 

type QueryPart struct {
	Index                  int
	Kind                   QueryPartKind
	Regions                []Region
	Barriers               []Barrier
	ProjectionDependencies []string
}

type QueryPartKind 

type QueryPartKind string
const (
	QueryPartKindSingle QueryPartKind = "single"
	QueryPartKindMulti  QueryPartKind = "multi"
)

type Region 

type Region struct {
	QueryPartIndex     int
	StartClause        int
	EndClause          int
	Clauses            []MatchClause
	Bindings           []Binding
	BindingOccurrences []Binding
	PathVariables      []PathVariable
	Predicates         []Predicate
}

type Rule 

type Rule interface {
	Name() string
	Apply(*Plan) (bool, error)
}

func DefaultRules 

func DefaultRules() []Rule

type RuleResult 

type RuleResult struct {
	Name    string `json:"name"`
	Applied bool   `json:"applied"`
}

type SelectivityModel 

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

func NewSelectivityModel 

func NewSelectivityModel(bindings BindingLookup) SelectivityModel

func (SelectivityModel) EndpointSelectivity 

func (s SelectivityModel) EndpointSelectivity(expression pgsql.Expression, bound, hasPreviousFrameBinding bool) (int, error)

func (SelectivityModel) Measure 

func (s SelectivityModel) Measure(expression pgsql.Expression) (int, error)

func (SelectivityModel) ShouldFlipTraversalDirection 

func (s SelectivityModel) ShouldFlipTraversalDirection(leftBound, rightBound bool, leftExpression, rightExpression pgsql.Expression) (bool, error)

type ShortestPathFilterDecision 

type ShortestPathFilterDecision struct {
	Target TraversalStepTarget    `json:"target"`
	Mode   ShortestPathFilterMode `json:"mode"`
	Reason string                 `json:"reason,omitempty"`
}

type ShortestPathFilterMode 

type ShortestPathFilterMode string
const (
	ShortestPathFilterTerminal     ShortestPathFilterMode = "terminal"
	ShortestPathFilterEndpointPair ShortestPathFilterMode = "endpoint_pair"
)

type ShortestPathStrategy 

type ShortestPathStrategy string
const (
	ShortestPathStrategyBidirectional  ShortestPathStrategy = "bidirectional"
	ShortestPathStrategyUnidirectional ShortestPathStrategy = "unidirectional"
)

type ShortestPathStrategyDecision 

type ShortestPathStrategyDecision struct {
	Target   TraversalStepTarget  `json:"target"`
	Strategy ShortestPathStrategy `json:"strategy"`
	Reason   string               `json:"reason,omitempty"`
}

type TraversalDirectionDecision 

type TraversalDirectionDecision struct {
	Target TraversalStepTarget `json:"target"`
	Flip   bool                `json:"flip,omitempty"`
	Reason string              `json:"reason,omitempty"`
}

type TraversalStepTarget 

type TraversalStepTarget struct {
	QueryPartIndex int  `json:"query_part_index"`
	ClauseIndex    int  `json:"clause_index"`
	PatternIndex   int  `json:"pattern_index"`
	Predicate      bool `json:"predicate,omitempty"`
	PredicateIndex int  `json:"predicate_index,omitempty"`
	StepIndex      int  `json:"step_index"`
}

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.