MySQL 9.1.0
Source Code Documentation
hypergraph Namespace Reference

Classes

struct  Hyperedge
 
struct  Hypergraph
 
class  NeighborhoodCache
 
struct  Node
 

Typedefs

using NodeMap = uint64_t
 Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 64-bit bit sets. More...
 

Functions

template<class T >
static void RemoveElement (const T &element, std::vector< T > *vec)
 
bool IsSimpleEdge (NodeMap left, NodeMap right)
 Is an edge between "left" and "right" a simple edge? More...
 
template<class Receiver >
bool EnumerateAllConnectedPartitions (Receiver *receiver)
 
std::string PrintSet (NodeMap x)
 
NodeMap FindNeighborhood (const Hypergraph &g, NodeMap subgraph, NodeMap forbidden, NodeMap just_grown_by, NeighborhoodCache *cache, NodeMap *full_neighborhood_arg)
 Find the neighborhood of the given subgraph (S); informally, the set of nodes immediately reachable from that subgraph. More...
 
template<class Receiver >
bool EnumerateComplementsTo (const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap full_neighborhood, NodeMap neighborhood, Receiver *receiver)
 
template<class Receiver >
bool ExpandSubgraph (const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap full_neighborhood, NodeMap neighborhood, NodeMap forbidden, Receiver *receiver)
 
template<class Receiver >
bool TryConnecting (const Hypergraph &g, NodeMap subgraph, NodeMap subgraph_full_neighborhood, NodeMap complement, Receiver *receiver)
 
template<class Receiver >
bool ExpandComplement (const Hypergraph &g, size_t lowest_node_idx, NodeMap subgraph, NodeMap subgraph_full_neighborhood, NodeMap complement, NodeMap neighborhood, NodeMap forbidden, Receiver *receiver)
 
template<class Receiver >
bool EnumerateAllConnectedPartitions (const Hypergraph &g, Receiver *receiver)
 

Typedef Documentation

◆ NodeMap

using hypergraph::NodeMap = typedef uint64_t

Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 64-bit bit sets.

