PaperlayerView exact revision on arXiv

Source-linked AI summary

JoinGR: Learning to Traverse Join Graphs for Table Retrieval

Sandipan De, Abhijit Chakraborty, Sambaran Bandyopadhyay, Vivek Gupta

arXiv:2610.01064v1cs.CLcs.AIcs.DBcs.IR

TL;DR

Independent table retrieval can miss required tables that become identifiable only through their join relationships to already relevant tables. JOINGR selects semantic anchors and performs query-conditioned traversal over the join graph, aggregating deposits into table scores. It is competitive on Spider and BIRD, improves recall on BEAVER, and transfers across benchmarks.

  • Problem

    Dense retrieval ranks schema elements independently and struggles to identify tables that are relevant only through multi-hop join relationships.

    Source: §1 · p. 1

  • Method

    JOINGR combines semantic anchor selection with query-conditioned traversal over a join graph and aggregates traversal deposits into table scores.

    Source: §1 · pp. 1–2

  • Results

    JOINGR is competitive with strong retrieval baselines on Spider and BIRD, improves recall and perfect recall on BEAVER, and transfers across benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Join structure can guide table retrieval when required tables are implied by their relationships to already relevant tables.

    Source: §8 · p. 8

    JOINGR depends on a constructable join graph; missing foreign keys must be inferred, and noise in those inferred edges propagates into the graph.

    Source: §9 · p. 9

Abstract

from arXiv · show

Retrieving the right tables is a prerequisite for Text-to-SQL over realistic databases. Dense table retrievers rank schema elements independently, but this ignores a key source of evidence: some required tables are not mentioned in the question and become identifiable only through their join relationships to already relevant tables. We introduce JOINGR, a join-aware table retrieval method that treats the database join graph as the retrieval space. Columns are represented as graph nodes, while intra-table and foreign-key relationships are represented as typed edges. Given a question, JOINGR selects semantically similar anchor tables, traverses join edges with a query-conditioned scorer, and aggregates the resulting edge deposits into table scores. The scorer is a lightweight MLP on top of frozen query, node, and edge embeddings, trained with a pairwise margin loss over gold tables. On BIRD and Spider datasets, JOINGR is competitive with the strongest retrieval baselines. On BEAVER, a challenging enterprise benchmark with multi-hop table requirements, JOINGR substantially improves recall over dense retrieval and re-ranking baselines. Cross-domain experiments show that the learned scorer transfers across benchmarks, indicating that the method captures reusable joingraph traversal behavior.

1 Introduction

Independent table retrieval can miss tables identifiable only through join structure, even though missing a required table can make correct SQL generation impossible. JOINGR combines semantic anchors with query-conditioned graph traversal and performs competitively where dense retrieval is strong while improving recall on multi-hop enterprise schemas.

1 Introduction

  • Independent retrieval struggles with multi-hop queries and ambiguous or abbreviated names because it cannot represent tables that become relevant only after another table is selected.Missing even one required table can make the correct query impossible to generate.Source: §1 · p. 1
  • JOINGR represents columns as graph nodes and intra-table and foreign-key relationships as typed edges, then uses query-conditioned edge scoring to guide traversal and aggregate table scores.Semantic matching selects anchor tables before the query-specific walks.Source: §1 · pp. 1–2
  • Spider has compact schemas where dense retrieval is strong, BIRD has larger databases, and BEAVER features cryptic table names and multi-hop table needs.The evaluation is designed to span settings where semantic retrieval may suffice and where relational structure is crucial.Source: §1 · pp. 1–2
  • JOINGR is competitive with strong retrieval baselines on Spider and BIRD, but improves recall and perfect recall on structurally challenging BEAVER.The introduction reports especially substantial gains on BEAVER, where independent retrieval and re-ranking struggle.Source: §1 · p. 2
  • Scorers trained on one benchmark transfer to another without retraining, suggesting reusable traversal behavior rather than memorization of dataset-specific table names.Source: §1 · p. 2

2 Problem Formulation

