On the Complexity of Approximate Query Optimization Sourav Chatterji, Sai Surya Kiran Evani, Sumit Ganguly, and Mahesh Datt Yemmanuru   View Paper (PDF)   Return to Query Processing and Optimization II Abstract In this work, we study the complexity of the problem of approximate query optimization. We show that, for any d > 0, the problem of finding a join order sequence whose cost is within a factor 2T(log1-d(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 - T(nt) = e(n) = n + T(nt) and t 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. DiSC'03 © 2003 Association for Computing Machinery