Recent advances in the manufacture of quantum computers attract much attention over a wide range of fields, as early-stage quantum processing units (QPU) have become accessible. While contemporary quantum machines are very limited in size and capabilities, mature QPUs are speculated to eventually excel at optimisation problems. This makes them an attractive technology for database problems, many of which are based on complex optimisation problems with large solution spaces. Yet, the use of quantum approaches on database problems remains largely unexplored.
puting hardware have sparked increased interest in this novel architecture from a plethora of research fields.
While the prototypical nature of contemporary quantum hardware does not yet allow for achieving practical utility, quantum processing units (QPU) are speculated to excel at optimisation problems, which govern a large portion of ongoing database research. However, despite the large presented a method to solve join ordering (JO) problems on contemporary QPUs, by applying faithful transformencoding for JO proposed by Trummer and Koch [6], into a quadratic unconstrained binary optimisation (QUBO) formulation. This encoding can be interpreted by QPUs, which enabled the JO optimisation of first small-scale queries on real QPUs.
However, by applying a transformation of the original MILP encoding into QUBO, their JO-QUBO inherits the Recent advances in the development of quantum com- ation of the mixed integer linear programming (MILP) plored. dustrial processes, the potential of using quantum syspotential of QPUs to accelerate computation-intense in- limitations of the MILP encoding. Most strikingly, their formulation only accounts for left-deep join trees. While tems on database-related issues remains largely unex- search space restriction to left-deep trees has historic
Still, recent database optimisation research has pion- fit of substantially lowering the exploration complexity, eered in exploring first means to harvest this potential: Trummer and Koch [1] investigated the use of quantum annealing on the multi query optimisation (MQO) problem. Groppe and Groppe [2], and Bittner and Groppe [3, 4], analysed QPU use for database (DB) transaction scheduling. Finally, Schönberger et al. [5] (W. Mauerer) JO-QPU method.
Still, the prospect of using QPUs for JO optimisation remains attractive. Therefore, in this paper, we address the drawbacks of the existing JO-QUBO formu© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License lation: Rather than transforming an existing encoding into QUBO, thereby inheriting its limitations, we propose QPUs can optimise problems formulated as quadratic unconstrained binary optimisation (QUBO) problems [11, 12, 13], which (1) only allow quadratic interactions between variables, (2) allow no explicit constraints, (3) limit variables to a binary domain and (4) encode optimisation problems. Physically, we may consider a QUBO encoding an energy formula, where the minimum energy corresponds to an optimal solution to the problem. Mathematically, they are given by the multivariate polynomial tailoring quantum systems to problem requirements. olation, thereby penalising invalid variable configurations . a novel QUBO encoding for optimising general bushy trees, while moreover retaining the ability to identify cross product solutions. In contrast to many competing JO methods, which either do not consider cross products or restrict the join tree shape, our new encoding enables QPUs to explore the complete, unrestricted search space of the JO problem.
Contributions. In detail, our contributions are as follows: 1. We propose a novel, native encoding of join ordering as a QUBO problem (instead of transforming an existing formulation and inheriting its limitations). 2. We enable QPUs to explore the most extensive class of join ordering problems, allowing them to optimise general, bushy join trees while also enabling the use of cross products. Thereby, we exhaust the full potential of quantum hardware for join order optimisation. 3. We substantially improve the resource-eficiency in
comparison to existing methods. 4. We identify architectural bottlenecks of contemporary quantum systems, quantify their impact on join order optimisation, and discuss means to address them by
The remainder of this paper is structured as follows: We provide fundamentals on quantum computing, including the required QUBO formalism, in Sec. 2. We explain our considered join ordering model in Sec. 3. We discuss our novel encoding for bushy join trees in Sec. 4. Finally, we discuss related work in Sec. 5 and conclude in Sec. 6. 2.
Unlike conventional CPUs, QPUs cannot be used for executing arbitrary code to run any algorithm. Instead, distinct programming paradigms are required for quantum computation. The two prevailing paradigms required for contemporary QPUs consist of gate-based quantum computation, as implemented, e.g., by IBM-Q systems [8], and quantum annealing, made accessible by D-Wave [9]. The latter exclusively solves optimisation problems, and thereby inherently meets our requirements of using QPUs for query optimisation, whereas gate-based QPUs allow the execution of gate-based quantum optimisation algorithms, most prominently the quantum approximate optimisation algorithm (QAOA) [10].
We next discuss a problem encoding supported by either approach. Based on this encoding, our method does hence not depend on the specific paradigm. For our purposes, the term QPU therefore includes both, gatebased and annealing-based quantum approaches. ( )⃗ = ∑ + ∑ , ≠ (1) (with
= ). where ∈ {0, 1} are variables, and ∈ ℝ coeficients
The biggest hurdle in solving optimisation problems on QPUs consists in determining problem formulations conforming to the QUBO requirements. Firstly, we have to identify validity constraints that must hold for every valid solution to our problem, and encode these constraints implicitly, by specifying terms akin to Eqn. 1 that evaluate to positive energy penalties for any constraint viSecondly, further QUBO terms are set to add energy in accordance to the quality, or costs, of a solution. If built correctly, minimising the overall energy formula will produce a variable configuration corresponding to a solution that is both, valid and optimal.
To provide the reader with an understanding of the QUBO encoding process, we illustrate the encoding principles based on three recurring encoding patterns, or operators, that will prove to be very useful in our quest of formulating a JO encoding for bushy join trees.
The first recurring scheme concerns groups of semantically matching variables, out of which only a limited amount may be active, or hot. As such, we refer to this pattern as n-hot encoding. Typically, it is applied for = 1 , and is usually called one-hot encoding. Expressed as QUBO, its most basic form is given by
H1hot = ( −
2 ∑ ) , ∈ where X denotes the set of binary variables. Expressing a quadratic term, H1hot is clearly minimised if the inner term evaluates to 0, which requires =
∑∈ . Therefore, minimising H1hot produces a variable configuration where exactly out of all variables within are active.
More complex versions of the encoding may substitute a linear term of variables and coeficients for constant .
This scheme is useful for ensuring a valid assignment of variables expressing mutually exclusive properties. For instance, we later apply it for enforcing that a relation is initially joined by only one out of all possible joins. where || denotes the size of . The ground state energy of Himpl is given by 0, since clearly, neither nor || − ∑∈ can assume negative values. Hence, to minimise Himpl , we require either = 0 or || − ∑∈ = 0 . Since || − ∑∈ = 0 requires = 1∀ ∈ , minimising Himpl activates all variables in if = 1 .
In case of JO, the implication operator will prove useful to us, e.g., for enforcing a relation , initially joined by join , to be considered an operand for all joins including and succeeding .
The input to a JO problem is given by a query graph = ( , ) , where the nodes 1, ..., ∈ represent the relations 1, ..., with cardinalities 1, ..., to be joined.
Further, an edge ∈ corresponds to the join predicate with selectivity 0 < ≤ 1.
Some JO algorithms require a strict adherence to the 2.2.2. Implication Operator query graph, only allowing joins between relations conFurther recurring encoding patterns involve logical oper- nected by a predicate. In contrast, other approaches ators. One of the most relevant operators is thereby given consider joins between any pair of relations, including by the implication operator. Given a binary variable and such with no predicates. Such operations are typically a set of binary variables , we express ∀ ∈ ∶ ⟹ referred to as cross products. Alternatively, we may conin QUBO as sider a cross product a join with selectivity 1, and add the missing edge in accordingly.
Clearly, including cross products can drastically enHimpl = (|| − ∑ ) , hance the set of allowed operations (in particular for a ∈ sparse query graph), which motivates their exclusion by many JO approaches, to limit the size of the search space.
In contrast, our method does not apply such restrictions, allowing it to benefit from the use of cross products, which can indeed be required by an optimal solution.
We moreover consider any query graph, without any restrictions on its shape (whereas some other approaches require, e.g., the graph to be acyclic [15]).
In contrast to a query graph, which corresponds to the 2.2.3. And-Operator input to the JO problem, a join tree represents a JO solution. Its leaf nodes thereby represent the base relations Finally, given three binary variables , and , we can to be joined, whereas its intermediate nodes correspond express the logical and-operator ∧ = in QUBO, as to join operations. Edges are directed towards the root described in the D-Wave problem reformulation hand- of the tree (i.e., the final join). As each join requires two book [14]: operands, each join node has two predecessors, corresponding to either a) a base relation, or b) another join, Hand = − 2 − 2 + 3. whose result is to be further joined. The join result further serves as an operand for another join, as expressed If = 1 and = 0 , only the term remains, inducing by an outgoing edge connecting to its successor. The only an energy penalty of 1, whereas = 1 in conjunction exception to this rule is given by the final join, which is with = 1 causes Hand to evaluate to 0. Likewise, = 0 no operand for any further join. and = 0 lead to energy 0, whereas for = 0 and = 1 , While these requirements must hold for any join tree, only the term 3 remains, inducing a penalty of 3. Thus, some JO methods further restrict the shape of join tree. minimising the energy for Hand indeed produces variable Much like the exclusion of cross products, such restricconfigurations in accordance to the and-operator.
tions are motivated by the greater eficiency of exploring We observe that we can use the and-operator to store a reduced search space. Most notably, some approaches the result ∧ into a single variable , which is useful to only consider left-deep join trees, which require each join maintain a degree of 2 for our polynomial, as required to take at least one base relation as an operand. Hence, by QUBO. individually joining two pairs of relations is not possible, since joining their results requires a join operating on 3. Join Ordering Model the results of two preceding joins. Instead, valid left-deep join orders must correspond to a permutation of relations.
Having laid out the fundamentals of encoding problems The restriction to left-deep trees was applied by the as QUBO, we next describe our encoding targets, i.e., the MILP method by Trummer and Koch [6], and hence various elements constituting a JO problem. moreover by the existing JO-QUBO proposed by Schönberger et al. [5], which faithfully transforms the MILP cannot make any a priori assertions about whether a join formulation into QUBO. However, the negative impact of succeeds a join , except for the final join, which is a this restriction on solution quality can be quite drastic, as successor to all other joins. shown, for instance, by the empirical analysis conducted by Neumann and Radke [7]. Therefore, our novel QUBO encoding considers general1, or bushy join trees, which are not limited by any further structural restrictions.
To circumvent this issue, it is possible to operate on a large tree structure that encompasses all possible bushy trees, providing us with a priori knowledge about the relationship between two joins, similarly to the left-deep scenario. However, this requires an exponentially growing number of tree nodes, making such an approach infeasible due to scaling limitations. Therefore, we apply a Finally, a cost function evaluates each join tree, by as- diferent formulation strategy for bushy trees. Instead of signing it a cost value. For our method, we consider the operating on a tree provided as an input, our encoding classic cost function , which sums over the intermedi- for bushy trees generates the join tree itself. ate cardinalities of all joins of a join tree [16]. For a pair of relations, their cardinalities and predicate selectivity, it is given by ( , ) ∶= . Hence, we require product operations to express this cost function, which poses an issue for determining a JO-QUBO encoding limited to quadratic terms. In the next section, we show how to mitigate this issue, by applying the same strategy as used by the MILP [6] and existing QUBO encoding [5]. 4.
To solve JO with optimisation methods such as MILP and QUBO, we have to encode variables and constraints in such a way that we receive valid join trees as solutions. However, unlike many other optimisation methods such as integer linear programming, solution validity cannot be enforced via explicit constraints for QUBO encodings. Instead, as demonstrated on some common operators in Sec. 2, the encoding needs to ensure that a variable configuration minimising the QUBO formula inherently corresponds to a valid solution.
To guide the reader, we first provide an overview of our encoding methodology and preliminary considerations in Sec. 4.1. Next, in Sec. 4.2, we show, in detail, how to encode valid bushy trees in QUBO. Finally, we describe our cost function encoding that assigns a cost value to a join tree in Sec. 4.3.
In case of left-deep join trees, the structure of the tree is identical for all possible solutions. This allows the use of a priori knowledge about the tree structure for the QUBO formulation. For instance, we may establish that join 0 is a direct predecessor to join 1, and can use this information to eficiently encode constraints, as done by the existing MILP and QUBO formulations for left-deep join trees [6, 5]. However, in case of bushy trees, the relationship between joins is, in general, unclear: We 1To clarify, the term general refers to the unrestricted structure of the join tree, and not to, e.g., details on join operators.
Thereby, we exploit global relationships that hold for every possible join tree. For instance, each join takes exactly two operands as inputs (which may either represent a base relation, or the result of a prior join), and produces precisely one result. Hence, each join has two incoming edges, and either one (in case of intermediary joins) or zero (in case of the final join) outgoing edges. As we later show in detail, we can translate these relationships into penalty terms, to enforce valid assignments for variables representing the edges in the join tree.
In stark contrast to left-deep trees, enforcing such relationships is not straightforward for bushy trees, since we lack a priori information about the relationship between a join pair. Hence, we require more sophisticated methods to enforce these conditions for bushy trees. These methods, in return, require the introduction of ancillary variables. For instance, by determining the depth of all relations and joins in the join tree, and saving this information using ancillary variables, it is possible to prevent the occurrence of cycles in the join tree. As we will show, it is possible to enforce a valid configuration of variables by introducing a number of ancillary variables that is cubic in the number of relations.
Outline. Firstly, we show how to enforce an assignment of variables conforming to valid bushy trees.
Hereby, in addition to the actual tree variables, we introduce variables to capture the depth of tree nodes.
Thereby, we prevent the occurrence of cycles. Secondly, to evaluate the quality of a join tree, we describe variables and penalty terms to encode the logarithmic costs of a tree. Finally, we approximate the actual join order costs based on the logarithmic values.
Our encoding requires a plethora of binary variables with individual semantics. To guide the reader, Table 1 depicts an overview on the semantics of each variable type, alongside further information such as the required amount of variables.
Vars rljrj jdsij rdrd jdjd rojrj pajpj trjtj
Semantics Is relation r leaf for join j? Is join j a direct successor to join i? Does relation r have depth d? Does join j have depth d? Is relation r an operand for join j? Is predicate p applicable for join j? Is threshold t reached by join j? Overview of all variables, their semantics and required amounts for queries joining relations with joins, using predicates and threshold values, at discretisation precision . Finally, max denotes the maximum logarithmic cardinality for join . 2 3 2 / / / 2 tree joining relations with joins. Let the binary vari- = ∑ (2 − ∑ jdsji − ∑ rljri) + ( − ∑ rljrf ) . two operands); (b) each node has one outgoing edge, ex- isation may yield the join order ( ⋈ ) ⋈ , expressed
We begin by introducing variables representing the join able rljrj (Relation is Leaf for Join), introduced for each relation , 1 ≤ ≤
and join , 1 ≤ ≤ , indicate whether uses the base relation as an operand. Further, let the binary variable jdsij (Join is Direct Successor ), added for every join pair (, ) , denote whether join is a direct successor to join .
We enforce a valid assignment of the newly introduced variables so they represent one out of all possible bushy trees. We exploit global constraints that must hold for every join tree (providing semantics in brackets), namely:
(a) Each node has two incoming edges, excluding leaf nodes, which have zero incoming edges (each join has cluding the root node, which lacks outgoing edges (each intermediate join produces an intermediate result used by a subsequent join, and each relation is a leaf assigned to one join); (c) no cycles may appear within a tree (each join is only applied once). straints into QUBO terms, whose minimisation will hence ensure the construction of a valid join tree. =1
=1,≠ =1 =1
2 The latter inequality requires the introduction of an ancillary binary variable , allowing a variable configuration such that the term evaluates to 0 if no more than one variable rljrf is active.
Example 4.1. Let us consider a query joining three relations , and with two joins and . Further, let jdsij = 1 indicate that is succeeded by . To produce a valid tree, must join and , or else any other pair of base relations, whereas must join the emerging intermediate result and the remaining base relation . Thus, successful minimas rljAi = rljBi = rljCj = 1, avoiding a penalty by as (2 −rljAi − rljBi)2 = 0 for join and (2 −jdsij − rljCj )2 = 0 for join . The same applies mutatis mutandis for any other join order permutation.
In contrast, consider when either join receives more or and (2 −jdsij − rljBj − rljCj )2 = 1 for join .
than rljBi = 1, producing a penalty (2 −rljAi)2 = 1 for join
In the following, we individually translate these con- less than two operands. For instance, let rljBj = 1 rather (a) Incoming Edges.
Each join requires two operands, (b) Outgoing Edges.
Similar considerations as for inwhich may either be base relations or intermediate results produced by another join. As such, we enforce that each join node has exactly two incoming edges, using a two-hot encoding. In addition, the final join, which we indicate by index , must receive the intermediate results of all preceding joins, and therefore have at least one join as a predecessor2. As such, we additionally enforce that at most one of the incoming edges connecting to the final join comes from a base relation: coming edges apply to outgoing ones: Each join produces one result, which may be the final result in case of the ifnal join , or else serve as an input to another join.
Therefore, each intermediate join node has one outgoing edge, which we enforce by a one-hot encoding. In contrast, the final join node has no outgoing edge. Hence, each jdsfi for any join adds a penalty of 1. In addition, we enforce that a relation may only be a leaf for a single join, using a one-hot encoding: 2Of course, this only holds for queries joining at least three relations, using at least two joins, which we consider the minimum size for meaningful JO optimisation. = ∑ =1,≠
=1,≠ (1 − ∑ jdsij ) +
∑ jdsfi 2
=1,≠ =1 + ∑ (1 − ∑ rljri) .
initially joined only by join , hence (1 −rljAi − rljAj )2 = 0. prevents the emergence of cycles. Example 4.2. (cont’d) We continue our example for a query joining three relations, where rljAi = rljBi = rljCj = jdsij = 1, expressing the join order ( ⋈ ) ⋈ This configuration satisfies our constraint: Relation is
However, since also precedes by joins, = + must moreover hold. Hence, = + = + + , . contradicting our assumption, since ≥ 1 and ≥ 1 .
Therefore, enforcing an unambiguous depth assignment have any outgoing edges, hence avoiding energy penalties. that contains cycles, since such a configuration cannot =1 −1 =0 2
2 =1 = ∑ (1 − ∑ jdjd ) + ∑ (1 − ∑ rdrd ) .
Next, we ensure that only the final join may have depth 0, by inducing a penalty if jdf0 = 0 and jdj0 = 1 for any ≠ : = (1 −jdf0 ) +
jdj0 .
We further ensure that no join of the maximum join depth dmax = − 1 has a predecessor:
A depth constraint enforcing an unambiguous depth assignment for joins penalises any variable configuration conform to the constraint. Hence, we next introduce the required variables and QUBO terms. We moreover introduce variables and terms assigning depth values to relations, which we require for subsequent steps.
Let the binary variables rdrd (Relation has Depth), introduced for each relation , 1 ≤ ≤
and possible depth , 1 ≤ ≤ (the largest possible depth equals the number of joins), and jdjd (Join has Depth), added for each join , 1 ≤ ≤
and possible depth , 0 ≤ ≤ − 1 , indicate whether or have depth or respectively.
Using one-hot encodings, we first enforce that each join and relation has an unambiguous depth: =1 ∑ =1,≠ The same applies mutatis mutandis for relations and .
Further, join is succeeded only by join . (1 −jdsij )2 = 0, whereas join , as the final join, does not
Thus,
In contrast, let us consider an invalid configuration with missing leaf assignments, where rljAi = 0 rather than rljAi = 1. Hence, (1−rljAi −rljAj )2 = 1 penalises the lack of join assignment for relation . The same energy penalty is induced for rljAi = rljAj = 1, illustrating that penalises both, insuficient and excessive amounts of outgoing edges. (c) Preventing Cycles. So far, our constraints ensure that each join node has the correct amount of incoming and outgoing edges. To complete our set of constraints for valid trees, we have to enforce one final property that needs to hold for every tree: Each tree must be an acyclic graph. Enforcing this property is significantly more complex, as it concerns connections between an arbitrary number of tree nodes, while QUBO restricts variable interactions to contain at most two variables. To solve this issue, we may introduce a set of ancilla variables to store and later retrieve node properties useful to enforce this constraint. Our construction is thereby similar to the cycle avoidance applied for encoding the directed feedback vertex set problem as QUBO [17]. Specifically, we will label each join node with a depth value, such that join must have depth if preceded by a join of depth + 1 . In case of at least one cycle, a well-defined and unambiguous depth assignment becomes impossible, as shown by Theorem 4.1.
Theorem 4.1. Enforcing an unambiguous, valid depth assignment for each join tree node prevents cycles.
Proof. We consider a depth assignment valid if each join is labeled by an unambiguous depth ≥ 0 , and = +1 holds for any join with depth that precedes join with depth . Let us assume an acyclic join tree with any set of joins (0, 1, ..., ), where denotes the final join (i.e., the root of the tree), which we assign depth = 0. Then, each join directly preceding the root is assigned depth
= + 1 = 1. The same applies, mutatis mutandis, for the remaining joins.
Let us now consider a configuration with two joins and , where precedes by joins (i.e., for = 1 , directly precedes , whereas for = 2 , precedes an intermediate join , which finally precedes ), where ≥ 1 , and precedes by joins, where ≥ 1 , hence creating a cycle. Assuming a depth labeling with depths and is possible, = + must hold, since precedes by joins.
=1 =1,≠ = ∑
∑ jdsij jdjdmax .
Finally, we need to assign the correct depths in accordance to the join tree expressed by jds and rlj. Specifically, jdjd = 1 has to respectively imply jdi(d+1) = 1 if jdsij = 1 or rdr(d+1) = 1 if rljrj = 1. However, directly expressing jdjd jdsij ⟹
jdi(d+1) is not possible for QUBO, as it requires a degree 3 polynomial. To circumvent this issue, we can first apply the and-operator to store the result of jdjd ∧ jdsij in an ancillary variable sjdij as −2 =0 =1 =1 = ∑ ∑
∑ jdjd jdsij − 2jdjd sjdij − 2jdsij sjdij + 3sjdij , allowing us to further implement the desired implication operation: −2 =0 =1 =1 = ∑ ∑ ∑ sjdij (1 −jdi(d+1)).
Unfortunately, we require one ancillary variable for each instance, Nayak et al. [18] include pre-computed costs join depth 0 ≤ ≤ − 2
and join pair (, ) . Therefore, for all possible intermediate joins as coeficients into the the number of needed ancillary variables is cubic in the QUBO encoding. Given the large solution space, this renumber of joins, which results in a significant variable overhead in comparison to left-deep join trees. quires an exponential number of variables, and severely impacts scaleability beyond small query sizes. For these, Similarly, for each relation , depth 0 ≤ ≤ − 1 and dynamic programming obtains optimal solutions [7]. join , we add the constraints Next, we must assign each join tree a cost value. A numThe next step enforces the goal that, once joined for ber of cost encoding methods have been proposed: For join , a relation is also present for all joins succeeding −1
dmax = 1, and add the newly discussed penalty terms.
Minimising the term assigns our final join depth = 0, by setting jdj0 = 1. Then, minimising and requires jdi1 = 1, since jdsij jdj0 = 1. However, as join now precedes a join of the maximum depth dmax = 1, penalty jdsjijdidmax = 1 is added in accordance to .
For the sake of illustrating the remaining terms, let us assume the maximum depth dmax = 3, such that won’t penalise the configuration, and further depth variables beyond the maximum depth. Since jdi1jdsji = 1, we further require jdj2 = 1 to minimise and . However, this begets the energy penalty (1 −jdj0 − jdj2 )2 = (−1)2 = 1 in accordance to , since depth assignment for join is no longer unambiguous. Due to the cyclic relationship between joins and , minimisation of and further activates their remaining depth variables, which begets increasingly higher energy penalties that can only be avoided by acyclic variable configurations. Minimising the discussed terms hence ensures acyclic join trees.
For the remainder of our running example, we set jdsji =
0, which begets the valid depth assignment jdi1 = jdj0 = rdA2 = rdB2 = rdC1 = 1.
Finally, we combine all terms discussed in this section into an overarching Hamiltonian for bushy join trees: Hbushy = + + + + + + + ℎ + .
As we are interested in applying quantum optimisation on larger queries, where conventional exhaustive search approaches fail and are replaced by heuristic methods, we have to rely on more variable-eficient cost encoding methods. Similarly to Trummer and Koch [6] and Schönberger et al. [5], we therefore encode a cost function, rather than costs themselves. Specifically, we consider the classic cost function [19], which sums over the sizes of intermediate join results. However, neither MILP nor QUBO support the product operations required for . For their MILP approach, Trummer and Koch [6] therefore propose to substitute sums of logarithmic cardinalities and selectivities for these product operations, as the logarithm of a product equals the sum of logarithms of its factors. Based on the logarithmic intermediate result sizes, Trummer and Koch approximate the actual cardinalities using an arbitrary number of threshold values. Similarly to Schönberger et al. [5], who faithfully transformed the MILP cost approximation into QUBO, we show, in the following, how to apply this approximation to our native QUBO formulation for bushy trees.
Based on the variables expressing a valid bushy tree, we derive a corresponding assignment of cost variables needed for calculating the cost of the join tree joining relations with joins using join predicates. Let the binary variable rojrj (Relation is Operand for Join), introduced for each relation , 1 ≤ ≤
and join , 1 ≤ ≤ , indicate whether is an operand for . Further, let the binary variables pajpj (Predicate is Applicable for Join), added for each predicate , 1 ≤ ≤
and join , 1 ≤ ≤ , denote whether predicate can be applied for join .
First, we need to derive a valid assignment of rojrj variables based on the bushy join tree representation introduced in Sec. 4.2. Our ultimate goal is to enforce that, once joined by a join , a relation serves as an operand for every join succeeding . Further, must not appear as an operand for a join unless is initially joined by , or is an operand for any join preceding .
We begin by enforcing that an activated leaf node variable rljrj implies the corresponding variable rojrj to be activated, using the implication operator:
=1 =1 = ∑ ∑ rljrj (1 −rojrj ). . In terms of variables, rojrj = 1 must imply rojri = 1 if jdsji = 1 (i.e., join is a direct successor to ).
To avoid polynomials of degree 3, we first store the
Making use of the existing depth variables, we apply an n-hot encoding, where is given by each respective depth, to achieve our goal of enforcing the correct number of result of rojrj ∧ jdsji in ancillary stij by active roj variables: = ∑ ∑ ∑ rojrj jdsji − 2rojrj stij − 2jdsjistij + 3stij , = ∑ (∑ ( ⋅ rdrd )− ∑ rojrj ) .
However, the constraints enforced so far are not yet suficient to produce a valid configuration of
roj variables: While we do ensure that all required roj variables are active, we must moreover enforce that no variable rojrj is active unless required by the join tree. Specifically, a relation must only serve as an operand for a join if it is also an operand for either join preceding , or else if it is a base relation initially joined by . Enforcing this constraint in the same manner as and is, however, very expensive, as we require constraints for each relation and join triplet (, , ) (since each constraint involves an intermediate join and two potential predecessors and ), engendering an amount of ancillary variables that is quartic in the number of relations.
To circumvent this issue, we can apply a diferent approach to ensure a variable rojrj remains inactive unless required: We may apply a constraint that bounds the number of allowed active roj variables by the correct amount, such that any additional active variables induce energy penalties. This requires us to determine the correct amount of joins considering a relation as an operand, and therefore the number of roj variables allowed to be active for . Fortunately, we have already determined the correct amount for each join in a previous step, since this number corresponds to the depth of in the join tree, as shown by Theorem 4.2.
Theorem 4.2. The number of joins that consider as an operand is given by the depth of in the join tree.
Proof. Assume that a relation is initially joined by the Example 4.4. (cont’d) To demonstrate the assignment of cost variables, we continue our example for a query joining three relations, where rljAi = rljBi = rljCj = jdsij = jdi1 = jdj0 = rdA2 = rdB2 = rdC1 = 1. We begin by adding cost variables roj for all relations and joins, and all terms discussed above, where enforces rojAi = rojBi = rojCj = 1, following from rlj variable assignments. Since jdsij = 1, relations and are moreover required as operands for join , which is enforced by minimising and , setting rojAj = rojBj = 1. Thereby, our encoding has ensured all required variables roj are active.
In addition, it must moreover prevent the activation of roj variables unless required. minimisation may activate rojCi
For instance, cost =
1 even though relation is not an operand for join . However, since rdC1 = 1, labeling relation with depth 1, must be an operand for exactly one join, in accordance to Theorem 4.2.
This is ensured by term , adding energy penalty (1 ⋅rdC1 − rojCi − rojCj )2 = (−1)2 = 1 if both, rojCi = 1 and rojCj = 1. Hence, minimising yields rojCi = 0.
Based on the correctly assigned roj variables, we derive valid assignments for predicate variables paj. Specifically, we need to enforce that pajpj = 1 only holds if both relations associated with predicate are operands for join , which we implement using the implication operator: = ∑ ∑ paj (2 −roj 1() − roj
2() ), relation associated with . where
(), 1 ≤ ≤ 2 , corresponds to the first or second Example 4.5. (cont’d) To illustrate the inclusion of predicates, we continue our example for a query joining three relations, where rojAi = rojAj = rojBi = rojBj = rojCj = 1.
We further consider two join predicates 1, associated with relations
and , and 2, for relations and .
Accordingly, we add variables paj1 , paj1 , paj2 and
=1 =1 ifnal join . Since is the root of the tree, it has depth 0, paj2 . To minimise the cost terms discussed below, any and any tree node connecting to has depth 1, including minimisation method seeks to apply as many predicates the leaf relation and join , which we assume precedes . as possible. Ideally, paj1 = paj1 = paj2 = paj2 = 1. joins succeeding ).
It follows that any leaf relation and further join connecting to has depth 2. This applies, mutatis mutandis, for all further joins and leaf relations in the join tree.
It is clear that the depth of a join then corresponds to the number of joins succeeding . If initially joins a relation , has depth = + 1. Consequently, must serve as an operand for exactly joins (i.e., join and all However, predicate 2 may not be applied for join , since relation is not an operand. Accordingly, energy penalty paj2 (2 − rojBi − rojCi) = 1(2 − 1 − 0) = 1is added to the overall costs, in accordance to . The configuration paj2 = 0 is hence enforced by minimising , assuming a proper balance between validity and cost terms, as discussed in Sec. 4.4, to ensure the energy penalty for activating paj2 is larger than any potential cost savings. consider logarithmic input cardinalities = = = 2, = ∑ ∑ (LogIntCard(j) −trjtj ⋅ ∞ + − log( )) .
2 =1 =1
Based on introduced cost variables, we now encode join tree costs. Following the existing MILP and QUBO formulations for left-deep trees [ 6, 5], we rely on an approximation of logarithmic costs, which allows us to encode the classic cost function Cout in QUBO. We express the logarithmic intermediate cardinality for join as: we hence convert the inequalities to equality constraints, using a continuous variable :
LogIntCard(j) −trjtj ⋅ ∞ + = log( ). (2) However, QUBO only allows binary variables, rather than the required continuous variable. Therefore, we next approximate as ≈ the continuous variable for multiple binary variables . We may tune the accuracy of this discretisation by choosing the number of allowed decimal positions . Then, = (0.1) denotes a discretisation precision, and we require = ⌊ log2(
discretisation, where /)⌋ + 1 binary variables for the
is the maximum logarithmic cardinality possible for join . For further details on this approximation, we refer the reader to Schönberger et al. [5]. The equality in Eqn. 2 is encoded as ∑ =1 2−1 , substituting LogIntCard(j) =∑ LogCard(r )rojrj +∑ LogSel(p)pajpj , where LogCard(r )and LogSel(p)denote log-cardinality for relation and log-selectivity for predicate . Example 4.6. (cont’d) To illustrate the logarithmic cost calculation, we continue our example for a query joining three relations, where rojAi = rojAj = rojBi = rojBj = rojCj = paj1i = paj1j = paj2j = 1. Thereby, we and logarithmic predicate selectivities 1 = 2 = −1.
Then, for join i, we obtain the logarithmic result size LogIntCard(i) = rojAi + rojBi + 1paj1i = 2+2−1 = 3, and LogIntCard(j)
= rojAj + rojBj + + rojCj + 1paj1j + 2paj2j = 2 + 2 + 2 − 1 − 1 = 4 for join .
We next approximate intermediate join cardinalities.
Following the MILP and QUBO approaches for left-deep join trees [6, 5], a set of threshold values is added to the model to approximate the actual intermediate join cardinalities based on the logarithmic ones: Let the binary variables trjtj (Threshold is Reached by Join), added for every threshold value , 1 ≤ ≤ and intermediate join , 1 ≤ ≤ − 1
(we exclude the final join, whose cost is invariant w.r.t. the join tree), indicate if cardinality of the intermediate result produced by join exceeds the logarithmic threshold log( ). In this case, the threshold is added to the overall costs:
Hcost = ∑
∑ trjtj . −1 =1 =1 size produced by join : In the original MILP encoding, the following inequality constraint activates trjtj if log( )is exceeded by the result
LogIntCard(j) −trjtj ⋅ ∞ ≤ log( ).
Specifically, if LogIntCard(j) >log( ), the constraint can only be satisfied by activating trjtj , which subtracts the suficiently large constant
∞ .
However, such inequality operations are not inherently supported by QUBO. Following Schönberger et al. [5], −1 =1 =1 Example 4.7. (cont’d) We complete our running example by illustrating the cost approximation for our query joining three relations. Recall the logarithmic intermediate result sizes LogIntCard(i) = 3and LogIntCard(j) = 4for joins and respectively, as calculated in Example 4.6. We consider two thresholds 1 = 100 and 2 = 1000 for the cost approximation, and hence introduce variables trj1i, trj1j , trj2i and trj2j . To minimise cost, a minimisation method will seek to leave as many threshold variables inactive as possible. Ideally, trj1i = trj1j = trj2i = trj2j = 0. However, since LogIntCard(i) = 3 > 2 = log( 1), trj1i must be active to avoid a penalty induced by . The same holds for trj1j , since LogIntCard(j) = 4 > 2 = log( 1), and trj2j , since LogIntCard(j) = 4 > 3 = log( 2). Hence, Hcost = 1trj1i + 1trj1j + 2trj2j = 100+100+1000 = 1200 adds cost accordingly. We observe that the accuracy of the approximation strongly depends on the selected thresholds, and approximation quality increases as more thresholds are added.
Combining all terms leads to the overall Hamiltonian
Hval = Hbushy + + + + + + .
Based on the validity and cost Hamiltonians, we can now construct the complete Hamiltonian H :
H = Hval + Hcost .
Penalty weight amplifies the penalty for violating validity terms, such that the added energy always outweighs any potential cost savings resulting from the violation.
Setting arbitrarily large can lead to slowdowns [20].
Hence, we next derive a lower bound for .
This lower bound depends on the smallest possible ary QPUs. Further, (2) the baseline approach restricts its penalty that may be engendered by any constraint violsolution space to left-deep join trees, which commonly ation due to . Most of our penalty terms induce an energy value of 1 when violated, with the exception of which enforces an activation of threshold variables if the corresponding thresholds were exceeded. For deyield significantly higher cost than bushy join trees [ 7].
In contrast, our novel encoding applies no restrictions on the JO solution space, enabling quantum optimisation of general, unrestricted trees, in conjunction with the termining , we hence focus on the term , as it can ability to include beneficial cross products. Our encoding engender penalties less than 1: Following Schönberger can hence derive cheap plans unobtainable within more et al. [5], the smallest violation in depends on the dis- restricted JO solution spaces. cretisation precision . Specifically, = / =
∑=1 be assumed by , and is some small constant.
Finally, our encoding substantially improves resourceeficiency in comparison to Nayak
et al. [18], mandating a number of qubits that is cubic, rather than exponential, in the number of relations. lysed in [37], including JO optimisation. Their method exploits information learned from prior joins. However, it remains challenging to make such approaches robust against frequent data updates, as required for databases, to avoid ineficiencies engendered by repeated learning. ing by Schönberger et al. [5] in several ways: (1) While the baseline encoding is a faithful transformation of the JO-MILP method by Trummer and Koch [6], and hence inherits MILP limitations, our novel encoding natively encodes JO as QUBO, and is hence tailored to contemporquantum machine learning for database research is ana- the requirements for such systems, by identifying, analysOur work heavily improves on the baseline encod- funding program “Quantum Technologies—from Basic Re
MS and WM were supported by the German Federal Ministry of Education and Research (BMBF), search to Market”, grant number 13N15647. MS and WM also acknowledge support by the High-Tech Agenda of the Free State of Bavaria.
While quantum computing remains largely unexplored within database research, the aptness of QPUs was recently analysed for a selection of database issues [21]. These problems include database transaction scheduling [2, 3, 4] and multiple query optimisation [1]. However, their methods and encodings are problem-specific, and hence cannot be re-used for JO optimisation.
The JO problem is one of the most fundamental and well studied problems in query optimisation [22, 16, 23, 7, 6, 24]. Methods to handle this problem largely follow one of two fundamental paradigms: Firstly, dynamic programming (DP) approaches [25, 26, 15, 27, 28], yielding optimal solutions, yet unable to scale to large queries, given the super-polynomial search space growth of common JO classifications. Hence, heuristic methods [29, 30, 31, 32, 33, 34, 35] seek to optimise larger queries, where DP methods fail, at the cost of no guarantees on solution quality. This category includes both, the baseline JO method for QPUs by Schönberger et al. [5], and our novel method.
The JO problem was originally solved on QPUs by Schönberger et al. [5]. A QUBO encoding for bushy join trees has been proposed and analysed by Nayak et al. [18]. As discussed above, the exponential scaling of qubits substantially limits the scalability of their approach. Winker et al. [36] explore the use of quantum machine learning on JO optimisation [36], and the broader potential of
Our novel JO-QUBO encoding exhausts the full potential of quantum hardware for join ordering, allowing QPUs to optimise general, unrestricted join trees. However, even for solution spaces restricted to left-deep trees, current early-stage QPUs can only optimise small-scale queries [5]. Therefore, we cannot expect contemporary systems to yield meaningful results when optimising yet more complex JO classifications.
Still, our novel encoding provides valuable architectural insights: For instance, the reduction of degree 3 terms, required to conform to contemporary quantum hardware, yields a variable overhead that is cubic in the number of relations, which (1) substantially increases the number of required qubits, and (2) severely enhances the search space, to the detriment of scalability.
We hence identify the requirement for quadratic terms as a clear limitation of current quantum systems, which can be addressed by augmenting QPUs to allow degree 3 polynomials. Thereby, we can significantly enhance the conformance of QPUs for JO optimisation. In addition, we plan to investigate the applicability of gate-based quantum approaches like QAOA, which can trade qubit requirements for increased algorithmic complexity in other areas, on our novel encoding, as part of future research. Hence, rather than merely waiting for the arrival of mature quantum systems, it is necessary to specify ing and optimising problem encodings, such that QPUs tailored to those requirements can be crafted. ary optimization problem preprocessing: Theory and empirical analysis (2017). a r X i v : 1 7 0 5 . 0 9 8 4 4 . [1] I. Trummer, C. Koch, Multiple query optimiza- [13] T. Krüger, W. Mauerer, Quantum annealing-based tion on the D-Wave 2X adiabatic quantum com- software components: An experimental case study puter, Proceedings of the VLDB Endowment 9 with SAT solving, in: Proceedings of the IEEE/ACM (2016) 648–659. 42nd International Conference on Software En[2] S. Groppe, J. Groppe, Optimizing transaction gineering Workshops, ICSEW’20, Association for schedules on universal quantum computers via Computing Machinery, New York, NY, USA, 2020, code generation for grover’s search algorithm, in: p. 445–450. URL: https://doi.org/10.1145/3387940. 25th International Database Engineering & Applic- 3391472. doi:1 0 . 1 1 4 5 / 3 3 8 7 9 4 0 . 3 3 9 1 4 7 2 . ations Symposium, IDEAS 2021, Association for [14] D.-W. S. Inc., Problem-solving handbook, 2023. Computing Machinery, New York, NY, USA, 2021, URL: https://docs.dwavesys.com/docs/latest/ p. 149–156. URL: https://doi.org/10.1145/3472163. handbook_reformulating.html.
3472164. doi:1 0 . 1 1 4 5 / 3 4 7 2 1 6 3 . 3 4 7 2 1 6 4 . [15] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, [3] T. Bittner, S. Groppe, Hardware accelerating the R. A. Lorie, T. G. Price, Access path selection in a optimization of transaction schedules via quantum relational database management system, in: Proannealing by avoiding blocking, Open Journal of ceedings of the 1979 ACM SIGMOD International Cloud Computing (OJCC) 7 (2020) 1–21. Conference on Management of Data, SIGMOD ’79, [4] T. Bittner, S. Groppe, Avoiding blocking by schedul- Association for Computing Machinery, New York, ing transactions using quantum annealing, in: NY, USA, 1979, p. 23–34. URL: https://doi.org/10. Proceedings of the 24th Symposium on Interna- 1145/582095.582099. doi:1 0 . 1 1 4 5 / 5 8 2 0 9 5 . 5 8 2 0 9 9 . tional Database Engineering & Applications, IDEAS [16] G. Moerkotte, Building query compilers, 2020. URL: ’20, Association for Computing Machinery, New https://pi3.informatik.uni-mannheim.de/~moer/ York, NY, USA, 2020. URL: https://doi.org/10.1145/ querycompiler.pdf.
3410566.3410593. doi:1 0 . 1 1 4 5 / 3 4 1 0 5 6 6 . 3 4 1 0 5 9 3 . [17] A. Lucas, Ising formulations of many NP problems, [5] M. Schönberger, S. Scherzinger, W. Mauerer, Ready Frontiers in Physics 2 (2014) 5. to leap (by co-design)? join order optimisation on [18] N. Nayak, J. Rehfeld, T. Winker, B. Warnke, U. Çaquantum hardware, in: Proceedings of the 2023 likyilmaz, S. Groppe, Constructing optimal bushy ACM International Conference on Management of join trees by solving qubo problems on quantum Data, ACM, Seattle, WA, USA, 2023. hardware and simulators, in: Proceedings of the In[6] I. Trummer, C. Koch, Solving the join ordering ternational Workshop on Big Data in Emergent Disproblem via mixed integer linear programming, in: tributed Environments, BiDEDE ’23, Association Proceedings of the 2017 ACM International Confer- for Computing Machinery, New York, NY, USA, ence on Management of Data, ACM, New York, NY, 2023. URL: https://doi.org/10.1145/3579142.3594298.
USA, 2017, pp. 1025–1040. doi:1 0 . 1 1 4 5 / 3 5 7 9 1 4 2 . 3 5 9 4 2 9 8 . [7] T. Neumann, B. Radke, Adaptive optimization [19] S. Cluet, G. Moerkotte, On the complexity of generof very large join queries, in: Proceedings of ating optimal left-deep processing trees with cross the 2018 International Conference on Manage- products, in: Database Theory — ICDT ’95, Springer ment of Data, SIGMOD ’18, Association for Com- Berlin Heidelberg, Berlin, Heidelberg, 1995, pp. puting Machinery, New York, NY, USA, 2018, 54–67. p. 677–692. URL: https://doi.org/10.1145/3183713. [20] B. O’Gorman, R. Babbush, A. Perdomo-Ortiz, 3183733. doi:1 0 . 1 1 4 5 / 3 1 8 3 7 1 3 . 3 1 8 3 7 3 3 . A. Aspuru-Guzik, V. Smelyanskiy, Bayesian net[8] IBM Quantum, Cloud access to quantum com- work structure learning using quantum annealing, puters provided by IBM, 2022. URL: https:// The European Physical Journal Special Topics 224 quantum-computing.ibm.com. (2015) 163–188. [9] C. McGeoch, P. Farré, The D-Wave Advantage sys- [21] U. Çalikyilmaz, S. Groppe, J. Groppe, T. Winker, tem: An overview, Technical Report 14-1049A-A, S. Prestel, F. Shagieva, D. Arya, F. Preis, L. GruD-Wave Systems Inc, 2020. enwald, Opportunities for quantum acceleration [10] E. Farhi, J. Goldstone, S. Gutmann, A of databases: Optimization of queries and transquantum approximate optimization algorithm action schedules, Proc. VLDB Endow. 16 (2023) (2014). a r X i v : 1 4 1 1 . 4 0 2 8 . 2344–2353. URL: https://doi.org/10.14778/3598581. [11] Z. Bian, F. Chudak, W. Macready, G. Rose, The Ising 3598603. doi:1 0 . 1 4 7 7 8 / 3 5 9 8 5 8 1 . 3 5 9 8 6 0 3 . model: Teaching an old problem new tricks, Tech- [22] V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. Boncz, nical Report, D-Wave Systems Inc., 2010. A. Kemper, T. Neumann, Query optimization [12] M. Lewis, F. Glover, Quadratic unconstrained bin- through the looking glass, and what we found running the join order benchmark, The VLDB Journal for optimizing large join queries, volume 19, Asso27 (2018) 643–668. ciation for Computing Machinery, New York, NY, [23] T. Neumann, Query simplification: Graceful de- USA, 1990, p. 312–321. URL: https://doi.org/10.1145/ gradation for join-order optimization, in: Proceed- 93605.98740. doi:1 0 . 1 1 4 5 / 9 3 6 0 5 . 9 8 7 4 0 . ings of the 2009 ACM SIGMOD International Con- [33] A. Swami, A. Gupta, Optimization of large join ference on Management of Data, SIGMOD ’09, As- queries, volume 17, Association for Computing sociation for Computing Machinery, New York, NY, Machinery, New York, NY, USA, 1988, p. 8–17. URL: USA, 2009, p. 403–414. URL: https://doi.org/10.1145/ https://doi.org/10.1145/971701.50203. doi:1 0 . 1 1 4 5 / 1559845.1559889. doi:1 0 . 1 1 4 5 / 1 5 5 9 8 4 5 . 1 5 5 9 8 8 9 . 9 7 1 7 0 1 . 5 0 2 0 3 . [24] X. Yu, G. Li, C. Chai, N. Tang, Reinforcement learn- [34] A. Swami, Optimization of large join queries: Coming with tree-lstm for join order selection, in: 2020 bining heuristics and combinatorial techniques, in: IEEE 36th International Conference on Data Engin- Proceedings of the 1989 ACM SIGMOD Internaeering (ICDE), 2020, pp. 1297–1308. doi:1 0 . 1 1 0 9 / tional Conference on Management of Data, SIGI C D E 4 8 3 0 7 . 2 0 2 0 . 0 0 1 1 6 . MOD ’89, Association for Computing Machinery, [25] A. Meister, G. Saake, GPU-accelerated dy- New York, NY, USA, 1989, p. 367–376. URL: https: namic programming for join-order op- //doi.org/10.1145/67544.66961. doi:1 0 . 1 1 4 5 / 6 7 5 4 4 . timization, Technical Report, 2020. URL: 6 6 9 6 1 . https://www.inf.ovgu.de/inf_media/downloads/ [35] I. Trummer, C. Koch, Parallelizing query optimforschung/technical_reports_und_preprints/2020/ ization on shared-nothing architectures, Proc.
TechnicalReport+02_2020-p-8268.pdf. VLDB Endow. 9 (2016) 660–671. URL: https: [26] G. Moerkotte, T. Neumann, Analysis of two existing //doi.org/10.14778/2947618.2947622. doi:1 0 . 1 4 7 7 8 / and one new dynamic programming algorithm for 2 9 4 7 6 1 8 . 2 9 4 7 6 2 2 . the generation of optimal bushy join trees without [36] T. Winker, U. Çalikyilmaz, L. Gruenwald, S. Groppe, cross products, in: Proceedings of the 32nd Interna- Quantum machine learning for join order optimiztional Conference on Very Large Data Bases, VLDB ation using variational quantum circuits, in: Pro’06, VLDB Endowment, 2006, p. 930–941. ceedings of the International Workshop on Big Data [27] B. Vance, D. Maier, Rapid bushy join-order optimiza- in Emergent Distributed Environments, BiDEDE tion with cartesian products, in: Proceedings of the ’23, Association for Computing Machinery, New 1996 ACM SIGMOD International Conference on York, NY, USA, 2023. URL: https://doi.org/10.1145/ Management of Data, SIGMOD ’96, Association for 3579142.3594299. doi:1 0 . 1 1 4 5 / 3 5 7 9 1 4 2 . 3 5 9 4 2 9 9 . Computing Machinery, New York, NY, USA, 1996, p. [37] T. Winker, S. Groppe, V. Uotila, Z. Yan, J. Lu, 35–46. URL: https://doi.org/10.1145/233269.233317. M. Franz, W. Mauerer, Quantum machine learning: doi:1 0 . 1 1 4 5 / 2 3 3 2 6 9 . 2 3 3 3 1 7 . Foundation, new techniques, and opportunities for [28] G. Moerkotte, T. Neumann, Dynamic program- database research, in: Companion of the 2023 Interming strikes back, in: Proceedings of the 2008 national Conference on Management of Data, SIGACM SIGMOD International Conference on Man- MOD ’23, Association for Computing Machinery, agement of Data, SIGMOD ’08, Association for New York, NY, USA, 2023, p. 45–52. URL: https://doi. Computing Machinery, New York, NY, USA, 2008, org/10.1145/3555041.3589404. doi:1 0 . 1 1 4 5 / 3 5 5 5 0 4 1 . p. 539–552. URL: https://doi.org/10.1145/1376616. 3 5 8 9 4 0 4 .
1376672. doi:1 0 . 1 1 4 5 / 1 3 7 6 6 1 6 . 1 3 7 6 6 7 2 . [29] M. Steinbrunn, G. Moerkotte, A. Kemper, Heuristic and randomized optimization for the join ordering problem, The VLDB journal 6 (1997) 191–208. [30] J.-T. Horng, C.-Y. Kao, B.-J. Liu, A genetic algorithm for database query optimization, in: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, 1994, pp. 350–355 vol.1.
doi:1 0 . 1 1 0 9 / I C E C . 1 9 9 4 . 3 4 9 9 2 6 . [31] N. Bruno, C. Galindo-Legaria, M. Joshi, Polynomial heuristics for query optimization, in: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), 2010, pp. 589–600. doi:1 0 . 1 1 0 9 / I C D E .
2 0 1 0 . 5 4 4 7 9 1 6 . [32] Y. E. Ioannidis, Y. Kang, Randomized algorithms