UQE: A Query Engine for Unstructured Databases

We thank the reviewer for the insightful comments, and we do value your opinion regarding the latency issues. Below we try to justify from the use cases and existing baselines, and also provide more experimental results.

Q1 "...latency...far distance from practice..."

The latency is per query and is averaged over 8 runs. We agree that this latency is not meant for real-time queries like the SQL engine behind web apps. The type of query that is most useful is for massive data analytics, where the alternative solution is usually to train a task specific ml model, build up the data preprocessing pipeline and then run SQL, which can easily take days for data scientists.

Secondly, our framework offers the flexibility to do trade-offs between latency and accuracy. Take the IMDB retrieval experiment as an example:

And for aggregation:

So comparing to alternative solutions for data analytics, which take days to first preprocess the data into structured columns and then run SQL, the speed of UQE is significantly improved.

Q2 "...cost of embedding... cost of Algorithm 2...g function..."

The embedding cost is the same as the vector DBs. This is a pre-processing step and only needs to be done once per dataset. For text we use voyage-2 which costs 0.1 USD / million tokens, and it roughly take 8h (due to rate limit) to embed these datasets. For image we use Cloud Vertex multi-modal embedding and it takes 12h (due to rate limit).

For a query on IMDB that takes 21s, querying g and updating g takes 1.5s and 0.5s respectively. The main reason for the latency is the sequential nature of online learning of g, and a potential improvement is to leverage batched online learning to improve the parallelism.

Q3 "...baselines.. the trade-off made by Algorithm 1 between accuracy and latency"

We followed the reviewer's advice to include BINDER (the viper-gpt is similar but for images) in all the experiments, and as shown in our global rebuttal, the performance of BINDER is much worse when given the same LLM budgets (we stop the BINDER execution when running out of budget, as looping over the entire database can easily cost hundreds of dollars, which is not feasible for us).

To see how the accuracy evolves for both UQE and BINDER, we perform the following experiments on aggregation tasks (IMDB) by varying the budgets. In paper we use B=128, and we lower/higher the budget for UQE/BINDER respectively in the table below.

we can see that both BINDER and UQE will have more accurate estimation when given more budget. But for BINDER, it takes 16x more LLM calls (512) compared to UQE (32) to obtain the same level of accuracy or precision. We hope this answers the question of tradeoff of Algorithm 1.

Q4 "...latency and cost...in the main text..."

We have provided the cost per query in every table in the main text. We will follow the reviewer's advice to include the latency and also the above trade-off analysis into the main text.

Q5 "... lc-gpt-4-turbo also has quite a high latency..."

lc-gpt-4-turbo is basically the baseline on feeding the entire content into gpt-4-turbo and ask questions. There could be several ways that make it faster (though it is not the focus of this paper to make LLM itself run faster):

1. prefix caching; if the data never changes, one can cache majority of the kv states of prompts which can save 2x of the cost/latency or so.

2. in general, the models will only get faster/cheaper, e.g., gpt-4o-mini which came out recently.

Dear reviewer E5QU,

We have provided additional experiments and explanations to address your valuable feedback.

Could you please kindly take a look, and let us know if you have further concerns so that we can provide further clarifications if needed?

Thank you so much!

Best,

We thank the reviewer for the valuable comments. Below we try to address the potential misunderstandings, and provide more experimental results for justifications.

Q1 "...machine-specific code...clarify the details..."

The analogy is to show how to convert the query (in UQL) to the machine code (the concrete prompts that work with LLMs). Concretely, for example, a WHERE cond statement would be "compiled" to

Please analyze the following movie review, and only reply <True> if cond, or <False> otherwise.

and executed on the rows sampled by the online-learning or unbiased samplers. We provided the full set of prompts in appendix for your information.

Q1 "...LLM dominates the overall cost per query...Providing detailed information"

For example, a query on clevr dataset costs 0.2USD using gpt-4o. The compute on the client side only takes CPU time for 30s. On AWS such a machine costs 5.80USD/month, so 30s of compute would be nothing, compared to the LLM calls.

Q2 "...database indexing...sampling...impact efficiency? ...accuracy?"

The traditional database is able to build index on the columns that might be conditioned on, so as to avoid linear scan of the entire database. For unstructured data, as we don't know the query beforehand, there is no such indexing. Vector DB builds the embedding based indexing, but can only be useful for limited types of queries as we have seen in the experiments.

Based on that, we propose the analogy of indexing in unstructured database, i.e. the sampling techniques to 1) avoid linear scan; 2) handle complex reasonings; 3) have statistical guarantee.

So to answer your question, it is actually the sampling (and the online learning) that makes things efficient. There's rich literature [1] on approximated compute engine, and we have shown that its accuracy is much better than alternatives throughout comprehensive experiments (e.g., 40x F1 score compared to the reviewer suggested Milvus for some queries).

Q3 "...addresses unstructured datasets, including video and audio. However, the experiments only involve text and images"

The proposed UQE framework rely on the LLM backend for multi-modal queries, and the optimization done in the paper is agnostic to the modality.

Nevertheless, we provide new experimental results on the Audio MNIST, which contains 30k wav files from 60 speakers pronouncing digits 0-9.

Below we perform the audio semantic retrieval experiments. The query is first converted to audio space using TTS and the corresponding audio embedding is used for MIPS/Milvus search.

We can see UQE consistently does better than alternatives, and it also allow complex queries that require reasoning, while embedding based MIPS or Milvus is limited to the type of queries.

