Hide menu

Combining Result Size Estimation and Query Execution for Facebook's GraphQL Query Language

This project is designed for master students.

Description: After developing and using it internally for three years, in 2016, Facebook released a specification and a reference implementation of a framework, called GraphQL, that introduces a new type of Web-based data access interfaces. A core component of this GraphQL framework is a query language for expressing the data retrieval requests issued to GraphQL-aware Web servers.
In an ongoing research collaboration between the Universidad de Chile and Linköping University we are studying this new query language and we have developed an algorithm that can be used to determine the size of the result of a given query without having to execute the query. While the algorithm can be used to protect GraphQL servers from queries that would produce unmanageably huge results, for simple "harmless" queries, running the algorithm takes roughly the same time as executing the query. Hence, using the algorithm in these cases essentially doubles the overall query processing time.
The goal of this thesis project is to address this problem by extending our algorithm such that the intermediate data structures created during the run time of the algorithm can by used not only to determine the result size but also to produce the query result itself. The research questions to be be addressed are: What additional information needs to be collected during the run time of the extended algorithm? How can this additional information be efficiently captured in the intermediate data structures (i.e., without an exponential blow-up of the memory footprint of these data structures)? What are the performance trade-offs of the extended algorithm? To answer the latter question, a prototype of the extended algorithm has to be implemented and, based on this prototype, the algorithm has to be evaluated experimentally.

Prerequisites: Students who want to work on this project should have read a course on Database Technology. Additionally, good programming experience is recommended (ideally using JavaScript).

Contact: Olaf Hartig.

Page responsible: Olaf Hartig
Last updated: 2018-10-26