Contextual suggestions for SQL syntax

In CockroachDB v23.1, we are introducing a new feature which enables external SQL query editors to provide contextual suggestions on SQL syntax to developers. As a proof of concept, we have integrated this feature in CockroachDB’s own interactive SQL shell to provide a long and often requested UX enhancement: tab completion!

If you’re in a hurry, this short video gives you the take away for the entire story that follows:

Prologue: the essence of tech demos

As you may recall, in our previous post we introduced Charm and Bubble Tea, the technology that enabled us to implement a new line editor for the CockroachDB SQL shell.

That story was about the outcomes of that work; today, we are going to rewind the clock and look at that story as it was still being written, and capture a moving scene of people, communication and human expectations.

This story thus starts at the end of August 2022, perhaps September. At the time, we knew Charm was giving us a solid foundation. We were happy about Bubbline and how it was solving many bugs we had in the past. And yet… What was there to see?

Picture this: an engineer blabbering about how this community (Charm) and tool (Bubble Tea) would be saving the day, and how we would now be able to design rich terminal-based user experiences, all the while unable to show more than an uninspiring single line of text on the screen:

This was not good communication.

The mission, if there was one, was to get a team of folk interested in this new development. Showing them UX (a prompt and a line editor) that was more-or-less equivalent to what they knew already would certainly not achieve that. What would?

In essence, a good tech demo needs to exhibit the following traits.

First, it should show something valuable. For example, it can show a solution to a problem that the audience knows exists already. Or it could introduce something that looks innovative / interesting, whereby the audience would feel they are learning something. Value stimulates attention. A CLI prompt that is functionally equivalent to its previous version does not solve a visible problem, nor does it teach anything.

Get Started with the ccloud CLI

Second, it should show something interactive. The audience should expect to be able to input or “do” something, and see the artifact react in response. A one way demo leaves the audience passive; active interaction stimulates engagement. While the Charm tools would have allowed us to extend the interactive prompt with colors, fancy animations or a new layout, none of those changes in appearance would be truly interactive.

Third, it should show something that is ostensibly not trivial. This is a variant of A.C. Clarke’s third law: the audience should feel challenged to explain what they are seeing, and unable to explain away what has been done as something that they, themselves, could have done with little effort. Magic stimulates curiosity.

This was the true introduction for the story that follows: in a quest to create a compelling demo for a terminal line editor, an artifact that would otherwise appear quite bland, we needed to find a “side car” project to show value, interaction and magic. Where did this bring us? A quick search through our issue backlog revealed the most frequently requested feature, involving an interactive component, and where some magic was needed since previous efforts had not succeeded: auto-completion for the SQL shell.

What we mean with “tab completion”

You know that one friend, the one who always completes your sentences for you?

In a nutshell, contextual syntax suggestions, also known as “auto-completion”, is a feature of command interpreters where the application tries to guess what the user would likely want to input next. Originally invented for productivity/convenience, auto-completion has since been recognized as an important tool for exploratory learning: it enables the user to incrementally discover what is possible to do, without looking at documentation or other more labor-intensive inspection facilities.

An example of auto-completion is that provided by the unix shell. It is activated by pressing the Tab key (hence the name “tab completion”), the list of candidates is generated from file and directory names, and in the case there are multiple candidates, the list of candidates is simply printed on the screen once, followed by a new prompt.

Design considerations

From a technical perspective, we can decompose auto-completion as follows:

a presentation user interface (UI), which is the logic that presents the candidates on the user’s screen, alongside with explanatory text, and either lets them choose a candidate interactively (when there are multiple candidates) or immediately completes the input.
candidate generation, which is a function which takes the position of the cursor and the text already entered as input, and produces a list of possible completions at that point: the input words themselves, at the very least, and optionally additional explanatory text to help the user choose between candidates.

There are numerous reasons why these two components should be considered as entirely separate engineering projects.

One is that the engineering work needed for each of these two components is remarkably different. Designing and building a presentation UI is quite distinctly a “front-end” project, albeit in a terminal instead of a web browser. It requires a degree of aesthetic sensitivity and acknowledgement for user expectations around use of screen real-estate, response latency, on-screen hints, keyboard shortcuts, etc. In contrast, candidate generation is a pure “back-end” project, which can be reasoned about purely algorithmically without a human-in-the-loop. Given that the auto-completion components would be maintained by different teams (with different expertises), the presentation UI and the candidate generation need to be implemented separately, each following the coding idioms of the area owned by its respective team.

Another reason is a difference in development velocity. On the one hand, there are only so many ways to present completion candidates on the screen. So we do not foresee many iterations on the presentation UI. In contrast, we are likely to improve the quality of candidate generation over time, every time we update or extend our SQL dialect. If candidate generation was tied with the presentation UI, in the client-side interactive SQL shell, we would need to tell our users to upgrade their client executable every time we made an improvement. This is inconvenient. Thankfully, we can do better with Cockroach Cloud: by implementing candidate generation server-side, all our users can benefit from new auto-completion logic each time we upgrade Cockroach Cloud, without taking action on their side.