Q4 "...Can UQE outperform ... Milvus and MillenniumDB..."

In our paper we compared against MIPS (Maximum inner-product search) and we show the clear advantage in Table 2. Vector DB like Milvus is designed for fast but approximated nearest neighbor (ANN) search. By default it uses inner product as the similarity metric, thus is expected to be an approximation of MIPS in our paper (where we do full vector database scan without approximation).

Nevertheless, we still run Milvus on all benchmarks, and the results have been included in the global response and UQE still wins in almost all query types. MillenniumDB is for graph or structured data query and thus may not be suitable to compare. We hope this would resolve some misunderstandings.

Q5 "...join operations..."

No, we have stated in our conclusion section that table join optimization is not done in our paper. With that said, one can still create the virtual columns in UQL via SELECT and then use existing SQL engine for the joins, at a potential very high cost of language model calls. We hope to optimize the join operation in future work.

Q6 "...code/models"

The model/data and prompts are all provided already. We will release the code.

Limitation section

We have already clearly stated the limitation of current work in the conclusion section, including 1) lack of table join optimization; 2) LLM selection; 3) even larger datasets. And we will work on these in future works.

References:

[1] A handbook for building an approximate query engine.

Dear reviewer rs84,

We have provided additional experiments and explanations to address your valuable feedback.

Could you please kindly take a look, and let us know if you have further concerns so that we can provide further clarifications if needed?

Thank you so much!

Best,

We thank the reviewer for providing insightful and constructive feedback. We provide our response below, as well as extra experimental results in the global response. We look forward to learning your further thoughts.

"... difference between BINDER..."

Yes as the reviewer pointed out, our focus is on the analogy of "indexing" (or sampling and search) to efficiently implement the unstructured database query engine. BINDER focuses on translating natural language questions into programs with llm as a callable function. The execution of this program is delegated to existing SQL implementations. These two can actually work together to deliver a better end to end system.

"...used BINDER as their baseline?"

While BINDER and our UQE have different focuses, we provided additional experiments using BINDER on our tasks in the general response. We can see that without the query engine optimization, BINDER would achieve much higher variance and error when performing aggregation queries, and the retrieval F1 is also much lower compared to UQE under the same LLM budgets.

"...consistently return the same results...compromise their reliability"*

We totally agree with the reviewer that the consistency and reliability is important, and that's why our algorithm (especially the one for the aggregation query) optimizes for low-variance and zero-bias estimation, which has significantly boosted this compared to all baselines. In addition to that, one can further reduce the temperature of the LLMs and use fixed random seeds to make sure the results are reproducible for a given setup.

The reviewer raised another good point where the LLM behind the scene gets updated and that would cause the inconsistency across different versions of LLMs. This is a generic problem of the application built on top of LLMs, but here are several ways to mitigate it.

1. Result caching: for the same query, one can always cache the intermediate or final results to save the compute and also make it consistent for the same question.

2. Prompt calibration: once a new model is deployed, a common practice is to adjust the prompt a bit to make it consistent or fitting better on the target tasks. Similar practices can be made for the database queries, as long as a proper evaluation set is available. In our experiment we prepare multi-modal datasets with the ground-truth labels to validate and calibrate the prompts.

3. Even without any further effort, it may not be that inconsistent in some situations. In our paper we used claude-3-haiku as the backbone, and below we use the latest gpt-4o-mini to provide more justification for that. On IMDB we see little variation, where we can see that, the difference caused by the model switching is much lower than using a worse query engine.

Of course, this behavior shift would be task related, but with the advances of LLMs we believe this variation would converge and be more stable to prompts.

We thank the reviewer for the valuable comments. Below we try to address the potential misunderstandings, and provide more experimental results for justifications.

"...technical report...the strong assumption that LLMs work on intra-row semantic understanding"

While generating the virtual column entirely and process with SQL is a feasible approach, the goal of the paper is to present an efficient system that can void such kind of "linear scan" of the database content, and thus the core of the contribution lies in the unbiased+low-variance sampler and the online learning approach that orchestrates well with the LLMs. Thus we focus on providing algorithmic detail and the proof (see appendix A) for these while put less attention on the database and system layer. If the reviewer have specific details that would like to learn more, please feel free to let us know. We will also release the code afterwards.

Regarding the assumption that LLMs work on intra-row semantic understanding, we have carefully examined this. On IMDB dataset, the gpt model can achieve 97% accuracy on average over each review, and many of the errors are actually due to the unclear sentiment from the data. Definitely the accuracy would depend on the difficulty of the question, but having a good-enough out-of-the-box solution can be a good starting point, given that people are still pushing the frontier of LLMs.

"...failure rate in output formatting..."

We completely rewrite the entire SQL engine and thus the error handling can be easily done in our system. As is shown in Appendix, most of the time we ask LLMs to output <True> or <False> based on the query. We did a quick experiment to see when the LLM failed to generate either of these.

We can see the above models, despite being small and cheap, are very good at instruction following and the formatting violation rate can be tolerated with extra error handling. And we believe that the next generation LLMs can only be better at instruction following. Actually as of Aug-6, openai released a new version of gpt-4o (gpt-4o-2024-08-06) which claimed to have 100% accuracy on complex format following.

Dear reviewer uiEW,

We have provided additional experiments and explanations to address your valuable feedback.

Could you please kindly take a look, and let us know if you have further concerns so that we can provide further clarifications if needed?

Thank you so much!

Best,