Guided SQL-Based Data Exploration

Personalized, step-by-step SQL query recommendations learned online from user feedback with multi-armed bandits

Paper (ICDE 2024) Code on GitHub

Description

The exploration of large, real-world databases poses major challenges to users due to their volume and complexity. SQL is the preferred language for data exploration. However, the process of iteratively refining SQL queries is tedious and time consuming. We formulate the automation of personalized SQL-based data exploration as the problem of suggesting the most relevant query and accounting for user feedback at each step. We develop an end-to-end solution and a system to assist users in exploring different components of a complex database. We instantiate our solution using Multi-Armed Bandits, a category of algorithms that are suitable for interactive online learning by balancing exploration with exploitation. We design a lightweight algorithm to personalize stepwise SQL recommendations that efficiently discovers the current user preferences in coordination with that user's feedback and what other users prefer. We run extensive experiments that demonstrate the utility of our approach for large-scale data exploration.


Overview

Instead of recommending full SQL queries, the user builds a query step by step, top-down, and a recommender helps at every step:

FROM (tables) → SELECT (columns) → WHERE (columns) → WHERE (predicates)
  1. Table recommender suggests tables for the FROM clause.
  2. Column recommenders suggest columns of the selected tables for the SELECT and WHERE clauses.
  3. Predicate recommenders suggest filters on a chosen column:
    • categorical columns get column = value predicates;
    • numerical columns get column BETWEEN x AND y regions, built with equal-width, equal-height or K-means binning.

Breaking the problem up this way means each recommender picks from a small, finite pool of items (for example, only the columns of the tables already selected), rather than from every possible query.

Each recommender is a multi-armed bandit that returns the top-K items and learns online from which ones the user picks (any number, in any position). Feedback is implicit: the system reads it from the queries the user builds, so the user never rates anything. A selected item gets a reward of 1. For numerical regions, the reward is how much the recommended bin overlaps the region the user chose.

We design pUCB, a lightweight personalized variant of UCB that needs no user or item features. It ranks items by combining what the current user has picked before with what all users prefer, weighted by a personalization factor.

Key Results

Offline evaluation replays real query logs from the Sloan Digital Sky Survey (SDSS DR7: 115 tables, 52 views, 9,903 columns). We compare pUCB with UCB, Thompson Sampling, ε-greedy and a Popular baseline.

pUCB scores highest on every dataset and clause. MAP@K on the TH50 dataset:

Clause Popular ε-greedy TS UCB pUCB
SELECT 0.60 0.57 0.61 0.64 0.75
FROM 0.45 0.40 0.44 0.45 0.64
WHERE 0.56 0.50 0.53 0.58 0.69

User study. 17 participants used Query Builder (QB), a system built on this framework, on the CORDIS database of European research projects. Each did NL-to-SQL and data-navigation tasks, some with QB and some writing SQL by hand. They fully completed 90% of tasks with QB, compared with 70% by hand, and finished much faster. Every participant, including the SQL experts, said they preferred QB to writing SQL manually.

Code

The code, experiments and user study are available on GitHub.

Key Persons

Antonis Mandamadiotis

Georgia Koutrika