Join Order calculator

join.go

package join

type Table struct {
	Name string
	Selectivity float64
}

func (t *Table) String() string {
	return t.Name
}

func newTable(name string, selectivity float64) *Table {
	return &Table{Name: name, Selectivity: selectivity}
}

const (
	joinTypeLeft = iota + 1
	joinTypeRight
	joinTypeInner
)

type joint struct {
	A *Table
	IndexA bool
	B *Table
	IndexB bool
}

func newJoint(a *Table, idxA bool,  b *Table, idxB bool) *joint {
	return &joint{A:a, IndexA: idxA, B:b, IndexB: idxB}
}

type graph struct {
	nodes map[string]*graphNode
}

func newGraph() *graph {
	return &graph{
		nodes : map[string]*graphNode{},
	}
}

type graphNode struct {
	t *Table
	srcs []*graphNode
	srcIdx []bool
	dests []*graphNode
	destIdx []bool
}

func (n *graphNode) isSource() bool {
	for _, src := range n.srcs {
		if src != nil {
			return false
		}
	}
	return true
}

func (n *graphNode) deleteSource(name string) {
	for i, src := range n.srcs {
		if src != nil && src.t.Name == name {
			n.srcs[i] = nil
		}
	}
}

func (n *graphNode) addSource(src *graphNode, hasIndex bool) {
	for _, src := range n.srcs {
		if src.t.Name == src.t.Name {
			return
		}
	}
	n.srcs = append(n.srcs, src)
	n.srcIdx = append(n.srcIdx, hasIndex)
}

func (n *graphNode) addDest(dest *graphNode, hasIndex bool) {
	for _, src := range n.srcs {
		if src.t.Name == src.t.Name {
			return
		}
	}
	n.dests = append(n.dests, dest)
	n.destIdx = append(n.destIdx, hasIndex)
}

type joinOrder struct {
	tables []*Table
	cost float64
	rowCount float64
}

// BuildJoinOrder builds a join from tables and joints.
func BuildJoinOrder(tables []*Table, joints []*joint) *joinOrder {
	fullGraph := buildFullGraph(tables, joints)
	connectedGraphs := splitGraph(fullGraph)
	var orders []*joinOrder
	for _, g := range connectedGraphs {
		orders = append(orders, buildJoinOrderFromConnectedGraph(g))
	}
	return
}

func buildFullGraph(tables []*Table, joints []*joint) *graph {
	fullGraph := newGraph()
	for _, t := range tables {
		fullGraph.nodes[t.Name] = &graphNode{t: t}
	}

	for _, join := range joints {
		nodeA := fullGraph.nodes[join.A.Name]
		nodeB := fullGraph.nodes[join.B.Name]

		nodeA.addSource(nodeB, join.IndexA)
		nodeB.addDest(nodeA, join.IndexA)

		nodeA.addDest(nodeB, join.IndexB)
		nodeB.addSource(nodeA, join.IndexB)
	}
	return fullGraph
}

// splitGraph splits tableGraph into multiple connected sub graphs.
func splitGraph(fullGraph *graph) []*graph {
	var connectedGraphs []*graph
	for _, va := range fullGraph.nodes {
		connected := buildConnectedGraph(va, nil)
		for _, cg := range connected.nodes {
			delete(fullGraph, cg.t.Name)
		}
		connectedGraphs = append(connectedGraphs, connected)
	}
	return connectedGraphs
}

// recursively build connected graph from a node.
func buildConnectedGraph(node *graphNode, g *graph) *graph {
	if g == nil {
		g = newGraph()
	}
	if g.nodes[node.t.Name] == nil {
		g.nodes[node.t.Name] = node
		for _, src := range node.srcs {
			buildConnectedGraph(src, g)
		}
	}
	return g
}

func mergeJoinOrders(orders []*joinOrder) *joinOrder {
	return nil
}

func buildJoinOrderFromConnectedGraph(graph *graph) *joinOrder {
	dagGraph := buildDagGraph(graph)

	dagOrders := allDagOrders(dagGraph)
	var bestOrder *joinOrder
	var bestCost float64
	for _, dagOrder := range dagOrders {
		jOrder := joinOrderFromDagOrder(dagOrder)
		if bestOrder == nil {
			bestOrder = jOrder
			bestCost = jOrder.cost
		} else if jOrder.cost < bestCost {
			bestOrder = jOrder
			bestCost = jOrder.cost
		}
	}
	return bestOrder
}

type dagGraphNode struct {
	strongComponent []*graphNode

	srcs []*dagGraphNode
	dests []*dagGraphNode
}

type dagGraph struct {
	nodes map[string]*dagGraphNode
}

func buildDagGraph(graph *graph) *dagGraph {
	return nil
}

func allDagOrders(dagGraph *dagGraph) [][]*dagGraphNode {
	return nil
}

func joinOrderFromDagOrder(dagOrder []*dagGraphNode) *joinOrder {
	return nil
}