On the complexity of approximate query optimization

ABSTRACT

In this work, we study the complexity of the problem of approximate query optimization. We show that, for any δ > 0, the problem of finding a join order sequence whose cost is within a factor 2^{Θ(log1-δ(K))} of K, where K is the cost of the optimal join order sequence is NP-Hard. The complexity gap remains if the number of edges in the query graph is constrained to be a given function e(n) of the number of vertices n of the query graph, where n(n - 1)/2 - Θ(n^τ) ≥ e(n) ≥ n + Θ(n^τ) and τ is any constant between 0 and 1. These results show that, unless P=NP, the query optimization problem cannot be approximately solved by an algorithm that runs in polynomial time and has a competitive ratio that is within some polylogarithmic factor of the optimal cost.

REFERENCES

• 1: Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
• 2: Sophie Cluet , Guido Moerkotte, On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Proceedings of the 5th International Conference on Database Theory, p.54-67, January 11-13, 1995
• 3: Chihping Wang , Ming-Syan Chen, On the Complexity of Distributed Query Optimization, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.650-662, August 1996 [doi>10.1109/69.536256]
• 4: Sanjeev Arora. Probabilistic Checking of Proofs and Hardness of Approximation Algorithms. Technical Report TR-476-94. Department of Computer Science, Princeton University, 1994.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 7: S. Chatterji, S. S. K. Evani, S. Ganguly and M. D. Yemmanuru. On the complexity of approximate query optimization. Lucent Internal Technical Document ITD-02-42549Z, 2002. Lucent Technologies.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Design, Languages, Theory