groupBy v2: Deadlock on deeply nested subqueries

[gianm]

Deeply nested groupBys can cause deadlocks, because they require a separate merge buffer on the broker for each layer beyond the first layer of the groupBy. Since the merge buffers are limited in number and are acquired one-by-one, two problems can occur:

• Case 1: a nested groupBy needs X buffers but numMergeBuffers < X, so it can never get what it needs
• Case 2: two nested groupBys each need X buffers, but numMergeBuffers < X * 2 - 1, so it's possible for them to deadlock (both might get X - 1 buffers and then neither of them can get the final buffer).

Better behavior would be:

• Case 1: the query should fail
• Case 2: buffer acquisition should be atomic, so the queries can proceed without deadlocks

[gianm]

#3806 proposes adding some doc blurbs about this, so if that patch goes through, then the fix to this issue should adjust those. They're in sql.md and broker.md.

[jihoonson]

I'm working on this.

[jihoonson]

Hi Gian, I'm investigating what the root cause and its fundamental solution are.

IMHO, the root cause looks that a nested group-by query needs to allocate two or more merge buffers during preparing query execution even though at most one query block (containing a group-by subquery) can be executed at the same time. So, I think it would be better if fine-grained memory management is possible. Of course we still need to make queries fail if they cannot acquire sufficient memory for certain amount of time.

What do you think?

[gianm]

@jihoonson What do you have in mind for more fine-grained memory management?

[jihoonson]

Currently, it is required to acquire all merge buffers for every subquery before query execution. For example, given a nested group-by query consisting of an inner group-by and an outer group-by, two merge buffers need to be acquired before actual query execution.
However, since the outer group-by should be executed after the inner one completes, this query can be executed with only one merge buffer.

So, it would be better if we can postpone buffer acquisition until it is really needed and release the acquired buffer as soon as the buffer is not needed anymore. I think merge buffers can be acquired before executing a subquery and released as the processing of the subquery completes.

[gianm]

Deeply nested groupBys still require two merge buffers at once though. If you do groupBy A -> groupBy B -> table, then when groupBy A is running, it needs its own merge buffer to put results in, but also it needs B's merge buffer to read B's results from.

[jihoonson]

Oh, you are right. So, does it make sense to always use at most two merge buffers for deeply nested groupBys like groupBy A -> groupBy B -> groupBy C -> table?

[gianm]

I think so yes. We still have the deadlock problem to fix with two merge buffers, but two merge buffers is better than unbounded!

[jihoonson]

Thanks!
I think the deadlock problem can be avoided by guaranteeing the order of requests for buffer acquisition. For example, given a query of groupBy A -> groupBy B -> groupBy C -> table, the inner-most subquery (groupBy C -> table) requests a buffer first, and then its outer subquery (groupBy B -> groupBy C) requests a buffer. If it cannot acquire the buffer for certain amount of time, the query should fail at that point. If it can, release the buffer for the (groupBy C -> table) subquery, request a new buffer for (groupBy A -> groupBy B).