Can Deep Neural Networks Predict
Data Correlations from Column Names?

Immanuel Trummer

Cornell Database Group
Ithaca, NY

For humans, it is often possible to predict data correlations from column names. We conduct experiments to find out whether deep neural networks can learn to do the same. If so, e.g., it would open up the possibility of tuning tools that use NLP analysis on schema elements to prioritize their efforts for correlation detection.

We analyze correlations for around 120,000 column pairs, taken from around 4,000 data sets. We try to predict correlations, based on column names alone. For predictions, we exploit pre-trained language models, based on the recently proposed Transformer architecture. We consider different types of correlations, multiple prediction methods, and various prediction scenarios. We study the impact of factors such as column name length or the amount of training data on prediction accuracy. Altogether, we find that deep neural networks can predict correlations with a relatively high accuracy in many scenarios (e.g., with an accuracy of 95% for long column names).

scaled y ticks=false, log ticks with fixed point

discard if/.style 2 args=
x filter/.code=

discard if not/.style 2 args=
x filter/.code=

[group style=group size=5 by 1, y descriptions at=edge left, horizontal sep=5pt, width=2.75cm, height=3cm, ybar=0pt, ymajorgrids, ylabel=Score, ylabel near ticks, ymin=0, ymax=1, xtick=, legend entries=#2, legend columns=4, legend to name=lastLegend]
+[discard if not=id1] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=acc] #1;

[group style=group size=5 by 1, y descriptions at=edge left, horizontal sep=5pt, width=2.75cm, height=3cm, ybar=0pt, ymajorgrids, ylabel=Score, ylabel near ticks, ymin=0, ymax=1, xtick=, legend entries=#2, legend columns=4, legend to name=lastLegend]
+[discard if not=id1] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=acc] #1;

[group style=group size=5 by 1, y descriptions at=edge left, horizontal sep=5pt, width=2.75cm, height=3cm, ybar=0pt, ymajorgrids, ylabel=Score, ylabel near ticks, ymin=0, ymax=1, xtick=, legend entries=#2, legend columns=4, legend to name=lastLegend]
+[discard if not=id1] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id4] table[col sep=comma, x expr=0, y=f1] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id4] table[col sep=comma, x expr=0, y=rec] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id4] table[col sep=comma, x expr=0, y=pre] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id4] table[col sep=comma, x expr=0, y=mcc] #1;
+[discard if not=id1] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id2] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id3] table[col sep=comma, x expr=0, y=acc] #1;
+[discard if not=id4] table[col sep=comma, x expr=0, y=acc] #1;

§ INTRODUCTION

The code used for the following experiments is available online at <https://github.com/itrummer/DataCorrelationPredictionWithNLP>.

Consider a table named “cars” with columns named “maker” and “model”. Most people would assume, based on column names alone, that maker and model columns are correlated (i.e., knowing the maker will restrict options for the model). This assumption is based on commonsense knowledge and on the assumption that column names accurately describe column content. In most cases, the assumption would be correct. In this paper, we study the question of whether automated tuning tools could apply a similar kind of reasoning. To do so, we exploit recent innovations in the domain of natural language analysis (NLP): pre-trained language models <cit.>.

Detecting correlations in data has been a topic of significant interest in the database research community <cit.>. Knowing data correlation is useful in many scenarios. For instance, query optimizers <cit.> (as well as other tuning tools) often depend on accurate predictions of intermediate result sizes. Classical prediction models assume uncorrelated data, thereby being misled in practice <cit.>. As pointed out in prior work <cit.>, knowing about correlations can help to correct cardinality estimates. Alternatively, knowing about possible data correlations can help to prune options with correlation-related uncertainty from the search space (e.g., the optimizer can favor join orders where intermediate result sizes do not depend on columns that are likely correlated).

Typically, we detect correlations by analyzing data. Instead of analyzing all data, we can use data samples to reduce associated overheads <cit.>. However, for a fixed confidence threshold, the required sample size grows in the amount of data. Typically, the overheads of analysis grow in the data size as well. This makes correlation analysis expensive for large data sets.

In our experiments, we study a complementary method to detect possible correlations. It is not based on actual data. Instead, it is based on database schema elements. This means that the overheads for correlation detection do not depend on the amount of data. They only depend on the size of the database schema.

In this study, we use column names as features. We hypothesize that it is often possible to predict correlations in data, based on the column names alone (like in the initial example). Of course, the corresponding correlations may be less “interesting” from the perspective of a data analyst (as they are implied by column semantics and commonsense knowledge). However, they remain highly relevant from the perspective of tuning tools that may otherwise make sub-optimal choices.

Our goal is to automatically identify pairs of columns that are likely correlated, before looking at the actual data and using column names alone. We propose to train deep neural networks for that task. Until quite recently, learning to predict correlations would have required very significant amounts of training data. We propose, however, to exploit an approach that has recently advanced the state of the art in NLP significantly: pre-trained language models <cit.>. Such models are pre-trained on tasks such as masked language modelling (i.e., predicting masked words based on surrounding text) where large amounts of training data (i.e., any written text) are available. After pre-training, the number of training samples required for specialization to new tasks is very significantly reduced <cit.>.

We predict correlation for column pairs, using pre-trained language models, based on column names. We use a diverse range of several thousand data sets, considering around 120,000 unique column pairs. During our experiments, we consider different types of correlations, based for instance on Pearson's correlation coefficient, on Spearman's correlation coefficient, or on Theil's U (those metrics are discussed in more detail in Section <ref>). We vary various scenario properties, consider data subsets (characterized, for instance, by properties of the column names), and compare different prediction methods. Our overarching goal is to find out up to which extent and under which circumstances prediction is possible. To measure prediction success, we consider multiple different metrics, outlined in more detail in Section <ref>.

In principle, column names may be misleading. In practice, the authors of a data set often have an interest in reducing overheads for users of their data. Choosing meaningful names for columns is one approach to do that. Still, it seems not realistic to predict correlations accurately in all cases. This is however not required for such prediction methods to become useful. For instance, detecting correlations even for a subset of column pairs can already reduce risks due to correlation in query optimization. Also, NLP-based correlation prediction can be used to prioritize and to narrow down the search space for more expensive correlation detection methods (based on analyzing data).

We do not evaluate concrete methods to exploit predicted correlations for any of the aforementioned use cases. Instead, the goal of this initial study is to find out whether prediction accuracy seems high enough to make such follow-up projects possible. Broadly, this work is part of a recently introduced work stream that uses NLP techniques to enhance database tuning tools <cit.>.

In summary, our original scientific contributions in this experimental paper are the following.

* We introduce the problem of predicting data correlations based on schema properties (here: column names) alone.

* We evaluate pre-trained language models for this prediction task (and compare against a simple baseline).

* We consider different metrics, scenarios, and correlation coefficients, and analyze how test case properties influence prediction accuracy.

The remainder of this paper is organized as follows. In Section <ref> we provide background on the techniques used throughout the paper and discuss related work. Then, in Section <ref>, we describe the experimental setup for the following sections in detail (covering the prediction methods used, as well as the process generation training and test data). Next, in Section <ref>, we analyze the training data used in the following sections. We show extracts from that data (i.e., column pairs with and without correlations) and aggregate statistics, describing correlations and column name properties. Next, in Section <ref>, we apply different methods to predict data correlations, including pre-trained models and baselines. In Section <ref>, we vary several scenario properties, including the amount and quality of training data, to study the impact on prediction performance. In Section <ref>, we analyze prediction performance for different data subsets separately, breaking down, for instance, by column name length among other properties. In Section <ref>, we vary the type of correlation studied, thereby obtaining insights into how well our findings generalize. Finally, we sketch out possible use cases for NLP-based correlation predication and discuss extensions to the evaluated prediction methods. We conclude with a summary of our results and future work directions. In the appendix, we present more detailed results, corroborating our findings.

§ BACKGROUND AND RELATED WORK

We discuss different categories of background and prior work. First, we discuss prior work on database tuning (one of the motivating use cases for this work) and correlation detection. Then, we discuss pre-trained natural language models. Finally, we discuss applications of NLP techniques in the context of database management systems.

§.§ Database Tuning

