import sys, pathlib

# Put the repo root (the directory containing `system/`) on sys.path so
# `from system...` works whether this notebook is opened from its own
# folder or from the repo root.
for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
    if (_p / "system").is_dir():
        if str(_p) not in sys.path:
            sys.path.insert(0, str(_p))
        break

from typing import Type, Iterator

import numpy as np
import matplotlib.pyplot as plt
from abc import ABC, abstractmethod

Matplotlib is building the font cache; this may take a moment.

from system.interfaces.cost_functions import CostFunction
from system.query_optimization.cardinality_table import CardinalityTable
from system.query_optimization.join_graph import JoinGraph


class PlanEnumerator(ABC):
    """
    Abstract enumerator class to enumerate the join plans for a given join graph.
    """

    @abstractmethod
    def enumerate(
        self,
        join_graph: JoinGraph,
        cardinality_table: CardinalityTable,
        cost_function: CostFunction,
        print_info: bool = False,
    ) -> tuple[int, tuple, int]:
        """
        Computes and returns the best join order for the given problem sizes.
        # TODO: join order vs join plan
        :param join_graph: The join graph.
        :param cardinality_table: The cardinality table to be used.
        :param cost_function: A cost function determining the cost of different operations.
        :param print_info: A flag indicating whether additional info should be printed during enumeration.
        :return: A tuple, consisting of the costs of the best plan, the best plan as a tuple and the number of pairs that were enumerated.
        """

from system.query_optimization.problems import Problem
from system.query_optimization.plan_table import SizeBasedPlanTable


