RYANSQL: Recursively Applying Sketch-based Slot Fillings for Complex Text-to-SQL in Cross-Domain Databases

Introduction

Text-to-SQL is the task of generating SQL queries when database and natural language user questions are given. Recently proposed neural net architectures achieved more than 80% exact matching accuracy on the well-known Text-to-SQL benchmarks such as ATIS, GeoQuery and WikiSQL (Xu et al., 2017; Yu et al., 2018a; Shi et al., 2018; Dong and Lapata, 2018; Hwang et al., 2019; He et al., 2019). However, those benchmarks have shortcomings of either assuming the same database across the training and test dataset(ATIS, GeoQuery) or assuming the database of a single table and restricting the complexity of SQL query to have a unitary SELECT statement with a single SELECT and WHERE clause (WikiSQL).

Different from those benchmarks, the Spider benchmark proposed by Yu et al. (2018b) contains complex SQL queries with cross-domain databases. Cross-domain means that the databases for the training dataset and test dataset are different; the system should predict with an unseen database as its input during testing. Also, different from another cross-domain benchmark WikiSQL, the SQL queries in Spider benchmark contain nested queries with multiple JOINed tables, and clauses like ORDERBY, GROUPBY, and HAVING. Yu et al. (2018b) showed that the state-of-the-art systems for the previous benchmarks do not perform well on the Spider dataset.

In this paper, we propose a novel network architecture called RYANSQL (Recursively Yielding Annotation Network for SQL) to handle such complex, cross-domain Text-to-SQL problem. The proposed approach generates nested queries by recursively yielding its component SELECT statements. A sketch-based slot filling approach is proposed to predict each SELECT statement. In addition, two simple but effective input manipulation methods are proposed to improve the overall system performance. The proposed system improves the previous state-of-the-art system by 3.2%p in terms of the test set exact matching accuracy, using BERT (Devlin et al., 2019). Our contributions are summarized as follows.

We propose a detailed sketch for the complex SELECT statements, along with a network architecture to fill the slots.

Statement Position Code (SPC) is introduced to recursively predict nested queries with sketch-based slot filling algorithm.

We suggest two simple input manipulation methods to improve performance further. Those methods are easy to apply, and they improve the overall system performance significantly.

Related Works

Most recent works on Text-to-SQL task used encoder-decoder model. Those works could be classified into three main categories, based on their decoder outputs. Direct Sequence-to-Sequence approaches (Dong and Lapata, 2016; Zhong et al., 2017) generate SQL query tokens as their decoder outputs; due to the risk of generating grammatically incorrect SQL queries, the Direct Sequence-to-Sequence approaches are rarely used in recent works.

Grammar-based approaches generate a sequence of grammar rules and apply the generated rules sequentially to get the resultant SQL query. Shi et al. (2018) defines a structural representation of an SQL query and a set of parse actions to handle the WikiSQL dataset. Guo et al. (2019) defines SemQL queries, which is an abstraction of SQL query in tree form, along with a set of grammar rules to synthesize SemQL queries; Synthesizing SQL query from a SemQL tree structure is straightforward. Bogin et al. (2019) focused on the DB constraints selection problem during the grammar decoding process; they applied global reasoning between question words and database columns/tables.

Sketch-based slot-filling approaches, firstly proposed by Xu et al. (2017) to handle the WikiSQL dataset, define a sketch with slots for SQL queries, and the decoder classifies values for those slots. Sketch-based approaches Hwang et al. (2019) and He et al. (2019) achieved state-of-the-art performances on the WikiSQL dataset, with the aid of BERT (Devlin et al., 2019). However, sketch-based approach on more complex Spider benchmark (Lee, 2019) showed relatively low performance compared to the grammar-based approaches. There are two major reasons: (1) It is hard to define a sketch for Spider queries since the allowed syntax of the Spider SQL queries is far more complicated than that of the WikiSQL queries. (2) Since the sketch-based approaches fill values for the predefined slots, the approaches have difficulties in predicting the nested queries.

In this paper, a sketch-based slot filling approach is proposed to solve the complex Text-to-SQL problem. A detailed sketch for complex SELECT statements is newly proposed, along with Statement Position Code (SPC) to effectively predict for the nested queries.

Task Definition

The Text-to-SQL task considered in this paper is defined as follows: Given a question with $n$ tokens $Q=\{w^{Q}_{1},...,w^{Q}_{n}\}$ and a DB schema with $t$ tables and $f$ foreign key relations $D=\{T_{1},...,T_{t},F_{1},...,F_{f}\}$, find $S$, the SQL translation of $Q$. Each table $T_{i}$ consists of a table name with $t_{i}$ words $\{w^{T_{i}}_{1},...,w^{T_{i}}_{t_{i}}\}$, and a set of columns $\{C_{j},...,C_{k}\}$. Each column $C_{j}$ consists of a column name $\{w^{C_{j}}_{1},...,w^{C_{j}}_{c_{j}}\}$, and a marker to check if the column is a primary key.

