Efficient Detection of Empty-Result Queries

Abstract

Frequently encountered in query processing, empty query results usually do not provide users with much useful information. Yet, users might still have to wait for a long time before they disappointingly realize that their results are empty. To significantly reduce such unfavorable delays, in this paper, we propose a novel method to quickly detect, without actual execution, those queries that will return empty results. Our key idea is to remember and reuse the results from previously-executed, empty-result queries. These results are stored in the form of so-called atomic query parts so that the (partial) results from multiple queries can be combined together to handle a new query without incurring much overhead. To increase our chance of detecting empty-result queries with only a limited storage, our method (1) stores the most “valuable” information about empty-result queries, (2) removes redundant information among different empty-result queries, (3) continuously updates the stored information to adapt to the current query pattern, and (4) utilizes a set of special properties of empty results. We evaluate the efficiency of our method through a theoretical analysis and an initial implementation in PostgreSQL. The results show that our method has low overhead and can often successfully avoid executing empty-result queries.