Overview

Note: The four-part series that follows details my journey and helpful things I discovered along the way in solving all of the Leetcode database problems over roughly 2 weeks in July 2021. This was originally only 1 post, but you will quickly see why I ran into a content length issue (didn't know Leetcode had that for its discussion posts!). The references included at the end apply to all four parts.

Personal background: I originally had somewhat of a disdain for SQL. As with all developers, you will have expertise in some realms of development and need for improvement in others. It didn't take long in my development career (I'm still quite new) for me to realize that SQL was somewhat of a handicap I needed to overcome in order to be a more complete developer. Most people on Leetcode, including myself, are not here for the database problems but for the data structure and algorithm problems. Nonetheless, I wanted to improve my SQL capabilities, and I was happy to see Leetcode had a generous selection of database problems.

Preparation for Leetcode database problems: It didn't take long for me to realize I wasn't all that prepared for many of the SQL problems Leetcode had to offer. As with the data structure and algorithm problems, Leetcode assumes a certain level of familiarity on the part of the user. The problems given are supposed to be similar to interview problems after all!

All this to say: I realized I needed to do some "preparation" before I began my Leetcode work in earnest. After a few different false starts, I'm convinced the following resources will be helpful to anyone looking to adequately prepare for all of Leetcode's database problems:

• SQL Tutorial (sqltutorial . org): General SQL reference for true SQL beginners. Downloading the sample database is highly encouraged for learning in an interactive fashion.
• MySQL Tutorial (mysqltutorial . org): This is an excellent MySQL reference. It's similar to the reference immediately above, but this resource is restricted to MySQL as opposed to being completely database agnostic. Again, downloading the sample database is highly encouraged so as to learn in an interactive fashion.
• SQLBolt (sqlbolt . com): Work through a tutorial that covers many SQL basics via interactive lessons.
• PostgreSQL Exercises (pgexercises . com): Even if you are not using Postgres as your database, this is an excellent resource to work through in its entirety before embarking on all of the Leetcode problems. Its contents are largely applicable (except for issues of syntax and maybe a few other minor details) to all major databases (i.e., MySQL, SQL Server, Oracle, etc.). Its exercises cover SQL basics, joins and subqueries, data modification, aggregates, dates, strings, and recursive queries.

Once I had gone through the resources above, specifically the Postgres exercises, I felt like I was probably ready to tackle the Leetcode database problems in their entirety. I worked through every single Leetcode database problem over the span of about two weeks in July 2021. This is almost certainly not a normal pace--I devoted a great deal of time each day to knocking out the problems. And I learned a great deal in the process.

Study guide motivation and description: The two weeks I devoted to completing all of the Leetcode database problems were rather eye-opening. I quickly learned 5 things, all of which I will expound on more later in this study guide:

1. Understanding query execution order is critical. How can you accurately determine your result set if you do not know how it is being formed?
2. Consistent formatting matters. This is not just a cosmetic issue--your style and formatting can impact how you think.

The next three points were probably the biggest revelation to me throughout the course of my two week journey:

3. Window functions make difficult problems easy. There's a reason why window functions show up in most Medium/Hard problems. They're immensely powerful when used with care. I provide a listing of different window functions and some of the problems in which I have found them to be helpful.
4. Common table expressions (CTEs) are agents of clarity and utility. Have you ever gotten tired of making a mess by using sizable subqueries? CTEs provide the ability to use "named subqueries" that are especially useful when dealing with hierarchical data. You can also use recursive CTEs (more on this later) which add a whole new dimension to crafting powerful queries to solve complex problems. I provide problem solutions to illustrate how CTEs can be agents of clarity and utility.
5. Recursive CTEs. Tricky at first but opens up all sorts of possibilities, especially when it comes to dealing with hierarchical data. I provide some references, examples, and, just as with window functions, I provide a listing of different Leetcode problems where using WITH RECURSIVE is a viable option.

Everything below delves into each of these points in greater detail.

Note: I did all of the database problems with a Leetcode premium subscription. Most of the database problems require a premium subscription; hence, when Leetcode problems are explicitly referenced in this guide, it is fairly safe to assume they are problems that require a subscription to view. Most of the material in this guide, however, will be of use with or without a subscription.

Order of Execution of a Query

Short Version: The logical processing order of the SELECT statement is generally as follows:

1. FROM/JOIN (and all associated ON conditions)
2. WHERE
3. GROUP BY
4. HAVING
5. SELECT (including window functions)
6. DISTINCT
7. ORDER BY
8. LIMIT/OFFSET

Long Version:

Motivation: Without hesitation, compute the following as quickly as you can in your head:

1 + 2 / 3 * 4 ^ 5 - 6

This immediately comes off as a "trick PEMDAS problem," where the goal is to "test" whether or not someone "really" understands the order of operations for evaluating mathematical expressions. But you would never encounter an expression like the one above in the wild. Why? Because it's been intentionally made unclear as to how to go about evaluating the given expression. Specifically, the complete absence of parentheses makes it unnecessarily difficult to understand what the result of the mathematical expression should be.

Importance: Trying to write a SQL SELECT statement without understanding its logical processing order is like trying to evaluate a complicated mathematical expression with no parentheses. It's unnecessarily difficult, and it can lead to uncertainty in what the result set for a query should be.

Documentation: If you search for order of execution of a SQL query, then you are likely to stumble across threads on Stack Overflow, and who knows what else. But there's little in the way of "official documentation" except the following helpful excerpt from the SQL Server docs

The following steps show the logical processing order, or binding order, for a SELECT statement. This order determines when the objects defined in one step are made available to the clauses in subsequent steps. For example, if the query processor can bind to (access) the tables or views defined in the FROM clause, these objects and their columns are made available to all subsequent steps. Conversely, because the SELECT clause is step 8, any column aliases or derived columns defined in that clause cannot be referenced by preceding clauses. However, they can be referenced by subsequent clauses such as the ORDER BY clause. The actual physical execution of the statement is determined by the query processor and the order may vary from this list.

1. FROM
2. ON
3. JOIN
4. WHERE
5. GROUP BY
6. WITH CUBE or WITH ROLLUP
7. HAVING
8. SELECT
9. DISTINCT
10. ORDER BY
11. TOP

This excerpt ends with a warning:

The preceding sequence is usually true. However, there are uncommon cases where the sequence may differ.

Mental model (how to think about SELECT statements): For the sake of simplicity, the list above may be expressed in the following manner to capture the (usually true) logical processing order of the SELECT statement:

1. FROM/JOIN (and all associated ON conditions)
2. WHERE
3. GROUP BY
4. HAVING
5. SELECT (including window functions)
6. DISTINCT
7. ORDER BY
8. LIMIT/OFFSET

The listing above is how you should think about a SELECT query, but this is different from how you would write a SELECT query. How do we typically write a SELECT query?

Writing model (how to write SELECT statements): If we were to hop over to the Postgres docs, then we might be a little overwhelmed by what's provided for the "synopsis" of the SELECT statement (reproduced below).

[ WITH [ RECURSIVE ] with_query [, ...] ]
SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ]
    [ * | expression [ [ AS ] output_name ] [, ...] ]
    [ FROM from_item [, ...] ]
    [ WHERE condition ]
    [ GROUP BY [ ALL | DISTINCT ] grouping_element [, ...] ]
    [ HAVING condition ]
    [ WINDOW window_name AS ( window_definition ) [, ...] ]
    [ { UNION | INTERSECT | EXCEPT } [ ALL | DISTINCT ] select ]
    [ ORDER BY expression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ]
    [ LIMIT { count | ALL } ]
    [ OFFSET start [ ROW | ROWS ] ]
    [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } { ONLY | WITH TIES } ]
    [ FOR { UPDATE | NO KEY UPDATE | SHARE | KEY SHARE } [ OF table_name [, ...] ] [ NOWAIT | SKIP LOCKED ] [...] ]

where from_item can be one of:

    [ ONLY ] table_name [ * ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ]
                [ TABLESAMPLE sampling_method ( argument [, ...] ) [ REPEATABLE ( seed ) ] ]
    [ LATERAL ] ( select ) [ AS ] alias [ ( column_alias [, ...] ) ]
    with_query_name [ [ AS ] alias [ ( column_alias [, ...] ) ] ]
    [ LATERAL ] function_name ( [ argument [, ...] ] )
                [ WITH ORDINALITY ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ]
    [ LATERAL ] function_name ( [ argument [, ...] ] ) [ AS ] alias ( column_definition [, ...] )
    [ LATERAL ] function_name ( [ argument [, ...] ] ) AS ( column_definition [, ...] )
    [ LATERAL ] ROWS FROM( function_name ( [ argument [, ...] ] ) [ AS ( column_definition [, ...] ) ] [, ...] )
                [ WITH ORDINALITY ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ]
    from_item [ NATURAL ] join_type from_item [ ON join_condition | USING ( join_column [, ...] ) [ AS join_using_alias ] ]