This allows for a compact representation and very fast set manipulation; the algorithm does a fair amount of intersections and unions. If we should need extensions to larger graphs later (this will require additional heuristics for reducing the search space), we can use dynamic bit sets, although at a performance cost (we'd probably templatize off the NodeMap type).

Function Documentation

◆ EnumerateAllConnectedPartitions() [1/2]

template<class Receiver >
bool hypergraph::EnumerateAllConnectedPartitions ( const Hypergraph g,
Receiver *  receiver 
)

◆ EnumerateAllConnectedPartitions() [2/2]

template<class Receiver >
bool hypergraph::EnumerateAllConnectedPartitions ( Receiver *  receiver)

◆ EnumerateComplementsTo()

template<class Receiver >
bool hypergraph::EnumerateComplementsTo ( const Hypergraph g,
size_t  lowest_node_idx,
NodeMap  subgraph,
NodeMap  full_neighborhood,
NodeMap  neighborhood,
Receiver *  receiver 
)

◆ ExpandComplement()

template<class Receiver >
bool hypergraph::ExpandComplement ( const Hypergraph g,
size_t  lowest_node_idx,
NodeMap  subgraph,
NodeMap  subgraph_full_neighborhood,
NodeMap  complement,
NodeMap  neighborhood,
NodeMap  forbidden,
Receiver *  receiver 
)

◆ ExpandSubgraph()

template<class Receiver >
bool hypergraph::ExpandSubgraph ( const Hypergraph g,
size_t  lowest_node_idx,
NodeMap  subgraph,
NodeMap  full_neighborhood,
NodeMap  neighborhood,
NodeMap  forbidden,
Receiver *  receiver 
)

◆ FindNeighborhood()

NodeMap hypergraph::FindNeighborhood ( const Hypergraph g,
NodeMap  subgraph,
NodeMap  forbidden,
NodeMap  just_grown_by,
NeighborhoodCache cache,
NodeMap full_neighborhood_arg 
)
inline

Find the neighborhood of the given subgraph (S); informally, the set of nodes immediately reachable from that subgraph.

There's an additional constraint in that the edges used to do so must not touch the forbidden set of nodes (X). The DPhyp paper calls this function N(S, X) (with a calligraphic N).

How to calculate the neighborhood efficiently is one of the least explicitly described parts of the paper. The definition goes about as follows:

  1. Find E↓'(S,X), the set of “interesting hypernodes” (outgoing edge destinations from S). These are the (endpoints of) edges that have one side entirely within S, that have the other side entirely outside S, and none of the sides touch the forbidden set X.
  2. Minimize E↓'(S,X) by removing all “subsumed hypernodes”, giving E↓(S,X). u subsumes v if it is a proper subset; if so, we can never go to where v points to before we've been at u, so it's pointless to keep v.
  3. For each hypernode in E↓(S,X), pick node with lowest index as a representative, because our subset enumeration algorithms cannot enumerate subsets of hypernodes, only subsets of normal nodes. (Actually, any node that's part of the hypernode would do; it does not even need to be consistent.) These nodes together constitute the neighborhood.

There are a couple of points to note here:

First, adding more nodes than needed to the neighborhood does not affect correctness of the algorithm, only speed. We try all combinations of included/excluded for the neighborhood (2^N in the number of nodes), so this covers all potential subgraphs; in theory, we could even just choose all non-forbidden nodes and reduce to the algorithm known as DPhyp, it just wouldn't be very efficient.

Second, step 3 means that we may very well end up with a non-connected subgraph. This is harmless; we may eventually grow it to a connected one or we may not, we just won't start looking for any complements until we have a connected one (and we know whether it's connected or not based on whether we saw it as a csg-cmp pair in the algorithm earlier).

Third, due to the way we grow our subgraph, only the nodes that we have just grown by can contribute to the E↓'(S,X). The reason is simple; every node from the previous neighborhood will have been added either to S or to X, and both exclude them from the new neighborhood. (Step 2 doesn't affect this, as any hypernode that was subsumed would also have to touch S or X. But there's an exception in that occasionally, we can remove nodes from X; see ExpandSubgraph().)

Fourth, perfect minimization seems to be impossible to actually implement efficiently. This is known as the minimum set problem, and the best known algorithms to do this are in O(n² / log n) time (see e.g. Pritchard: ”An Old Sub-Quadratic Algorithm for Finding Extremal Sets”), which can be quite a lot when there are lots of edges. (The trivial O(n²) algorithm is to just test every set against every smaller set, and throw it out if it's a superset.) Since loops in our hypergraphs are presumed to be fairly rare, it would not seem worth it to do full minimization.

Instead, we pick the low-hanging fruit only: Every simple edge is trivial to test against. We just collect the simple edges into a mask, and any (complex) hyperedge that overlaps with that bitmap can immediately be discarded. Even more, since we don't have to pick min(S) but can pick something arbitrary, we can let {R2,R3} (which gets R2 as its representative node) subsume {R1,R2}, even though it's not an actual subset, by pretending we picked R2 as the representative node for the latter! This is similar to what Moerkotte describes in his “Building Query Compilers” document, which seems to contain a slightly extended version of the DPhyp paper (under a different name). We could have collected all the simple edges in a separate pass first, but the microbenchmarks show that the added loop overhead isn't worth it.

Note that we also keep E↓'(S,X), the set of interesting hypernodes; we bitwise-or it into “full_neighborhood”. This is useful later when searching for edges to connect the connected subgraph and its complement; we know that only edges into “full_neighborhood” can connect the two.

This function accounts for roughly 20–70% of the total DPhyp running time, depending on the shape of the graph (~40% average across the microbenchmarks). It is fairly big to inline, but it helps speed significantly, probably due to the large amount of parameters to be passed back and forth.

◆ IsSimpleEdge()

bool hypergraph::IsSimpleEdge ( NodeMap  left,
NodeMap  right 
)
inline

Is an edge between "left" and "right" a simple edge?

◆ PrintSet()

std::string hypergraph::PrintSet ( NodeMap  x)
inline

◆ RemoveElement()

template<class T >
static void hypergraph::RemoveElement ( const T &  element,
std::vector< T > *  vec 
)
static

◆ TryConnecting()

template<class Receiver >
bool hypergraph::TryConnecting ( const Hypergraph g,
NodeMap  subgraph,
NodeMap  subgraph_full_neighborhood,
NodeMap  complement,
Receiver *  receiver 
)