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

From: Jeff Davis <[email-masked]>
Date: Tue, 21 Jan 2025 13:26:52 -0800

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.

> -- Second, we could say, instead: the small Hash Join is *highly
> unlikely* to use > 1 MB, so let’s just give both Hash Joins 1023 MB,
> expecting that the small Hash Join won’t use more than 1 MB of its
> 1023 MB allotment anyway, so we won’t run OOM. In effect, we’re
> oversubscribing, betting that the small Hash Join will just stay
> within some smaller, “unenforced” memory limit.
> 
> In this example, this bet is probably fine — but it won’t work in
> general. I don’t want to be in the business of gambling with customer
> resources: if the small Hash Join is unlikely to use more than 1 MB,
> then let’s just assign it 1 MB of work_mem.

I like this idea. Operators that either know they don't need much
memory, or estimate that they don't need much memory, can constrain
themselves. That would protect against misestimations and advertise to
the higher levels of the planner how much memory the operator actually
wants. Right now, the planner doesn't know which operators need a lot
of memory and which ones don't need any significant amount at all.

The challenge, of course, is what the higher levels of the planner
would do with that information, which goes to the rest of your
proposal. But tracking the information seems very reasonable to me.

> 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.

Regards,
	Jeff Davis

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 22 Jan 2025 21:48:51 +0100

> of memory and which ones don't need any significant amount at all.

I'm not sure I like the idea that much.

At first restricting the operator to the amount the optimizer predicts
will be needed seems reasonable, because that's generally the best idea
of memory usage we have without running the query.

But these estimates are often pretty fundamentally unreliable - maybe
not for simple examples, but once you put an aggregate on top of a join,
the errors can be pretty wild. And allowing the operator to still use
more work_mem makes this more adaptive. I suspect forcing the operator
to adhere to the estimated work_mem might make this much worse (but I
haven't tried, maybe spilling to temp files is not that bad).

> proposal. But tracking the information seems very reasonable to me.

I agree. Tracking additional information seems like a good idea, but
it's not clear to me what would the planner use this. I can imagine
various approaches - e.g. we might do the planning as usual and then
distribute the query_work_mem between the nodes in proportion to the
estimated amount of memory. But it all seems like a very ad hoc
heuristics, and easy to confuse / make the wrong decision.

> your email.) I agree that this is complex and may not have enough

Right, it seems rather at odds with the bottom-up construction of paths.
The amount of memory an operator may use seems like a pretty fundamental
information, but if it's available only after the whole plan is built,
that seems ... not great.

I don't know if generating (and keeping) low/high-memory paths is quite
feasible. Isn't that really a continuum for many paths? A hash join may
need very little memory (with batching) or a lot of memory (if keeping
everything in memory), so how would this work? Would we generate paths
for a range of work_mem values (with different costs)?

regards

-- 
Tomas Vondra

---

From: James Hunter <[email-masked]>
Date: Fri, 24 Jan 2025 17:04:40 -0800

> 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.

> your email.) I agree that this is complex and may not have enough

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.

>         Jeff Davis

Thanks for your comments!
James

---

From: Jeff Davis <[email-masked]>
Date: Fri, 24 Jan 2025 17:48:44 -0800

> 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

---

From: James Hunter <[email-masked]>
Date: Mon, 10 Feb 2025 19:09:25 -0800

On Fri, Jan 24, 2025 at 5:48 PM Jeff Davis <[email-masked]> wrote:
> ways to prune early. ...

I think it makes sense to split the work into two parts: one part that
improves SQL execution, and a second part that improves the optimizer,
to reflect the improvements to execution.

It seems better to me to wait until we have the ability to enforce
memory limits, before worrying about ways to generate different paths
with different memory limits. Then we would be able to tune the
optimizer heuristics based on the actual executor, instead of
extrapolating how the executor would behave under different memory
limits.

James

---

From: Jeff Davis <[email-masked]>
Date: Tue, 11 Feb 2025 10:00:14 -0800

> to reflect the improvements to execution.

I like the idea to store the value of work_mem in the
path/plan/executor nodes, and use that at execution time rather than
the GUC directly.

IIUC, that would allow an extension to do what you want, right? A
planner hook could just walk the tree and edit those values for
individual nodes, and the executor would enforce them.

Regards,
	Jeff Davis

---

From: James Hunter <[email-masked]>
Date: Tue, 11 Feb 2025 10:39:51 -0800

> individual nodes, and the executor would enforce them.

Yes, exactly!

* The Path would store "nbytes" (= the optimizer's estimate of how
much working memory a given Path will use), to allow for future
optimizer logic to consider memory usage when choosing the best Path.

* The Plan would store a copy of "nbytes," along with "work_mem," and
the executor would enforce work_mem. A "(work_mem on)" option to the
"EXPLAIN" command would display both "nbytes" and "work_mem", per Plan
node.

* Either built-in logic or an extensibility hook would set "work_mem"
on each individual Plan node, based on whatever heuristic or rule it
chooses.

Right now, my prototype sets "work_mem" inside ExecInitNode().

Thanks,
James

---

From: Jeff Davis <[email-masked]>
Date: Tue, 11 Feb 2025 14:04:45 -0800

> "EXPLAIN" command would display both "nbytes" and "work_mem", per

Storing work_mem in each Plan node, and using that to enforce the
memory limit (rather than using the GUC directly), seems
uncontroversial to me. I'd suggest a standalone patch.

Storing the optimizer's estimate of the memory wanted also sounds like
a good idea. Let's pick a better name than "nbytes" though; maybe
"requested_mem" or something? This change would make it a lot easier
for an extension to adjust the per-node-work_mem, and also seems like
good infrastructure for anything we build into the planner later. I
suggest a standalone patch for this, as well.

Can you write a useful extension with just the above two core patches?

Regards,
	Jeff Davis