memo

Documentation

Index

• type Group
  • func NewGroup(prop *property.LogicalProperty) *Group
  • func (g *Group) Equals(other any) bool
  • func (g *Group) Exists(hash64u uint64) bool
  • func (g *Group) GetFirstElem(operand pattern.Operand) *list.Element
  • func (g *Group) GetGroupID() GroupID
  • func (g *Group) GetLogicalExpressions() *list.List
  • func (g *Group) Hash64(h base.Hasher)
  • func (g *Group) Insert(e *GroupExpression) bool
  • func (g *Group) String(w io.Writer)
• type GroupExpression
  • func NewGroupExpression(lp base.LogicalPlan, inputs []*Group) *GroupExpression
  • func (e *GroupExpression) Equals(other any) bool
  • func (e *GroupExpression) GetGroup() *Group
  • func (e *GroupExpression) GetLogicalPlan() base.LogicalPlan
  • func (e *GroupExpression) Hash64(h base2.Hasher)
  • func (e *GroupExpression) Init(h base2.Hasher)
  • func (e *GroupExpression) String(w io.Writer)
  • func (e *GroupExpression) Sum64() uint64
• type GroupID
• type GroupIDGenerator
  • func (gi *GroupIDGenerator) NextGroupID() GroupID
• type Memo
  • func NewMemo(ctx sessionctx.Context) *Memo
  • func (m *Memo) CopyIn(target *Group, lp base.LogicalPlan) *GroupExpression
  • func (m *Memo) GetGroupID2Group() map[GroupID]*list.Element
  • func (m *Memo) GetGroups() *list.List
  • func (m *Memo) GetHasher() base2.Hasher
  • func (m *Memo) GetRootGroup() *Group
  • func (m *Memo) Init(plan base.LogicalPlan) *GroupExpression
  • func (m *Memo) NewGroup() *Group
• type MemoExpression
  • func NewMemoExpressionFromGroupExpression(ge *GroupExpression) *MemoExpression
  • func NewMemoExpressionFromPlan(plan base.LogicalPlan) *MemoExpression
  • func NewMemoExpressionFromPlanAndInputs(plan base.LogicalPlan, inputs []*MemoExpression) *MemoExpression
  • func (me *MemoExpression) IsGroupExpression() bool
  • func (me *MemoExpression) IsLogicalPlan() bool

Types

type Group

type Group struct {

	// Operand2FirstExpr is used to locate to the first same type logical expression
	// in list above instead of traverse them all.
	Operand2FirstExpr map[pattern.Operand]*list.Element
	// contains filtered or unexported fields
}

Group is basic infra to store all the logically equivalent expressions for one logical operator in current context.

func NewGroup

func NewGroup(prop *property.LogicalProperty) *Group

NewGroup creates a new Group with given logical prop.

func (*Group) Equals

func (g *Group) Equals(other any) bool

Equals implements the HashEquals.<1st> interface.

func (*Group) Exists

func (g *Group) Exists(hash64u uint64) bool

Exists checks whether a Group expression existed in a Group.

func (*Group) GetFirstElem

func (g *Group) GetFirstElem(operand pattern.Operand) *list.Element

GetFirstElem returns the first Group expression which matches the Operand. Return a nil pointer if there isn't.

func (*Group) GetGroupID

func (g *Group) GetGroupID() GroupID

GetGroupID gets the group id.

func (*Group) GetLogicalExpressions

func (g *Group) GetLogicalExpressions() *list.List

GetLogicalExpressions gets the logical expressions list.

func (*Group) Hash64

func (g *Group) Hash64(h base.Hasher)

Hash64 implements the HashEquals.<0th> interface.

func (*Group) Insert

func (g *Group) Insert(e *GroupExpression) bool

Insert adds a GroupExpression to the Group.

func (*Group) String

func (g *Group) String(w io.Writer)

String implements fmt.Stringer interface.

type GroupExpression

type GroupExpression struct {

	// inputs stores the Groups that this GroupExpression based on.
	Inputs []*Group
	// contains filtered or unexported fields
}

GroupExpression is a single expression from the equivalent list classes inside a group. it is a node in the expression tree, while it takes groups as inputs. This kind of loose coupling between Group and GroupExpression is the key to the success of the memory compact of representing a forest.

func NewGroupExpression

func NewGroupExpression(lp base.LogicalPlan, inputs []*Group) *GroupExpression