Table retrieval ranks database tables for a question so that all tables needed for its SQL query appear as high as possible. Because some required tables are identifiable only through their structural links to already relevant tables, JOINGR uses relational structure as its retrieval space.

2 Problem Formulation

  • The formulation denotes the database collection by D and its tables and columns by T(D) and C(D), with gold table sets and, when annotated, gold join-key pairs for each question.Source: §2 · p. 2
  • Given a question and database, table retrieval produces a ranked list that should include every gold table as near the top as possible.Source: §2 · p. 2
  • Independent table ranking can miss required tables that are not obvious from the question and become relevant through structural relationships to identified tables.JOINGR therefore uses the database relational structure as its retrieval space.Source: §2 · pp. 2–3

3 JOINGR

JOINGR represents schemas as join graphs and retrieves tables through semantic anchors, query-conditioned traversal, and aggregation of traversed-edge evidence. Its training objective uses gold table sets, with an edge-level variant when gold join keys are available.

3.1 Join Graph Construction

  • Columns are graph nodes with descriptors, while typed intra-table and foreign-key join edges connect them.Node descriptors include canonical names, LLM-generated semantic names and purposes, data types, and key flags; edge descriptors include endpoint information and a purpose.Source: §3.1 · p. 3

3.2 Anchor →Walk →Aggregate

  • JOINGR selects semantically relevant anchor tables, walks their join edges with a query-conditioned scorer, and aggregates traversed-edge evidence into table scores.The procedure retrieves a query-specific subgraph from the larger join graph.Source: §3.2 · p. 3

3.2.1 Encoding

  • Frozen query, node, and edge embeddings share a normalized space in which dot products represent cosine similarity.The encoder embeds queries and schema descriptors offline; all vectors are L2-normalized.Source: §3.2.1 · p. 3

3.2.2 Anchor Selection

  • Candidate tables are scored by their most query-similar column, and top-scoring tables become anchors for traversal.The best-matching node embedding also supplies a query-dependent table representation for later use.Source: §3.2.2 · p. 3

3.2.3 Learned Graph Walk

  • At each frontier, a scorer uses query, edge, endpoint-table, incoming-deposit, and hop features to rank outgoing join edges.Outgoing scores are locally softmax-normalized; edge deposits accumulate across anchors and hops, and visited sets prevent cycles within each anchor walk.Source: §3.2.3 · p. 4

3.2.4 Aggregation

  • Accumulated edge deposits are projected onto endpoint tables, which are ranked by their resulting table scores.The score aggregates evidence from edges across anchors and hops.Source: §3.2.4 · p. 4

3.2.5 Training

  • Training uses a pairwise margin objective over gold and negative table sets; an edge-level variant is available when gold join keys exist.The main experiments use table-level loss because standard text-to-SQL benchmarks provide gold table sets.Source: §3.2.5 · p. 4

4 Experimental Setup

The experiments compare JOINGR across benchmarks with different table-retrieval challenges, using dense and relation-aware baselines, a fixed-weight JOINGR variant, and cross-domain evaluation.

Datasets

  • Spider, BIRD, and BEAVER span compact schemas, larger databases, and enterprise queries with cryptic names and multi-hop table needs.The setup reports dataset and join-graph statistics, and Figure 4 summarizes the number of required gold tables per query.Source: §4 · p. 4, Table 1 · p. 5, Figure 4 · p. 5

Encoders and baselines

  • Frozen MiniLM and BGE embeddings support a vanilla retriever that ranks tables by their most similar column, alongside relation-aware retrieval and reranking baselines.REaR refines retrieved candidates, while JAR and IterativeJAR use joinability signals with global optimization or greedy search, respectively.Source: §4 · pp. 4–5
  • A heuristic JOINGR variant keeps the anchor–walk–aggregate pipeline but replaces learned edge scores with fixed propagation weights.Comparisons with dense retrieval and trained JOINGR separate semantic retrieval, fixed-weight graph expansion, and learned edge weighting.Source: §4 · p. 5

