Database Theory in Action: Direct Access to Query Answers
This work addresses the practical efficiency of direct access for database queries, which is incremental as it builds on existing theoretical studies by providing empirical evaluation.
The paper tackled the practical performance of data structures for direct access to query answers by ranked position, which had been studied theoretically but not evaluated in practice. The authors implemented a system covering various queries and orders, enabling investigation of performance comparisons between database systems and the relationship between direct access and single-access methods.
Direct access asks for the retrieval of query answers by their ranked position, given a query and a desired order. While the time complexity of data structures supporting such accesses has been studied in depth, and efficient algorithms for many queries and common orders are known, their practical performance has received little attention. We provide an implementation covering a wide range of queries and orders; it allows us to investigate intriguing practical aspects, including the comparative performance of database systems and the relationship between direct access and its single-access counterpart.