Spatial queries with k-Nearest-Neighbor and relational predicates

The ubiquity of location-aware devices and smartphones has unleashed an unprecedented proliferation of location-based services that require processing queries with both spatial and relational predicates. Many algorithms and index structures already exist for processing fc-Nearest-Neighbor (kNN, for short) predicates either solely or when combined with textual keyword search. Unfortunately, there has not been enough study on how to efficiently process queries where kNN predicates are combined with general relational predicates, i.e., ones that have selects, joins and group-by's. One major challenge is that because the kNN is a ranking operation, applying a relational predicate before or after a kNN predicate in a query evaluation pipeline (QEP, for short) can result in different outputs, and hence leads to different query semantics. In particular, this renders classical relational query optimization heuristics, e.g., pushing selects below joins, inapplicable. This paper presents various query optimization heuristics for queries that involve combinations of kNN select/join predicates and relational predicates. The proposed optimizations can significantly enhance the performance of these queries while preserving their semantics. Experimental results that are based on queries from the TPC-H benchmark and real spatial data from OpenStreetMap demonstrate that the proposed optimizations can achieve orders of magnitude enhancement in query performance.