The last reason we have considered, and perhaps the most important, is that we foresee there will be multiple SQL interactive shells or editors implemented over time to interact with CockroachDB. If candidate generation was bundled with the presentation UI in just one SQL shell, every other shell would need to duplicate that functionality. By creating an API in our SQL dialect to generate completion candidates, we enable any and all future SQL editors and interactive shells to share our progress with auto-completion at no extra cost.

Bubbly completions

The presentation UI we implemented for CockroachDB’s SQL shell is integrated inside the Bubbline library. It is a rather thin layer of logic.

Its data model is a list of categories, and in each category a list of entries. Each entry is formed by a word, which will be the final input if selected, and an explanatory description which is only displayed on the screen while the user is navigating through entries.

Bubbline does not have a specific opinion about what the categories should represent; this is left to the client application to decide. For example, in CockroachDB’s SQL shell, we map the different types of SQL syntax to Bubbline categories: keywords, databases, schemas, relations, functions, etc. We will come back to this mapping below.

Each category is presented on the screen as a separate column, whose implementation is fully delegated to the standard list widget from the Bubble library. The list widget takes care of limiting the display depending on screen height, adding pagination, and narrowing down the list using a fuzzy filter (activated using the “/” key).

Bubbline’s remaining participation is mainly to render the columns side-by-side, displaying each candidate’s description underneath, and mapping the left/right keys to switching focus between columns.

All this presentation UI is neatly encapsulated inside Bubbline: client applications do not have control over the presentation or navigation/selection. Instead, Bubbline defines its external API as follows:

The client application (in our case, CockroachDB’s SQL shell) provides its own candidate generation function as a configuration variable .
Bubbline recognizes when the user requests auto-completion, and passes the user input so far and the cursor location to the client app’s candidate generator as arguments.
The client candidate generator then returns the candidates, as a mapping of categories and entries (as described above), together with properties that tell Bubbline how to insert the candidate text at the current cursor position.

From this point on, the only responsibility remaining to implement in the client app is the candidate generation function.

Contextual suggestions in CockroachDB SQL

The API we are making available for 3rd party SQL editors and interactive shells is a special, CockroachDB-specific SQL statement with the following syntax:

SHOW COMPLETIONS AT OFFSET <position> FOR <text>

Its inputs are the user input text, which may contain partial or invalid SQL; and a cursor position as a byte offset relative to the beginning of the input text. Its output is a table which enumerates the suggestions (completion candidates) at that position, together with their category and explanatory description. For example:

The start/end columns specify the boundaries of the input word being replaced. They make it possible for different suggestions to replace different amounts of text. In this example, both suggestions replace the same prefix “veh”.

Under the hood, SHOW COMPLETIONS runs a series of generous heuristics that produce suggestions at that cursor position. What do we mean by this?

Generous suggestions

An important design constraint for auto-completion, regardless of environment, is that users expect it to be generous.

We believe that it is generally OK for candidate generation to list more candidates than are possible, for the user can always filter the list down to just what they need. We found experimentally through user research that it is much less OK to list fewer candidates than are possible, for then the user becomes confused of not seeing what they expected to see, or frustrated that the tool is not helping them.

Of course, ideally auto-completion should be precise, when it neither generates too many nor too few candidates. However, as we will see below, reaching a high level of precision constitutes a hard computing problem. The conservative, practical strategy is thus to err on the side of excess generosity.

Heuristic-based candidate generation

Computationally, the generation of contextual syntax suggestions for SQL is a hard algorithmic problem.

When the solution is too simple, it generates too much noise and does not help the user much. For example, if we use only the last few characters in the input before the cursor and try to complete from there, we would too quickly generate nonsensical candidates. An additional complexity is that if the cursor is in the middle of a string literal (e.g. SELECT ‘my text… ) or a SQL comment, we do not want to expand anything.

Meanwhile, the extreme diversity of SQL syntax rules makes it extremely hard to reach maximum precision. In the Chomsky hierarchy, the SQL grammar is context-free (Type 2) but not regular (Type 3), which precludes any approach based on regular expressions. We cannot either reuse CockroachDB’s internal SQL parser directly. It is fundamentally a LALR(2) parser which guarantees parsing latency and memory usage to be bound linearly to input size, at the cost of being unable to process incomplete input. This limitation would be incompatible with the requirement that syntax suggestions be available before the input is complete. Even if we switched the parsing algorithm (e.g. using GLR), we would need a special grammar with “holes” to represent incomplete input at the cursor position; the result of parsing would be syntax forests instead of trees; and we would need to extend our query planner to expand syntax holes into candidates instead of generating query plans. This would be a huge undertaking, resulting in a large amount of new complexity in the database engine, just at the service of a front-end application.