Scorer implementation and training

  • The edge scorer is a one-hidden-layer MLP, while encoders and graph embeddings remain frozen and only the scorer and hop-decay parameters are trained.The setup uses maximum walk depth H = 5, dropout 0.3, and Adam with learning rate 10^-3 and weight decay 10^-4.Source: §4 · p. 5

Evaluation protocol

  • Spider and BIRD use standard train/dev splits, BEAVER uses five-fold cross-validation, and cross-domain tests transfer between benchmarks without target-domain supervision.Evaluation reports P@K, R@K, and PR@K at K ∈ {5, 15}; PR@K requires every gold table to appear in the top K.Source: §4 · p. 5

5 Results

JOINGR achieves its clearest gains on structurally challenging BEAVER, while remaining competitive on BIRD and Spider, where dense retrieval is already strong. Cross-domain results show that its scorer transfers between benchmarks without target-domain supervision.

5.1 Results on BEAVER (DW)

  • Trained JOINGR raises BEAVER (DW) PR@15 over heuristic JOINGR from 0.405 to 0.645 with BGE and from 0.430 to 0.653 with MiniLM.The heuristic variant also improves R@15 over vanilla retrieval for both encoders.Source: §5.1 · p. 6
  • With BGE, JOINGR raises BEAVER (DW) R@15 from 0.697 to 0.875 and PR@15 from 0.339 to 0.645 over the vanilla retriever.With MiniLM, it raises R@15 from 0.667 to 0.873 and PR@15 from 0.273 to 0.653.Source: §5.1 · p. 5, Table 2 · p. 6

5.2 Results on BIRD

  • On BIRD, where 84% of queries require only one or two tables, vanilla BGE retrieval already reaches R@15 of 0.983 and PR@15 of 0.964; JOINGR remains competitive.With BGE, REaR achieves the strongest R@15 and PR@15, while JOINGR obtains the best P@5 and PR@5.Source: §5.2 · p. 6, Table 3 · p. 6
  • With MiniLM on BIRD, JOINGR improves R@5 from 0.886 to 0.909 and PR@15 from 0.936 to 0.951 over vanilla retrieval.The reported gains are clearer with the lightweight encoder.Source: §5.2 · p. 6

5.3 Results on SPIDER

  • On Spider, where 94% of queries require only one or two tables, JOINGR remains close to vanilla retrieval, with MiniLM R@15 of 0.748 versus 0.752.The passage characterizes retrieval there as largely solved by direct query-schema similarity.Source: §5.3 · p. 6

5.4 Cross-Domain Transfer

  • A BIRD-trained scorer remains competitive on BEAVER without target-domain supervision, and BEAVER-trained scorers remain close to in-domain JOINGR on BIRD and Spider.The authors present cross-domain results as support for reusable scoring before local supervision, with fine-tuning when local data justifies it.Source: §5.4 · p. 7

6 Analysis

Query-conditioned graph traversal preserves strong performance on simpler queries and recovers relevant tables beyond semantic anchors, especially on BEAVER. Longer BEAVER join paths and incorrect anchors remain failure points.

6.1 Precision and Recall by Query Complexity

  • On BIRD, recall remains high for one- and two-table queries, while on BEAVER it remains higher as required table count grows, though it drops for four- and five-plus-table queries.The analysis uses required gold-table count as a proxy for join structure and reports P/R at @5 and @15.Source: Figure 5 · p. 7, §6.1 · p. 7

6.2 Semantic Anchors vs. Graph Expansion

  • With small anchor budgets on BEAVER, graph-based methods outperform the vanilla retriever; trained JOINGR has the best overall recall, especially at larger budgets.The comparison varies anchors from 1 to 7 and evaluates R@10 at K = 10.Source: §6.2 · p. 7, Figure 6 · p. 8

6.3 Failure Cases

  • Failures arise from long narrative joins, where probability mass can split across plausible third-hop neighbors, and from anchor mis-selection when question terms overlap several tables.Additional anchors or hops mitigate both failure modes at the cost of latency.Source: §6.3 · p. 8

7 Related Work