class DP_Size(PlanEnumerator):
    """
    DPsize uses a size-based problem enumeration, i.e. it enumerates problems of increasing sizes. During the enumeration, it does
    not consider the actual join graph, which means that Cartesian Products, as well as disconnected join pairs will be enumerated. In other words,
    we also enumerate cross products in the algorithm (but then discard them).
    """

    def enumerate(
        self,
        join_graph: JoinGraph,
        cardinality_table: CardinalityTable,
        cost_function: CostFunction,
        print_info: bool = False,
    ) -> tuple[int, tuple, int]:
        """
        Computes and returns the best join order for the given problem sizes.
        :param join_graph: The join graph.
        :param cardinality_table: The cardinality table to be used.
        :param cost_function: A cost function determining the cost of different operations.
        :param print_info: A flag indicating whether additional info should be printed during enumeration.
        :return: A tuple consisting of: the costs of the best plan, the best plan as a tuple and the number of pairs that were enumerated.
        """

        # Initialize plan table with the join graph
        # A size plan table stores entries according to their problem size, which
        # allows iterating through existing problems based on their size
        plan_table: SizeBasedPlanTable = SizeBasedPlanTable(
            join_graph, cost_function, cardinality_table
        )

        # Count number of pairs that were enumerated
        enumerated_pairs: int = 0

        # Count number of valid pairs
        valid_pairs: int = 0

        # Go through each pair generated by the enumerator below
        # It still needs to make sure that both problems are actually
        # connected and that they are disjoint.
        for s1, s2 in self.__generate_pairs_size_based(join_graph, plan_table):
            # Both s1 and s2 will already be in the plan table
            enumerated_pairs += 1

            # Check whether s1 and s2 are disjoint. Pairs which are not disjoint
            # are no valid pairs. They also need to be connected in the join graph.
            # this condition could be removed to also enumerate disconnected problems, i.e. cross products
            if not s1.intersects(s2) and join_graph.are_connected(s1, s2):
                valid_pairs += 1

                # Update the table with the newly generated pair
                plan_table.update_table(s1, s2, cardinality_table, cost_function)
                if print_info:
                    print(f"Enumerated valid pair {s1.as_set()}, {s2.as_set()}.")
            else:
                if print_info:
                    print(f"Enumerated invalid pair {s1.as_set()}, {s2.as_set()}.")

        problem_with_all_relations: Problem = Problem.get_problem_with_all_relations(
            len(join_graph)
        )

        if print_info:
            print(
                f"{enumerated_pairs} pairs were enumerated, out of which {valid_pairs} were valid!"
            )

        return (
            plan_table.get_costs_for_problem(problem_with_all_relations),
            plan_table.get_plan_for_problem(problem_with_all_relations),
            enumerated_pairs,
        )

    def __generate_pairs_size_based(
        self, join_graph: JoinGraph, plan_table: SizeBasedPlanTable
    ) -> Iterator[tuple[Problem, Problem]]:
        """
        Enumerate through the search space by utilizing the size of problems.
        :param join_graph: The join graph.
        :param plan_table: The underlying plan table.
        """
        num_nodes: int = len(join_graph.adjacency_matrix)
        # Enumerate all possible problem sizes starting from 2
        for main_size in range(2, num_nodes + 1):
            # Enumerate all sizes that are smaller than size_1 // 2
            # to avoid duplicate work.
            for s1_size in range(1, (main_size // 2) + 1):
                s2_size: int = main_size - s1_size

                # If both sizes are equal, you need to evaluate symmetric pairs only once
                if s1_size == s2_size:
                    # Enumerate all problems of size s1_size
                    for i, s1 in enumerate(plan_table.entries_with_size(s1_size)):
                        # Evaluated entries can be addressed by an index
                        # Enumerate all problems of size s2_size, and start with index i + 1
                        # to avoid having to re-enumerate symmetric pairs
                        for s2 in plan_table.entries_with_size(s2_size, i + 1):
                            # New pair was generated
                            yield s1, s2
                else:
                    # Enumerate all problems of size s1_size
                    for s1 in plan_table.entries_with_size(s1_size):
                        # Enumerate all problems of size s2_size
                        for s2 in plan_table.entries_with_size(s2_size):
                            # New pair was generated
                            yield s1, s2

from system.query_optimization.cost_function import C_Out
from system.query_optimization.utils import randomize_cardinalities, print_results
from system.query_optimization.join_graph import CycleQueryFactory

# Construct a cycle query with 4 nodes. Therefore, this query has the following structure:
# 0 -- 1
# |    |
# 2 -- 3
cycle_query = CycleQueryFactory.construct_join_graph(4)

# Define a Cardinality Table, i.e. a table estimating the sizes of problems.
# For this demonstration, we just randomize them, i.e. they do not represent realistic data by any means
cardinality_table: CardinalityTable = CardinalityTable()
randomize_cardinalities(cardinality_table, 4, 42)

# Start the enumeration, use C_out as the underlying cost function
results = DP_Size().enumerate(
    join_graph=cycle_query,
    cardinality_table=cardinality_table,
    cost_function=C_Out(),
    print_info=True,
)
print_results(results)

Enumerated valid pair {0}, {1}.
Enumerated invalid pair {0}, {2}.
Enumerated valid pair {0}, {3}.
Enumerated valid pair {1}, {2}.
Enumerated invalid pair {1}, {3}.
Enumerated valid pair {2}, {3}.
Enumerated invalid pair {0}, {0, 1}.
Enumerated invalid pair {0}, {0, 3}.
Enumerated valid pair {0}, {1, 2}.
Enumerated valid pair {0}, {2, 3}.
Enumerated invalid pair {1}, {0, 1}.
Enumerated valid pair {1}, {0, 3}.
Enumerated invalid pair {1}, {1, 2}.
Enumerated valid pair {1}, {2, 3}.
Enumerated valid pair {2}, {0, 1}.
Enumerated valid pair {2}, {0, 3}.
Enumerated invalid pair {2}, {1, 2}.
Enumerated invalid pair {2}, {2, 3}.
Enumerated valid pair {3}, {0, 1}.
Enumerated invalid pair {3}, {0, 3}.
Enumerated valid pair {3}, {1, 2}.
Enumerated invalid pair {3}, {2, 3}.
Enumerated invalid pair {0}, {0, 1, 2}.
Enumerated invalid pair {0}, {0, 2, 3}.
Enumerated invalid pair {0}, {0, 1, 3}.
Enumerated valid pair {0}, {1, 2, 3}.
Enumerated invalid pair {1}, {0, 1, 2}.
Enumerated valid pair {1}, {0, 2, 3}.
Enumerated invalid pair {1}, {0, 1, 3}.
Enumerated invalid pair {1}, {1, 2, 3}.
Enumerated invalid pair {2}, {0, 1, 2}.
Enumerated invalid pair {2}, {0, 2, 3}.
Enumerated valid pair {2}, {0, 1, 3}.
Enumerated invalid pair {2}, {1, 2, 3}.
Enumerated valid pair {3}, {0, 1, 2}.
Enumerated invalid pair {3}, {0, 2, 3}.
Enumerated invalid pair {3}, {0, 1, 3}.
Enumerated invalid pair {3}, {1, 2, 3}.
Enumerated invalid pair {0, 1}, {0, 3}.
Enumerated invalid pair {0, 1}, {1, 2}.
Enumerated valid pair {0, 1}, {2, 3}.
Enumerated valid pair {0, 3}, {1, 2}.
Enumerated invalid pair {0, 3}, {2, 3}.
Enumerated invalid pair {1, 2}, {2, 3}.
44 pairs were enumerated, out of which 18 were valid!
The best join plan is (3⋈((1⋈0)⋈2)) with costs 2011! Overall, we needed to enumerate 44 pairs.

from system.query_optimization.plan_table import StandardPlanTable
from system.interfaces.query_optimization.planning import PlanTable


class DP_Sub(PlanEnumerator):
    """
    DPsub generates all possible pairs for each connected problem. It still generates Cartesian Products, that need to be filtered out.
    """

    def enumerate(
        self,
        join_graph: JoinGraph,
        cardinality_table: CardinalityTable,
        cost_function: CostFunction,
        print_info: bool = False,
    ) -> tuple[int, tuple, int]:
        """
        Computes and returns the best join order for the given problem sizes.
        :param join_graph: The join graph.
        :param cardinality_table: The cardinality table to be used.
        :param cost_function: A cost function determining the cost of different operations.
        :param print_info: A flag indicating whether additional info should be printed during enumeration.
        :return: A tuple, consisting of the costs of the best plan, the best plan as a tuple and the number of pairs that were enumerated.
        """
        # Initialize plan table with the join graph
        plan_table: PlanTable = StandardPlanTable(
            join_graph, cost_function, cardinality_table
        )

        # Count number of pairs that were enumerated
        enumerated_pairs: int = 0
        # Count number of valid pairs
        valid_pairs: int = 0

        # Go through each generated pair and make sure that both problems s1 and s2
        # are connected
        for s1, s2 in self.__generate_pairs_sub_based(join_graph):
            enumerated_pairs += 1
            # s1 | s2 is guaranteed to be connected and disjoint as this point
            # We still need to check whether s1 and s2 themselves are connected
            # s1 and s2 are connected if they are contained in the plan table
            # meaning they were enumerated as a valid problem at an earlier point
            if s1 in plan_table and s2 in plan_table:
                valid_pairs += 1
                # Update the table with the newly generated pair
                plan_table.update_table(s1, s2, cardinality_table, cost_function)
                if print_info:
                    print(f"Enumerated valid pair {s1.as_set()}, {s2.as_set()}")
            else:
                if print_info:
                    print(f"Enumerated invalid pair {s1.as_set()}, {s2.as_set()}")

        problem_with_all_relations: Problem = Problem.get_problem_with_all_relations(
            len(join_graph)
        )

        if print_info:
            print(
                f"{enumerated_pairs} pairs were enumerated, out of which {valid_pairs} were valid"
            )

        return (
            plan_table.get_costs_for_problem(problem_with_all_relations),
            plan_table.get_plan_for_problem(problem_with_all_relations),
            enumerated_pairs,
        )

    def __generate_pairs_sub_based(
        self, join_graph: JoinGraph
    ) -> Iterator[tuple[Problem, Problem]]:
        """
        Generate the required pairs by enumerating all possible problems.
        :param join_graph: The join graph.
        """
        num_nodes: int = len(join_graph.adjacency_matrix)
        # Enumerate all problems by increasing the underlying problem number
        for i in range(1, 1 << num_nodes):
            # Find the best plan for this problem
            main_problem: Problem = Problem(i)

            # Singletons do not have to be considered
            if len(main_problem) == 1:
                continue

            # The problem also needs to be connected, otherwise
            # it would not be a valid problem
            if not join_graph.is_connected(main_problem):
                continue

            # Again, there is no need to enumerate symmetric pair twice, which can be achieved
            # by stopping the enumeration after the first half is done.
            # Setting the stop problem exactly to the singleton pointing to the
            # position of the MSB stops the enumeration exactly at this point
            stop_problem: Problem = main_problem.get_most_significant_bit()
            # Start the enumeration with the smallest singleton of the main problem, stop when the stop problem has been reached
            for s1 in Problem.enumerate_all_problems(
                main_problem, stop_problem=stop_problem
            ):
                # Generate the corresponding partner subset
                # Given that s1 | s2 == main_problem, we know s1 and s2 are connected via at least one join edge
                s2: Problem = main_problem - s1
                # New pair was generated
                yield s1, s2

results = DP_Sub().enumerate(
    join_graph=cycle_query,
    cardinality_table=cardinality_table,
    cost_function=C_Out(),
    print_info=True,
)
print_results(results)

Enumerated valid pair {0}, {1}
Enumerated valid pair {1}, {2}
Enumerated valid pair {0}, {1, 2}
Enumerated invalid pair {1}, {0, 2}
Enumerated valid pair {0, 1}, {2}
Enumerated valid pair {0}, {3}
Enumerated invalid pair {0}, {1, 3}
Enumerated valid pair {1}, {0, 3}
Enumerated valid pair {0, 1}, {3}
Enumerated valid pair {2}, {3}
Enumerated valid pair {0}, {2, 3}
Enumerated valid pair {2}, {0, 3}
Enumerated invalid pair {0, 2}, {3}
Enumerated valid pair {1}, {2, 3}
Enumerated invalid pair {2}, {1, 3}
Enumerated valid pair {1, 2}, {3}
Enumerated valid pair {0}, {1, 2, 3}
Enumerated valid pair {1}, {0, 2, 3}
Enumerated valid pair {0, 1}, {2, 3}
Enumerated valid pair {2}, {0, 1, 3}
Enumerated invalid pair {0, 2}, {1, 3}
Enumerated valid pair {1, 2}, {0, 3}
Enumerated valid pair {0, 1, 2}, {3}
23 pairs were enumerated, out of which 18 were valid
The best join plan is (3⋈((1⋈0)⋈2)) with costs 2011! Overall, we needed to enumerate 23 pairs.

def generate_connected_problems(join_graph: JoinGraph) -> Iterator[Problem]:
    """
    Generate all connected problems of the join graph, according to the description given above.
    :param join_graph: The join graph.
    """
    problem_with_all_relations: Problem = Problem.get_problem_with_all_relations(
        len(join_graph)
    )

    # Top-level exclude set, always ignore neighbors whose order is <= than the current singleton. See the cell above for more details.
    exclude: Problem = problem_with_all_relations

    # Traverse all singleton sets (sets containing only one relation) as starting point. Go from the highest bit to the lowest bit.
    for singleton in reversed(problem_with_all_relations):
        yield singleton

        # Recursively extend the singleton with all its neighbors, as long as the order of the neighbor is not lower/equal than the singleton
        yield from generate_recursively(join_graph, singleton, exclude)

        # Current problem can now be considered
        exclude -= singleton


def generate_recursively(
    join_graph: JoinGraph,
    start: Problem,
    exclude: Problem,
) -> Iterator[Problem]:
    """
    Recursively extends the given start problem with its neighbors. Ignores relations contained in the exclude problem.
    :param join_graph: The join graph.
    :param start: The start problem.
    :param exclude: The exclude problem.
    """
    # Get direct neighbors of the problem, ignore those from the exclude set
    neighbors: Problem = join_graph.get_neighbors(start) - exclude

    # Get all problems contained in the neighbor set
    neighbor_problems: list[Problem] = Problem.get_all_problems(neighbors)

    # Combine all neighbor problems with the start problem
    for neighbor_problem in neighbor_problems:
        yield start | neighbor_problem

    for neighbor_problem in neighbor_problems:
        # Proceed recursively, extend the exclude set with the current neighbors
        yield from generate_recursively(
            join_graph,
            start | neighbor_problem,
            exclude | neighbors,
        )

for problem in generate_connected_problems(cycle_query):
    print(f"{problem}")

{3}
{2}
{2, 3}
{1}
{1, 2}
{1, 2, 3}
{0}
{0, 1}
{0, 3}
{0, 1, 3}
{0, 1, 2}
{0, 2, 3}
{0, 1, 2, 3}

def generate_ccp_pairs(join_graph: JoinGraph) -> Iterator[tuple[Problem, Problem]]:
    """
    Enumerate all ccp pairs of the given join graph.
    :param join_graph: The join graph.
    """
    for csg in generate_connected_problems(join_graph):
        # We do not want the csg_problem to be contained in any cmp problem at any problem
        # We also always want to ignore cmp problems that contain relations whose number is smaller than the smallest in the csg
        always_exclude_set: Problem = csg | csg.get_smaller_or_equal_relations()

        # Start the enumeration of the cmp problems with the direct neighbors of the csg problem
        csg_neighbors: Problem = join_graph.get_neighbors(csg) - always_exclude_set

        # Define an additional top-level ignore set, we still want to ignore all problems with smaller/equal numbers than the current problem
        # This time, however, we only enumerate the direct neighbors of the csg, thus we need to gradually reduce the neighbor set, instead of the whole problem.
        exclude_set: Problem = csg_neighbors

        # Again traverse all singleton problems in reversed order
        for singleton in reversed(csg_neighbors):
            yield csg, singleton

            # The exclude_set is gradually reduced, we still need to make sure that we never include a relation from the always_exclude_set
            # Make use of the already defined recursive function, as the required behavior here is exactly the same.
            for cmp_problem in generate_recursively(
                join_graph,
                singleton,
                exclude_set | always_exclude_set,
            ):
                yield csg, cmp_problem

            # Current problem can now be considered
            exclude_set -= singleton

for ccp_pair in generate_ccp_pairs(cycle_query):
    print(f"Enumerated ccp pair ({ccp_pair[0].as_set()}, {ccp_pair[1].as_set()})")

Enumerated ccp pair ({2}, {3})
Enumerated ccp pair ({1}, {2})
Enumerated ccp pair ({1}, {2, 3})
Enumerated ccp pair ({1, 2}, {3})
Enumerated ccp pair ({0}, {3})
Enumerated ccp pair ({0}, {2, 3})
Enumerated ccp pair ({0}, {1})
Enumerated ccp pair ({0}, {1, 2})
Enumerated ccp pair ({0}, {1, 2, 3})
Enumerated ccp pair ({0, 1}, {3})
Enumerated ccp pair ({0, 1}, {2})
Enumerated ccp pair ({0, 1}, {2, 3})
Enumerated ccp pair ({0, 3}, {2})
Enumerated ccp pair ({0, 3}, {1})
Enumerated ccp pair ({0, 3}, {1, 2})
Enumerated ccp pair ({0, 1, 3}, {2})
Enumerated ccp pair ({0, 1, 2}, {3})
Enumerated ccp pair ({0, 2, 3}, {1})

class DP_CCP(PlanEnumerator):
    """
    Uses the join graph to enumerate all ccp pairs, without enumerating any invalid pair.
    """

    def enumerate(
        self,
        join_graph: JoinGraph,
        cardinality_table: CardinalityTable,
        cost_function: CostFunction,
        print_info: bool = False,
    ) -> tuple[int, tuple, int]:
        """
        Computes and returns the best join order for the given problem sizes.
        :param join_graph: The join graph.
        :param cardinality_table: The cardinality table to be used.
        :param cost_function: A cost function determining the cost of different operations.
        :param print_info: A flag indicating whether additional info should be printed during enumeration.
        :return: A tuple, consisting of the costs of the best plan, the best plan as a tuple and the number of pairs that were enumerated.
        """
        # Initialize plan table with the join graph
        plan_table: PlanTable = StandardPlanTable(
            join_graph, cost_function, cardinality_table
        )

        # Count number of pairs that were enumerated
        enumerated_pairs: int = 0

        # Use previously defined generator to iterator through each ccp
        # Note that no checks are required here anymore, as the ccp is guaranteed to be valid
        for s1, s2 in generate_ccp_pairs(join_graph):
            enumerated_pairs += 1

            if print_info:
                print(f"Enumerated valid pair {s1.as_set()}, {s2.as_set()}")

            # Update the table with the newly generated pair
            plan_table.update_table(s1, s2, cardinality_table, cost_function)

        problem_with_all_relations: Problem = Problem.get_problem_with_all_relations(
            len(join_graph)
        )

        if print_info:
            print(f"Enumerated {enumerated_pairs} valid pairs")

        return (
            plan_table.get_costs_for_problem(problem_with_all_relations),
            plan_table.get_plan_for_problem(problem_with_all_relations),
            enumerated_pairs,
        )

results = DP_CCP().enumerate(
    join_graph=cycle_query,
    cardinality_table=cardinality_table,
    cost_function=C_Out(),
    print_info=True,
)
print_results(results)

Enumerated valid pair {2}, {3}
Enumerated valid pair {1}, {2}
Enumerated valid pair {1}, {2, 3}
Enumerated valid pair {1, 2}, {3}
Enumerated valid pair {0}, {3}
Enumerated valid pair {0}, {2, 3}
Enumerated valid pair {0}, {1}
Enumerated valid pair {0}, {1, 2}
Enumerated valid pair {0}, {1, 2, 3}
Enumerated valid pair {0, 1}, {3}
Enumerated valid pair {0, 1}, {2}
Enumerated valid pair {0, 1}, {2, 3}
Enumerated valid pair {0, 3}, {2}
Enumerated valid pair {0, 3}, {1}
Enumerated valid pair {0, 3}, {1, 2}
Enumerated valid pair {0, 1, 3}, {2}
Enumerated valid pair {0, 1, 2}, {3}
Enumerated valid pair {0, 2, 3}, {1}
Enumerated 18 valid pairs
The best join plan is (3⋈((1⋈0)⋈2)) with costs 2011! Overall, we needed to enumerate 18 pairs.

from system.query_optimization.utils import (
    randomize_cardinalities_and_enumerate_join_graph,
)
from system.query_optimization.join_graph import JoinGraphFactory
import time

# Number of join-graph nodes (relations) the benchmark below runs for. The
# enumeration cost grows exponentially in the number of relations -- for the
# clique query in particular DP_Size/DP_Sub explode -- so the largest value
# dominates the total run time. We cap it at 9 to keep CI fast (~2s instead of
# ~90s). For the lecture, uncomment the range(5, 15) line to show the full
# exponential blow-up in the plots.
num_nodes: list[int] = list(range(5, 10))
# num_nodes: list[int] = list(range(5, 15))


def evaluate_algorithms_on_graphs(graph_factory: Type[JoinGraphFactory]):
    """
    Evaluate all enumeration algorithms on different graph sizes.
    :param graph_factory: A static class type used to define methods to create certain graphs.
    """
    # Store number of enumerated pairs and the required time
    result_dict: dict[str, list[int]] = {
        algorithm: [] for algorithm in ["DP_CCP", "DP_Sub", "DP_Size"]
    }
    method_dict: dict[str, PlanEnumerator] = {
        "DP_CCP": DP_CCP(),
        "DP_Sub": DP_Sub(),
        "DP_Size": DP_Size(),
    }

    # Do an experiment for each node size
    for num in num_nodes:
        # Perform the experiment for each algorithm and store the result in the dictionary from above
        for algorithm, algorithm_result_lists in result_dict.items():
            start_time = time.time()
            _, _, _ = randomize_cardinalities_and_enumerate_join_graph(
                graph_factory.construct_join_graph(num), method_dict[algorithm]
            )
            end_time = time.time()
            algorithm_result_lists.append(end_time - start_time)

    # Plot data
    x = np.arange(len(num_nodes))
    fig, ax = plt.subplots(layout="constrained", figsize=(4, 3))
    for shape, shape_list in result_dict.items():
        ax.plot(x, shape_list, label=shape)

    ax.set_ylabel("Required Enumeration time in s")
    ax.set_xlabel("# of Nodes")
    ax.set_xticks(x, num_nodes)
    fig.legend(bbox_to_anchor=(0.2, 0.99), loc="upper left")

from system.query_optimization.join_graph import ChainQueryFactory

evaluate_algorithms_on_graphs(ChainQueryFactory)

from system.query_optimization.join_graph import StarQueryFactory

evaluate_algorithms_on_graphs(StarQueryFactory)

evaluate_algorithms_on_graphs(CycleQueryFactory)

from system.query_optimization.join_graph import CliqueQueryFactory

evaluate_algorithms_on_graphs(CliqueQueryFactory)

import unittest


class EnumeratorTests(unittest.TestCase):
    def test_plan_enumerators(self):
        join_graph: JoinGraph = ChainQueryFactory.construct_join_graph(5)
        cardinality_table: CardinalityTable = CardinalityTable()
        # Set cardinalities for important problems
        # Cardinalities for Size 1
        cardinality_table.update_cardinality_estimation(Problem(0b1, 5), 5000)
        cardinality_table.update_cardinality_estimation(Problem(0b10, 5), 4000)
        cardinality_table.update_cardinality_estimation(Problem(0b100, 5), 500)
        cardinality_table.update_cardinality_estimation(Problem(0b1000, 5), 100)
        cardinality_table.update_cardinality_estimation(Problem(0b10000, 5), 1000)

        # Cardinalities for Size 2
        cardinality_table.update_cardinality_estimation(Problem(0b11, 5), 100)
        cardinality_table.update_cardinality_estimation(Problem(0b110, 5), 500)
        cardinality_table.update_cardinality_estimation(Problem(0b1100, 5), 100)
        cardinality_table.update_cardinality_estimation(Problem(0b11000, 5), 100)

        # Cardinalities for Size 3
        cardinality_table.update_cardinality_estimation(Problem(0b111, 5), 500)
        cardinality_table.update_cardinality_estimation(Problem(0b1110, 5), 50)
        cardinality_table.update_cardinality_estimation(Problem(0b11100, 5), 100)

        # Cardinalities for Size 4
        cardinality_table.update_cardinality_estimation(Problem(0b1111, 5), 10)
        cardinality_table.update_cardinality_estimation(Problem(0b11110, 5), 100)

        # Cardinalities for Size 5
        cardinality_table.update_cardinality_estimation(Problem(0b11111, 5), 10)

        best_plan: tuple = (
            (((3, 2), 1), 0),
            4,
        )
        best_costs: int = 10770
        algorithm_pairs: dict[str, int] = {
            "DP_Sub": 42,
            "DP_Size": 73,
            "DP_CCP": 20,
        }

        def _test_plan_costs(enumeration_algorithm: PlanEnumerator):
            costs, plan, enumerated_pairs = enumeration_algorithm.enumerate(
                join_graph, cardinality_table, C_Out(), False
            )
            self.assertEqual(plan, best_plan)
            self.assertEqual(costs, best_costs)
            self.assertEqual(
                enumerated_pairs,
                algorithm_pairs[enumeration_algorithm.__class__.__name__],
            )

        _test_plan_costs(DP_Size())
        _test_plan_costs(DP_Sub())
        _test_plan_costs(DP_CCP())

    def test_csg_enumeration(self):
        chain_query: JoinGraph = ChainQueryFactory.construct_join_graph(5)
        correct_csgs: list[Problem] = [
            Problem(0b10000, 5),
            Problem(0b1000, 5),
            Problem(0b11000, 5),
            Problem(0b100, 5),
            Problem(0b1100, 5),
            Problem(0b11100, 5),
            Problem(0b10, 5),
            Problem(0b110, 5),
            Problem(0b1110, 5),
            Problem(0b11110, 5),
            Problem(0b1, 5),
            Problem(0b11, 5),
            Problem(0b111, 5),
            Problem(0b1111, 5),
            Problem(0b11111, 5),
        ]

        csgs_without_duplicates: list[Problem] = list(
            generate_connected_problems(chain_query)
        )

        self.assertListEqual(csgs_without_duplicates, correct_csgs)

    def test_ccp_helper_enumeration(self):
        chain_query: JoinGraph = ChainQueryFactory.construct_join_graph(5)

        correct_ccps: list[tuple[Problem, Problem]] = [
            (Problem(0b1000, 5), Problem(0b10000, 5)),
            (Problem(0b100, 5), Problem(0b1000, 5)),
            (Problem(0b100, 5), Problem(0b11000, 5)),
            (Problem(0b1100, 5), Problem(0b10000, 5)),
            (Problem(0b10, 5), Problem(0b100, 5)),
            (Problem(0b10, 5), Problem(0b1100, 5)),
            (Problem(0b10, 5), Problem(0b11100, 5)),
            (Problem(0b110, 5), Problem(0b1000, 5)),
            (Problem(0b110, 5), Problem(0b11000, 5)),
            (Problem(0b1110, 5), Problem(0b10000, 5)),
            (Problem(0b1, 5), Problem(0b10, 5)),
            (Problem(0b1, 5), Problem(0b110, 5)),
            (Problem(0b1, 5), Problem(0b1110, 5)),
            (Problem(0b1, 5), Problem(0b11110, 5)),
            (Problem(0b11, 5), Problem(0b100, 5)),
            (Problem(0b11, 5), Problem(0b1100, 5)),
            (Problem(0b11, 5), Problem(0b11100, 5)),
            (Problem(0b111, 5), Problem(0b1000, 5)),
            (Problem(0b111, 5), Problem(0b11000, 5)),
            (Problem(0b1111, 5), Problem(0b10000, 5)),
        ]

        generated_ccps = list(generate_ccp_pairs(chain_query))
        self.assertListEqual(generated_ccps, correct_ccps)


unittest.main(
    argv=["ignored", "-v"], defaultTest="EnumeratorTests", verbosity=2, exit=False
)

test_ccp_helper_enumeration (__main__.EnumeratorTests.test_ccp_helper_enumeration) ... ok
test_csg_enumeration (__main__.EnumeratorTests.test_csg_enumeration) ... ok
test_plan_enumerators (__main__.EnumeratorTests.test_plan_enumerators) ... ok

----------------------------------------------------------------------
Ran 3 tests in 0.002s

OK

<unittest.main.TestProgram at 0x10d93a750>