For an SQL query $S$ we define a non-nested form of $S$, $N(S)=\{(P_{1},S_{1}),...,(P_{l},S_{l})\}$. In the definition, $P_{i}$ is the $i$-th SPC, and $S_{i}$ is its corresponding SELECT statement. Table 1 shows an example of natural language query $Q$, SQL translation $S$ and its non-nested form $N(S)$.

Each SPC $P$ could be considered as a sequence of $p$ position code elements, $P=[c^{P}_{1},...,c^{P}_{p}]$. The possible set of position code elements is $\{$NONE, UNION, INTERSECT, EXCEPT, WHERE, HAVING, PARALLEL$\}$. NONE represents the outermost statement, while PARALLEL means the parallel elements inside a single clause like the second element of the WHERE clause. Other position code elements represent corresponding SQL clauses.

Since it is straightforward to construct $S$ from $N(S)$, the goal of the proposed system is to construct $N(S)$ for the given $Q$ and $D$. To achieve the goal, the proposed system first sets the initial SPC $P_{1}=[\texttt{NONE}]$, and predicts its corresponding SELECT statement and nested SPCs. The system recursively finds out the corresponding SELECT statements for remaining SPCs, until every SPC has its corresponding SELECT statement.

Generating a SELECT Statement

In this section, the method to create the SELECT statement for the given question $Q$, database $D$, and SPC $P$ is described. Section 4.1 describes the input encoder; the sketch-based slot-filling decoder is described in section 4.2.

Figure 1 shows the overall network architecture. The input encoder consists of five layers: Embedding layer, Embedding Encoder layer, Question-Column Alignment layer, Table Encoder layer, and Question-Table Alignment layer.

In this layer, the column vectors are modeled with contextual information of the question by attending question tokens with their corresponding columns. Scaled dot-product attention (Vaswani et al., 2017) is used to align question tokens with column vectors:

The heuristic fusion function $fusion(x,y)$, proposed in Hu et al. (2018), is applied to merge $A_{QtoC}$ with $H^{C}$:

1.1 BERT-based Input Encoder

Inspired by the work of Hwang et al. (2019) and Guo et al. (2019), BERT (Devlin et al., 2019) is considered as another version of input encoder. The input to BERT is constructed by concatenating question words, SPC elements and column words as follows: [CLS], $w^{Q}_{i}$, [SEP], $c^{P}_{j}$, [SEP], $w^{C_{1}}_{k}$, [SEP], …, $w^{C_{m}}_{l}$, [SEP].

Hidden states of the last layer are retrieved to form $V^{Q}$ and $V^{C}$; for $V^{C}$, the state of each column’s last word is taken to represent encoded column vector. Each table vector $v^{T}_{j}$ is calculated as a self-attended vector of its containing columns; $v^{Q}$, $v^{D}$, and $v^{P}$ are calculated as the same.

2 Sketch-based Slot-Filling Decoder

Table 2 shows the proposed sketch for a SELECT statement. The sketch-based slot-filling decoder predicts values for slots of the proposed sketch.

By the term base structure of a SELECT statement, we refer to the existence of its component clauses and the number of conditions for each clause. We first combine the encoded vectors $v^{Q}$, $v^{D}$ and $v^{P}$ to get the statement encoding vector $v^{S}$, as follows:

Eleven values $b_{g},b_{o},b_{l},b_{w},b_{h},n_{g},n_{o},n_{s},n_{w}$, $n_{h}$ and $c_{\texttt{IUEN}}$ are classified by applying two fully-connected layers on $v^{S}$. Binary values $b_{g},b_{o},b_{l},b_{w},b_{h}$ represent the existence of GROUPBY, ORDERBY, LIMIT, WHERE and HAVING, respectively. Note that FROM and SELECT clauses must exist to form a valid SELECT statement. $n_{g},n_{o},n_{s},n_{w},n_{h}$ represent the number of conditions in GROUPBY, ORDERBY, SELECT, WHERE and HAVING clause, respectively. The maximal number of conditions $N_{g}=3$, $N_{o}=3$, $N_{s}=6$, $N_{w}=4$, and $N_{h}=2$ are defined for GROUPBY, ORDERBY, SELECT, WHERE and HAVING clauses, to solve the problem as $n$-way classification problem. The values of maximal condition numbers are chosen to cover all the training cases.

Finally, $c_{\texttt{IUEN}}$ represents the existence of one of INTERSECT, UNION or EXCEPT, or NONE if no such clause exists. If the value of $c_{\texttt{IUEN}}$ is one of INTERSECT, UNION or EXCEPT, the corresponding SPC is created, and the SELECT statement for that SPC is generated recursively.

