WorksComputer Science
Approximation Algorithms for Product Query Optimization
Abstract
We study database query optimization for Cartesian products. This problem is equivalent to finding an optimal plan for multiplying non-negative integers. We call this problem multiplication ordering. We show that the problem has an FPTAS when the cost of a plan is the sum of all intermediate products; both in the case when the overall final product is counted and when it is not. We show that using the optimal solution to the well-known product partition problem does not always lead to an optimal plan, but we establish connections between the product partition and multiplication ordering problems. Finally, we prove that multiplication ordering is in PTIME (resp. \NP-complete) when integers are powers of a same base where the exponents are written in unary (resp. in binary).
Introduction
In database systems, query optimization consists in choosing the right actions to perform for computing the result of a query. For instance, should we compute the plan or the plan , where is the join operation for answering to the following SQL query?
SELECT a.*
FROM a,
b,
c
WHERE a.a_id = b.a_id
AND b.b_id = c.b_id
In a seminal paper, [6] proved that computing an optimal plan is NP-complete; their plans are left-deep join trees and they model the cost by means of a selectivity factor between two relations and giving an estimation on the proportion of the size of compared to . They ask to compute a plan that only uses the join operations explicitly given in the query. In [4], NP-hardness is proven for a more general notion of cost satisfying so-called ASI (adjacent sequence interchange) property and allowing for computing any Cartesian products in the plan. In [10], it was proven that the problem is also NP-complete when plans are arbitrary trees (bushy trees) and only Cartesian products are considered. They consider the output cost that is the sum of the sizes (i.e., number of tuples) of all intermediate products computed during the plan.
Example 1. Consider relations , , , of respective sizes 2, 2, 5, 10. The plan can be represented by the following tree on which we have written the intermediate product sizes:

