A CLICKHOUSE BATTLE STORY
3 Million Billboards 20 Million Places 1 Query
A battle story of making millions-scale proximity joins cheap in ClickHouse
Amaan Shaikh
Solutions Consultant at Sahaj Software
Agenda
1
The problem
2
The constraints
3
The attempts
4
The solution
5
The takeaways
THE PROBLEM
Out-of-home advertising
What we do
We build the software that plans out-of-home campaigns:
which billboards and screens a brand should book.
Billboards and places
It all runs on two sets of points on the map: the billboards
we can book, and the places people go. Close to 3 million on
one side, around 20 million on the other.
Billboards
Places
Downtown
0.5 mile
1
2
3
4
5
THE PROBLEM
“Show me the billboards near our coffee shops”
Our coffee shop
Near
Downtown
0.5 mile
Billboards
Places
1
2
3
4
5
THE CONSTRAINTS
What we were up against
Anywhere from 1 to 10 miles
The search radius is
never the same
Fast under load
Subsecond to seconds,
20 to 50 users
Cheap to run
No big new machines
1
2
3
4
5
THE ATTEMPTS
Two datasets
Two point tables. Every billboard and every place is an id, a lat, a lon.
billboard_id
lat
lon
b_1042
40.71
-74.00
b_1043
40.75
-73.98
b_1044
40.73
-73.99
b_1045
40.72
-74.02
…
…
…
b_2984120
40.69
-73.91
Billboards
≈ 3 million rows
place_id
lat
lon
p_5501
40.72
-74.01
p_5502
40.68
-73.95
p_5503
40.71
-73.96
p_5504
40.66
-73.93
…
…
…
p_19847302
40.80
-73.90
Places
≈ 20 million rows
1
2
3
4
5
THE ATTEMPTS
Precompute the pairs
Precompute every billboard-place pair within ten miles, once.
We did the napkin math before writing any code.
~8 hours
To build the table
~600 GB
Of pairs to store
Costly
To serve it fast
And the radius is baked in, so a new radius rebuilds all of it.
Too big, too rigid, not cost-effective. We never built it.
1
2
3
4
5
THE ATTEMPTS
Just run the query
Skip precompute. Just measure the distances at query time, with a plain join.
One nationwide query, for a big coffee-shop brand:
35,000 coffee shops
one brand, nationwide
×
3 million billboards
the whole country
=
105 billion
Distance checks, one query
No index skips a distance you have to compute. Too slow, every time.
1
2
3
4
5
THE ATTEMPTS
The real problem
Both attempts were built on the same join condition.
ON distance(billboard, place) <= radius
A range
Precompute
Ran it for every pair, up front
Too costly
Just run it
Ran it for every pair, live
Too slow
A range is something you can't index or skip.
1
2
3
4
5
THE SOLUTION
Change the condition
Neither attempt asked whether the join condition could change.
distance(billboard, place) <= radius
A range you compute, per pair
billboard.area = place.area
A match you look up
Turn “how far” into “which area”.
1
2
3
4
5
H3
THE SOLUTION
Meet H3
H3 is Uber's open-source geospatial index.
Coordinates become a cell id
Every location is one cell id, not raw
latitude and longitude
Spatial work gets cheap
Proximity, aggregation, neighbours and
indexing on ids, not geometry
geoToH3
(40.71, -74.00, 5)
=
852a1073fffffff
1
2
3
4
5
THE SOLUTION
The resolution is a knob
geoToH3
(40.71, -74.00, 5)
=
852a1073fffffff
res
h3 cell
cell area
0
~4,300,000 sq km
…
…
…
4
~1,800 sq km
5
~250 sq km
6
~36 sq km
…
…
…
15
~0.9 sq m
802a
fffffffffff
842a107
ffffffff
852a1073
fffffff
862a10737
ffffff
8f2a1073b59c2d4
1
2
3
4
5
THE SOLUTION
Tag each point, join on the cell
Give every point its H3 cell. Join on it, then measure the few that match.
billboard_id
lat
lon
h3
b_1042
40.71
-74.00
852a100bfffffff
b_1043
40.75
-73.98
852a1073fffffff
b_2984120
40.69
-73.91
852a100ffffffff
Billboards
place_id
lat
lon
h3
p_5501
40.72
-74.01
852a1051fffffff
p_5502
40.68
-73.95
852a1068fffffff
p_19847302
40.80
-73.90
852a100ffffffff
Places
H3 = geoToH3(lat, lon, 5), one new column per point
SELECT b.billboard_id
FROM billboards b
JOIN places p ON b.h3 = p.h3
WHERE p.brand = 'coffee shops'
AND geoDistance(b.lon, b.lat, p.lon, p.lat) <= 16093
Cheap cell match first, then exact distance on the few that survive.
1
2
3
4
5
THE SOLUTION
One cell is never enough
1
2
3
4
5
The edge effect
The place's cell
Closer, but missed
The cell and its ring
Now caught
Add the ring
THE SOLUTION
The ring is a knob too, in ClickHouse
The ring we just added is one call: h3kRing.
It takes a cell and k, and returns the cell
plus k rings.
Dial resolution and k to fit the radius. At
res 5, k = 2 is about 10 miles.
SELECT b.billboard_id
FROM billboards b
JOIN places p ON b.h3 IN h3kRing(p.h3, 2)
WHERE p.brand = 'coffee shops'
AND geoDistance(b.lon, b.lat, p.lon, p.lat) <= 16093
Place
k = 0 the place's cell
k = 1 the first ring
k = 2 a wider ring
1
2
3
4
5
THE SOLUTION
Attempts vs the solution
distance(billboard, place) <= radius
billboard.h3 = place.h3
600 GB, or 105 billion checks a query
Radius baked in
Minutes, or no answer
~1 GB of points
Any radius, just dial k
Answers in seconds
Change the condition, and everything downstream shrinks.
1
2
3
4
5
THE SOLUTION
Coffee shops, nationwide
The widest query there is: every billboard near any coffee shop, nationwide.
Within 10 miles
10-15s
On ClickHouse
Even the country's widest query returns now.
1
2
3
4
5
THE SOLUTION
End to end
Precompute
Tag every billboard and place
with its H3 cell
Store
Store the points and their
cells. ~1GB, not pairs
Serve
Expand the k-ring, join on
cell, exact distance on the
few
Points, not pairs. About 1GB, not 600GB.
1
2
3
4
5
THE TAKEAWAYS
Change the condition,
not the query.
A range became a cell, and the
work we couldn't skip
disappeared.
Know when and how much
to precompute.
Fast per query, but too big
and rigid. Weigh every
constraint, not just speed.
1
2
3
4
5
Questions?
Amaan Shaikh
Solutions Consultant at Sahaj Software