What's new in CockroachDB? | Azure, Multi-region serverless, & new migration tools

Like other SQL shells before us, we have thus settled for a middle ground, using heuristics to generate completion candidates. Heuristics are defined as a list of rules, where each rule contains a pattern of tokens around the cursor position, and a candidate generation function to use when the pattern is recognized.

The most comprehensive heuristic-based completion engines are perhaps those found in PostgreSQL’s own psql shell and the one in the multi-database shell usql.

However, this degree of sophistication is both a blessing and a curse. The blessing is that they are rather precise; for example they know to only generate table names as candidates after “INSERT INTO”, “UPDATE”, or “FROM/JOIN”. The curse is that the list of heuristics must be updated manually every time a new feature is added to the main SQL grammar. This is an obstacle in two ways. For one, these pre-existing heuristics do not know about CockroachDB’s special SQL syntax (e.g. BACKUP), and would need to be extended accordingly. Second, and most significantly, these heuristics are defined in a different location in the source code as the main grammar, and yet both the grammar and heuristics must be kept in sync with each other. Given that the current internal organization at Cockroach Labs lets different teams modify the SQL grammar incrementally to suit their needs, the risk is just simply too great that some of these teams would “forget” to also incrementally extend the completion heuristics for “their” features. With incomplete heuristics, the completion generation would become greedy and run afoul of the user expectation of generosity.

To reduce this risk, CockroachDB’s new heuristic-based completion engine is further simplified to look at sketches of the input tokens, instead of the tokens themselves. A sketch is an alternate, simplified representation of the input which preserves its punctuation, but merges all word-like tokens (identifiers and keywords) into a single abstract “word” token type. Starting from a sketch, a heuristic can be for example, “if the input cursor is positioned after a sequence of not-period, word, period, word, then try to complete database objects within the schema or database whose name is specified before the period”. Within this framework, we implemented heuristics to generate candidate function, database, schema and relation (view/table/sequence) names. The framework is readily extensible and we expect to add more heuristics over time.

Image Credit:Henrik Kniberg

Tying everything together

After we built a presentation UI in Bubbline and a candidate generation facility in CockroachDB SQL, the remaining integration in CockroachDB’s interactive SQL shell was rather straightforward.

Upon instantiating a Bubbline editor, the SQL shell configures it with an “AutoCompleteFn” which runs a SHOW COMPLETIONS query remotely in the database. The results of SHOW COMPLETIONS are then fed into the Bubbline completion data model using categories and entries. Bubbline then delegates the interaction to the Bubbles list widgets, as described previously. Et voila! Magic.

Lessons learned and next steps

Here ends the story of building an “interesting” tech demo for the new line editor we’ve built for CockroachDB v23.1.

What comes next? For one, we expect experience reports from our users as they experiment with CockroachDB v23.1. In response, we will iterate on both the presentation UI and the candidate generation. We will also keep a warm hand extended towards the Charm community, hoping to learn from other application developers how we can make our UX more useful in exchange for our patches to Bubble Tea and making Bubbline reusable in other Go applications.

One lesson (re)learned from this project is how innovation can be the fruit of serendipity and accident, instead of careful product research followed by project planning. After all, extending Bubbline with a presentation UI, and extending CockroachDB with a generous heuristic-based generator for syntax suggestions, were “just” meant to add some additional spiciness to a project otherwise focused on fixing past shortcomings with our line editor. Yet, it is undeniable that good value was delivered as a side effect. The integration of the completion widget in the Bubbline UI provides a good example of widget composition using the Bubble Tea framework, and will teach maintainers the means to enhance our terminal UX further. Our updated back-end SHOW COMPLETIONS logic can now be leveraged to power contextual suggestions in other tools, for example Cockroach Cloud’s upcoming web-based SQL editor. Its extensive test suite also constitutes a solid exercise of our SQL schema introspection logic.

The other lesson learned is how to keep organizational focus in mind. Cockroach Labs is primarily a database company, not a unix TTY engineering department. None of the work presented here would be possible without the intelligent event model of Charm’s Bubble Tea, which allowed us to avoid learning how to control the terminal directly, and forced us to decouple control from display logic in the presentation layer—a separation essential to build solid unit tests. Similarly, Cockroach Labs is a database company, not a programming language research lab. The implementation of a precise candidate generation engine, with all its new parsing and query planning technology, would be an opportunity cost we found too large to bear. Instead, our choice of simplified sketch-based heuristics limits the maintenance burden for our SQL teams, and guarantees a modest learning curve for folk wanting to add new heuristics.