and grouping_element can be one of:

    ( )
    expression
    ( expression [, ...] )
    ROLLUP ( { expression | ( expression [, ...] ) } [, ...] )
    CUBE ( { expression | ( expression [, ...] ) } [, ...] )
    GROUPING SETS ( grouping_element [, ...] )

and with_query is:

    with_query_name [ ( column_name [, ...] ) ] AS [ [ NOT ] MATERIALIZED ] ( select | values | insert | update | delete )
        [ SEARCH { BREADTH | DEPTH } FIRST BY column_name [, ...] SET search_seq_col_name ]
        [ CYCLE column_name [, ...] SET cycle_mark_col_name [ TO cycle_mark_value DEFAULT cycle_mark_default ] USING cycle_path_col_name ]

TABLE [ ONLY ] table_name [ * ]

We can produce a more useful writing model by stripping the general SELECT statement down to its essentials:

-- writing model for a general SELECT statement
SELECT DISTINCT 
  column, AGG_FUNC(column_or_expression), ...
FROM 
  mytable M JOIN another_table A ON M.column = A.column
WHERE 
  constraint_expression
GROUP BY 
  column
HAVING 
  constraint_expression
ORDER BY 
  column ASC/DESC
LIMIT 
  returnCount OFFSET skipCount;

Tabular summary of writing model:

List summary of writing model:

1. FROM/JOIN: The FROM clause and subsequent JOINs are first executed to determine the total working set of data that is being queried. This includes subqueries in this clause, and can cause temporary tables to be created under the hood containing all the columns and rows of the tables being joined.
2. WHERE: Once we have the total working set of data, the first-pass WHERE constraints are applied to the individual rows. The rows that do not satisfy the constraint are discarded. Each of the constraints can only access columns directly from the tables requested in the FROM clause. Aliases in the SELECT part of the query are not accessible in most databases since they may include expressions dependent on parts of the query that have not yet executed.
3. GROUP BY: The remaining rows after the WHERE constraints are applied are then grouped based on common values in the column(s) specified in the GROUP BY clause. As a result of the grouping, there will only be as many rows as there are unique values in that column. Implicitly, this means that you should only need to use this when you have aggregate functions in your query.
4. HAVING: If the query has a GROUP BY clause, then the constraints in the HAVING clause are then applied to the grouped rows, discarding the grouped rows that do not satisfy the constraint(s). Like the WHERE clause, aliases are also not accessible from this step in most databases. Finally, just remember that the WHERE clause is to individual rows what HAVING is to grouped rows by means of GROUP BY (i.e., HAVING is the multi-row version of WHERE).
5. SELECT: Any expressions in the SELECT part of the query are finally computed.
6. DISTINCT: Of the remaining rows, rows with duplicate values in the column(s) marked as DISTINCT will be discarded.
7. ORDER BY: If an order is specified by the ORDER BY clause, the rows are then sorted by the specified data in either ascending or descending order. Since all the expressions in the SELECT part of the query have been computed, you can reference aliases in this clause.
8. LIMIT/OFFSET: Finally, the rows that fall outside the range specified by the LIMIT and OFFSET are discarded, leaving the final set of rows to be returned from the query.

Style Guide

SELECT FirstName, LastName, City, State FROM Person LEFT JOIN Address USING(PersonId);

SELECT
  P.FirstName,
  P.LastName,
  A.City,
  A.State
FROM
  Person P
  LEFT JOIN Address A ON P.PersonId = A.PersonId;

Formatting Guidelines: Click the widget above to see the rationale behind everything that appears immediately below.

Some of the guidelines above are less relevant than others in the context of solving Leetcode problems (e.g., you have no choice concerning the naming of tables in whatever schema you are provided for a particular problem), but I have found most of them to be immensely useful in the process of cobbling together my own queries.

As always, rules are made to be broken. The rules above are meant to provide you freedom and clarity. They are not meant to be a straightjacket. I try to follow my own rules most of the time, but I occasionally make exceptions (especially when using UNION or UNION ALL for some reason) or slip up (more often than I care to admit). Adopt what you find to be helpful. Leave the rest.

References

[1].
Gordon Linoff.
Data Analysis Using SQL and Excel.
Wiley. 2016. 39.

[2].
Alan Beaulieu.
Learning SQL.
O'Reilly. 2020. 267.

[3].
Anthony Molinaro.
SQL Cookbook.
O'Reilly. 2021. 519.

[4].
Anthony Molinaro.
SQL Cookbook.
O'Reilly. 2021. 520.

[5].
Alan Beaulieu.
Learning SQL.
O'Reilly. 2020. 181.

[6].
Anthony Molinaro.
SQL Cookbook.
O'Reilly. 2021. 535-537.