Introduction
Selecting similar sets in SQL means finding groups of records that share common elements, such as orders with overlapping products, users with shared interests, or documents with matching tags. The core techniques are self-joins for pairwise comparison, Jaccard similarity for measuring overlap, and set intersection/difference operators. The key challenge is performance: naive approaches create O(n^2) comparisons, so indexing and pre-filtering are critical.
Setup: Example Data
1-- Orders with products (each row = one product in one order)
2CREATE TABLE order_items (
3 order_id INT,
4 product_id INT
5);
6
7INSERT INTO order_items VALUES
8(1, 101), (1, 102), (1, 103),
9(2, 101), (2, 102), (2, 104),
10(3, 201), (3, 202),
11(4, 101), (4, 102), (4, 103);
12
13-- Order 1 and 4 are identical {101, 102, 103}
14-- Order 1 and 2 share {101, 102}, so they are similar
15-- Order 3 shares nothing with 1, 2, or 4
Finding Exact Matching Sets
Orders that contain exactly the same products:
1-- Step 1: Create a set signature for each order
2WITH order_sets AS (
3 SELECT
4 order_id,
5 GROUP_CONCAT(product_id ORDER BY product_id) AS product_set
6 FROM order_items
7 GROUP BY order_id
8)
9-- Step 2: Find orders with identical signatures
10SELECT a.order_id AS order_a, b.order_id AS order_b, a.product_set
11FROM order_sets a
12JOIN order_sets b ON a.product_set = b.product_set
13 AND a.order_id < b.order_id;
14-- Result: order_a=1, order_b=4, product_set="101,102,103"
GROUP_CONCAT (MySQL) or STRING_AGG (PostgreSQL) creates a string signature of the sorted set. Identical signatures mean identical sets.
PostgreSQL Version
1WITH order_sets AS (
2 SELECT
3 order_id,
4 ARRAY_AGG(product_id ORDER BY product_id) AS products
5 FROM order_items
6 GROUP BY order_id
7)
8SELECT a.order_id, b.order_id, a.products
9FROM order_sets a
10JOIN order_sets b ON a.products = b.products
11 AND a.order_id < b.order_id;
Counting Shared Elements (Intersection Size)
1-- Find pairs of orders and how many products they share
2SELECT
3 a.order_id AS order_a,
4 b.order_id AS order_b,
5 COUNT(*) AS shared_products
6FROM order_items a
7JOIN order_items b
8 ON a.product_id = b.product_id
9 AND a.order_id < b.order_id
10GROUP BY a.order_id, b.order_id
11HAVING COUNT(*) >= 2
12ORDER BY shared_products DESC;
13
14-- Result:
15-- order_a=1, order_b=4, shared=3
16-- order_a=1, order_b=2, shared=2
17-- order_a=2, order_b=4, shared=2
The self-join on product_id finds all shared products. HAVING COUNT(*) >= 2 filters for pairs with at least 2 common items.
Jaccard Similarity
Jaccard similarity = |intersection| / |union|. Ranges from 0 (no overlap) to 1 (identical sets):
1WITH order_sizes AS (
2 SELECT order_id, COUNT(*) AS size
3 FROM order_items
4 GROUP BY order_id
5),
6shared AS (
7 SELECT
8 a.order_id AS order_a,
9 b.order_id AS order_b,
10 COUNT(*) AS intersection_size
11 FROM order_items a
12 JOIN order_items b
13 ON a.product_id = b.product_id
14 AND a.order_id < b.order_id
15 GROUP BY a.order_id, b.order_id
16)
17SELECT
18 s.order_a,
19 s.order_b,
20 s.intersection_size,
21 sa.size AS size_a,
22 sb.size AS size_b,
23 ROUND(
24 s.intersection_size * 1.0 /
25 (sa.size + sb.size - s.intersection_size),
26 2
27 ) AS jaccard_similarity
28FROM shared s
29JOIN order_sizes sa ON s.order_a = sa.order_id
30JOIN order_sizes sb ON s.order_b = sb.order_id
31ORDER BY jaccard_similarity DESC;
32
33-- Result:
34-- order_a=1, order_b=4, jaccard=1.00 (identical)
35-- order_a=1, order_b=2, jaccard=0.50 (2 shared out of 4 unique)
36-- order_a=2, order_b=4, jaccard=0.50
Finding Sets That Contain a Given Subset
Which orders contain ALL of products {101, 102}?
1SELECT order_id
2FROM order_items
3WHERE product_id IN (101, 102)
4GROUP BY order_id
5HAVING COUNT(DISTINCT product_id) = 2;
6-- Orders: 1, 2, 4
The HAVING COUNT = N ensures the order contains all N required products (not just any one).
Finding Sets Similar to a Specific Set
Find orders most similar to order 1:
1WITH target AS (
2 SELECT product_id FROM order_items WHERE order_id = 1
3),
4target_size AS (
5 SELECT COUNT(*) AS size FROM target
6),
7matches AS (
8 SELECT
9 oi.order_id,
10 COUNT(*) AS shared,
11 (SELECT size FROM target_size) AS target_size,
12 COUNT(*) OVER (PARTITION BY oi.order_id) AS candidate_size
13 FROM order_items oi
14 JOIN target t ON oi.product_id = t.product_id
15 WHERE oi.order_id != 1
16 GROUP BY oi.order_id
17)
18SELECT
19 order_id,
20 shared,
21 ROUND(shared * 1.0 / (target_size + candidate_size - shared), 2)
22 AS jaccard
23FROM matches
24JOIN (SELECT order_id, COUNT(*) AS candidate_size
25 FROM order_items WHERE order_id != 1
26 GROUP BY order_id) sizes USING (order_id)
27ORDER BY jaccard DESC;
Set Operations (PostgreSQL)
PostgreSQL supports array operations for set comparisons:
1WITH order_arrays AS (
2 SELECT
3 order_id,
4 ARRAY_AGG(product_id ORDER BY product_id) AS products
5 FROM order_items
6 GROUP BY order_id
7)
8SELECT
9 a.order_id AS order_a,
10 b.order_id AS order_b,
11 -- Intersection (elements in both)
12 ARRAY(SELECT UNNEST(a.products) INTERSECT SELECT UNNEST(b.products))
13 AS shared,
14 -- Symmetric difference (elements in one but not both)
15 ARRAY(SELECT UNNEST(a.products) EXCEPT SELECT UNNEST(b.products))
16 AS only_in_a
17FROM order_arrays a
18CROSS JOIN order_arrays b
19WHERE a.order_id < b.order_id;
1-- Index on the join column
2CREATE INDEX idx_order_items_product ON order_items(product_id);
3CREATE INDEX idx_order_items_order ON order_items(order_id);
4
5-- Composite index for both
6CREATE INDEX idx_order_items_both ON order_items(product_id, order_id);
For large datasets, pre-compute set signatures:
1-- Materialized view for set signatures
2CREATE MATERIALIZED VIEW order_signatures AS
3SELECT
4 order_id,
5 MD5(GROUP_CONCAT(product_id ORDER BY product_id)) AS set_hash
6FROM order_items
7GROUP BY order_id;
8
9CREATE INDEX idx_set_hash ON order_signatures(set_hash);
10
11-- Fast exact-set matching via hash
12SELECT a.order_id, b.order_id
13FROM order_signatures a
14JOIN order_signatures b ON a.set_hash = b.set_hash
15 AND a.order_id < b.order_id;
Common Pitfalls
O(n^2) comparisons: Self-joining all pairs is expensive for large tables. Pre-filter by requiring at least one shared element (the self-join on product_id already does this) and add a minimum intersection threshold.
Duplicates in sets: If order_items can have duplicate (order_id, product_id) rows, use COUNT(DISTINCT product_id) instead of COUNT(*).
NULL handling: GROUP_CONCAT and ARRAY_AGG skip NULLs. If product_id can be NULL, filter it explicitly or the set signature will be wrong.
GROUP_CONCAT length limit: MySQL's group_concat_max_len defaults to 1024 bytes. For sets with many elements, increase it: SET SESSION group_concat_max_len = 1000000.
Hash collisions: MD5 signatures for exact matching can collide (extremely rare). For critical applications, compare the full sorted array as a secondary check.
Summary
Use self-joins on shared elements to find overlapping sets and count intersection sizes
Use GROUP_CONCAT / ARRAY_AGG to create set signatures for exact matching
Calculate Jaccard similarity as |intersection| / |union| for measuring set overlap
Use HAVING COUNT(DISTINCT) = N to find sets containing a required subset
Index the element column (product_id) for fast joins
Pre-compute set hashes in materialized views for large-scale exact matching
