Translating natural language to SQL for data retrieval has become more accessible thanks to code generation LLMs. But how hard is it to generate SQL code? While databases can become unbounded in complexity, the complexity of queries is bounded by real life utility and human needs. With a sample of 376 databases, we show that SQL queries, as translations of natural language questions are finite in practical complexity. There is no clear monotonic relationship between increases in database table count and increases in complexity of SQL queries. In their template forms, SQL queries follow a Power Law-like distribution of frequency where 70% of our tested queries can be covered with just 13% of all template types, indicating that the high majority of SQL queries are predictable. This suggests that while LLMs for code generation can be useful, in the domain of database access, they may be operating in a narrow, highly formulaic space where templates could be safer, cheaper, and auditable.
Figures & tables
Figure 1: Frequency curve of soft templates.
Source
#DB
#T/DB
#Q
Bird23-train-filtered Li et al. (2023)
69
7.57
6,601
Spider 1.0 Yu et al. (2018)
196
5.15
11,245
Spider 2.0-lite Lei et al. (2024)
15
14.87
287
KaggleDBQA Lee et al. (2021)
8
2.12
244
drawSQL
88
14.34
2,112
Overall
376
8.07
20,489
Table 1: Statistics of database schemas collected from text-to-SQL benchmarks and drawSQL. #DB indicates the number of databases from each data source, #T/DB indicates the average number of tables per database, and #Q indicates the number of SQL queries per source. For drawSQL, we manually generate three difficulty levels of NLQs: easy, medium, and difficult. Appendix A provides concrete examples.
Proxy
Definition
Num_tables
# of distinct tables referenced (i.e., number of data sources involved)
Num_joins
# of JOIN operations (capturing cross-table relational reasoning)
Num_subqueries
# of nested subqueries (capturing hierarchical reasoning)
Max_nesting_depth
Maximum depth of nested queries (i.e., levels of embedding)
Num_aggs_plus_group_by
# of aggregation operations (e.g., COUNT, SUM) and GROUP BY clauses
Advanced_feature_count
# of advanced constructs (e.g., window functions, FILTER, set operations, CTEs)
Table 2: Structural proxies for SQL query complexity, capturing aspects such as multi-table interactions, hierarchical structure, and advanced analytical operations.
Proxy
Median
Average
Min
Max
Peak Value
Num_tables
2.00
1.73
1
27
1.94
Num_joins
1.00
0.73
0
26
0.90
Num_subqueries
0.00
0.11
0
7
0.22
Max_nesting_depth
1.00
0.62
0
5
0.74
Num_aggs_plus_group_by
0.00
0.74
0
9
0.81
Advanced_feature_count
0.00
0.06
0
6
0.17
Table 3: Summary statistics and peak characteristics of six SQL complexity proxies.
Figure 2: Moving average values of six proxies (window size = 15).
Figure 3: Log–log plots for hard and soft templates.
Template Type
Query Coverage (%)
10
30
50
70
90
100
Hard
9 (0.13%)
58 (0.87%)
306 (4.57%)
1616 (24.12%)
4677 (69.82%)
6699 (100%)
Soft
7 (0.15%)
42 (0.92%)
140 (3.05%)
605 (13.19%)
2565 (55.92%)
4587 (100%)
Table 4: Number of templates required to cover different proportions of SQL queries. Numbers in parentheses denote the cumulative percentage of templates.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Frequency curves for hard and soft templates.
Proxy
ρ
p-value
Num_tables
-0.3673
2.33×10−2
Num_joins
-0.3839
1.73×10−2
Num_subqueries
0.4481
4.79×10−3
Max_nesting_depth
0.3124
5.62×10−2
Num_aggs_plus_group_by
-0.4263
7.61×10−3
Advanced_feature_count
0.4921
1.70×10−3
Appendix
Table 5: Spearman correlation test for the monotonic relationship between each proxy and the table count.
Figure 5: Individual Plots for Six Proxies. Each point represents the average value of a proxy metric for a specific table count. The dashed line denotes the moving average of the proxy values with a window size of 15.
Metric
Type
High
Middle
Long Tail
Once
Num_tables
Soft
1.41
1.74
1.83
2.12
Hard
1.12
1.55
1.91
2.21
Num_joins
Soft
0.41
0.74
0.82
1.10
Hard
0.12
0.55
0.91
1.20
Num_subqueries
Soft
0.03
0.11
0.14
0.23
Hard
0.04
0.13
0.11
0.15
Appendix
Table 6: Average proxy values across template frequency groups. The maximum value in each row is highlighted in bold.
Template Type
High ( ≥ 100)
Middle (10–99)
Long Tail (2–9)
Once (1)
Hard
19 (0.3%)
223 (3.3%)
2358 (35.2%)
4099 (61.2%)
Soft
28 (0.6%)
260 (5.7%)
1958 (42.7%)
2341 (51.0%)
Appendix
Table 7: Template frequency distribution. Percentages indicate the proportion of templates in each frequency category.