Query optimization techniques are a proven tool essential for high performance of the database management systems. However, in a context of data spaces or new querying paradigms, such as similarity based search, exact query evaluation is neither computationally feasible nor meaningful and approximate query evaluation is the only reasonable option. In this paper a problem of resource allocation for approximate evaluation of complex queries is considered and an approximate algorithm for an optimal resource allocation is presented, providing the best feasible quality of the output result subject to a limited total cost of a query.