Low perf on NATURAL JOINs

[campoy]

I have these two requests which should perform basically the same:

SELECT f.repository_id, COUNT(*) as n
FROM   files AS f
       JOIN commit_files cf ON
            f.repository_id=cf.repository_id AND
            f.file_path=cf.file_path AND
            f.blob_hash=cf.blob_hash AND
            f.tree_hash=cf.tree_hash
       JOIN refs ON
            cf.repository_id = refs.repository_id AND
            cf.commit_hash = refs.commit_hash
WHERE  ref_name = 'HEAD'
GROUP BY f.repository_id
ORDER BY n DESC

and its NATURAL JOIN equivalent

SELECT f.repository_id, COUNT(*) as n
FROM   files AS f
       NATURAL JOIN commit_files cf
       NATURAL JOIN refs
WHERE  ref_name = 'HEAD'
GROUP BY f.repository_id
ORDER BY n DESC

Unfortunately, while the first one finishes after a couple of seconds, the second one takes double that.
I analyzed their EXPLAIN output and saw there's a tiny difference and wonder whether this could be the culprit.

For the first JOIN ON version, the plan is:

Sort(n DESC)
 └─ Project(files.repository_id, COUNT(*) as n)
     └─ GroupBy
         ├─ Aggregate(files.repository_id, COUNT(*))
         ├─ Grouping(files.repository_id)
         └─ Exchange(parallelism=96)
             └─ SquashedTable(refs, commit_files, files)
                 ├─ Columns
                 │   ├─ Column(repository_id, TEXT, nullable=false)
                 │   ├─ Column(file_path, TEXT, nullable=false)
                 │   ├─ Column(blob_hash, TEXT, nullable=false)
                 │   ├─ Column(tree_hash, TEXT, nullable=false)
                 │   ├─ Column(tree_entry_mode, TEXT, nullable=false)
                 │   ├─ Column(blob_content, BLOB, nullable=false)
                 │   ├─ Column(blob_size, INT64, nullable=false)
                 │   ├─ Column(repository_id, TEXT, nullable=false)
                 │   ├─ Column(commit_hash, TEXT, nullable=false)
                 │   ├─ Column(file_path, TEXT, nullable=false)
                 │   ├─ Column(blob_hash, TEXT, nullable=false)
                 │   ├─ Column(tree_hash, TEXT, nullable=false)
                 │   ├─ Column(repository_id, TEXT, nullable=false)
                 │   ├─ Column(ref_name, TEXT, nullable=false)
                 │   └─ Column(commit_hash, TEXT, nullable=false)
                 └─ Filters
                     ├─ commit_files.repository_id = refs.repository_id
                     ├─ commit_files.commit_hash = refs.commit_hash
                     ├─ files.repository_id = commit_files.repository_id
                     ├─ files.file_path = commit_files.file_path
                     ├─ files.blob_hash = commit_files.blob_hash
                     ├─ files.tree_hash = commit_files.tree_hash
                     └─ refs.ref_name = "HEAD"

While for the one with NATURAL JOIN:

Sort(n DESC)
 └─ Project(files.repository_id, COUNT(*) as n)
     └─ GroupBy
         ├─ Aggregate(files.repository_id, COUNT(*))
         ├─ Grouping(files.repository_id)
         └─ Exchange(parallelism=96)
             └─ Project(files.repository_id, commit_files.commit_hash, files.file_path, files.blob_hash, files.tree_hash, files.tree_entry_mode, files.blob_content, files.blob_size, refs.ref_name)
                 └─ Filter(files.repository_id = refs.repository_id)
                     └─ SquashedTable(refs, commit_files, files)
                         ├─ Columns
                         │   ├─ Column(repository_id, TEXT, nullable=false)
                         │   ├─ Column(file_path, TEXT, nullable=false)
                         │   ├─ Column(blob_hash, TEXT, nullable=false)
                         │   ├─ Column(tree_hash, TEXT, nullable=false)
                         │   ├─ Column(tree_entry_mode, TEXT, nullable=false)
                         │   ├─ Column(blob_content, BLOB, nullable=false)
                         │   ├─ Column(blob_size, INT64, nullable=false)
                         │   ├─ Column(repository_id, TEXT, nullable=false)
                         │   ├─ Column(commit_hash, TEXT, nullable=false)
                         │   ├─ Column(file_path, TEXT, nullable=false)
                         │   ├─ Column(blob_hash, TEXT, nullable=false)
                         │   ├─ Column(tree_hash, TEXT, nullable=false)
                         │   ├─ Column(repository_id, TEXT, nullable=false)
                         │   ├─ Column(ref_name, TEXT, nullable=false)
                         │   └─ Column(commit_hash, TEXT, nullable=false)
                         └─ Filters
                             ├─ commit_files.commit_hash = refs.commit_hash
                             ├─ files.repository_id = commit_files.repository_id
                             ├─ files.file_path = commit_files.file_path
                             ├─ files.blob_hash = commit_files.blob_hash
                             ├─ files.tree_hash = commit_files.tree_hash
                             └─ refs.ref_name = "HEAD"