The performance of database systems is influenced by various tuning choices. Those tuning choices include, for instance, join order, optimized by the query optimizer <cit.>, as well as physical design decisions. The latter category includes index selection <cit.>, materialized view selection <cit.>, or partitioning choices <cit.>, among others. Automated tuning components recommend choices for all of the aforementioned decisions to reduce processing overheads (e.g., for an example workload). Processing cost often depends on the sizes of intermediate results, generated during data processing. Data correlations make it hard to estimate the sizes of those results <cit.>. Hence, knowledge on data correlations is valuable to make more reliable tuning choices <cit.>.

§.§ Detecting Correlations

The fact that data correlations are important has motivated work aimed at finding correlations in data sets <cit.>. More specifically, significant work has been dedicated to the problem of selectivity estimation with correlations <cit.>. Here, correlations play an important role in estimating aggregate selectivity of predicate groups. More recently, machine learning has been proposed as a method to solve various types of tuning problems in the context of databases <cit.>. Correlated data is a primary reason to replace more traditional cost models, often based on the independence assumption, via learned models. This stream of work connects to our work as we apply machine learning for predicting correlations. However, we use machine learning in the form of NLP-based analysis of database schema elements.

§.§ Pre-Trained Language Models

Pre-trained language models have recently led to significant advances on a multitude of NLP tasks. Pre-trained language models are based on the idea of “transfer learning”. For many specialized NLP tasks, it is difficult to accumulate a large enough body of training data. Also, overheads related to the training of large neural networks from scratch can be significant. This motivates the following approach. We perform a pre-training stage in which a deep neural network is trained on an NLP task for which training data is in ample supply. For instance, we can train on the “masked language modelling” task <cit.>. Here, the goal is to predict masked words in a sentence. Doing so well requires many capabilities that are useful for other NLP tasks as well. Furthermore, any written text can be used as training data for the latter task. After pre-training, the resulting network (with associated weights) can be specialized (“refinement”) to another task. This refinement step requires only moderate computational resources and few training samples <cit.>, compared to the initial training. Nowadays, pre-trained language models <cit.> achieve state of the art performance over a wide range of NLP tasks. We use them for the following experiments.

§.§ NLP for Databases

