LeetCode 183 - Customers Who Never Order¶

Database Language: PostgreSQL

Difficulty:

Problem Description¶

Input¶

Table: Customers¶

Column Name	Type
id	int
name	varchar

id is the primary key (column with unique VALUES) for this table. Each row of this table indicates the ID and name of a customer.

Table: Orders¶

Column Name	Type
id	int
customerId	int

id is the primary key (column with unique VALUES) for this table. customerId is a foreign key (reference columns) of the ID from the Customers table. Each row of this table indicates the ID of an order and the ID of the customer who ordered it.

Requirement¶

Write a solution to find all customers who never order anything.

Return the result table in any order.

The result format is in the following example.

Examples¶

Example 1¶

Input¶

Customers table:

id	name
1	Joe
2	Henry
3	Sam
4	Max

Orders table:

id	customerId
1	3
2	1

Output¶

Customers
Henry
Max

SQL Schema¶

CREATE TABLE IF NOT EXISTS Customers (id INT PRIMARY KEY, name VARCHAR(255));
CREATE TABLE IF NOT EXISTS Orders (id INT PRIMARY KEY, customerId INT);

TRUNCATE TABLE Customers;
INSERT INTO Customers (id, name) VALUES ('1', 'Joe');
INSERT INTO Customers (id, name) VALUES ('2', 'Henry');
INSERT INTO Customers (id, name) VALUES ('3', 'Sam');
INSERT INTO Customers (id, name) VALUES ('4', 'Max');

TRUNCATE TABLE Orders;
INSERT INTO Orders (id, customerId) VALUES ('1', '3');
INSERT INTO Orders (id, customerId) VALUES ('2', '1');

Solutions¶

When doing queries on 2 tables wherein the goal is to return all rows in the first table that does not exist on a second table, there are 3 possible ways of accomplishing this:

Using LEFT OUTER JOIN
Using NOT EXISTS
Using NOT IN

Solution #1 - Using LEFT OUTER JOIN¶

To identify rows in one table that does not exist on another table using the LEFT OUTER JOIN, the basic query structure is as follows:

SELECT <Output Columns>
FROM <Table 1> LEFT OUTER JOIN <Table 2>
  ON <Table 1>.<Column 1> = <Table 2>.<Column 1>
WHERE <Table 2>.<Column 2> IS NULL

Using this basic query structure, to identify customers in the Customers who has never ordered anything (or does not have any rows in the Orders table based on the customerId), the 2 tables need to be joined on the customer ID column and then the result needs to be filtered out by checking if the Orders.id IS NULL. Here's how the query will look like using the LEFT OUTER JOIN:

# Final Solution 1 Query - Using LEFT OUTER JOIN
SELECT name AS Customers
FROM Customers LEFT OUTER JOIN Orders
  ON Customers.id = Orders.customerId
WHERE Orders.id IS NULL

Here's the corresponding query plan generated by PostgreSQL:

Hash Right Join  (cost=13.15..51.80 rows=8 width=516)
  Hash Cond: (orders.customerid = customers.id)
  Filter: (orders.id IS NULL)
  ->  Seq Scan on orders  (cost=0.00..32.60 rows=2260 width=8)
  ->  Hash  (cost=11.40..11.40 rows=140 width=520)
        ->  Seq Scan on customers  (cost=0.00..11.40 rows=140 width=520)

And here's the fastest runtime for this query:

Runtime: 201ms
Beats: 93.23% as of July 15, 2024

Solution #2 - Using NOT EXISTS¶

The basic structure of using NOT EXISTS in identifying rows in one table where no row exists on another table is as follows:

SELECT <Output Columns>
FROM <Table 1>
WHERE NOT EXISTS (SELECT 'X' FROM <Table 2>
                  WHERE <Table 1>.<Column> = <Table 2>.<Column>)

Using this basic query structure that uses the NOT EXISTS to identify customers in the Customers table that do not have any orders in the Orders table using the customerId in the Orders to match against the id in the Customers table, the query will look as follows:

# Final Solution 2 Query - Using NOT EXISTS
SELECT name AS Customers
FROM Customers
WHERE NOT EXISTS (SELECT 'X' FROM Orders
                  WHERE Customers.id = Orders.customerId)

Here's the query plan generated by MySQL for this query:

Hash Right Anti Join  (cost=13.15..64.25 rows=70 width=516)
  Hash Cond: (orders.customerid = customers.id)
  ->  Seq Scan on orders  (cost=0.00..32.60 rows=2260 width=4)
  ->  Hash  (cost=11.40..11.40 rows=140 width=520)
        ->  Seq Scan on customers  (cost=0.00..11.40 rows=140 width=520)

And here's the fastest runtime for the NOT EXISTS solution:

Runtime: 197ms
Beats: 97.56% as of July 15, 2024

Solution #3 - Using NOT IN¶

The basic structure in using NOT IN in identifying rows in one table where no row exists on another table is as follows:

SELECT <Output Columns>
FROM <Table 1>
WHERE <Column 1> NOT IN (SELECT <Column> FROM <Table 2>)

Using this basic query structure that uses the NOT IN to identify customers in the Customers table that do not have any orders in the Orders table using the customerId in the Orders to match against the id in the Customers table, the query will look as follows:

# Final Solution 3 Query - Using NOT IN
SELECT name AS Customers
FROM Customers
WHERE id NOT IN (SELECT customerId FROM Orders)

Here's the query plan generated by MySQL for this query:

Seq Scan on customers  (cost=38.25..50.00 rows=70 width=516)
  Filter: (NOT (hashed SubPlan 1))
  SubPlan 1
    ->  Seq Scan on orders  (cost=0.00..32.60 rows=2260 width=4)

And here's the fastest runtime for the NOT EXISTS solution:

Runtime: 201ms
Beats: 93.23% as of July 15, 2024

Solution Runtime Comparison¶

Here's the comparison of the fastest runtime for each of the solutions.

Solution #	Runtime	Beats
1 - Using LEFT OUTER JOIN	201ms	93.23%
2 - Using NOT EXISTS	197ms	97.56%
3 - Using NOT IN	201ms	93.23%