A list of $TBLs should be decided to predict the FROM clause. For each table$i$,$P_{\textbf{fromtbl}}(i|Q,D,P)$, the probability that table$i$ is included in the FROM clause, is calculated:

Top $n_{t}$ tables with the highest $P_{\textbf{fromtbl}}(i)$ values are chosen. We set an upper bound $N_{t}=6$ on possible number of tables. The formula to get $P_{\textbf{\#tbl}}(n_{t})$ for each possible $n_{t}$ is:

In the equation, $full_{2}$ means the application of two fully-connected layers, and table score vector $s$ is from equation 7.

The decoder first generates $N_{s}$ conditions to predict the SELECT. Since each condition depends on different parts of $Q$, we calculate attended question vector for each condition:

Where $W_{7}$ is a trainable variable, and $hc(x,y)$ is defined in equation 5. The probabilities for $DIST1,$AGG1, $ARI and$AGG are calculated by applying a fully connected layer on $U^{Q}_{\textbf{sel\_col1}}[i]$.

Equation 10 is reused to calculate $P_{\textbf{sel\_col2}}$, with $V^{Q}_{\textbf{sel}}[i]$ replaced by $U^{Q}_{\textbf{sel\_col1}}[i]$; then $U^{Q}_{\textbf{sel\_col2}}$ is retrieved in the same way as equation 11, and the probabilities of $DIST2 and$AGG2 are calculated in the same way as $DIST1 and$AGG1. Finally, the $DIST slot, DISTINCT marker for overall SELECT clause, is calculated by applying a fully-connected layer on$v^{S}$.

Once all the slots are filled for $N_{s}$ conditions, the decoder retrieves the first $n_{s}$ conditions to predict the SELECT clause. That is possible since the CNN with Dense Connection used for question encoding (Yoon et al., 2018) captures relative position information. In combine with the SQL consistency protocol of the Spider benchmark (Yu et al., 2018b), we expect the conditions are ordered in the same way as they are presented in $Q$. For the datasets without such consistency protocol, the proposed slot filling method could easily be changed to an LSTM-based model, as shown in Xu et al. (2017).

The same network structure as a SELECT clause is applied. The only difference is the prediction for $ORD slot; this could be done by applying a fully connected layer on$U^{Q}_{\textbf{ob\_col1}}$, which is the correspondence of$U^{Q}_{\textbf{sel\_col1}}$.

The same network structure as a SELECT clause is applied. For the GROUPBY case, retrieving only the values of $P_{\textbf{gb\_col1}}$ is enough to fill the necessary slots.

Questions do not contain the $NUM slot value for LIMIT clauses explicitly in many cases, if the questions are for the top-1 result (Example: “Show the name and the release year of the song by the youngest singer”). Thus, the LIMIT decoder first determines if the given$Q$requests for the top-1 result. If so, the decoder sets the$NUM value to 1; otherwise, it tries to find the specific token for $NUM among the tokens of$Q$using pointer network (Vinyals et al., 2015). LIMIT top-1 probability$P_{\textbf{limit\_top1}}$is retrieved by applying a fully-connected layer on$v^{S}$.$P^{Q}_{\textbf{limit\_num}}[i]$, the probability of$i$-th question token for$NUM slot value, is calculated as:

A fully-connected layer is applied on $U^{Q}_{\textbf{wh\_col1}}$ and $U^{Q}_{\textbf{wh\_col2}}$ to determine if the condition value for each column is another nested SELECT statement or not. If the value is determined as a nested SELECT statement, the corresponding SPC is generated, and the SELECT statement for the SPC is predicted recursively. If not, the pointer network is used to get the start and end position of the value span from question tokens.

The same network structure as a WHERE clause is applied.

Two Input Manipulation Methods

In this section, we introduce two input manipulation methods to improve the performance of our proposed system further.

In a FROM clause, some tables may be used only to make “link” between other tables; Table 3 shows such an example. Those “link” tables are necessary to create the proper SELECT statement, but they work as noise for Question-Table alignment since they do not have the corresponding tokens in $Q$. Thus, we discard those tables from FROM clauses during training; while inferencing, the link tables are easily recovered using foreign key relations.

2 Supplemented Column Names

We supplement the column names with its table names to distinguish between columns with the same name but belonging to different tables and representing different entities. Table names are concatenated in front of their belonging column names to form SCNs, but if the stemmed form of a table name is wholly included in a stemmed form of the column name, the table name is not concatenated. Table 4 shows SCN examples; the three columns with the same name id are distinguished using their SCNs.

Experiment

Spider dataset (Yu et al., 2018b) is used to evaluate our proposed system. We use the same data split as Yu et al. (2018b); 206 databases are split into 146 train, 20 dev, and 40 test. All questions for the same database are in the same split; there are 8659 questions for train, 1034 for dev, and 2147 for test. The test set of Spider is not publicly available, so for testing our models are submitted to the data owner. For evaluation, we used exact matching accuracy, with the same definition as defined in Yu et al. (2018b).

The proposed system is implemented with Tensorflow (Abadi et al., 2015). Layernorm (Ba et al., 2016) and dropout (Srivastava et al., 2014) are applied between layers, with a dropout rate of 0.1. Exponential decay with decay rate 0.8 is applied for every 3 epochs. On each epoch, the trained classifier is evaluated against the validation dataset, and the training stops when the exact match score for the validation dataset is not improved for 20 consequent training epochs. Minibatch size is set to 16; learning rate is set to $4e^{-4}$. Loss is defined as the sum of all classification losses from the slot-filling decoder.

For BERT-based input encoding, we downloaded the publicly available pre-trained model of BERT, BERT-Large, Uncased (Whole Word Masking), and fine-tuned the model during training. The learning rate is set to $1e^{-5}$, and minibatch size is set to 4.

2 Experimental Results

Table 5 shows the comparisons of our system with several state-of-the-art systems; Evaluation scores for dev and test datasets are retrieved from the Spider leaderboardhttps://yale-lily.github.io/spider. The performance of the proposed system is compared with grammar-based systems GrammarSQL (Lin et al., 2019), Global-GNN (Bogin et al., 2019) and IRNet (Guo et al., 2019). Also, we compared the system performance with RCSQL (Lee, 2019), which so far showed the best performance on the Spider dataset using a sketch-based slot-filling approach.

As can be observed from the table, the proposed system RYANSQL improves the previous slot filling based system RCSQL by a large margin of 15%p on the development dataset. With the use of BERT, our system outperforms the current state-of-the-art by 3.2%p on the hidden test dataset, in terms of exact matching accuracy.

Ablation studies are conducted to further figure out the effect of SPC and the two input manipulation methods. Since the test dataset is not publicly available, we use the development dataset to run the tests. The results are presented in Table 6. In addition, the ablation study results of RYANSQL(BERT) for each hardness level is presented in Table 7. The definitions of hardness levels are the same as the definitions in Yu et al. (2018b). In the tables, Proposed means our proposed system, while -SPC means the one without Statement Position Code, -JTF means the one without JOIN Table Filtering, and -SCN means the one without Supplemented Column Names.

As can be observed from the tables, the use of SPC significantly improves the system performance, especially for Hard and Extra Hard queries. The result suggests that by introducing the SPC the proposed system could effectively handle the nested queries. The JTF feature showed some improvements over Medium and Hard queries, meaning that the JTF feature is effective for handling the statements with multiple tables and clauses.

Finally, the SCN feature showed the most significant performance improvement among the three proposed features. When the SCN feature is used, the system performances of all hardness levels are improved significantly. The evaluation result suggests that our proposed input encoder network architectures do not integrate the table names efficiently during the encoding process. But the evaluation result also shows that the proposed system could successfully integrate the table names into encoding vectors by simply applying the proposed SCN feature, instead of modifying the network architectures.

3 Error Analysis

We analyzed 345 failed examples of the RYANSQL(BERT) system on the development set. 195 of those examples are analyzed to figure out the main reasons for failure.

The most common cause of failure is column selection failure; 68 out of 195 cases (34.9%) suffered from the error. In many of those cases, the correct column name is not mentioned in a question; for example, for the question “What is the airport name for airport ‘AKO’?”, the decoder chooses column AirportName instead of AirportCode as its WHERE clause condition column. As mentioned in Yavuz et al. (2018), cell value examples for each column will be helpful to solve this problem.

The second frequent error is table number classification error; 49 out of 195 cases (25.2%) belong to the category. The decoder occasionally chooses too many tables for the FROM clause, resulting unnecessary table JOINs. Similarly, 22 out of 195 cases (11.3%) were due to condition number classification error. Those errors could be resolved by observing and updating the extracted slot values as a whole; our future work will focus on this problem.

The remaining 150 errors were either hard to be classified into one category, and some of them were due to different representations of the same meaning, for example: “SELECT max(age) FROM Dogs” vs. “SELECT age FROM Dogs ORDER BY age DESC LIMIT 1”.

Conclusion

In this paper, we proposed a sketch-based slot filling algorithm for complex, cross-domain Text-to-SQL problem. A detailed sketch for complex SELECT statement prediction is proposed, along with the Statement Position Code to handle nested queries. Also, two input manipulation methods are proposed to enhance the overall system performance further. Our proposed system achieved the state-of-the-art performance on the challenging Spider benchmark dataset.

The error analysis suggests that we should update slot values based on other slots’ prediction results. Our future work will focus on this slot value updating problem.

References