Thread: Re: Proposal: "query_work_mem" GUC, to distribute working memory to the query's individual operators

On Tue, Jan 21, 2025 at 1:26 PM Jeff Davis <pgsql@j-davis.com> wrote:
>
> On Fri, 2025-01-10 at 10:00 -0800, James Hunter wrote:
> > How should “query_work_mem” work? Let’s start with an example:
> > suppose
> > we have an OLAP query that has 2 Hash Joins, and no other operators
> > that use work_mem.
>
> So we plan first, and then assign available memory afterward? If we do
> it that way, then the costing will be inaccurate, because the original
> costs are based on the original work_mem.
>
> It may be better than killing the query, but not ideal.

As you point out, the outcome is better, but not ideal. My intuition
is that an "ideal" solution would increase query compilation times
beyond what customers would accept...

But at least the outcome, if not ideal is better than killing the
query! So it is a net improvement.

> > I propose that we add a “query_work_mem” GUC, which works by
> > distributing (using some algorithm to be described in a follow-up
> > email) the entire “query_work_mem” to the query’s operators. And then
> > each operator will spill when it exceeds its own work_mem limit. So
> > we’ll preserve the existing “spill” logic as much as possible.
>
> The description above sounds too "top-down" to me. That may work, but
> has the disadvantage that costing has already happened. We should also
> consider:
>
> * Reusing the path generation infrastructure so that both "high memory"
> and "low memory" paths can be considered, and if a path requires too
> much memory in aggregate, then it would be rejected in favor of a path
> that uses less memory. This feels like it fits within the planner
> architecture the best, but it also might lead to a path explosion, so
> we may need additional controls.
>
> * Some kind of negotiation where the top level of the planner finds
> that the plan uses too much memory, and replans some or all of it. (I
> think is similar to what you described as the "feedback loop" later in
> your email.) I agree that this is complex and may not have enough
> benefit to justify.

Generating "high memory" vs. "low memory" paths would be tricky,
because the definition of "high" vs. "low" depends on the entire path
tree, not just on a single path node. So I think it would quickly lead
to a state-space explosion, as you mention.

And I think negotiation has the same problem: it's based on the entire
tree, not just an individual path node. I think the general problem is
not so much "top-down" vs. "bottom-up", as "individual path node" vs.
"entire path tree." Today, PostgreSQL costs each path node
individually, by referring to the static "work_mem" GUC. In any
attempt to improve the optimizer's choice, I think we'd have to cost
the entire path tree. And there are many more trees than there are
tree nodes.

For example, the decision whether to prefer a Nested Loop vs. a Hash
Join that takes 2 MB of working memory, depends on what the query's
other joins are doing.

At any rate, I think we can solve the problem of "killing the query"
now; and then worry, in the future, about the ideal solution of how to
pick the optimal execution plan.

> Regards,
>         Jeff Davis

Thanks for your comments!
James

On Fri, 2025-01-24 at 17:04 -0800, James Hunter wrote:
> Generating "high memory" vs. "low memory" paths would be tricky,
> because the definition of "high" vs. "low" depends on the entire path
> tree, not just on a single path node. So I think it would quickly
> lead
> to a state-space explosion, as you mention.

At first, it appears to lead to an explosion, but there are a lot of
ways to prune early. Many operators, like an index scan, don't even
need to track memory, so they'd just have the one path. Other operators
can just generate a low memory path because estimates show that it's
unlikely to need more than that. And if there's a blocking operator,
then that resets the memory requirement, pruning the space further.

And I assume you are talking about analytic queries with reasonably
large values of work_mem anyway. That justifies a bit more planning
time -- no need to generate extra paths for cheap queries.

Maybe my idea doesn't work out, but I think it's too early to dismiss
it.

Regards,
    Jeff Davis