memo

Documentation

Index

• type Group
  • func NewGroup(prop *property.LogicalProperty) *Group
  • func (g *Group) Delete(e *GroupExpression)
  • func (g *Group) Equals(other any) bool
  • func (g *Group) ForEachGE(f func(ge *GroupExpression) bool)
  • func (g *Group) GetFirstElem(operand pattern.Operand) *list.Element
  • func (g *Group) GetGroupID() GroupID
  • func (g *Group) GetLogicalExpressions() *list.List
  • func (g *Group) GetLogicalProperty() *property.LogicalProperty
  • func (g *Group) HasLogicalProperty() bool
  • func (g *Group) Hash64(h base.Hasher)
  • func (g *Group) Insert(e *GroupExpression) bool
  • func (g *Group) IsExplored() bool
  • func (g *Group) SetExplored()
  • func (g *Group) SetLogicalProperty(prop *property.LogicalProperty)
  • func (g *Group) String(w util.StrBufferWriter)
• type GroupExpression
  • func (e *GroupExpression) DeriveLogicalProp() (err error)
  • func (e *GroupExpression) Equals(other any) bool
  • func (e *GroupExpression) GetGroup() *Group
  • func (e *GroupExpression) GetHash64() uint64
  • func (e *GroupExpression) Hash64(h base2.Hasher)
  • func (e *GroupExpression) Init(h base2.Hasher)
  • func (e *GroupExpression) IsAbandoned() bool
  • func (e *GroupExpression) IsExplored(i uint) bool
  • func (e *GroupExpression) SetAbandoned()
  • func (e *GroupExpression) SetExplored(i uint)
  • func (e *GroupExpression) String(w util.StrBufferWriter)
• type GroupID
• type GroupIDGenerator
  • func (gi *GroupIDGenerator) NextGroupID() GroupID
• type Memo
  • func NewMemo() *Memo
  • func (mm *Memo) CopyIn(target *Group, lp base.LogicalPlan) (*GroupExpression, error)
  • func (mm *Memo) ForEachGroup(f func(g *Group) bool)
  • func (mm *Memo) GetGroupID2Group() map[GroupID]*list.Element
  • func (mm *Memo) GetGroups() *list.List
  • func (mm *Memo) GetHasher() base2.Hasher
  • func (mm *Memo) GetRootGroup() *Group
  • func (mm *Memo) Init(plan base.LogicalPlan) (*GroupExpression, error)
  • func (mm *Memo) InsertGroupExpression(groupExpr *GroupExpression, target *Group) (*GroupExpression, bool)
  • func (mm *Memo) NewGroup() *Group
  • func (mm *Memo) NewGroupExpression(lp base.LogicalPlan, inputs []*Group) *GroupExpression

Types

type Group

type Group struct {

	// Operand2FirstExpr is used to locate to the first same type logicalExpression list.
	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) Delete

func (g *Group) Delete(e *GroupExpression)

Delete an existing Group expression

func (*Group) Equals

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

Equals implements the HashEquals.<1st> interface.

func (*Group) ForEachGE

func (g *Group) ForEachGE(f func(ge *GroupExpression) bool)

ForEachGE traverse the inside group expression with f call on them each.

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) GetLogicalProperty

func (g *Group) GetLogicalProperty() *property.LogicalProperty

GetLogicalProperty return this group's logical property.

func (*Group) HasLogicalProperty

func (g *Group) HasLogicalProperty() bool

HasLogicalProperty check whether current group has the logical property.

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) IsExplored

func (g *Group) IsExplored() bool

IsExplored returns whether this group is explored.

func (*Group) SetExplored

func (g *Group) SetExplored()

SetExplored set the group as tagged as explored.

func (*Group) SetLogicalProperty

func (g *Group) SetLogicalProperty(prop *property.LogicalProperty)

SetLogicalProperty set this group's logical property.

func (*Group) String

func (g *Group) String(w util.StrBufferWriter)

String implements fmt.Stringer interface.

type GroupExpression

type GroupExpression struct {
	// LogicalPlan is internal logical expression stands for this groupExpr.
	// Define it in the header element can make GE as Logical Plan implementor.
	base.LogicalPlan

	// 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 (*GroupExpression) DeriveLogicalProp

func (e *GroupExpression) DeriveLogicalProp() (err error)

DeriveLogicalProp derive the new group's logical property from a specific GE. DeriveLogicalProp is not called with recursive, because we only examine and init new group from bottom-up, so we can sure that this new group's children has already gotten its logical prop.

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) GetHash64

func (e *GroupExpression) GetHash64() uint64

GetHash64 returns the cached hash64 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) IsAbandoned

func (e *GroupExpression) IsAbandoned() bool

IsAbandoned returns whether this gE is abandoned.

func (*GroupExpression) IsExplored

func (e *GroupExpression) IsExplored(i uint) bool

IsExplored return whether this gE has explored rule i.

func (*GroupExpression) SetAbandoned

func (e *GroupExpression) SetAbandoned()

SetAbandoned set this gE as abandoned.

func (*GroupExpression) SetExplored

func (e *GroupExpression) SetExplored(i uint)

SetExplored set this gE as explored in rule i.

func (*GroupExpression) String

func (e *GroupExpression) String(w util.StrBufferWriter)

String implements the fmt.Stringer interface.

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() *Memo

NewMemo creates a new memo.

func (*Memo) CopyIn

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

CopyIn copies a MemoExpression representation into the memo with format as GroupExpression inside. The generic logical forest inside memo is represented as memo group expression tree, while for entering and re-feeding the memo, we use the memoExpression as the currency：

entering(init memo)

  lp                          ┌──────────┐
 /  \                         │ memo:    │
lp   lp       --copyIN->      │  G(ge)   │
    /  \                      │   /  \   │
  ...  ...                    │  G    G  │
                              └──────────┘

re-feeding (intake XForm output)

  lp                          ┌──────────┐
 /  \                         │ memo:    │
GE  lp        --copyIN->      │  G(ge)   │
     |                        │   /  \   │
    GE                        │  G    G  │
                              └──────────┘

the bare lp means the new created logical op or that whose child has changed which invalidate it's original old belonged group, make it back to bare-lp for re-inserting again in copyIn.

func (*Memo) ForEachGroup

func (mm *Memo) ForEachGroup(f func(g *Group) bool)

ForEachGroup traverse the inside group expression with f call on them each.

func (*Memo) GetGroupID2Group

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

GetGroupID2Group gets the map from group id to group.

func (*Memo) GetGroups

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

GetGroups gets all groups in the memo.

func (*Memo) GetHasher

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

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

func (*Memo) GetRootGroup

func (mm *Memo) GetRootGroup() *Group

GetRootGroup gets the root group of the memo.

func (*Memo) Init

func (mm *Memo) Init(plan base.LogicalPlan) (*GroupExpression, error)

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

func (*Memo) InsertGroupExpression

func (mm *Memo) InsertGroupExpression(groupExpr *GroupExpression, target *Group) (*GroupExpression, bool)

InsertGroupExpression insert ge into a target group. @GroupExpression indicates the returned group expression, which may be the existed one or the newly inserted. @bool indicates whether the groupExpr is inserted to a new group.

func (*Memo) NewGroup

func (mm *Memo) NewGroup() *Group

NewGroup creates a new group.

func (*Memo) NewGroupExpression

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

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