There have been significant efforts to leverage NLP techniques for database systems. Typically, the focus of those efforts is the query interface. Here, a long standing goal in database research is to enable natural language query interfaces <cit.>. Sequence-to-sequence models have been successfully used for this task over the past years <cit.>. More recently, pre-trained language models, based primarily on the Transformer architecture <cit.>, have achieved excellent results on text-to-SQL benchmarks such as Spider[<https://yale-lily.github.io/spider>] or WikiSQL[<https://github.com/salesforce/WikiSQL>]. We use this type of approach in the following.

This work applies NLP not for the interface but rather for the database backend. It thereby connects to another, recently accepted paper <cit.>. The latter work describes experimental results for a prototype system that parses database tuning hints from text documents. In this work, we present experimental results for predicting data correlations from schema elements instead.

§ EXPERIMENTAL SETUP

We analyzed correlations in publicly available data sets. The resulting data is used as training and test data for the following experiments. Our goal was to experiment with a diverse collection of data sets. We obtained those data sets from the Kaggle Web site[<www.kaggle.com>] (using a corresponding API[<https://github.com/Kaggle/kaggle-api>]). We queried the Kaggle API for data sets with the following filters. First, we restrict our attention to data sets in “.csv” format. Second, to limit analysis overheads, we consider data sets only up to a size of one megabyte.

Using those constraints, we downloaded several thousand data sets (in the order in which they are returned by the Kaggle API). For each data set, we consider column pairs. As justified in prior work <cit.>, pairwise column correlations (as opposed to correlations between more than two columns) tend to be particularly useful in practice. We limit the analysis to at most 100 column pairs per data set (otherwise, performance results would be dominated by a few data sets with many columns). We consider each pair of columns only once. More precisely, for any given columns $c_1$ and $c_2$, our data set contains only one of $\langle c_1,c_2\rangle$ or $\langle c_2,c_1\rangle$ (but not both). While some of the correlation metrics we consider are not symmetric, we want to avoid using training samples that are too similar (thereby, potentially, leading to overly optimistic prediction performance results). For each column pair, we extract column names and analyze correlation of the associated data. For the correlation analysis, we use Python 3 and SciPy's stats package[<https://docs.scipy.org/doc/scipy/reference/stats.html>].

We analyze correlation according to multiple metrics. First, we analyze correlation via the Pearson correlation coefficient <cit.>. This coefficient is a measure of linear correlation between two data sets. The coefficient itself, denoted as $R$, is contained in the interval $[-1,1]$. It comes with a p-value, indicating the probability of obtaining a specific $R$ value by chance. In the following, we define correlation according to different thresholds for $|R|$ while typically using a threshold of 5% for the p-Value.

The Pearson correlation coefficient measures linear dependencies. As an alternative, we consider Spearman's correlation coefficient <cit.>. This coefficient, typically denoted as $\rho$, measures how well the relationship between two data sets can be characterized by a monotonic (but not necessarily linear) function. Again, the coefficient takes values from the interval $[-1,1]$. It comes with a p-Value, indicating the probability of observing given correlations for uncorrelated data. We try different thresholds on $\rho$ while typically requiring a p-value of 5% or less (to qualify as statistically significant correlation).

We use the aforementioned coefficients, Pearson's and Spearman's coefficient, to express correlation between numerical columns. For categorical columns (in addition to numerical ones), we use the entropy coefficient <cit.>, also called Theil's U, instead. We use the term “Theil's U” in the following. This coefficient is a normalized version of the mutual information between two variables. Intuitively, it measures how many bits we can predict for one column, given the value in the other one. We vary the threshold on Theil's U, starting from which we consider two columns correlated, in the following experiments.

The result of data preparation is a new data set, containing the names of columns pairs, together with their correlation according to different correlation metrics. We use portions of this data as training and test data for the following experiments.

For training and testing, we use an EC2 instance as platform. We use an EC2 p3.2xlarge instance, recommended for machine learning workloads, with the following characteristics. Our EC2 instance features a Tesla V100 GPU with 5,120 CUDA cores, 8 vCPUs, and 488 GB of RAM. We use the Deep Learning AMI version 38.0. For predictions, we use the simpletransformers Python library[<https://simpletransformers.ai/>]. Except if noted otherwise, we use the default parameter settings of that library. The simpletransformers library is internally based on the Huggingface library[<https://huggingface.co/transformers/>] which supports a wide range of pre-trained language models. In the following, we compare different models, using the Roberta model <cit.> (“roberta-base”) as default. As alternatives, we also consider Albert <cit.> (“albert-base-v2”) and DistilBERT <cit.> (“distilbert-base-cased”), two more efficient alternatives. By default, we train for five epochs (a setting that works well for most NLP tasks in the context of pre-trained models <cit.>), using training and test batches of size 100. We use the GPU for training.

The following experiments evaluate the quality of correlation prediction methods in different scenarios. We assess prediction quality according to multiple metrics. More precisely, we consider five metrics of prediction quality. We consider recall, precision, and the F1 score (which combines recall and precision). Here, recall is the percentage of correlated column pairs that were accurately identified. Precision is the ratio of actual column pairs among the ones predicted to be correlated. The F1 score is defined as $2\cdot p\cdot r/(p+r)$ (where $p$ and $r$ are precision and recall, respectively). The aforementioned three metrics are typically used in scenarios where a relatively sparse class of elements should be identified. Here, we identify correlated column pairs (which are typically less common than uncorrelated columns).

Also, we measure Matthew's Correlation Coefficient (MCC) <cit.> and simple prediction accuracy (considering the two classes “correlated” and “uncorrelated” for each column pair). All of the aforementioned quality metrics yield values from the interval $[0,1]$ and higher values represent better quality. We report all five metrics in the following plots. When verifying hypotheses about prediction quality, we consider a hypotheses as validated, if it is validated according to all of those five metrics.

§ DATA ANALYSIS

Examples for strongly correlated (top) and less correlated (bottom) columns according to Pearson's coefficient.

Data Set     Column 1     Column 2     $R$ value     $p$ value

epl1920leaguetable.csv      Points     Wins     99%     0%

emission data.csv      1751     1752     100%     0%

india-districts-census-2011.csv     Female_Literate     Male_Literate     98%     0%

Google_Stock_Price_Test.csv     High     Open     96%     0%

housing.csv     total_bedrooms     total_rooms     93%     0%

time_series_2019-ncov-Confirmed.csv      1/24/20 0:00     Lat     -6%     83%

diabetes_merged_date-time-sorted-includes-patient-id.csv     code     patient_id     2%     0%

Heart.csv     RestECG     Sex     2%     71%

2020.12.09/2020.12.09.csv     num_pkts_out     dest_ip     -5%     0%

nyc-east-river-bicycle-counts.csv     Williamsburg Bridge     Unnamed: 0     10%     16%

We analyze the data set used for training and testing in the following. This data set captures correlations for column pairs, as described in more detail in the previous section. Table <ref> shows an extract from this data set. The upper part of the table shows five highly correlated columns, measured via the Pearson coefficient, the lower half shows five column pairs with low correlation. At the same time, it shows column names and the names of the associated data sets.

For the examples in the table, it seems often possible, using commonsense knowledge, to identify likely candidates for correlations. For instance, the number of points for a team in a table with sports statistics often correlates with the number of wins (more points often lead to more wins). Indeed, the corresponding column pair shows relatively high correlation that is statistically significant (using the common thresholds of 5% to separate statistically significant from non-significant p-Values). On the other side, there is no obvious indication of any correlation between two columns named “Williamsburg Bridge” and “Unnamed: 0”. Indeed, the corresponding column pair shows only weak correlation. Our goal is to partially automate this kind of reasoning via pre-trained language models.

Statistics on benchmark data sets.

Property     Value

Number of data sets     3,952

Number of column pairs     119,384

Number of numerical column pairs     59,449

Number of rows (Avg.)     103,126

Number of distinct values per column (Avg.)     6,200

Table <ref> summarizes size-related statistics, describing our correlation data set. Altogether, we extracted correlations from about 4,000 data sets. Those data sets derive from various sources and cover various topics (the examples in Table <ref> give a first impression of their diversity). From those data sets, we extracted about 120K column pairs, about half of them of numerical (or integer) type, and analyzed their correlations. In average, the source data sets contain over 100K rows and each column contains over 6K unique values.

[group style=group size=2 by 1, y descriptions at=edge left, horizontal sep=10pt, ylabel=Count, width=4.5cm, height=3cm, ybar=0pt, ymajorgrids, ymode=log, ymax=250000, ymin=1, xmin=0]
[bar width=6pt, xlabel=$\log_2(Chars)$]
table[x index=0, y index=1] results/analysis/lengthh;
[bar width=8.5pt, xlabel=$\log_2(Tokens)$]
table[x index=0, y index=1] results/analysis/tokensh;

Distribution of column name length, measured as the number of characters (left) and number of tokens (right).

Our goal is to predict data correlations from column names. Hence, we analyze properties of our features, the column names. In particular, we are interested in column name length. Intuitively, having longer column names should be more informative. Potentially, this makes correlation prediction easier. Figure <ref> shows histograms summarizing the distribution of column name length, measured according to different metrics. On the left hand side, we show the distribution over character length. On the right hand side, we measure the number of tokens (i.e., text snippets separated by spaces or underscores) in column pairs. Note the logarithmic x-axis.

Analyzing length, measured in characters, we find that the typical column name length is around 16 characters. This is sufficient for few, short words. The number of tokens is typically limited to two (i.e., we have one word in each of the columns). Later, in Section <ref>, we analyze how column name properties correlate with prediction accuracy.

[group style=group size=3 by 1, y descriptions at=edge left, horizontal sep=10pt, ylabel=Count, width=3.5cm, height=3cm, ybar=0pt, ymajorgrids, ymode=log, ymax=100000, ymin=1, xmin=0, xtick=0, 5, 10, xticklabels=0,0.5,1, xmin=-0.5, xmax=10.5]
[bar width=5pt, xlabel=Pearson ($|R|$)]
table[x index=0, y index=1] results/analysis/pearsonh;
[bar width=5pt, xlabel=Spearman ($|\rho|$)]
table[x index=0, y index=1] results/analysis/spearmanh;
[bar width=5pt, xlabel=Theil's U]
table[x index=0, y index=1] results/analysis/theilsuh;

Distribution of correlation coefficient values according to different metrics.

Our goal is to predict correlations, measured according to three methods. In the following, we consider correlation as a binary property, varying the thresholds on the corresponding coefficients. This makes it interesting to analyze how correlation is distributed over column pairs. Figure <ref> shows histograms, characterizing the corresponding distributions. From left to right, it shows correlation according to Pearson's coefficient, Spearman's coefficient, and according to Theil's U. In particular for Pearson's and Spearman's coefficients, low values are more likely than higher ones. For all correlation metrics, we see a slightly bimodal distribution with increased probability for  maxima and minima.

§ COMPARING PREDICTION METHODS

Our goal is to predict data correlations, based on column names. In this section, we compare different prediction methods in terms of their training time (if any) and output quality. We focus on pre-trained language models, based on the recently proposed Transformer architecture <cit.>. Such models achieve state of the art performance in a variety of NLP tasks <cit.>. Next, we describe all compared prediction methods. Afterwards, we present corresponding results.

§.§ Description of Methods

We consider three pre-trained models. First, we consider Roberta <cit.>. Roberta (short for “Robustly Optimized BERT approach”) expands BERT <cit.>, another pre-trained language model that has achieved widespread popularity. Compared to BERT, Roberta is pre-trained using more data and for a longer period of time. The authors demonstrate that the resulting model outperforms the original BERT model on various benchmarks.

Albert (short for “A lite BERT architecture”) <cit.> reduces the number of parameters, compared to BERT and Roberta, significantly. It uses two parameter reduction techniques. First, it decomposes the vocabulary embedding matrix into two smaller matrices. Second, it shares parameters across different layers (thereby reducing parameter growth as a function of network depth). The authors demonstrate that this model achieves significant speedups without affecting result quality significantly.

Distilbert <cit.>, a “distilled” version of BERT, uses knowledge distillation to reduce parameters and training time. As suggested by the name, it uses knowledge distillation to reduce the network size, compared to BERT. Here, BERT serves as a “teacher” that trains a smaller network, Distilbert. The authors of Distilbert show significant speedups with very moderate loss in quality.

Beyond pre-trained models, we also compare against a simple baseline. This baseline decomposes names of the compared columns into tokens. Then, it computes the Jaccard similarity on the two token sets, associated with the compared columns. It predicts a correlation if the Jaccard similarity is at least 0.5. Hence, this baseline considers columns as correlated if their names are sufficiently similar.

§.§ Comparison Results

We compare the methods described in the last subsection. In particular, we verify three hypotheses on the relative performance of those methods.

Pre-trained language models predict correlations better than simpler baselines.

Larger models predict correlations more reliably than smaller models.

We can reduce training time significantly when switching to smaller, pre-trained language models.

For the following experiments, we use the Pearson correlation coefficient. We consider two columns as correlated if $|R|\geq 0.9$ with a p-value of at most 5%. We use 80% of numerical column pairs as training data (around 47K pairs) and test on the remaining 20%. We measure prediction quality according to various metrics. Also, we measure training time (for the baselines with training phase).

results/performance/methodscmp.csvBaseline, Albert, Distilbert, Roberta

Comparison of correlation prediction methods.

Figure <ref> compares prediction quality across the four prediction methods. The simple baseline performs quite well (even though not as good as the other methods) for precision and accuracy. Here, the baseline benefits as it predicts no correlation in most cases. As correlated column pairs are rare, this simple strategy can achieve a relatively high accuracy (which, among other things, motivates us to consider multiple quality metrics). The baseline predicts a correlation for columns with very similar names. It seems that such column pairs tend to be correlated indeed, explaining the reasonably high precision values. However, the simple baseline achieves only poor results for recall, F1 score, and the MCC metric. For instance, its recall is around 1% only. This demonstrates the need for a more sophisticated approach (thereby validating Hypothesis <ref>).

The performance of all three pre-trained models is quite similar. For the F1 score, precision, MCC, and recall, Roberta performs best, even though only by a small margin. This is expected as Roberta is the largest of the three models. For recall, Distilbert has a slight advantage. In general, Distilbert performs slightly better than Albert in our experiments. MCC is the metric with the largest gap between the three models. Here, Roberta gains a performance advantage of 4% over Albert. Altogether, the three models realize however comparable prediction performance (providing only weak evidence for Hypothesis <ref>).

[legend entries=Distilbert, Albert, Roberta, legend pos=outer north east, width=5cm, height=3cm, ybar=0pt, ymin=0, ymajorgrids, xtick=, ylabel=Time (minutes)]
coordinates (0,13);
coordinates (0,17);
coordinates (0,25);

Training time of different transformer variants.

Next, we consider training time. Figure <ref> shows training time (in minutes) for the three pre-trained models. Here, we report training time for specializing those models to the correlation prediction task (i.e., we do not report time for pre-training which is significantly more expensive).

Albert and Distilbert have been designed with the goal of reducing overheads, compared to larger models such as Roberta. Our results indicate that this approach pays off for our specific prediction task as well. For instance, training time is more than two times smaller for Distilbert, compared to Roberta. Given the slightly better performance of Distilbert, compared to Albert, this model seems like the best alternative to reduce training overheads. In the following, due to slightly higher precision, we will use Roberta as default method for correlation predictions.

+[discard if not=id1] table[col sep=comma, x expr=0, y=f1] results/methods/predcmp.csv;
+[discard if not=id2] table[col sep=comma, x expr=0, y=f1] results/methods/predcmp.csv;
+[discard if not=id3] table[col sep=comma, x expr=0, y=f1] results/methods/predcmp.csv;
+[discard if not=id4] table[col sep=comma, x expr=0, y=f1] results/methods/predcmp.csv;

[group style=group size=3 by 3, ylabels at=edge left, xlabels at=edge bottom, width=3cm, height=3.25cm, ymajorgrids, try min ticks=3, xlabel=Time (s), ylabel=Score, ylabel near ticks, legend entries=Albert, D-BERT, BERT, Roberta, legend columns=4, legend to name=dnnLegend]

[title=Theil's U, F1]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnTuF1.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnSmF1.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnTuF1.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnTuF1.csv;
[title=Theil's U, MCC]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnTuMcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnTuMcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnTuMcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnTuMcc.csv;
[title=Theil's U, Acc]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnTuAcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnTuAcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnTuAcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnTuAcc.csv;

[title=Pearson, F1]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnPsF1.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnPsF1.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnPsF1.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnPsF1.csv;
[title=Pearson, MCC]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnPsMcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnPsMcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnPsMcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnPsMcc.csv;
[title=Pearson, Acc]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnPsAcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnPsAcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnPsAcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnPsAcc.csv;

[title=Spearman, F1]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnSmF1.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnSmF1.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnSmF1.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnSmF1.csv;
[title=Spearman, MCC]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnSmMcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnSmMcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnSmMcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnSmMcc.csv;
[title=Spearman, Acc]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/dnns/DnnSmAcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/dnns/DnnSmAcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/dnns/DnnSmAcc.csv;
table[col sep=comma, x index=0, y index=22, ignore chars="] results/dnns/DnnSmAcc.csv;

Comparison of correlation prediction methods.

Metric     Roberta     D-BERT     Albert     Baseline

F1 Score      77%     78%     75%     2%

Recall     85%     86%     87%     1%

Precision     70%     71%     65%     77%

MCC     64%     66%     61%     6%

Accuracy     83%     84%     81%     67%

§ SCENARIO VARIANTS

We analyze which scenario properties influence prediction performance. We consider variations in the amount of training data and in the relationship between training and test data. Also, we compare performance for different definitions of correlation. More precisely, we conduct experiments to analyze the following hypotheses.

Correlation predictions become more accurate when training on more column pairs.

Predicting correlations for new column pairs becomes easier after observing correlations from other column pairs in the same data set.

Predicting strong correlations is easier than predicting weak correlations.

For the following experiments, we use the Roberta model. We define correlation via the Pearson coefficient, using a maximal p-Value of 5%. We vary the thresholds on the absolute value of $R$ in the following, using a default of $|R|\geq0.9$. We vary the quantity of training data, using 80% of numerical column pairs as default. We use the remaining data for testing.

results/performance/tquantcmp.csv80% Training Data, 20% Training Data

Impact of training data quantity.

First, we analyze Hypothesis <ref>. Figure <ref> shows corresponding results. We compare prediction performance as a function of the training (and test) ratio. We compare performance in two scenarios. In the first scenario, we use 80% of column pairs as training data (i.e., around 47K column pairs) and the rest for testing. In the second scenario, we use 20% of column pairs as training data while using the rest for testing. For all five metrics of prediction quality, as expected, having more training data helps. This validates Hypothesis <ref>.

However, given the significant difference in the amount of training data (the amount of training data differs by a factor of four across the two scenarios), the differences in prediction performance seem moderate. The maximal difference across all five performance metrics is six percent. This is consistent with prior results for other tasks from the NLP domain, showing that pre-trained language models achieve reasonable performance, already with modest amounts of training data <cit.>.

results/performance/tqualicmp.csvSeparate by Data Set, Separate by Column Pair

Impact of training data quality.

Next, we analyze the impact of the relationship between training and test data on prediction performance (Hypothesis <ref>). We consider two scenarios. In the first scenario, we separate training and test data at the granularity of column pairs. This means that training and test data may contain column pairs from the same data set. Of course, we consider each column pair only once (i.e., we never use the same column pair in training and test data, independently of the column order). In the second scenario, we ensure that training and test data are derived from different data sets. This means that we separate data sets (the ones used for correlation analysis) into training and test data sets. Then, we derive column pairs for training and testing only from the corresponding data sets. With this method, training and test samples derive from entirely different data sets.

Figure <ref> shows corresponding results. Here, we vary the quality (i.e., how closely it relates to the test examples) but not the quantity of training data. For all five quality metrics, allowing column pairs from the same data set in training and testing improves performance. Depending on the metric, this increase is moderate (recall increase by only 2%) or more significant (precision increases by 14%). In any case, the results support Hypothesis <ref>.

results/performance/strongcmp.csv$|R|\geq0.8$, $|R|\geq0.9$, $|R|\geq0.95$, $|R|\geq0.99$

Comparing prediction quality for different degrees of correlation.

Finally, we analyze Hypothesis <ref>. This hypothesis connects the criterion for defining correlation to prediction performance. We use a p-Value threshold of 5% but vary the threshold on $|R|$ between $0.8$ and $0.99$. Figure <ref> shows corresponding results. The results do not show clear tendencies. Recall generally increases while precision and F1 scores decrease, as the requirements for correlation become tighter. Accuracy and MCC do not show clear tendencies. Altogether, the experimental results do not provide strong evidence for Hypothesis <ref>.

Impact of training data quality: are training and test column pairs taken from overlapping data sets (DS)?

Metric     Overlapping DS     Non-Overlapping DS

F1 Score     77%     72%

Recall     85%     82%

Precision     70%     65%

MCC     64%     57%

Accuracy     83%     79%

Training tables use, by default, Roberta, 0.2 test data, minv1=0.5, maxv2=0.05, pearson, defsep

Impact of training data quantity.

Metric     4/5 Test     1/5 Test

F1 Score     73%     77%

Recall     83%     85%

Precision     66%     70%

MCC     58%     64%

Accuracy     80%     83%

Impact of threshold for R.

Metric     R=0.25     R=0.5     R=0.75

F1 Score     81     77     73

Recall     84     85     85

Precision     77     70     64

MCC     63     65     64

Accuracy     81     83     85

Impact of threshold for p value.

Metric     $p\leq 0.05$     $p\leq 1$

F1 Score     77     77

Recall     85     85

Precision     70     70

MCC     64     65

Accuracy     83     83

§ RESULT BREAKDOWNS

We analyze which properties of test cases contribute to making correlations more or less difficult to predict. We use column names as features. Hence, we break down results based on properties of column names. More specifically, we test the following two hypotheses.

Longer column names yield more information and make prediction more accurate.

Column names with a higher ratio of English words (as opposed to abbreviations or other symbols) can be more easily interpreted and make predictions more accurate.

results/performance/nrchars.csvQ0-25%, Q25-50%, Q50-100%

Impact of column name length.

results/performance/nrtokens.csvQ0-25%, Q25-50%, Q50-100%

Impact of number of words in column names.

The following experiments use the Roberta model and the Pearson correlation coefficient. We consider columns correlated for an absolute R-value of at least $0.9$ and a p-Value of at most 5%.

To test the first hypothesis, we use two metrics for column name length. We consider the number of characters as well as the number of tokens (i.e., the number of text snippets, separated by spaces and underscores). Figure <ref> reports results for the number of characters and Figure <ref> results for the number of tokens. Both figures report results for three length ranges separately. Those ranges refer to the quantiles (e.g., the range “Q50-100%” includes pairs of columns whose length is at or above average length).

The differences are significant. For both column name metrics and all five prediction quality metrics, having longer column names improves performance. Those differences are more pronounced when measuring length as the number of characters (compared to the number of words). For instance, when measuring length as the number of characters, the MCC score improves from 42% to 83% when going from short to long names. Precision improves from 45% to 81%. Those results provide strong experimental evidence validating Hypothesis <ref>.

results/performance/wordratio.csvQ0-25%, Q25-50%, Q50-100%

Impact of ratio of English words in column names.

Next, we analyze Hypothesis <ref>. Figure <ref> reports results for subsets of column pairs, characterized by the ratio of English words in column names. We measure that ratio as follows. First, we divide both column names into tokens, using common separators. Then, we check for each token whether it appears in an English dictionary. The ratio of words, contained in the dictionary, to the number of all tokens is the word ratio. For Figure <ref>, we separate column pairs into three groups, associated with different ranges for that ratio (e.g., “Q50-100%” includes column pairs whose ratio of English words is at or above the average).

Here, the absolute differences between low and high word ratios are relatively small. For instance, MCC scores increase only from 60% to 65%, moving from low to high ratios. Recall, for instance, decreases slightly from 88% to 87%. Altogether, the experimental evidence for Hypothesis <ref> is weak.

Impact of column name length.

Metric     [0,0.25]     [0.25,0.5]     [0.5,1]

F1 Score     65     71     85

Recall     83     83     89

Precision     54     62     82

MCC     39     55     78

Accuracy     67     78     90

Impact of number of tokens in column names.

Metric     [0,0.25]     [0.25,0.5]     [0.5,1]

F1 Score     72     72     77

Recall     83     83     85

Precision     64     64     70

MCC     60     60     64

Accuracy     82     82     83

Impact of word ratio in column names.

Metric     [0,0.25]     [0.25,0.5]     [0.5,1]

F1 Score     75     75     77

Recall     86     86     85

Precision     66     66     70

MCC     59     59     64

Accuracy     79     79     83

§ OTHER CORRELATION METRICS

So far, we have focused on the Pearson coefficient, a popular correlation metric. In the following, we perform experiments with different correlation coefficients to see whether our findings generalize. We consider Spearman's coefficient and Theil's U (discussed in more detail in Section <ref>). Unless noted otherwise, we consider columns correlated, according to Spearman's coefficient, if the absolute coefficient value is at or above 0.9 ($|\rho|\geq0.9$) with a p-value of at most 5%. For Theil's U, we use a threshold of 0.9 as well. By default, we use again 80% of column pairs as training data and separate training from test data at the granularity of column pairs. Note that we can apply Theil's U for all column data types, thereby increasing the number of eligible column pairs (for training and testing) to around 119,000. We use the Roberta model for all experiments in this section.

results/performance/metricscmp.csvPearson, Spearman, Theil's U

Comparison of different correlation measures.

Figure <ref> compares prediction performance for all three definitions of correlation. While prediction performance is close for Pearson and Spearman coefficients, prediction performance increases for Theil's U according to all quality metrics. A first hypothesis is that the higher amount of training data (columns of all types as opposed to numerical columns only) contributes to that performance.

results/performance/sptquantcmp.csv80% Training Data, 20% Training Data

Impact of training data quantity when predicting correlation according to Spearman's coefficient.

results/performance/sptqualicmp.csvSeparate by Data Set, Separate by Column Pair

Impact of training data quality when predicting correlation according to Spearman's coefficient.

results/performance/spstrongcmp.csv$|\rho|\geq0.8$, $|\rho|\geq0.9$, $|\rho|\geq0.95$, $|\rho|\geq 0.99$

Comparing prediction quality for different degrees of correlation, measured via Spearman's coefficient.

Figures <ref> to <ref> re-test the hypotheses from Section <ref> for Spearman's coefficient. We observe again a slight increase in performance if more training data (Hypothesis <ref>) is provided and if training data relates more closely to test cases (Hypothesis <ref>). The tendencies are less clear for the threshold on $\rho$ (Hypothesis <ref>).

results/performance/spnrchars.csvQ0-25%, Q25-50%, Q50-100%

Impact of column name length when predicting correlation according to Spearman's coefficient.

results/performance/spnrtokens.csvQ0-25%, Q25-50%, Q50-100%

Impact of number of words in column names when predicting correlation according to Spearman's coefficient.

results/performance/spwordratio.csvQ0-25%, Q25-50%, Q50-100%

Impact of ratio of English words in column names when predicting correlation according to Spearman's coefficient.

Figures <ref> to <ref> validate the hypotheses from Section <ref> for Spearman's coefficient. Here, we consider different data subsets and compare prediction performance. Again, the most important parameter influencing prediction performance seems to be the column name length (Hypothesis <ref>).

results/performance/tutquantcmp.csv80% Training Data, 20% Training Data

Impact of training data quantity when predicting correlation according to Theil's U.

results/performance/tutqualicmp.csvSeparate by Data Set, Separate by Column Pair

Impact of training data quality when predicting correlation according to Theil's U.

results/performance/tustrongcmp.csv$U\geq0.8$, $U\geq0.9$

Comparing prediction quality for different degrees of correlation, measured via Theil's U.

Figures <ref> to <ref> compare different prediction scenarios for Theil's U. Here, the relative tendencies are similar to prior experiments while the absolute values are significantly better. It is interesting that prediction quality for Theil's U when using 20% training data (i.e., around 24K training samples) is still better than prediction performance for the other coefficients when using 80% training data (i.e., around 47K training samples). This shows that, beyond the amount of training data, other factors must contribute to the improved performance. We plan to analyze those factors in future work.

results/performance/tunrchars.csvQ0-25%, Q25-50%, Q50-100%

Impact of column name length when predicting correlation according to Theil's U.

results/performance/tunrtokens.csvQ0-25%, Q25-50%, Q50-100%

Impact of number of words in column names when predicting correlation according to Theil's U.

results/performance/tuwordratio.csvQ0-25%, Q25-50%, Q50-100%

Impact of ratio of English words in column names when predicting correlation according to Theil's U.

Figures <ref> to <ref> study prediction performance for Theil's U and different data subsets. While column name length remains the most important factor, we also observe a clearer tendency relating a higher ratio of English words in column names to better prediction accuracy (except for the precision metric). Despite of that, the absolute differences remain relatively small.

Altogether, we find that the primary outcomes of our prior experiments generalize to other definitions of correlation. This provides evidence for the potential of NLP-based correlation prediction methods in a variety of scenarios.

[group style=group size=3 by 2, ylabels at=edge left, xlabels at=edge bottom, width=3cm, height=3.25cm, ymajorgrids, try min ticks=3, xlabel=Time (s), ylabel=Score, ylabel near ticks, legend entries=Theil's U, Spearman, Pearson, legend columns=3, legend to name=metricsLegend]

[title=F1 Score]
table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metF1.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metF1.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metF1.csv;
table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metPre.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metPre.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metPre.csv;
table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metRec.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metRec.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metRec.csv;

table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metMcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metMcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metMcc.csv;
table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metAcc.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metAcc.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metAcc.csv;
table[col sep=comma, x index=0, y index=4, ignore chars="] results/metrics/metLoss.csv;
table[col sep=comma, x index=0, y index=10, ignore chars="] results/metrics/metLoss.csv;
table[col sep=comma, x index=0, y index=16, ignore chars="] results/metrics/metLoss.csv;

Predictions of column relationships based on column names for fresh data set (excluded from training).

Metric     Theil's U     Spearman     Pearson

F1 Score     84%     72%     77%

Recall     84%     82%     84%

Precision     84%     65%     64%

MCC     64%     54%     57%

Accuracy     82%     77%     79%

§ IMPLICATIONS AND OUTLOOK

Predicting correlations without expensive data analysis is useful in various scenarios. In the following, we connect our results to application scenarios around database tuning. Section <ref> discusses a corresponding use case. Also, in Section <ref>, we discuss extensions of the prediction methods used in the experiments presented so far.

§.§ Use Case in Database Tuning

We predict correlations based on column names. The resulting correlations are less interesting from the perspective of data exploration. If correlations can be predicted from column names alone, they relate to commonsense knowledge and do not yield new and interesting insights about specific data sets. However, in the introduction, we have partially motivated our experiments with use cases around database tuning. In this section, we make those motivations more concrete by sketching out a use case for correlation prediction in the context of query optimization. Note that specifying or evaluating a corresponding solution in detail is beyond the scope of this publication. Merely, we want to elaborate on our initial references to potential use cases.

component=[fill=blue!10, rectangle, draw=black, font=]
dataflow=[->, ultra thick]

[io] (data) at (-2,0) Data;
[io] (schema) at (2,0) Schema;
[component] (danalysis) at (-2,-1) Data Analysis;
[component] (sanalysis) at (2,-1) NLP Analysis;
[component] (model) at (0,-2) Cost and Cardinality Model;
[component] (optimizer) at (0,-3) Query Optimizer;
[io] (query) at (-3,-3) Query;
[io] (plan) at (3,-3) Plan;
[dataflow] (data) – (danalysis);
[dataflow] (schema) – (sanalysis);
[dataflow] (danalysis) – (model);
[dataflow] (sanalysis) – (model);
[dataflow] (model) – (optimizer);
[dataflow] (query) – (optimizer);
[dataflow] (optimizer) – (plan);

Sketch of NLP-enhanced query optimizer.

Figure <ref> sketches out a system that uses NLP-based correlation prediction for query optimization. A query optimizer generally tries to map a query to a near-optimal query plan. To do so, it must estimate processing costs for plan candidates. Processing cost depends however on the cardinality of intermediate results. Data correlations can throw off estimation which, at least according to standard models <cit.>, assumes uniform data and independent query predicates <cit.>.

NLP-based correlation prediction could become one additional source of information in cost estimation. For instance, it could be used to target efforts in collecting data statistics. Instead of collecting statistics on all possible column pairs, collection could focus on column pairs that are likely correlated, based on their column names. According to our results, a corresponding approach would not find all but most of the correlated column pairs (while significantly reducing analysis overheads). Our results indicate that integrating initial correlation results, obtained while analyzing a specific data set, could improve further predictions on that data further (Hypothesis <ref>). Here, NLP-backed correlation prediction may help to lower overheads in collecting statistics used by more traditional cost models. This can make query optimization more reliable.

Recent work explores the use of machine learning for cost and cardinality estimation in the context of query optimization <cit.>. In that context, NLP-based correlation prediction could serve as an additional input feature. Especially for new data sets, for which few queries have been processed so far, it could serve for initialization until more training data has been observed. We plan to explore corresponding approaches in our future work.

The systems outlined above only serve as an illustration, showing at a high level of abstraction how correlation prediction can become useful for database tuning. The applicability of NLP-based correlation predication is however not restricted to those use cases. Next, we discuss several extensions to the prediction methods used so far.

§.§ Extensions

The prediction methods evaluated in the previous sections use only column names as features. While already informative, we see several possibilities to expand the scope of input features further. A first possibility is to use the name of the data set or any text associated with the data. Many data sets, e.g. on Kaggle, come with so called “data dictionaries”. Those dictionaries explain semantics of columns in more detail, typically using one or multiple paragraphs of text. Clearly, this text often yields information beyond what can be inferred from column names alone. However, trying to exploit such text via NLP leads to new challenges. It is still difficult to accurately interpret longer text documents, even though significant progress has been made recently <cit.>. We plan to evaluate some of those recently proposed methods on data-related text documents, as opposed to short column names, in our future work.

Up until now, we have treated correlation prediction as a binary classification problem (i.e., we classify column pairs into correlated and non-correlated pairs). This requires setting thresholds defining which degree of correlation qualifies. Alternatively, we can model correlation prediction as a regression problem. E.g., instead of predicting whether the $R$ value of specific columns exceeds a threshold, we can try to predict $R$ directly. We plan to explore this option in future work.

The aforementioned extensions change the problem model. Beyond that, there are several optimizations of the current approach that we have not yet exploited. For instance, our approach uses raw column names as input, only replacing underscores by spaces. There are other methods that are often used to construct column names from words. For instance, we observed several cases of “camel caps” notation. Resolving such cases in a pre-processing step could yield further performance improvements.

§ CONCLUSION

Detecting data correlations is useful for various applications. Prior work analyzes data or data samples to identify correlations. In this work, we test a complementary method. We try to predict correlations, not based on data but based on column names instead.

While perfect correlation predictions seems illusory, we find that prediction is possible with relatively high accuracy in many scenarios. For instance, for Pearson correlation and column names with a length above average, we find an F1 score of up to 85% and an accuracy of up to 95% (an F1 score of 71% and accuracy of 87% in general). For predicting correlation according to Theil's U, we even obtain an F1 score of 92% for long column names (and 89% for the general case). This means that correlation prediction can be useful at least for a subset of schema elements that are easy to recognize.

We tried different prediction methods. While naive baselines fail, we found that several pre-trained models achieve good prediction performance. We use a relatively large model, Roberta, for most of our experiments. However, we show that other models reduce training time significantly with moderate precision loss. Here, we tried in particular the Albert and Distilbert model which use less parameters, compared to Roberta, and reduce training time by more than 50%.

We sketch out a use case for NLP-based correlation prediction in the context of database optimization. Here, NLP-based predictions can help to prioritize statistics collection or serve as input features for learning-based cost estimation. In future work, we plan to explore more use cases for NLP-based features in database tuning and to expand the scope of the evaluated techniques.

§ RESULTS FOR ALL COLUMN PAIRS

In the main part of the paper, we present an extract of our experimental results. In this appendix, we provide additional results, corroborating our findings. In this section, we present average results for the Pearson correlation coefficient and for all numerical column pairs. In the next section, we present results specifically for column names that have at least average length.

In the following, we present results for Pearson correlation. Generally, we require a p-value of at most 5% to consider a correlation statistically significant. The experiments reported in the following vary the prediction method (using the three pre-trained models described in Section <ref>). Also, we vary the definition of correlation by setting different thresholds for $|R|$, ranging from 0.8 to 0.99. Furthermore, we vary the amount of training data used. The following three tables (Tables <ref> to <ref>) report results when separating training from test data at the granularity of single column pairs.

In this and the following tables, the first column ($|R|$) reports the minimal threshold on the Pearson correlation coefficient $|R|$. The second column denotes the ratio of data used for testing, as opposed to training (i.e., “0.2” means that 20% of data were used for testing while the other 80% were used for training). The following columns denote the prediction quality metrics introduced in Section <ref> (i.e., the F1 score, recall, precision, accuracy, and MCC, in that order). Each of the following tables reports results for one of the three pre-trained models.

Correlation prediction quality for column pair separation and the Roberta transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     72     86     62     86     64
0.8     0.8     68     84     57     83     59
0.9     0.2     71     87     61     87     65
0.9     0.8     67     84     56     85     60
0.95     0.2     68     91     54     86     63
0.95     0.8     65     87     52     85     59
0.99     0.2     65     93     50     87     62
0.99     0.8     62     89     48     86     58

Correlation prediction quality for column pair separation and the Albert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     70     81     61     85     61
0.8     0.8     67     76     60     84     57
0.9     0.2     68     86     57     85     61
0.9     0.8     58     66     52     82     48
0.95     0.2     67     88     54     86     61
0.95     0.8     66     78     57     87     59
0.99     0.2     64     91     50     87     61
0.99     0.8     62     87     49     86     58

Correlation prediction quality for column pair separation and the Distilbert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     72     86     62     85     64
0.8     0.8     69     81     61     84     60
0.9     0.2     71     87     60     87     65
0.9     0.8     68     83     57     85     60
0.95     0.2     68     90     55     86     63
0.95     0.8     65     87     51     84     58
0.99     0.2     65     93     50     87     62
0.99     0.8     62     88     48     86     58

The results are mostly consistent with the hypotheses established in the main part of the paper. As a general rule, using more training data increases accuracy (Hypothesis <ref>) by a few percentage points for most metrics. Again, tendencies are less clear for the threshold on the Pearson coefficient. The F1 scores typically decrease once the definition of correlation becomes more restrictive. This is mostly driven by a decrease in precision while recall even increases in several cases. On the other side, accuracy remains quite stable and even increases in some cases, as the number of correlated columns shrinks.

Comparing the three models, we find Roberta to be the most accurate one in most cases. The other models are close in terms of accuracy with few exceptions. For instance, Albert shows a relatively large gap of 9% for F1 scores, considering the condition $|R|\geq 0.9$ and a test ratio of 80%. Distilbert performs generally well with a precision loss of few percentage points at most, compared to Roberta. In some cases, Distilbert performs even slightly better (e.g., $|R|\geq0.8$ with 80% test ratio), cementing its status as a valid alternative to Roberta for our prediction problem.

The following three tables (Table <ref> to <ref>) report results for the scenario we considered in Section <ref>. Here, we separate training and test data not at the granularity of column pairs. Instead, we separate them at the granularity of data sets. The following three tables report results for the three models (the semantics of all columns is the same as in the previous tables).

Correlation prediction quality for data set separation and the Roberta transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     66     82     55     82     56
0.8     0.8     61     79     50     78     49
0.9     0.2     60     85     47     81     53
0.9     0.8     59     79     48     80     50
0.95     0.2     59     87     44     82     53
0.95     0.8     59     80     46     82     51
0.99     0.2     55     89     40     83     52
0.99     0.8     56     87     41     81     51

Correlation prediction quality for data set separation and the Albert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     64     76     54     82     53
0.8     0.8     59     73     49     77     46
0.9     0.2     62     80     51     84     54
0.9     0.8     59     72     49     81     48
0.95     0.2     57     83     44     82     51
0.95     0.8     58     76     47     82     50
0.99     0.2     55     85     41     84     52
0.99     0.8     56     84     42     83     51

Correlation prediction quality for data set separation and the Distilbert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     66     81     55     83     56
0.8     0.8     61     76     51     78     48
0.9     0.2     63     82     51     84     55
0.9     0.8     60     77     49     81     50
0.95     0.2     59     87     44     82     53
0.95     0.8     59     81     46     81     51
0.99     0.2     56     89     41     83     53
0.99     0.8     56     84     42     82     51

For all models and metrics, accuracy decreases, compared to the previous partitioning methods. The relative ranking across models remains similar. All models benefit again from additional training data.

§ RESULTS FOR LONG COLUMNS NAMES

Long column names contain more information that can be exploited for correlation prediction. In this section, we report results only for those column pairs with a length above average (measured as the number of characters). The following three tables (Table <ref> to Table <ref>) report results for each of the three models. The column semantics was introduced in the previous section.

Correlation prediction quality for long column names, column pair separation and the Roberta transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     83     88     79     93     79
0.8     0.8     77     85     70     89     71
0.9     0.2     85     90     81     95     83
0.9     0.8     77     84     71     92     72
0.95     0.2     85     90     81     96     83
0.95     0.8     76     87     68     93     73
0.99     0.2     85     93     77     97     83
0.99     0.8     77     88     69     95     75

Correlation prediction quality for long column names, column pair separation and the Albert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     82     86     78     92     77
0.8     0.8     77     78     75     90     71
0.9     0.2     84     89     81     95     81
0.9     0.8     65     64     66     89     58
0.95     0.2     85     89     81     96     82
0.95     0.8     78     79     77     94     74
0.99     0.2     84     91     78     96     82
0.99     0.8     79     85     73     95     76

Correlation prediction quality for long column names, column pair separation and the Distilbert transformer ($p\leq 0.05$).

$\mathbf{|R|}$     Test     F1     Rec     Pre     Acc     MCC

0.8     0.2     83     87     79     93     79
0.8     0.8     78     81     76     91     73
0.9     0.2     85     90     80     95     82
0.9     0.8     79     82     76     93     75
0.95     0.2     86     90     82     96     84
0.95     0.8     79     83     75     94     75
0.99     0.2     85     93     77     97     83
0.99     0.8     78     87     71     95     76

Clearly, having longer column names improves prediction performance, compared to the general case (i.e., Tables <ref> to <ref>). On the other side, the relative tendencies (between models and for different amounts of training data) remain the same as before.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Androutsopoulos, Ritchie, and
ThanischAndroutsopoulos et al1995]
authorpersonI. Androutsopoulos, personG. D.
Ritchie, and personP. Thanisch.
Natural language interfaces to databases - an
journalJournal of Natural Language Engineering
volume1, number1 (year1995),

[arxiv]9503016 [cmp-lg]

[Asgharzadeh Talebi, Chirkova, and
FathiAsgharzadeh Talebi et al2013]
authorpersonZohreh Asgharzadeh Talebi,
personRada Chirkova, and personYahya Fathi.
An integer programming approach for the view and
index selection problem.
journalDKE  volume83
(year2013), pages111–125.

[Beltagy, Peters, and CohanBeltagy
et al2020]
authorpersonIz Beltagy, personMatthew E.
Peters, and personArman Cohan.
Longformer: The Long-Document Transformer.
journalarXiv (year2020).

[Brown and HassBrown and Hass2003]
authorpersonPG Brown and personPJ Hass.
BHUNT: Automatic discovery of fuzzy algebraic
constraints in relational data. In booktitleVLDB.

[Bruno, Bruno, Chaudhuri, and ChaudhuriBruno
et al2004]
authorpersonN Bruno, personN Bruno,
personS Chaudhuri, and personS Chaudhuri.
Conditional selectivity for statistics on query
expressions. In booktitleSIGMOD.

[Caprara, Maio, and FischettiCaprara
et al1995]
authorpersonAlberto Caprara, personDario
Maio, and personMatteo Fischetti.
Exact and Approximate Algorithms for the Index
Selection Problem in Physical Database Design.
journalIEEE Transactions on Knowledge and Data
Engineering volume7, number6
(year1995), pages955–967.

[Chicco and JurmanChicco and Jurman2020]
authorpersonDavide Chicco and
personGiuseppe Jurman. year2020.
The advantages of the Matthews correlation
coefficient (MCC) over F1 score and accuracy in binary classification
journalBMC Genomics volume21,
number1 (year2020), pages1–13.

[Devlin, Chang, Lee, and ToutanovaDevlin
et al2019]
authorpersonJacob Devlin, personMing Wei
Chang, personKenton Lee, and personKristina
Toutanova. year2019.
BERT: Pre-training of deep bidirectional
transformers for language understanding. In
booktitleNAACL, Vol. volume1.

[Gubichev, Boncz, Kemper, and NeumannGubichev
et al2015]
authorpersonAndrey Gubichev, personPeter
Boncz, personAlfons Kemper, and personThomas
Neumann. year2015.
How good are query optimizers, really?
journalPVLDB volume9,
number3 (year2015), pages204–215.

[Gupta, Harinarayan, Rajaraman, and
UllmanGupta et al1997]
authorpersonHimanshu Gupta, personVenky
Harinarayan, personAnand Rajaraman, and
personJeffrey D Ullman. year1997.
Index selection for OLAP. In
booktitleICDE. pages208–219.

[Hoeffding and KendallHoeffding and
authorpersonWassily Hoeffding and
personM. G. Kendall. year1957.
Rank Correlation Methods.
journalEconometrica volume25,
number1 (year1957), pages181.

[Howard and RuderHoward and Ruder2018]
authorpersonJeremy Howard and
personSebastian Ruder. year2018.
Universal Language Model Fine-tuning for Text
Classification. In booktitleACL.

[Hwang, Yim, Park, and SeoHwang
et al2019]
authorpersonWonseok Hwang, personJingyeung
Yim, personSeunghyun Park, and personMinjoon Seo.
title(SQLNova) A Comprehensive Exploration on WikiSQL
with Table-Aware Word Contextualization.

[Ilyas, Markl, Haas, Brown, and
AboulnagaIlyas et al2004]
authorpersonI F Ilyas, personV Markl,
personP Haas, personP Brown, and
personAshraf Aboulnaga. year2004.
CORDS: Automatic discovery of correlations and
soft functional dependencies. In booktitleSIGMOD.

[arxiv]ISBN 0-89791-128-8

[Kipf, Kipf, Radke, Leis, Boncz, and
KemperKipf et al2018]
authorpersonAndreas Kipf, personThomas
Kipf, personBernhard Radke, personViktor Leis,
personPeter Boncz, and personAlfons Kemper.
Learned cardinalities: estimating correlated joins
with deep learning. In booktitleCIDR.

[Lan, Chen, Goodman, Gimpel, Sharma, and
SoricutLan et al2019]
authorpersonZhenzhong Lan, personMingda
Chen, personSebastian Goodman, personKevin Gimpel,
personPiyush Sharma, and personRadu Soricut.
Albert: A lite bert for self-supervised learning
of language representations.
journalarXiv (year2019),

[Li and JagadishLi and Jagadish2014]
authorpersonFei Li and personHV
Jagadish. year2014.
NaLIR: an interactive natural language interface
for querying relational databases.
journalSIGMOD (year2014),

[Li and JagadishLi and Jagadish2016]
authorpersonFei Li and personHV
Jagadish. year2016.
Understanding natural language queries over
relational databases.
journalSIGMOD Record volume45,
number1 (year2016), pages6–13.

[Liu, Ott, Goyal, Du, Joshi, Chen, Levy, Lewis,
Zettlemoyer, and StoyanovLiu et al2019]
authorpersonYinhan Liu, personMyle Ott,
personNaman Goyal, personJingfei Du,
personMandar Joshi, personDanqi Chen,
personOmer Levy, personMike Lewis,
personLuke Zettlemoyer, and personVeselin
Stoyanov. year2019.
RoBERTa: A robustly optimized BERT pretraining
journalarXiv number1

[Marcus, Negi, Mao, Zhang, Alizadeh, Kraska,
Papaemmanouil, and TatbulMarcus et al2018]
authorpersonRyan Marcus, personParimarjan
Negi, personHongzi Mao, personChi Zhang,
personMohammad Alizadeh, personTim Kraska,
personOlga Papaemmanouil, and personNesime Tatbul.
Neo: A Learned query optimizer.
journalPVLDB volume12,
number11 (year2018), pages1705–1718.

[Markl, Haas, Kutsch, Megiddo, Srivastava, and
TranMarkl et al2007]
authorpersonV. Markl, personP. J. Haas,
personM. Kutsch, personN. Megiddo,
personU. Srivastava, and personT. M. Tran.
Consistent selectivity estimation via maximum
journalVLDB Journal volume16,
number1 (year2007), pages55–76.

[Mistry, Roy, Ramamritham, and
SudarshanMistry et al2000]
authorpersonHoshi Mistry, personPrasan Roy,
personKrithi Ramamritham, and personS. Sudarshan.
Materialized view selection and maintenance using
multi-query optimization.
journalSIGMOD Record volume30,
number2 (year2000), pages307–318.

[arxiv]0003006 [cs]

[Nehme and BrunoNehme and Bruno2011]
authorpersonRimma Nehme and personNicolas
Bruno. year2011.
Automated partitioning design in parallel database
systems. In booktitleSIGMOD.

<https://doi.org/doi: 10.1145/1989323.1989444>

[Park, Zhong, and MozafariPark
et al2020]
authorpersonYongjoo Park, personShucheng
Zhong, and personBarzan Mozafari.
QuickSel: Quick Selectivity Learning with Mixture
Models. In booktitleSIGMOD. pages1017–1033.

authorpersonSage Publications.
Theil ' s Forecast Accuracy Coefficient :
volume10, number4 (year2018),

[Saha, Floratou, Sankaranarayanan, Minhas,
Mittal, and OzcanSaha et al2016]
authorpersonDiptikalyan Saha, personAvrilia
Floratou, personKarthik Sankaranarayanan,
personUmar Farooq Minhas, personAshish R Mittal,
and personFatma Ozcan. year2016.
ATHENA: An ontology-driven system for natural
language querying over relational data stores.
journalVLDB volume9,
number12 (year2016), pages1209–1220.

[Sanh, Debut, Chaumond, and WolfSanh
et al2019]
authorpersonVictor Sanh, personLysandre
Debut, personJulien Chaumond, and personThomas
Wolf. year2019.
DistilBERT, a distilled version of BERT: Smaller,
faster, cheaper and lighter.
journalarXiv (year2019),

[Selinger, Astrahan, Chamberlin, Lorie, and
PriceSelinger et al1979]
authorpersonPG G Selinger, personMM M
Astrahan, personD D Chamberlin, personR A Lorie,
and personT G Price. year1979.
Access path selection in a relational database
management system. In booktitleSIGMOD.

[Sen, Lei, Quamar, Özcan, Efthymiou,
Dalmia, Stager, Mittal, Saha, and SankaranarayananSen
et al2020]
authorpersonJaydeep Sen, personChuan Lei,
personAbdul Quamar, personFatma Özcan,
personVasilis Efthymiou, personAyushi Dalmia,
personGreg Stager, personAshish Mittal,
personDiptikalyan Saha, and personKarthik
Sankaranarayanan. year2020.
ATHENA++: natural language querying for complex
nested SQL queries.
journalProceedings of the VLDB Endowment
volume13, number12 (year2020),

[Sun and LiSun and Li2020]
authorpersonJi Sun and personGuoliang
Li. year2020.
An end-to-end learning-based cost estimator. In
booktitleVLDBJ, Vol. volume13.

[Taft, Mansour, Serafini, Duggan, Elmore,
Aboulnaga, Pavlo, and StonebrakerTaft et al2014]
authorpersonRebecca Taft, personEssam
Mansour, personMarco Serafini, personJennie Duggan,
personAaron J Elmore, personAshraf Aboulnaga,
personAndrew Pavlo, and personMichael Stonebraker.
E-Store: fine-grained elastic partitioning for
distributed transaction processing systems.
journalVLDB volume8,
number3 (year2014), pages245–256.

authorpersonImmanuel Trummer.
The case for NLP-enhanced database tuning: towards
tuning tools that “read the manual”. In

[Tzoumas, Dehspande, and JensenTzoumas
et al2011]
authorpersonKostas Tzoumas, personAmol
Dehspande, and personChristian S Jensen.
Lightweight graphical models for selectivity
estimation without independence assumptions. In
booktitleVLDB. pages852–863.

[Valentin, Zuliani, Zilio, Lohman, and
SkelleyValentin et al2000]
authorpersonGary Valentin, personM.
Zuliani, personDaniel C. Zilio, personGuy M Lohman,
and personAlan Skelley. year2000.
DB2 advisor: An optimizer smart enough to
recommend its own indexes. In booktitleICDE.

[Vaswani, Shazeer, Parmar, Uszkoreit, Jones,
Gomez, Kaiser, and PolosukhinVaswani et al2017]
authorpersonAshish Vaswani, personNoam
Shazeer, personNiki Parmar, personJakob Uszkoreit,
personLlion Jones, personAidan N. Gomez,
personŁukasz Kaiser, and personIllia
Polosukhin. year2017.
Attention is all you need.
journalAdvances in Neural Information Processing
Systems volume2017-Decem, numberNips
(year2017), pages5999–6009.

authorpersonJiguang Wang.
Pearson Correlation Coefficient.
journalEncyclopedia of Systems Biology
volume2 (year2013), pages1671–1671.

[Woltmann, Hartmann, Thiele, and
HabichWoltmann et al2019]
authorpersonLucas Woltmann, personClaudio
Hartmann, personMaik Thiele, and personDirk
Habich. year2019.
Cardinality estimation with local deep learning
models. In booktitleaiDM.

[Xu, Liu, and SongXu et al2017]
authorpersonXiaojun Xu, personChang Liu,
and personDawn Song. year2017.
SQLNet: generating structured queries from natural
language without reinforcement Learning. pages1–13.

[Yang, Zhang, Li, Bendersky, and NajorkYang
et al2020]
authorpersonLiu Yang, personMingyang Zhang,
personCheng Li, personMichael Bendersky, and
personMarc Najork. year2020.
Beyond 512 Tokens: Siamese Multi-depth
Transformer-based Hierarchical Encoder for Long-Form Document Matching.
journalInternational Conference on Information and
Knowledge Management, Proceedings (year2020),

[Zaheer, Guruganesh, Dubey, Ainslie, Alberti,
Ontanon, Pham, Ravula, Wang, Yang, and AhmedZaheer et al2020]
authorpersonManzil Zaheer, personGuru
Guruganesh, personAvinava Dubey, personJoshua
Ainslie, personChris Alberti, personSantiago
Ontanon, personPhilip Pham, personAnirudh Ravula,
personQifan Wang, personLi Yang, and
personAmr Ahmed. year2020.
Big Bird: Transformers for Longer Sequences.
journalarXiv (year2020),

[Zhong, Xiong, and SocherZhong
et al2017]
authorpersonVictor Zhong, personCaiming
Xiong, and personRichard Socher.
Seq2SQL: Generating Structured Queries from
Natural Language using Reinforcement Learning.
(year2017), pages1–12.