Efficient ranked access to database query answers
Nikolaos Tziavelis · 2024
Database queries can produce a huge output that is infeasible to compute, regardless of the algorithm or system that processes them. This can often occur when the query joins large data from multiple tables or sources. However, computing the entire query output may not be necessary when users have preferences over the output answers and are interested in accessing only a small subset according to the preference order; either to retrieve the most important answers or the quantiles (e.g., the median answer) for a statistics summary. Can we compute these specific query answers, under a specified order, without first computing the join output? We show that for many such queries, ranking functions, and access patterns over the answers, this type of ranked access can indeed be performed efficiently. This is captured theoretically by non-trivial complexity guarantees and shown in practice with efficient implementations that avoid the cost of expensive join operations. For most cases that we study where an efficient algorithm is missing, we establish lower bounds that, under certain assumptions that we adopt from fine-grained complexity, prove no such algorithm can exist. As a result, we chart precisely how the interplay between the query, the ranking function, and the specific ranked access pattern affects the complexity of the problem. Besides addressing fundamental questions regarding the limits of query processing, this work opens up unexplored possibilities for the design of database systems. We clearly demonstrate how existing systems fall short in handling ranking efficiently, with our protoype implementation outperforming them by orders of magnitude. --Author's abstract