Efficient Database Query Synthesis: Experiment Results

In today’s world, databases play a vital role in storing and retrieving information. One area of interest is how to create database Queries efficiently. This report examines a set of experiments designed to evaluate the effectiveness of a system that creates document database queries from examples of input and output data.

#Research Questions

The main focus of the experiments was to answer a few important questions:

1. Can we effectively and efficiently create document database queries from input-output examples?
2. What impact does each part of the collection abstraction have on the time it takes to create these queries?
3. How does the system compare to other similar tools?
4. How does the size of the input-output examples collection affect Performance?

#Experimental Setup

All the experiments were carried out on a computer with an Intel i9-13905H CPU and 32 GB of RAM, running on the Ubuntu 22.04 WSL2 operating system. This setup provided a solid foundation to assess the performance of the query synthesis system.

#Datasets

A total of 110 Benchmarks were collected from four different sources: StackOverflow, the MongoDB official documentation, the Twitter API, and Kaggle competitions. Each source offers a unique look into real-world scenarios.

• StackOverflow: This dataset includes posts where developers ask real-world questions, with an average of 453,000 visits and various interactions including answers and votes. The examples were extracted from the content of these posts.
• MongoDB Documents: This collection consists of commonly used queries that the MongoDB community finds helpful, with examples pulled directly from the official documentation.
• Twitter API: Here, tweets and user replies illustrate typical queries for gathering tweet statistics, such as counts of replies. Examples are derived from the responses provided by APIs.
• Kaggle: This dataset focuses on satellite images, with queries aimed at scientific research, especially for extracting labels for machine learning models. Examples are sampled from JSON files provided during competitions.

The complexity of these datasets varies, with Twitter API and Kaggle benchmarks being generally more intricate than the others.

#Ground Truth Queries

In addition to the benchmarks, information was gathered on the actual queries that are considered correct or "ground truth." These queries were analyzed to assess their complexity, measuring aspects such as the number of nodes and operators in the queries.

The maximum size of the abstract syntax tree (AST) representing these queries was 33, while the average size stood at 12. Over half of the queries had sizes larger than 10, indicating a considerable level of complexity. The number of operators varied from 1 to 6, with some operators causing notable challenges in query synthesis since they could dramatically alter the structure of the collections and documents.

#Effectiveness and Efficiency

The experiments showed that the system was able to solve 108 out of 110 benchmarks. On average, it took just about 14.2 seconds to complete the synthesis of a query. The system explored a total of 175 sketches, completing 57 full programs on average. This efficiency in pruning infeasible sketches sped up the entire process.

#Qualitative Analysis

A deeper look into the data revealed that several factors impact how long it takes to create a query. These included the number of attributes in a document, the depth of that document, and the overall complexity of the query. For example, benchmarks from the Kaggle dataset took longer due to having a higher number of attributes and deeper nesting. As a rule of thumb, more complex queries meant more sketches needed to be explored.

#Non-Desired Programs

An important part of any system is how well it meets its goal. Upon reviewing the 108 synthesized queries, it turned out that 107 were equivalent to the desired outcomes. Only one query strayed from expectations. The reason was that this particular benchmark had a complex condition requiring numerous examples to identify the right solution. Unfortunately, due to a lack of enough examples, the system produced a plausible but not desired query.

#Ablation Study

A further investigation was conducted through an ablation study. This involved creating three versions of the system, disabling specific information types to see how they influenced query synthesis times. The study showed that without size information, the synthesis process was slower, and without type information, it was even slower still.

This clearly indicates that the information regarding document types enhances the speed of the synthesis process significantly.

#Comparison with Baselines

To understand how well our system performed, a comparison was made against a baseline tool called eusolver-tacas17 which is designed for query synthesis. While our system solved 108 benchmarks, the baseline could only manage a modest 25 within the same time limit.

Additionally, a comparison with a popular language model called ChatGPT illustrated that it could only produce the desired query for 53 out of 110 benchmarks. Some of its attempts were plausible but not entirely right, indicating room for improvement.

#Impact of Collection Size

The size of the example collection can play a vital role in how effectively the system operates. Experiments were run with collections containing between 1 and 10 documents. The findings suggested that the synthesis time remained fairly stable regardless of collection size. However, the rate of producing the desired outcome increased notably as the collection size grew from 1 to 3, after which it leveled off.

#Threats to Validity

While the findings are promising, several factors could affect the results:

1. The selected datasets may not represent all possible real-world scenarios, meaning the tool's performance could vary in different contexts.
2. The domain-specific language used only covers a core part of MongoDB's capabilities. Changing the query operators could impact performance.
3. The experiments were conducted on a specific computer setup, and running them on different machines might lead to different outcomes.

#Conclusion

This evaluation demonstrates that the system is highly effective at synthesizing document database queries from provided examples. With the ability to tackle a majority of complex benchmarks in a relatively short time, the findings suggest a promising development in the realm of database query synthesis. As with all technology, improvements can be made, and further research may unveil even better results in the future.

And who knows? Maybe one day, we'll have a system that makes querying databases as easy as ordering pizza!