Is it possible that the extra Project and Filter right above the SquashedTable can cause such a change in performance?

[ajnavarro]

I think that filter after the squashed table instead of inside the squashed node is causing that more rows go up instead of being filtered at the table level.

[erizocosmico]

@ajnavarro nope, that filter is already done inside the squash. Same rows must go up in those queries. It might just be a matter of having to go through 2 more nodes.

@campoy can you run this with a bigger dataset and see if the difference is very noticeable?

[campoy]

That was a large dataset already, 96 largest repos under github.com/google

[erizocosmico]

You're right, those two queries have a very different performance. After a bit of investigation, I came up with something: the order in which you join tables matters when it comes to natural join.

SELECT f.repository_id, COUNT(*) as n
FROM refs
NATURAL JOIN commit_files cf
NATURAL JOIN files f
WHERE ref_name = 'HEAD'
GROUP BY f.repository_id
ORDER BY n DESC

This has the exact same performance as the query without natural joins.

To avoid the creation of extra nodes, the natural joins should always go from the topmost table in the hierarchy, to the end.

So: repos -> refs -> ref_commits -> commits -> commit_files/blobs/files/trees -> files/blobs/tree_entries

Otherwise, natural join between refs and files generates a refs.repository_id = files.repository_id filter which is not removed and everything has to go through another node. However, even if it still has to go through another node, it's still a very big performance loss. I just haven't been able to discover why.

Perhaps a good start here would be to update the performance guide to include this tip.

UPDATE: it's because of the cache. First time you run this query it takes like 4s, then 0.4-0.6s each time. So, actually, both your query and mine take more or less the same. This explains why it takes so much with just a node of difference.

@campoy did you execute the one with natural joins first? Because that could be the reason.

[campoy]

That might have been the case, you can reproduce it on the same instance with this URL: http://35.239.XX.XX:8081 (ask in slack for the IP)

[erizocosmico]

I have been examining the traces of both queries and the place where it spends all the time is inside the SquashedTable node.

Since the only difference between two queries are the 2 extra Filter and Project node I decided to modify the SquashJoins rule to remove those and have a more similar tree.

Now this is the first query tree:

