rewrite

type Driver ¶

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

Driver runs all rules registered in a Registry to a fixed point.

The driver iterates at most maxIter times (default 16). On each iteration it applies every enabled rule across the full plan tree using WalkAndReplace. If no rule fires during an iteration the loop terminates early (fixed-point convergence).

package main

import (
	"context"
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/cypher/ir"
	"github.com/FlavioCFOliveira/GoGraph/cypher/ir/rewrite"
)

// selectOverProjection builds the plan
//
//	Selection(n.age > 18) → Projection(n) → AllNodesScan(n)
//
// which is the canonical input for the predicate-pushdown rule.
func selectOverProjection() ir.LogicalPlan {
	return ir.NewSelection("n.age > 18",
		ir.NewProjection(
			[]ir.ProjectionItem{{Name: "n", Expression: "n"}},
			ir.NewAllNodesScan("n"),
		),
	)
}

func main() {
	reg := &rewrite.Registry{}
	reg.Register(rewrite.PredicatePushdown{})

	driver := rewrite.NewDriver(reg)
	optimised, count := driver.Run(context.Background(), selectOverProjection())

	fmt.Println("rewrites applied:", count)
	fmt.Print(ir.Explain(optimised))
}

Output:
rewrites applied: 1
Projection [n]
└─ Selection [n.age > 18]
   └─ AllNodesScan [n]

func NewDriver(reg *Registry) *Driver

func (d *Driver) Run(ctx context.Context, plan ir.LogicalPlan) (result ir.LogicalPlan, applied int)

type EagerInsertion ¶

type EagerInsertion struct{}

EagerInsertion inserts Eager barrier operators before write operators that read from the same graph state they modify, following the semantics of Green et al. 2019 §5.

Rules implemented:

1. Merge always requires an Eager barrier (it both reads and writes atomically; see Green 2019 §5.3).
2. CREATE after MATCH (i.e. CreateNode or CreateRelationship whose subtree contains a scan/traversal operator) requires an Eager barrier.
3. DELETE (DeleteNode, DeleteRelationship, DetachDelete) after MATCH requires an Eager barrier.
4. SET/REMOVE (SetProperty, SetLabels, RemoveProperty, RemoveLabels) are non-eager unless they appear inside an iterating context (a loop). At the logical-plan level detected by the presence of a scan or traversal in the subtree. Since we cannot distinguish a loop at this IR level, we treat SET/REMOVE conservatively: they are NOT made eager here; the rule is left open for extension.

Idempotence: the rule checks whether an Eager is already the immediate child of the write operator to avoid double-insertion.

Concurrency: EagerInsertion is stateless and goroutine-safe.

func (EagerInsertion) Apply(plan ir.LogicalPlan) (ir.LogicalPlan, bool)

func (EagerInsertion) Name() string

type FusionRules ¶

type FusionRules struct{}

FusionRules implements three structural optimisations:

1. Distinct+Limit fusion → Top: Distinct(Limit(n, child)) is replaced by Top([], n, child). The Top operator sorts-and-limits in a single pass, but when no SortItems are present it degenerates to a stop-after-n operator with deduplication. This avoids materialising the full sorted stream before deduplication.

2. Double-Projection removal: Projection(outer, Projection(inner, child)) where every outer item references only columns produced by the inner Projection is collapsed into a single Projection by inlining the outer item expressions and retaining only items required by the outer.

3. Redundant-Distinct removal: Distinct(Distinct(child)) → Distinct(child). Also removes a Distinct above an operator that already produces unique rows, specifically EagerAggregation (GROUP BY always produces unique key combinations).

Concurrency: FusionRules is stateless and goroutine-safe.

func (FusionRules) Apply(plan ir.LogicalPlan) (ir.LogicalPlan, bool)

func (FusionRules) Name() string

type PredicatePushdown ¶

type PredicatePushdown struct{}

PredicatePushdown pushes Selection predicates down the plan tree toward the scan operators. A Selection can be pushed past any operator that is both transparent (does not introduce new variable bindings consumed by the predicate) and non-eager (does not act as a pipeline-breaking barrier).

Pushdown rules:

• Selection above Projection: push when all predicate variables are in the projected output.
• Selection above Limit / Skip / Sort: always push (they do not change the set of available variables).
• Selection above Eager: NEVER push (Eager is a hard barrier).
• Selection above another Selection: push the outer predicate past the inner selection so predicates accumulate close to the scan.

Concurrency: PredicatePushdown is stateless and goroutine-safe.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/cypher/ir"
	"github.com/FlavioCFOliveira/GoGraph/cypher/ir/rewrite"
)

// selectOverProjection builds the plan
//
//	Selection(n.age > 18) → Projection(n) → AllNodesScan(n)
//
// which is the canonical input for the predicate-pushdown rule.
func selectOverProjection() ir.LogicalPlan {
	return ir.NewSelection("n.age > 18",
		ir.NewProjection(
			[]ir.ProjectionItem{{Name: "n", Expression: "n"}},
			ir.NewAllNodesScan("n"),
		),
	)
}

func main() {
	plan := selectOverProjection()
	fmt.Print("before:\n", ir.Explain(plan))

	optimised, changed := rewrite.PredicatePushdown{}.Apply(plan)
	fmt.Println("changed:", changed)
	fmt.Print("after:\n", ir.Explain(optimised))
}

Output:
before:
Selection [n.age > 18]
└─ Projection [n]
   └─ AllNodesScan [n]
changed: true
after:
Projection [n]
└─ Selection [n.age > 18]
   └─ AllNodesScan [n]

func (PredicatePushdown) Apply(plan ir.LogicalPlan) (ir.LogicalPlan, bool)

func (PredicatePushdown) Name() string

type ProjectionPushdown ¶

type ProjectionPushdown struct{}

ProjectionPushdown removes Projection operators whose output columns are not referenced by any ancestor. It operates in two complementary modes:

1. Dead-column elimination: trim ProjectionItem entries whose Name is not in the required set propagated from ancestors. When all items are trimmed the Projection node itself is removed.
2. Redundant-node removal: when a Projection node becomes empty after trimming, replace it with its child.

The rule is stateless. Required-column information is threaded through the tree via a separate top-down walk that annotates each Projection with the set of columns actually needed by its ancestors.

Concurrency: ProjectionPushdown is stateless and goroutine-safe.

func (ProjectionPushdown) Apply(plan ir.LogicalPlan) (ir.LogicalPlan, bool)

func (ProjectionPushdown) Name() string

type Registry ¶

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

Registry is an ordered collection of rewrite rules. Rules are applied in registration order during each fixed-point iteration.

func (r *Registry) Register(rule Rule)

func (r *Registry) Rules() []Rule

type Rule ¶

type Rule interface {
	// Name returns a stable, unique identifier used for logging and selective
	// disabling via WithDisabledRules.
	Name() string
	// Apply attempts to rewrite plan. It returns the (possibly new) plan and
	// true when a rewrite was performed, or the original plan and false when no
	// rewrite applies.
	Apply(plan ir.LogicalPlan) (ir.LogicalPlan, bool)
}

Rule is the interface implemented by every rewrite rule.

Apply accepts a logical plan node and returns the (possibly rewritten) replacement node together with a boolean reporting whether any change was made. Apply must not modify the input node in place; it must return a new node when a rewrite occurs.

Apply is called bottom-up by WalkAndReplace: by the time it is invoked on a node, all descendants have already been processed.