NewGroupExpression creates a new GroupExpression with the given logical plan and children.

func (*GroupExpression) Equals

func (e *GroupExpression) Equals(other any) bool

Equals implements the Equals interface.

func (*GroupExpression) GetGroup

func (e *GroupExpression) GetGroup() *Group

GetGroup returns the Group that this GroupExpression belongs to.

func (*GroupExpression) GetLogicalPlan

func (e *GroupExpression) GetLogicalPlan() base.LogicalPlan

GetLogicalPlan returns the logical plan of the GroupExpression.

func (*GroupExpression) Hash64

func (e *GroupExpression) Hash64(h base2.Hasher)

Hash64 implements the Hash64 interface.

func (*GroupExpression) Init

func (e *GroupExpression) Init(h base2.Hasher)

Init initializes the GroupExpression with the given group and hasher.

func (*GroupExpression) String

func (e *GroupExpression) String(w io.Writer)

String implements the fmt.Stringer interface.

func (*GroupExpression) Sum64

func (e *GroupExpression) Sum64() uint64

Sum64 returns the cached hash64 of the GroupExpression.

type GroupID

type GroupID uint64

GroupID is the unique id for a group.

type GroupIDGenerator

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

GroupIDGenerator is used to generate group id.

func (*GroupIDGenerator) NextGroupID

func (gi *GroupIDGenerator) NextGroupID() GroupID

NextGroupID generates the next group id. It is not thread-safe, since memo optimizing is also in one thread.

type Memo

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

Memo is the main structure of the memo package.

func NewMemo

func NewMemo(ctx sessionctx.Context) *Memo

NewMemo creates a new memo.

func (*Memo) CopyIn

func (m *Memo) CopyIn(target *Group, lp base.LogicalPlan) *GroupExpression

CopyIn copies a logical plan into the memo with format as GroupExpression.

func (*Memo) GetGroupID2Group

func (m *Memo) GetGroupID2Group() map[GroupID]*list.Element

GetGroupID2Group gets the map from group id to group.

func (*Memo) GetGroups

func (m *Memo) GetGroups() *list.List

GetGroups gets all groups in the memo.

func (*Memo) GetHasher

func (m *Memo) GetHasher() base2.Hasher

GetHasher gets a hasher from the memo that ready to use.

func (*Memo) GetRootGroup

func (m *Memo) GetRootGroup() *Group

GetRootGroup gets the root group of the memo.

func (*Memo) Init

func (m *Memo) Init(plan base.LogicalPlan) *GroupExpression

Init initializes the memo with a logical plan, converting logical plan tree format into group tree.

func (*Memo) NewGroup

func (m *Memo) NewGroup() *Group

NewGroup creates a new group.

type MemoExpression

type MemoExpression struct {
	LP base.LogicalPlan

	GE *GroupExpression

	Inputs []*MemoExpression
}

MemoExpression is a unified representation of logical and group expression. 1: when stepping into memo optimization, we may convert a logical plan tree into a memoExpr,

so each node of them is simply an LP.

2: when XForm is called from a specific rule, substitution happened, the output may be a mixture

of logical plan and group expression.

Thus, memoExpr is responsible for representing both of them, leveraging the unified portal of

MemoExpression managing memo group generation and hashing functionality.

func NewMemoExpressionFromGroupExpression

func NewMemoExpressionFromGroupExpression(ge *GroupExpression) *MemoExpression

NewMemoExpressionFromGroupExpression inits a memoExpression with an existed group expression.

func NewMemoExpressionFromPlan

func NewMemoExpressionFromPlan(plan base.LogicalPlan) *MemoExpression

NewMemoExpressionFromPlan init a memeExpression with a logical plan.

func NewMemoExpressionFromPlanAndInputs

func NewMemoExpressionFromPlanAndInputs(plan base.LogicalPlan, inputs []*MemoExpression) *MemoExpression

NewMemoExpressionFromPlanAndInputs inits a memoExpression with mixed logical plan as current node, and certain memoExpressions as its input.

func (*MemoExpression) IsGroupExpression

func (me *MemoExpression) IsGroupExpression() bool

IsGroupExpression checks whether this me is a group expression.

func (*MemoExpression) IsLogicalPlan

func (me *MemoExpression) IsLogicalPlan() bool

IsLogicalPlan checks whether this me is a logical plan.