CRUSH 4 SQL : Collective Retrieval Using Schema Hallucination For T ext2 SQL (2023)

Abstract: Existing Text-to-SQL generators require the entire schema to be encoded with the user text. This is expensive or impractical for large databases with tens of thousands of columns. Standard dense retrieval techniques are inadequate for schema subsetting of a large structured database, where the correct semantics of retrieval demands that we rank sets of schema elements rather than individual documents. In response, we propose a two-stage process for effective coverage during retrieval. First, we use an LLM to hallucinate a minimal DB schema that it deems adequate to answer the query. We use the hallucinated schema to retrieve a subset of the actual schema, by composing the results from multiple dense retrievals. Remarkably, hallucination — generally considered a nuisance — turns out to be actually useful as a bridging mechanism. Since no existing benchmarks exist for schema subsetting on large databases, we introduce two benchmarks: (1) A semi-synthetic dataset of 4502 schema elements, by taking a union of schema on the well-known SPIDER dataset, and (2) A real-life benchmark called SocialDB sourced from an actual large data warehouse comprising of 17844 schema elements. We show that our method leads to significantly higher recall than SOTA retrieval-based augmentation methods.

## introduction state-of-the-art language model based text-to-sql generators provide impressive accuracies on well known benchmarks, but they require the entire db schema as input, along with the user question text @xcite @xcite . widely-used benchmarks such as spider @xcite and wikisql @xcite , and even "datasets in the wild," like sede @xcite , are all associated with modest-sized schema. e.g., the average number of tables and columns in any one schema for spider is 5.3 tables and 28.1 columns, and for sede is 29 tables and 212 columns. in contrast, real-life datasets may have thousands of tables with hundreds of columns per table. e.g., a real-life data warehouse of data about various social indicators of a country comprises of more than 17.8 thousand columns! for such large schema, we cannot afford to include the entire schema in the prompt preceding each query; only a high-recall subset of the schema can be attached to each question. llm-as-a-service usually charges for each token exchanged between client and server, so we want the subset to be as small as possible while ensuring high recall. even for in-house (l)lms or other text-to-sql methods, admitting extraneous schema elements as candidates for use in the generated sql reduces its accuracy @xcite . retrieving a subset of a corpus of passages to augment the llm prompt has become an emerging area @xcite for non-text-to-sql applications as well. most retrieval modules depend on standard "dense passage retrieval" (dpr) based on similarity between the question embedding and an embedding of a document @xcite or schema element @xcite . we argue (and later demonstrate) that text-to-sql needs a more circumspect approach to jointly leverage the strengths of llms and dense retrieval. consider a question "what is the change in female school enrollment and gdp in cameroon between 2010 and 2020?", to be answered from a large database like world bank data 2 . an effective text-to-sql system needs to realize that gdp and female school enrollment are two key 'atoms' in the question and match these to tables development indicators and education statistics respectively. additionally, it needs to generalize cameroon to country, and 2010,2020 to year to match correct columns in these tables. this requires generalization and phrase-level matching via llms (with all the world knowledge they incorporate); pre-deep-nlp and 'hard' segmentation techniques @xcite , as well as token-decomposed deep retrieval, such as colbert @xcite , are unlikely to suffice. our setting thus requires us to retrieve, score and select sets of schema elements that collectively cover or explain the whole query. this bears some superficial similarity with multi-hop question answering (qa). closer scrutiny reveals that, in multihop qa benchmarks such as hotpotqa, each question comes with only 10 passages, out of which 8 are 'distractors' and two need to be selected to extract the answer. the best-performing systems @xcite can afford exhaustive pairing of passages along with the question, followed by scoring using all-to-attention -such techniques do not scale to our problem setting with thousands of tables and hundreds of columns per table, where as many as 30 schema elements may be involved in a query. ## notation and problem statement we are given a large database schema d consisting of a set of tables t , with each table @xmath0. we will use d to denote a schema element ('document'), which can be either a table or a column. a schema element d has a textual name or description s(d). the text associated with a column t.c is written as the concatenation s(t).s(c) as shown in figure 1 . apart from the database, the input includes a natural language question x. question x is associated with a (possibly unknown) correct ('gold') sql query q(x). the gold sql query q(x) mentions a subset r(q(x)) of the schema elements from d. ## the crush4sql approach successfully matching a user question x to a relevant schema r(q(x)) could be quite non-trivial, since the schema element names or descriptions are often not directly mentioned in the question. for example, consider the question @xmath1. in order to match this question prop-erly to gold schema d, containing such schema elements as age, club description, and club members, etc., we need to perform multiple types of lexical and syntactic reasoning on the question and schema: • extract segments like older than 18 and bootup baltimore club, • generalize the first segment to a likely schema element age, and, • for the second segment, instead of attempting to match strings like bootup baltimore verbatim, match to a schema element called club description. to bridge such large lexical gap between the tokens of x and the gold schema r(q(x)), we designed a two-phase approach. in the first phase, we transform x into an intermediate form k(x) comprising of multiple generalized segments leveraging an llm. in the second phase, we use k(x) to retrieve from the db schema d suitable schema element subset r(x), by approximately optimizing a combinatorial objective that collectively maximizes coverage of all elements of k(x). we describe these two phases next. ## related work dense passage retrieval (dpr): a default method of identifying r(x) is based on nearest neighbors in a dense embedding space. first a language model (lm) m like sgpt (muennighoff, 2022) or openai's similarity and search embeddings api (model text-embedding-ada-002) converts each string s(d) into a fixed-length embedding vector which we denote @xmath2. given a question x, we obtain the embedding x of x, i.e., @xmath3, and then retrieve the k nearest neighbors of x in d as r(x) = k-nn(x, {d : @xmath4. this method has the limitation that the top-k retrieved elements may be skewed towards capturing similarity with only a subset of the gold schema r(q(x)). the resdsql @xcite text-to-sql system, too, selects the most relevant schema items for the encoder, using a cross-encoder (based on roberta) between the question and the whole schema. although the early-interaction encoder may implicitly align question tokens to schema tokens, there is no apparent mechanism to ensure phrase discovery and (llm knowledge mediated) measurement of coverage of question phrase with schema element descriptions. llms for ranking: sun et al. ( 2023 ) use an llm for relevance ranking in information retrieval. they show that a properly instructed llm can beat supervised learning-to-rank approaches. no query decomposition of multi-hop reasoning is involved. other uses of llms in scoring and ranking items are in recommender systems @xcite : turning user profiles and interaction history into (recency focused) prompts, encoding candidates and their attributes into llm inputs, and asking the llm to rank the candidates. notably, llms struggle to rank items as the size of the candidate set grows from 5 to 50. llms for question decompostion and retrieval: decomposing complex questions has been of interest for some years now @xcite . in the context of llms, @xcite propose a question answering system where supporting evidence to answer a question can be spread over multiple documents. similar to us, they use an llm to decompose the question using five in-context examples. the subquestions are used to retrieve passages. a more general architecture is proposed by @xcite . none of these methods use the notion of a hallucinated schema. they match subquestions to passages, not structured schema elements. they entrust the final collective answer extraction to an opaque lm. in contrast, we have an interpretable collective schema selection step. ## experiments in this section we compare crush with existing methods for schema subsetting. we also present a detailed ablation on the various design options for crush.