+------+
| plan |
+------+
| Sort(n DESC) |
|  └─ Project(files.repository_id, COUNT(*) as n) |
|      └─ GroupBy |
|          ├─ Aggregate(files.repository_id, COUNT(*)) |
|          ├─ Grouping(files.repository_id) |
|          └─ SquashedTable(refs, commit_files, files) |
|              ├─ Columns |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_entry_mode, TEXT, nullable=false) |
|              │   ├─ Column(blob_content, BLOB, nullable=false) |
|              │   ├─ Column(blob_size, INT64, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(commit_hash, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(ref_name, TEXT, nullable=false) |
|              │   └─ Column(commit_hash, TEXT, nullable=false) |
|              └─ Filters |
|                  ├─ commit_files.repository_id = refs.repository_id |
|                  ├─ commit_files.commit_hash = refs.commit_hash |
|                  ├─ files.repository_id = commit_files.repository_id |
|                  ├─ files.file_path = commit_files.file_path |
|                  ├─ files.blob_hash = commit_files.blob_hash |
|                  ├─ files.tree_hash = commit_files.tree_hash |
|                  └─ refs.ref_name = "HEAD" |
+------+

And the second query tree (natural joins) after my modifications:

+------+
| plan |
+------+
| Sort(n DESC) |
|  └─ Project(files.repository_id, COUNT(*) as n) |
|      └─ GroupBy |
|          ├─ Aggregate(files.repository_id, COUNT(*)) |
|          ├─ Grouping(files.repository_id) |
|          └─ SquashedTable(refs, commit_files, files) |
|              ├─ Columns |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_entry_mode, TEXT, nullable=false) |
|              │   ├─ Column(blob_content, BLOB, nullable=false) |
|              │   ├─ Column(blob_size, INT64, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(commit_hash, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(ref_name, TEXT, nullable=false) |
|              │   └─ Column(commit_hash, TEXT, nullable=false) |
|              └─ Filters |
|                  ├─ commit_files.commit_hash = refs.commit_hash |
|                  ├─ files.repository_id = commit_files.repository_id |
|                  ├─ files.file_path = commit_files.file_path |
|                  ├─ files.blob_hash = commit_files.blob_hash |
|                  ├─ files.tree_hash = commit_files.tree_hash |
|                  └─ refs.ref_name = "HEAD" |
+------+

The thing is... even without the extra nodes it's still slower than the other. Same tables, same squash, same filters.
The only difference between these trees is the following filter: commit_files.repository_id = refs.repository_id. But that's just how the squash rule works, so there is no need for that filter and the absence of it won't make it slower. In fact, having it should make it slower if it's not pruned as redundant filter.

So it makes no sense at all that the second tree takes 3x the first tree. I've also tried setting parallelism=1, so the partitions are accessed sequentially and therefore the cache reads the objects in the exact same way. Same results.

In fact, I just tried this query (first query removing the extra filter so the trees are identical):

SELECT f.repository_id, COUNT(*) as n
FROM   files AS f
       JOIN commit_files cf ON
            f.repository_id=cf.repository_id AND
            f.file_path=cf.file_path AND
            f.blob_hash=cf.blob_hash AND
            f.tree_hash=cf.tree_hash
       JOIN refs ON
            cf.commit_hash = refs.commit_hash
WHERE  ref_name = 'HEAD'
GROUP BY f.repository_id
ORDER BY n DESC

which has this tree:

+------+
| plan |
+------+
| Sort(n DESC) |
|  └─ Project(files.repository_id, COUNT(*) as n) |
|      └─ GroupBy |
|          ├─ Aggregate(files.repository_id, COUNT(*)) |
|          ├─ Grouping(files.repository_id) |
|          └─ SquashedTable(refs, commit_files, files) |
|              ├─ Columns |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_entry_mode, TEXT, nullable=false) |
|              │   ├─ Column(blob_content, BLOB, nullable=false) |
|              │   ├─ Column(blob_size, INT64, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(commit_hash, TEXT, nullable=false) |
|              │   ├─ Column(file_path, TEXT, nullable=false) |
|              │   ├─ Column(blob_hash, TEXT, nullable=false) |
|              │   ├─ Column(tree_hash, TEXT, nullable=false) |
|              │   ├─ Column(repository_id, TEXT, nullable=false) |
|              │   ├─ Column(ref_name, TEXT, nullable=false) |
|              │   └─ Column(commit_hash, TEXT, nullable=false) |
|              └─ Filters |
|                  ├─ commit_files.commit_hash = refs.commit_hash |
|                  ├─ files.repository_id = commit_files.repository_id |
|                  ├─ files.file_path = commit_files.file_path |
|                  ├─ files.blob_hash = commit_files.blob_hash |
|                  ├─ files.tree_hash = commit_files.tree_hash |
|                  └─ refs.ref_name = "HEAD" |
+------+

The results are the same (this is 3x faster than the second query).

NOTE: Every time I run the query it's in a freshly started server, so there is no cache thing going on here.

[kuba--]

Question (maybe not valid right now) - if we re-order NATURAL JOINS in the query (by priority mentioned by @erizocosmico) would it help?

[erizocosmico]

Not really. It's not about the natural join or not. It's the squashed table the one that takes all the time. I just can't figure out why two identical nodes consistently take such different times.