system.query_optimization.problems module

Problem type representing relation subsets as bit sequences for join enumeration.

class system.query_optimization.problems.Problem(number: int = 0, represented_number_of_bits: int | None = None)

Bases: IntegerBitSequence

Given a query graph of length n, a “problem” is a BitSequence of length n where each bit corresponds to a relation in the query graph. Note that these operations only work if there 1-1-mapping between positions in the bit sequence and relations, i.e., each bit always represents the same relation.

This class defines additional operations for integer bit sequences to efficiently store and manage subsets of relations.

get_next(n: Problem) → Problem

Returns the next problem in a problem enumeration w.r.t to the problem n. The idea here is that we have a superset n, whose subsets we want to enumerate, where self is assumed to be subset of n. By applying the formula below to self, we obtain another subset n, which is the next larger (in terms of the represented integer) subset. Repeating this process will eventually allow us to enumerate all subsets of the superset n. :param n: The problem n whose problems are to be enumerated. :return: The next subset as a problem.

get_smaller_or_equal_relations() → Problem

Returns the problem containing all relations with a smaller/equal relation id (i.e. the bit representing the relation) than the smallest id in self. :return: The problem containing all relations with a smaller/equal relation id than the smallest id in self.

get_relation_id() → int

Returns the relation id of the problem, if it is a singleton (i.e. only one bit is set to True). :return: The relation id.

static create_all_false_bit_sequence(represented_number_of_bits: int = 0) → Problem

See BitSequence.create_all_false_bit_sequence().

Returns the empty problem (no relation selected) as a Problem.

class SingletonIterator(problem: Problem)

Bases: object

An iterator to iterate through all singletons (i.e. a problem with only one bit set) of a given problem.

as_set() → set[int]

See BitSequence.as_set().

Bypasses the singleton-yielding __iter__() and returns the raw relation-id integers whose bit is set to True.

class SingletonReverseIterator(problem: Problem)

Bases: object

An iterator to traverse the singletons (i.e. a problem with only one bit set) of a problem in reverse order, i.e., starting with the singleton containing the most-significant bit.

static get_problem_for_relation(relation_id: int, number_of_bits: int) → Problem

Transform a relation id into the corresponding singleton problem. :param relation_id: The relation id. :param number_of_bits: The number of bits represented by the underlying join graph. :return: The relation as a problem.

static get_problem_with_all_relations(graph_size: int) → Problem

Get a problem containing all relations of given graph size. :param graph_size: The graph size. :return: A problem containing all relations of the given graph size.

class ProblemIterator(superset_problem: Problem, start_problem: Problem | None = None, stop_problem: Problem | None = None)

Bases: object

An iterator that enumerates all problems of the given superset problem. It starts with the optionally passed start problem or with the least-significant-bit-singleton if no such argument was passed. Further, it stops when the optionally given limit problem is reached, or when all problems were enumerated when no such argument was given.

static enumerate_all_problems(superset_problem: Problem, start_problem: Problem | None = None, stop_problem: Problem | None = None) → ProblemIterator

Enumerate all problems of the given superset problem. :param superset_problem: The problems whose problems are to be enumerated. :param start_problem: The optional problem to start the enumeration with. :param stop_problem: The optional problem after which the enumeration will stop. :return: An iterator to traverse through all problems of the given superset problem.

static get_all_problems(superset_problem: Problem) → list[Problem]

Computes all problems of a given superset problem and returns them as list. This helper method is useful when a list of subsets is utilized multiple times, so there is no need to regenerate the problems from scratch. :param superset_problem: The problem whose subsets are to be enumerated. :return: The list that stores all subsets as problems.