Related work covers schema retrieval, join-aware methods, graph retrieval, and schema-graph reasoning. JOINGR’s distinguishing focus is upstream table retrieval through learned traversal of the database join graph.

Table retrieval and schema linking for text-to-SQL

  • Text-to-SQL systems perform schema linking within parsers or as an upstream step, while JOINGR adds join-graph traversal to query-to-schema similarity.The passage notes that irrelevant schema elements can distract generation or cause spurious joins (Maamari et al., 2024).Source: §7 · p. 8

Table representations and join-aware retrieval

Graph-based retrieval

Schema graphs for tabular reasoning

  • Other schema-graph methods address end-to-end QA/SQL generation or training-free table linking, while JOINGR learns a traversal scorer for upstream retrieval over a column-level join graph.CORE-T instead combines offline LLM-generated metadata, a compatibility cache, and online dense retrieval with LLM selection for pooled tables without database IDs or gold foreign keys.Source: §7 · p. 8

8 Conclusion

JOINGR uses the database join graph as a search space, combining semantic anchors with query-conditioned edge traversal and table-score aggregation. The conclusion is that join structure guides retrieval, particularly when tables are related through relational context.

8 Conclusion

  • JOINGR starts from semantic anchors, traverses join edges with a query-conditioned scorer, and aggregates evidence into table scores.The design separates semantic matching from structural expansion.Source: §8 · p. 8
  • JOINGR competes with standard retrievers when independent table similarity suffices, while learned traversal aids recovery when tables are connected through relational context.The conclusion frames join structure as a retrieval signal, not only a guide for SQL generation.Source: §8 · p. 8

9 Limitations

JOINGR’s evaluation has several explicit boundaries: it requires a constructable join graph, uses frozen encoders, and covers only English questions on three benchmarks.

9 Limitations

  • Foreign keys absent from a schema must be inferred, and noise in that inference propagates into the join graph’s edges.The paper identifies heuristic name-matching or an LLM pass as typical inference approaches.Source: §9 · p. 9
  • Experiments use frozen encoders; the effect of jointly fine-tuning the encoder with the scorer has not been measured.The authors describe joint fine-tuning as a potentially useful but tangential extension.Source: §9 · p. 9
  • Evaluation is limited to English-language questions and three benchmarks, leaving multilingual and lower-resource settings unexplored.LLM-generated schema descriptors also incur a one-time cost that scales linearly with columns plus edges.Source: §9 · p. 9

10 Ethical Considerations

The paper recommends separating retrieval from authorization in deployment, describes its graph-search algorithms, and lists the hyperparameter categories used in the main experiments.

10 Ethical Considerations

  • Deployments should pair table retrieval with an independent authorization layer because incorrect retrieval can disclose unauthorized tables.The authors say JOINGR is no more or less prone to these privacy-related failures than the compared baselines.Source: §10 · p. 9

A Algorithms

  • Algorithm 1 builds a navigation graph over database schemas, while Algorithm 2 traverses join paths from retrieved anchors and ranks tables by accumulated deposits.The graph represents columns as nodes and uses intra-table and join edges.Source: A Algorithms · p. 11

B Hyperparameters

  • The main-experiment hyperparameter table covers anchor selection, traversal, model dimensions, optimization, training, and cross-validation settings.The listed categories include BFS hops, MMR weight, learning rate, margin, and training epochs.Source: B Hyperparameters · p. 11

C Full Results on Spider

The appendix points to complete Spider retrieval results and documents the query-conditioned search procedure and reported runtime.

C Full Results on Spider

D Reproducibility

  • The search algorithm embeds the query, retrieves candidate nodes, selects anchor tables, traverses join edges for up to a hop limit, and ranks tables by accumulated deposits.Edge scores are computed from query-conditioned features and propagated as deposits during traversal.Source: D Reproducibility · p. 11
  • With embeddings cached, full BFS-with-scorer evaluation runs at about 40 queries per second on CPU.The paper describes this throughput as making JOINGR suitable for online LLM-front-end use.Source: D Reproducibility · p. 11
Loading 2610.01064v1…