Problematic Query Patterns in Snowflake: Join Explosion

While I spend my day job digging into an amazing variety of performance issues, there are some patterns we see over and over again. The first pattern I blogged about was partition pruning. In this article, I’d like to address join explosion.

The Problem

When joining two tables on an equality predicate, assuming a inner join with a 1:1 or 1:many relationship for the data, the cardinality coming out of that join is not larger than the largest table going into the join. This obviously can change for outer joins or for tables where the data represents a many:many relationship. One sign of a join explosion is that the cardinality coming out of a join is greater than either of the tables going in to the join.

When I worked with Db2, in addition to the logical join types (left, inner, right, full outer), there were physical join types (Nested Loop, Hash, Merge Scan, and the more elusive Zig-Zag). For Db2, the default that would always work was Nested Loop. The other join types could be used if the conditions matched a set of defined requirements. Nested Loop was the slowest, so looking out for Nested Loop joins could be a strategy if other, more significant, query plan issues had been addressed.

When I worked with MySQL, it was my impression that MySQL only supported Nested Loop.

When I started working with Snowflake, I learned that Snowflake mostly uses Hash joins, with some tweaks when we hit things like range/banding. This actually surprised me, as I remembered from my Db2 days that in Db2, Hash joins were limited to inner equi-joins (joins on equality predicates only). In Snowflake the Hash join methodology is used for all kinds of joins that wouldn’t have qualified in Db2. I therefore had some confusion on how Snowflake made that work when Db2 would just choose a different join type.

The equi-join requirement seemed clear to me based on the way hash joins work. With a hash join, the inner or left table is used to build a hash table. The outer or right table then probes the hash table to find matches.

Since we are talking about hashed values and not actual values, only equality comparisons should work. Checking to see if one hash value is larger than another really has no meaning or reasonable answer.

What I learned is that Snowflake will instead perform a partial or full cartesian join and then use a post-join filter to apply the join predicates it was not able to apply during the join. This may make Snowflake joins on range predicates are slower. Even if you can’t see the join explosion and post-join filter in the query plan, it may be there and slowing the query down.

I have seen a bit less of this in the query plans I have been looking at for customers lately and have seen range/band join more often in our back-end tools. This is also why the ASOF join is one of my favorite new features in Snowflake – it makes certain types of range joins (where one is looking for a one-to-one relationship, but the exact interval is fluid) much more efficient. It does this by skipping the cartesian methodology, and instead using a union to stack the data based on a common timestamp reference and find the row from the right table immediately before or after the row from the left table.

That union methodology can be coded into the SQL fairly manually. Binning is another great methodology for different kinds of joins that require range predicates. See Ian Whitestone’s excellent article on a binning methodology.

Let’s take a look at some ways that a join explosion can appear in the query profile.

Examples

The simplest example of a join explosion is eliminating the join predicate. This happens by accident in complex queries more often than you might think. Take this query to work with SNOWFLAKE_SAMPLE_DATA as an example:

select * 
from snowflake_sample_data.TPCH_SF1.orders as o
    join snowflake_sample_data.TPCH_SF1.customer as c
    on o.o_custkey=c.c_custkey
where c_custkey in (121361, 84973, 47423)
;

The query profile for that looks pretty standard and sane:

Here the cardinality is clearly limited by the “many” side in the one-to-many relationship between customers and orders. We end up with 45 rows for three customer ids. What happens if we leave off the join condition? The SQL for that looks like this:

select * 
from snowflake_sample_data.TPCH_SF1.orders as o
    join snowflake_sample_data.TPCH_SF1.customer as c
where c_custkey in (121361, 84973, 47423)
;

The query profile looks somewhat different, though the shape is the same:

You might think we’d notice the difference in the rows returned, but when dealing with real-world result sets, it can be difficult to know how many rows to expect, and there can be complicating factors like aggregations that make it so we don’t see a different number of rows in the final result set.

The numbers are very different here than in the last profile. Instead of seeing the cardinality flowing up from the many side of our one-to-many relationship, we see the number of rows explode from 1.5 million on that branch of our plan to 4.5 million. This is why we call it join explosion.

Snowflake tries to clue us into a problem here by labeling that box “CartesianJoin”. This is a common element to join explosions, but joins can explode without this box being labeled as a CartesianJoin. In this case we really are doing a Cartesian Join to illustrate the point.

We also see the primary expense of the query moves from the table scans to above the join. In that case, that’s because we’re returning millions more rows. There are absolutely cases of major expense above the join that are entirely valid, so that is also not a definitive identifier for a join explosion, but is a common element.

Resolving Performance Problems Related to Join Explosions

The most common cause of join explosions is actually simply missing a join predicate. Particularly if the non-ansi syntax for joins is used, with the join conditions appearing in the where clause, it is not difficult to mistakenly remove a join predicate. Snowflake recommends using ANSI join syntax. This join style is a bit less likely to drop a join condition.

The most recent example of a join explosion I worked with a customer on, the customer realized they were using the wrong table, and one that would represent a many-to-many relationship. The table they were using was more a running log of data that was coming in and often had multiple copies of the same rows. The table they were supposed to be using represented a consolidation of those records such that there was only one copy of each row. This is one of the biggest reasons I come into customer engagements with more questions than answers – it is hard to tell from just the SQL and the performance characteristics of the SQL if a particular process and result is intended or is a mistake.

There are absolutely cases where a join explosion is the intended and required process to get to the desired result. This is particularly true in analytics databases where the relationships may be many-to-many. That type of relationship is rarer in an OLTP environment.

The first thing I do when I see a join explosion is to understand if it is required by the logic. If it is, then I’m next asking if there are any additonal conditions we can apply to limit the data coming in on either side of the join explosion. Most of the time, Snowflake understands transitive closure(t1.c1 = t2.c1, and t2.c1=t3.c1, so therefore t1.c1=t3.c1) and can use it to push predicates down to the tables. Sometimes Snowflake fails at this or the relationship is just slightly more complicated, so while it is not mathematically certain, it is a pattern you know exists for your data. For Snowflake, It is generally better to explicitly define the predicates you know to be true for this query, particularly if they can’t be 100% logically or mathematically deduced by the system.

A join explosion that is a problem with a million rows on each side often becomes not a problem if we can reduce the cardinality coming in on either side, so the more we can reduce the data set on either side, the less of a problem it becomes.

Remember that it is not a join explosion itself that is a problem. A join explosion is only a problem if that join or a filter after it are where our performance problem is for the query. On the other hand, if you’re looking a query profiles proactively while a data set is small, join explosions might be a place where queries blow up when the data set grows.