Figure 1.
The output cost of this plan is . As the final product size is always the same, we may also exclude it in the cost. The output cost without the root is .
The cost of a plan including the root is denoted by while its cost without the root is denoted by . Although this query optimization problem is called cross product optimization in [10], we change its name to MultOrd to emphasize the fact that the input instance only contains the sizes of the relations. In particular the optimization process is agnostic about the very content of the relations. Thus, MultOrd corresponds to the natural problem of computing Cartesian products (i.e., joins without any conditions; no WHERE clauses in SQL) and where only the sizes of the relations are used to determine an optimal plan.
Observe that the NP-hardness proven in [10] relies on a reduction from Exact Covering With 3-Sets, in which elements of sets are encoded by relations where sizes are prime numbers. This setting is rather rare and one may wonder whether the problem is really so difficult in general. Note that the reduction in [10] involves the first prime numbers making the resulting instance of MultOrd in poly-size even if numbers are given in unary. Said differently, MultOrd is NP-hard when numbers are given in unary. As the numbers represent sizes of relations written explicitly, it is practically relevant to consider the numbers written unary. In the current paper, we consider the numbers to be written binary making our approximation results stronger.
Our Contribution
We show that MultOrd, although NP-hard, is easy to approximate. This contrasts with the inaproximability of query optimization in general [3].
We show, see Theorem 2, that MultOrd has an FPTAS (fully polynomial-time approximation scheme), meaning that we can find a -approximate plan, in polytime in the size of the input and in . We assume that the size of the relation sizes are given in binary.
In the output cost, we always count the product of the sizes of all relations in the root. As this final product is present in all plans, we also consider the notion of cost in which we ignore the root (i.e., we do not count the global product of all the inputs). In the previous example, the cost is then . Theorem 3 shows that MultOrd with the cost ignoring the global product at the root also has an FPTAS.
We also compare multiplication ordering to product partition. First we show that an approximate solution for ProdPart helps to find an approximate solution for MultOrd (Lemma 10). However, applying product partition is not always part of the optimal plan, and we exhibit an example where applying a product partition at the root does not lead to an optimal plan for multiplication ordering (see Proposition 8).
Interestingly, we also focus on MultOrd when the sizes have a form of regularity (in contrast to being prime numbers as in the NP-hardness proof [6]). We prove that when the sizes are all powers of the same base (e.g., , , , , then MultOrd is in PTIME (see Theorem 4). However the problem becomes NP-complete when the exponents are written in binary (see Theorem 5).
Paper outline. In Section 2, we briefly discuss the related work both in database theory and in algorithms. In Section 3 we formally define MultOrd. Then, in Section 4, we explain how to exactly solve MultOrd with a naïve algorithm; this is important because it gives subroutines for the approximation algorithms. In Section 5, we give two preprocessing rules allowing us to only consider input numbers greater or equal to 2. In Section 6, we introduce two strategies: Pacman-plan and Half-plan and prove upper and lower bounds on the cost of any plan. In § 7, we show that MultOrd has a FPTAS both for cost and cost. In § 8, we highlight strong links between the famous ProductPartition problem and MultOrd. In § 9, we then tackle the restriction on the input to powers. In § 10, we discuss future work.
Related work
The MultOrd problem has direct connections to problems in database query optimization as well as to ordering problems studied in other areas.
Database theory
Ordering of joins in database is a vast topic, see Table p. 45 in [8]. The problem is NP-complete in general, see the seminal paper [6] in which they prove that it is NP-hardness to get an optimal left-deep join tree where we also give a selectivity factor for each pair of relations that can be joined. Later, in [4], they proved that this problem is also NP-complete if we allow for Cartesian products, meaning that all pair of relations are joinable. In [3], it is shown that query optimization in general cannot be approximated.
The case when all selectivity factors are equal to 1 corresponds to computing Cartesian products. In particular, searching for an optimal (with the output cost) bushy 1 tree for computing a Cartesian product is NP-hard [10]. This problem is exactly MultOrd. Observe that if we know the left-right order of the leaves of the tree, we can find OPT by dynamic programming. However nothing was known concerning approximation.
Ordering in the context of other multiplication problems
In algorithms, many problems involve ordering operations on a certain number of objects from some class. Sometimes the outcome is always the same (e.g., multiplying integers or matrices), but intermediate objects of vastly different sizes can be created, depending on the ordering of operations. Thus, an important goal in this context is to try to order these operations (e.g., multiplications) so as to reduce the sizes of the intermediate objects.
The most famous problem of this kind is finding the optimal ordering for the computation of a products of matrices, . This task can be done in and is a standard textbook exercise in dynamic programming [5]. Dynamic programming can be applied here because the left-right order of the matrices is fixed; only the optimal bushy tree has to be computed.
Many multiplication ordering problems are NP-hard. One problem which seems close is the Vertex-EliminationProblem [2] consisting of iteratively eliminating internal nodes in a directed graphs, namely adding edges from all in-neighbors to all out-neighbors and deleting the node. The cost to minimize is the sum of all in-degree times out-degree at the moment of the elimination of the node. Another related work can be found in [AKC†21].
Definition of the MultOrd problem
An instance of MultOrd is a multiset of positive integers . A plan for computing is a binary tree whose leaves are . A plan can be seen as a syntactic tree of an expression for computing with parenthesis. For the rest of the paper, unless stated otherwise, denotes the number of integers in the instance. We sometimes refer to these input integers as elements.
Example 2. A plan for could be that corresponds to the syntactic
tree
×
/ \
× ×
/ \ / \
5 2 10 2
For a plan , we denote by the multiset composed of the labels of the leaves of . The evaluation of a plan is , that is the product of all leaves of . The cost of a plan (denoted ) is the sum of all the intermediate products at internal nodes of (we exclude the root and include the leaves). The cost that also includes the root is denoted by . The formal definitions are as follows.
Definition 1 (cost including the root). For a leaf , . For a plan , .
Definition 2 (cost excluding the root). For al plan , .
Alternatively, the cost excluding the root can also be defined by induction as follows. The base case is for a leaf which is also a root in that case. The cost of the leaves will be accounted for during their evaluation. For a plan , we have .
Example 3. If is then and .
Definition 3. is the following optimization problem: given a multiset of positive integers written in binary, compute a plan to compute minimizing .
We will also consider the variant where we minimize . To avoid ambiguity, we talk about ‘ for cost’ and ‘ for ’. Note that the distinction is not important for exact solving, since in this case, the two problems are equivalent. However the distinction is important when considering approximation ratios.
Let be an instance of and a non-empty subset of . We say that a plan is following if it is of the form such that and . Moreover, for any subset , we denote the weight of in to be . Therefore the cost of a plan following is .
Exact solving
For an instance , we denote by (resp. ) the optimal cost of the problem for this instance using the cost (resp. ) objective function.
Solving could be decomposed into phases: find the right permutation on the leaves and then choose the inner structure of the tree. The following proposition states that if the right permutation has been found, the problem can be solved in polynomial time. This is especially useful since some algorithms in databases rely on a particular choice of permutation. Given an instance of , a plan computing respecting the order is a plan which in its associated bracketing, element appears before if and only if . Equivalently, it is a plan in which the binary tree’s leaves are in that order and such that no edges of the tree are crossing.
Example 4. For the instance , the plan computes the product and respects the order, but the plan does not respect the order.
Proposition 1. Let be an instance of . One can find an optimal plan respecting the order in time polynomial in the size of the instance.
Proof. We propose an algorithm based on dynamic programming. The subproblems are , which denote the optimal value of of a plan to compute that follows the order . We now prove that:
The base case is true. The inductive case is proven as follows. In the sequel, we say that is a plan for when it is a plan for computing in that order. Thus,
We can design a dynamic programming algorithm that fills a table of size . Each step costs at most arithmetic operations, resulting in a complexity of .
Since we can enumerate all permutations of and solve the problem for each permutation using Proposition 1, the final complexity is since .
Corollary 1. MultOrd is solvable in .
We can actually obtain a faster bound.
Theorem 1. MultOrd can be solved in time.
Proof. Let be an instance of MultOrd. At each step, every plan splits the instance into two child subplans. Thus,
Then, consider a dynamic programming algorithm for this formula. It has to feed an array of size . At each step, it goes though all non-trivial subsets. We denote by the biggest . Notice that the cost of computing the product of some ’s is equal to the sum of their representations’ sizes. Therefore the computation cost for the instance is:
Using the binomial theorem stating that . Thus the computation times is . Moreover, note that minimizing is the same as minimizing cost.
Preprocessing
In this section, we highlight some safe preprocessing rules that can be applied at the beginning of any algorithm so that we can restrict our attention to more specific instances.
Proposition 2. Let be an instance of MultOrd and let , then .
Proof. Let (resp. ) be an optimal plan for (resp. ) for the cost objective function. Let . Note that is a valid plan for the instance since where is the disjoint union operator. Then .
Proposition 3. Let be an instance of MultOrd such that one input element is equal to . Then there is an optimal strategy that starts by multiplying this element with the next smallest element.
Proof. Assume , that and that be the next smallest input element. Let be an optimal strategy on and be an optimal strategy on the instance . Let be the strategy where we first multiply and , then we apply the strategy of . We claim that is an optimal plan. To prove it, first notice that since the multiplication of and is accounted as a leaf in . Now, observe that in , is multiplied with some subtree . Let be the subplan appearing in and be the set of numbers involved in . First note that and that by definition of . Then,
Thus, is an optimal plan because is optimal.
Therefore, from now on, we assume that all numbers in any input instance of MultOrd are greater than or equal to 2.
Bounds on cost
In this section, we introduce new lower and upper bounds on the cost of plans on a fixed instance which, in the following, will allow us to prove approximation ratios for approximation algorithms. First, we introduce the Pacman-plan (denoted ) which has the highest cost for any instance. Specifically, given an instance on elements such that , the first multiplication is the product of and and for , the th multiplication is the product of with the product of the first elements. At each step, the Pacman plan introduces a new largest number; its shape is a caterpiller. Said differently, the Pacman-plan for is . Visually:

Figure 2 (PDF p. 6).
Example 5. The Pacman-plan for is .
The cost of a Pacman-plan is as follows.
Proposition 4. Let be an instance of MultOrd such that and let be the Pacman-plan on . Then, by definition,
Proposition 5. The Pacman-plan has the highest achievable cost.
Proof. For an instance on elements, we compare the Pacman-plan on , denoted , to another (arbitrary) plan . Both plans count the leaves and the root (using ), so we will only compare the cost of the multiplications at the internal nodes (i.e., non-root and non-leaf nodes).
We will argue that there is a bijection between the internal nodes of and the internal nodes of such that for all internal nodes of , the evaluation of this node is at least as large as the evaluation of the associated node of . To do this, for each plan, we order the multiplications in that plan so that a multiplication at a parent node comes after the multiplications corresponding to any of its children (and hence descendants). We call such an order a hierarchy-respecting order. We use the following claim.
Claim 1. In any hierarchy-respecting order, the multiplication corresponds to the product of at most elements.
Proof. Suppose each time we multiply two numbers together we use a piece of glue to connect them. For example, a product of two elements contains one piece of glue and a product of four elements contains three pieces of glue. Since we use exactly one new piece of glue for each multiplication, at the step we can produce a product corresponding to a number using at most pieces of glue. Hence, it can be the product of at most elements, which proves the claim. ◊
Observe that the multiplication in the (unique) hierarchy-respecting order of is the product of the largest elements. For a hierarchy-respecting order for , by Claim 1, the multiplication can be the product of at most elements, which is clearly at most the product of the largest elements corresponding to the multiplication in . □
Lemma 1. Let be an instance of MultOrd such that all numbers are at least 2 and let be a Pacman-plan on . Then .
Proof. Wlog, assume and and let . By Proposition 4 we have
Note that since all respect , then . Therefore,
Last inequality holds since and those the sum is converging. Therefore, . □
Corollary 2. Let be an instance of MultOrd such that all numbers are at least 2 and let be a Pacman-plan on . Then .
Lemma 2. Let be some integers greater or equal to 2, then .
Proof. For ,
Thus, the property is true for . Assume the property is true for and let be integers greater than 2. Then
The first inequality holds by the induction hypothesis and the second one holds by the case for . Then the property holds. □
Proposition 6. Consider an instance of MultOrd such that all numbers are at least 2, then for all plans on , .
Proof. Let be a Pacman-plan on . By Proposition 5, and using Corollary 2 and Lemma 2 we have . So . □
Lemma 3. Let be an instance of MultOrd on at least three elements and let be a plan on . Then .
Proof. Assume that both and are plans on at least two elements. Then no leaves are accounted in nor in . Therefore .
Otherwise, wlog, assume is a plan on only one element thus is a plan on at least two elements. Then .
Half-plan
In this subsection, we introduce the naive notion of a Half-plan (denoted ) and prove an upper bound on its cost. These results are used to prove approximation results such as an FPTAS for the cost with the root in Theorem 2. A Half-plan on an instance is a plan that puts half of the input numbers on one side and the rest of the numbers on the other side. Therefore if the Half-plan on instance on elements, , follows , then both and have at least elements. Notice that an instance can have several Half-plans.
Example 6. An example of a Half-plan for is .
Lemma 4. Let be an instance of MultOrd, then .
Proof. Let be an Half-plan on . Firstly, notice that since all numbers in are greater than or equal to and since contains at least numbers, we have, . Since , we have,
Similarly, . Therefore,
First inequality uses Proposition 6 on and and the second inequality uses the above inequalities.
Lemma 5. For any instance of MultOrd, .
Proof. Let be an instance of MultOrd such that then, by Proposition 4, we have
Using Lemma 4 we have,
Trivial approximation factors
Thanks to the bound on the cost of a plan obtained in Proposition 6, we are able to find approximation factors for any plan. Namely, we show that no matter the chosen plan, we can prove a guarantee on its cost.
Lemma 6. Let be an instance with all input elements . Then every plan on is a 3-approximation of for the cost objective function.
Proof. Let be a plan and let be an optimal strategy on . Then by Proposition 6 we have
Lemma 7. Let be an instance of such that all numbers are at least 2 and let . Then every plan on is a -approximation for cost.
Proof. Let be a plan on . Since then either or is bigger than . Thus . Thus . Moreover, by property 6 since all ’s are at least 2, we have . Thus .
FPTAS
In this section, we present a fully polynomial-time approximation scheme (FPTAS) for both the and cost objective functions. Given a parameter , the algorithm produces a -approximate solution in time polynomial in both and in the size of the instance.
Cost that includes the root
First, we tackle the case of the cost that includes the final product at the root, which is easier and will be used in the FPTAS for the case in which the cost excludes the root.
Theorem 2. for has an FPTAS.
Proof. Let be the parameter in the desired approximation bound and let be an instance of on elements. Thanks to Proposition 3, we can apply a polynomial times preprocessing on the instance and assume that all input elements in are at least 2. Then, we consider the following algorithm:
If , we solve it using the exact algorithm of Theorem 1.
Otherwise construct a Half-plan on (defined at the end of § 6).
The algorithm outputs a -approximation. If , we solve exactly the problem, the output strategy is optimal and thus is a -approximation. Otherwise, . Lemma 4 give us that since the smaller number in is at least 2. Therefore,
Since . Hence is a -approximation of using .
Complexity analysis. If then we consider the dynamic programming of Theorem 1 running in time . We have . Then which is polynomial in and does not depend on . Otherwise, notice that constructing and is polynomial in and in since we just split the ’s in half and take arbitrarily ordering. Thus, this shows that the proposed algorithm is a FPTAS algorithm.
Cost that excludes the root
We now tackle the problem where we use the cost objective function, which does not count the root. For this purpose, we introduce the known ProdPart problem which is an NP-complete problem first introduced in [9]. ProdPart takes as input a multiset of positive integers and outputs a non-empty subset minimizing the majority of in denoted .
ProdPart has been proved having an FPTAS algorithm in section 4 of [9]. We will use this result to design an FPTAS algorithm for MultOrd for cost.
Proposition 7. [See Section 4 of [9]]. There is an algorithm running in time that computes a -approximation of ProdPart.
In order to make the connection between ProdPart and MultOrd, we have to compare the majority and the weight. We will firstly show that the ProdPart is equivalent to finding a subset minimizing the weight of in , denoted . Notice that for every plan following a set , .
Lemma 8. Let be an instance of ProdPart, if minimizes then also minimizes .
Proof. Let . Notice first that and that .
Let . Notice that , so is increasing. Thus, , . Therefore, if minimizes , also minimizes .
Lemma 9. Let be an instance of ProdPart, , minimizing , and let be a -approximation of . Then is a -approximation of .
Proof. Firstly, since is a -approximation of , . Secondly, notice that . Thus . Let and , thus
Since is minimizing , by Lemma 8, also minimizing . This concludes the proof.
Corollary 3. There is an algorithm running in time that computes a -approximation of the minimization of on an instance of ProdPart.
Proof. By Proposition 7 and Lemma 9.
Theorem 3. MultOrd for cost has an FPTAS.
Proof. Let an instance of MultOrd and a fixed constant and let . As in the FPTAS presented previously, we first perform a preprocessing step so we can assume all numbers in are greater or equal to 2. We consider the following algorithm:
Compute a set that is a -approximation of .
Return where (resp. ) is computed via the FPTAS for with on instance (resp. ).
This algorithm outputs a -approximation Firstly, using the bound found in the proof of Theorem 2, we have that and the same holds for . Thus
Let be an optimal plan on , be the set followed by and be the subset minimizing . Thus using Lemma 9 and since is optimal. Therefore,
This concludes the proof that the algorithm is a -approximation of MultOrd for cost.
Complexity Step 1 can be implemented in polynomial time in , and the number of bits in the ’s thanks to Proposition 7. This is polynomial in the size of the input and in since ’s are given in binary, thus the log of the biggest is its size.
Link to ProdPart
The purpose of this section is to highlight links between MultOrd and ProdPart motivated by the FPTAS for the cost objective described in Theorem 3. More precisely, we prove that to reach optimality for MultOrd, the first partition from the top of the plan has to be a good approximation of ProdPart which gives rise to conditions to achieve optimality. However, MultOrd and ProdPart are not equivalent in the general case (but are when all input elements have the same value). Since instances of size two are obvious (no choices to make), we can assume that all considered instances in this section have at least three input elements.
Lemma 10. Let be an instance of MultOrd and let be an approximation of ProdPart on . Then every plan following is a -approximation for cost.
In particular, since each elements are greater or equal to 2, the plan is always a -approximation.
Proof. We first introduce three plans. Let be a plan following and be a plan following with being an optimal solution of ProdPart on and let be an optimal solution of MultOrd on . Then, let and . Wlog we can assume . Thus, and then . Therefore, using Lemma 1 on , we have
and using Lemma 1 on , we have
Then,
The first inequality uses above remarks. The second one is because is either equal to or to and by using the assumption that is a -approximation of ProdPart on . The third one is by observing that and . The fourth one is because is an optimal solution of ProdPart and the fifth one is using Lemma 3.
Corollary 4. Let be an instance of MultOrd and let be a plan following an optimal solution to ProdPart on . Then the cost of tend to the optimal cost when tends to infinity.
Proof. Let and using Lemma 10 with , we have
Lemma 11. Let be an instance of MultOrd and let be a subset of being worse than or equal to a -approximation of ProdPart. Then no plan following is optimal.
Proof. Let be a subset of being optimal for ProdPart and let following . Let following . Then,
First inequality uses Lemma 3, second uses the fact that is worst or equal to a -approximation of ProdPart. The third one uses the assumption that all elements are greater or equal to 2. The fourth inequality uses Lemma 1 on and on .
Lemma 10, Lemma 11, Proposition 9 and the FPTAS algorithm in Theorem 3 highlighted strong connections between MultOrd and ProdPart. Therefore, we introduce the notion of ProdPart-plan, which is a plan following the strategy consisting of splitting the instance using an optimal solution to ProdPart at each step. A direct consequence of Lemma 10 is that every ProdPart-plan are 2-approximation of MultOrd. However, the following proposition contradict optimality of ProdPart-plans.
Proposition 8. ProdPart-plans are not always optimal.
Proof. We highlight a counter example following this logic: Let , and , where there are occurrences of in the instance. So, for and , . Let be the plan following the described strategy. One can check that there is only one optimal solution of ProdPart on which is and is the set containing all the ’s. Let containing occurrences of . Let be the plan following at first step and then following the most balanced splitting for the subplan. Let be the plan following the ProdPart strategy, then follows . The best valid counter example found is for and . Thus is not following the ProdPart plan since its first split is not optimal for ProdPart. In fact, one can check that . One can also check that , which gives a ration of . Thus is not optimal. The values found here were verified with computers.
Proposition 9. Let be an instance of MultOrd with . Then we can solve MultOrd in time using ProdPart.
Proof. Firstly, we can assume that since if every plan will have a cost of 0 and if the optimal plan will be to successively multiply 1 to the smallest other number Proposition 3, namely any other number. Consider the following inductive algorithm:
If return the unique plan on a single leaf.
Otherwise, create , a subset containing half of the numbers (for instance ) and construct a plan following such that (resp. ) are constructed via this algorithm on the instance (resp. ).
We will show that if a plan does not split the instance in half then it cannot be optimal. Let splitting the instance in half and not doing that. Wlog, assume and . Thus . Therefore, and thus since .
Now, note that since all are equal then is the best product partition thus is worst or equal to a -approximation of ProdPart. Since and by Lemma 11, every plan not splitting in half the instance is not optimal. Thus, every optimal plan split the instance in half at each step.
The complexity analysis is simple, for an instance of size , let be the complexity to compute the solution. By induction, since the cost of creating is linear in . By the classic master theorem, .
Restriction when numbers are powers of a single basis
The NP-hardness proof in [10] uses a reduction where they construct an instance of MultOrd with distinct prime numbers in order to make distinctions between the solutions. In contrast, in this section, we consider the special case of instances with regularity. In particular, we consider instances where all the numbers are powers of the same base . For instance, for , an instance could be . Naturally, when numbers are written in binary, it corresponds to the exponents to be written in unary, which is the case we consider now.
Exponents in unary
Proposition 10. Let and let be an instance of positive powers of , namely, with . Let be a partition of the ’s which is not optimal for ProdPart. Then every plan following is not optimal.
Proof. Let be an optimal partition of ProdPart and let (resp. ) be a plan following (resp. ). Wlog, assume and . Because and all , all , therefore
Second inequality uses Corollary Corollary 2 on and . Since is not optimal for ProdPart but is, we have , which implies . Thus
First inequality uses lemma 3. Then, . Thus, every plan not following an optimal product partition on the instance are not optimal.
Theorem 4. Let and let be an instance of positive power of , namely, with . Then we can solve MultOrd on in polynomial time.
Proof. Consider the following strategy: at each level, find an optimal product partition of the instance and create a plan following it. This strategy is optimal by Proposition 10. Let be the set of index of the numbers in , namely, . Then, minimizing is the same as minimizing by Lemma 8 which is the same as minimizing which which is the same as minimizing
by taking the log. Since the number are given in binary, the exponents ’s are in unary. This is exactly an instance of 2-Partition with input written in unary which is solvable in polytime (see [7]).
Exponents in binary
Now we assume that the exponents are written in binary. For example, in the instance , , , , the exponents 5, 12, 12, 459 are written in binary. In that case, the problem becomes NP-complete.
Theorem 5. MultOrd when all numbers are power of a base and exponents written in binary is NP-complete.
Proof. For the NP-membership, the certificate is just a plan . For the NP-hardness proof, we reduce 2-Partition to MultOrd. 2-Partition is a problem that takes as input a mutliset of integers and the goal is to determine whether there exists a subset such that , it has been proved NP-complete in [7]. Let be an instance of 2-Partition with no zeros and let . Let and be an instance of MultOrd such that , . For all , we denote by . Let such that A_1\mathbin{\mathaccent\cdot\cup}A_2=A. Then let a plan following . Wlog assume that is a plan on and a plan on . If , thus we have
Similarly, we have, . Using Proposition 6, we have
Otherwise, and are such that . Wlog, we can assume that . So . Thus,
Therefore, if there are and satisfying 2-Partition problem, then we have a strategy satisfying . However, if the sets do not sum to equal value, then any will satisfies . Thus, 2-Partition reduces to MultOrd with only powers of 2. This concludes the proof. □
Future work
We believe that the bound of Lemma 10 and of Lemma 11 can be improved. We would also like to show that the plan that follows a ProdPart optimal solution at each level achieves a better approximation ratio. Another direction is to address the remaining cases from Proposition 10, when the single basis is 2 or 3.
Moreover, the MultOrd problem is a specific case of the JoinOrdering problem. Therefore, a future direction is to tackle the case of non-Cartesian product. Namely, instead of having as input only the sizes of the relations , the input is also composed of a list of selectivities that determine the sizes of the joins between relation and divided by the size of the Cartesian product between relation and . Then the only thing that changes in the problem is the definition of the evaluation of a plan on following that become
where denotes the set of indices of the elements in . However, this simple change makes the problem much harder as the evaluation is not forced to grow with successive multiplications. This generalization was already partially studied in [3], but one could use a different analysis to tackle special cases or specific conditions.
Lastly, one can consider other cost functions known in the literature and/or other abstract operations (in place of multiplication). What are the conditions for our results to still hold?
References
- [2]Matthias Bentert, Alex Crane, Pål Grønas Drange, Yosuke Mizutani, and Blair D. Sull-ivan. Structural optimal Jacobian accumulation and minimum edge count are NP-complete under vertex elimination. CoRR, abs/2506.17521, 2025.arxiv.org/abs/2506.17521
- [3]Sourav Chatterji, Sai Surya Kiran Evani, Sumit Ganguly, and Mahesh Datt Yemm-anuru. On the complexity of approximate query optimization. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 282–292, 2002.
- [4]Sophie Cluet and Guido Moerkotte. On the complexity of generating optimal left-deep processing trees with cross products. In Georg Gottlob and Moshe Y. Vardi, editors, Proceedings of the 5th Annual International Conference on Database Theory (ICDT), volume 893, pages 54–67, 1995.DOI
- [5]Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algorithms. McGraw-Hill, 2008.
- [6]Toshihide Ibaraki and Tiko Kameda. On the optimal nesting order for computing n-relational joins. ACM Trans. Database Syst., 9(3):482–502, 1984.DOI
- [7]Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–104. Plenum Press, New York, 1972.
- [8]Guido Moerkotte. Building query compilers (manuscript), 2006.
- [9]C. T. Ng, M. S. Barketau, T. C. Edwin Cheng, and Mikhail Y. Kovalyov. Product partition and related problems of scheduling and systems reliability: Computational complexity and approximation. Eur. J. Oper. Res., 207(2):601–604, 2010.DOI
- [10]Wolfgang Scheufele and Guido Moerkotte. On the complexity of generating optimal plans with cross products. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 238–248, 1997.