MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery

A training-free sketching strategy that makes value-level semantic join discovery scalable to high-cardinality columns while preserving fine-grained value alignment

Grace Fan; Eden Wu; Majid Daliri; Juliana Freire· 2026· DOI 10.48550/arXiv.2607.21781

The core problem

Join discovery is a core task in dataset search: given a query column, the goal is to find columns in a data lake that can be joined with it. Early approaches focused on equi-joins, where values match exactly. However, data lakes and open-data repositories frequently contain columns whose values refer to the same real-world entity but use different syntactic representations—for example, "IBM" vs. "International Business Machines" or "NYC" vs. "New York City". Such semantically joinable columns cannot be found by exact matching. Recent approaches to semantic join discovery face a fundamental trade-off. Value-level methods compare values directly and can accurately identify joinable columns, but they scale poorly to columns with high cardinality because the number of pairwise value comparisons grows rapidly. Column-level methods encode an entire column into a single embedding, which is efficient, but they lose the fine-grained value alignment that determines whether a join is actually possible. MosaicJoin is presented as a value-level semantic join discovery method that balances this trade-off. It achieves scalability through a novel sketching strategy that approximates the joinabil

Innovation

The authors conduct extensive experiments to evaluate MosaicJoin against previously published methods across multiple benchmarks. The key findings are: - **Accuracy.** MosaicJoin outperforms previously published methods across all benchmarks. This indicates that its value-level sketching approach preserves the fine-grained alignment needed for accurate semantic join discovery, unlike column-level embedding methods. - **Speed.** MosaicJoin runs up to 66 times faster than other value-level methods. This speedup is attributed to the sketching strategy and query subsampling, which bound the online scoring cost by the sketch size rather than the column cardinality. - **Scalability.** MosaicJoin scales robustly to query columns containing up to 57K values and data lake columns containing up to 1M values. This demonstrates its ability to handle high-cardinality columns that challenge value-level comparison methods. - **No training.** The method requires no training or fine-tuning, which simplifies deployment and avoids the need for labeled data. The results collectively show that MosaicJoin effectively balances the trade-off between accuracy and scalability in value-level semantic join

Join discovery is a core task in dataset search: given a query column, the goal is to find columns in a data lake that can be joined with it. Early approaches focused on equi-joins, where values match exactly. However, data lakes and open-data repositories frequently contain columns whose values refer to the same real-world entity but use different syntactic representations—for example, "IBM" vs. "International Business Machines" or "NYC" vs. "New York City". Such semantically joinable columns cannot be found by exact matching.

Recent approaches to semantic join discovery face a fundamental trade-off. Value-level methods compare values directly and can accurately identify joinable columns, but they scale poorly to columns with high cardinality because the number of pairwise value comparisons grows rapidly. Column-level methods encode an entire column into a single embedding, which is efficient, but they lose the fine-grained value alignment that determines whether a join is actually possible. MosaicJoin is presented as a value-level semantic join discovery method that balances this trade-off. It achieves scalability through a novel sketching strategy that approximates the joinability of a column pair without comparing all values. At query time, each candidate sketch is scored using a joinability score at a cost bounded by the sketch size, making retrieval efficient even for high-cardinality columns. A query subsampling operator further reduces online search time with provable accuracy guarantees, enabling robust retrieval for large query columns. The method requires no training or fine-tuning and is evaluated extensively against previously published methods.

Why it matters

The fundamental challenge addressed by MosaicJoin is the tension between value-level accuracy and scalability. Value-level methods are accurate because they compare actual values, but they become prohibitively expensive as cardinality grows. Column-level methods are efficient but lose the granularity needed to determine whether a join is possible. MosaicJoin resolves this by introducing a sketch that approximates joinability without comparing all values. The sketching strategy is the key innovation. By bounding the scoring cost by sketch size, MosaicJoin makes retrieval efficient even for columns with up to 1M values. The query subsampling operator adds another layer of efficiency, with provable accuracy guarantees that ensure robust retrieval for large query columns. This is particularly important because query columns can contain up to 57K values, and subsampling reduces the online search time without sacrificing reliability. The fact that MosaicJoin requires no training or fine-tuning is a significant practical advantage. It can be applied out-of-the-box to new data lakes and domains, avoiding the overhead of model training and the need for labeled data. The extensive experiments demonstrate that MosaicJoin outperforms prior methods across all benchmarks while being up to 66 times faster than other value-level methods. One limitation is that the paper does not provide details on the specific benchmarks used or the exact accuracy metrics, but the reported results are consistent across all benchmarks. Future work could explore extending the sketching approach to other types of joins, such as those involving multiple columns or complex matching functions. Overall, MosaicJoin represents a significant step forward in making value-level semantic join discovery practical for large-scale data lakes.

Who should read this

CS practitioners and researchers

Opening member content…