Multimedia selection operation placement

Based on the assumption that selections are zero-expense operations, “selection pushdown” rules, which apply selections in random order before as many joins as possible in order to reduce subsequent join costs, have been widely applied in traditional query optimization methods. However, in multimedia information systems, selections generally contain expensive multimedia operations, making “pushdown” rules no longer able to produce optimal query execution plan. Therefore, we in this paper develop a theory for optimizing queries with expensive multimedia operations, which can establish the optimal placement of each multimedia operation in a query plan by the comprehensive consideration of selectivity and unit execution cost of each operation. Then we present an algorithm for the theory and implement it in a prototype system. Experimental results show that, compared with traditional optimization algorithms, our algorithm not only has the modest time complexity that is polynomial in the number of multimedia operations in a query plan, but also can reduce the execution cost of a query plan by orders of magnitude.