Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rHeyb-003Zp9-Us for pgsql-hackers@arkaria.postgresql.org; Mon, 25 Dec 2023 07:02:14 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1rHeyZ-000HiG-Ie for pgsql-hackers@arkaria.postgresql.org; Mon, 25 Dec 2023 07:02:11 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rHeyY-000Hi7-U2 for pgsql-hackers@lists.postgresql.org; Mon, 25 Dec 2023 07:02:11 +0000 Received: from mail-yb1-xb31.google.com ([2607:f8b0:4864:20::b31]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1rHeyR-00C5fh-Jr for pgsql-hackers@postgresql.org; Mon, 25 Dec 2023 07:02:09 +0000 Received: by mail-yb1-xb31.google.com with SMTP id 3f1490d57ef6-dbd029beef4so3563433276.0 for ; Sun, 24 Dec 2023 23:02:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1703487723; x=1704092523; darn=postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=15WW1ffFI+Vc4CNRHALalF7N3kLvCmwzugVWcfnojiE=; b=TVXGAcDL13ZwxFZZQD4nrhTJM7oY5x4Vbrn73/LkCkKKYW3mAGFlpZkR5xcw+/9x9F 3cj3orKtRUV22uME+WwpaxbP5cQL9n6hdxSb6FdUZLdVelsvArriOWWKtlF/19+NRsCM SPYXqwilYFX91hbe0/owXgwYnI3WNKHtg8Yp11/GsRvtIuwZb+oxH/0QkgSeLdqP65qJ /HL5CitQXXve5efMnMwosSTYq5JOC4CDPnDiG55NjOKywkgieQaY4oAH+bdcXxFMNuNP BjFkQWOMCrPpOJFmwg0sAz+JI57FMC8doPvl/XBP6WQMmRor3DOlUoXwK9pE28cXisBH 6aAA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1703487723; x=1704092523; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=15WW1ffFI+Vc4CNRHALalF7N3kLvCmwzugVWcfnojiE=; b=kRcTr28rB+CbbeB5Cnwyfx6fuIt8ePp9oXIrsmG46jCpqkyL0JKn4hxQnbBnEhObVd B7sipO5eNzfiITnZGmkin1C1WWfQItvpaValsZIL/M3C35arsbzojGzKpbpO5R8Q6jHi IrPtj4nd/SAdUzGbpbTscFgicSDfUE5gE6i1zvLkd4ubx8lHE5oihjXSkqdUhCqIXXKd TcSKEhNTR3WzNb82cQmei+ks0e/lDowytYLExR12xCKHSqKdxPcme/ZsyaZtPYuJzpKR 1UpCBoN52BCMregwwhBaSO99Wvhhng5DlFIqg/x0eyfUeRqGfcOZgr4taMVeOX5Njw5+ xhHw== X-Gm-Message-State: AOJu0YygMRk0qt+nt9kASM9VOPeSpNiTlUYgotWMbE9W1KQdO9KTlfwo LDEcsUHu8OyINc1H/2PVVMtdRY6m+6uGblDNYtg= X-Google-Smtp-Source: AGHT+IF8zxkfBmjTh5wqW+ZU7fIHVFm/PdvPb5rtq+dJ74QyhQPm/QuKFp834k61BQ3BYzYp7vlznP3BsaOAX1B84UM= X-Received: by 2002:a81:ac0c:0:b0:5ea:6ac0:3c9c with SMTP id k12-20020a81ac0c000000b005ea6ac03c9cmr2264191ywh.29.1703487722792; Sun, 24 Dec 2023 23:02:02 -0800 (PST) MIME-Version: 1.0 References: <1724688.1688837323@sss.pgh.pa.us> In-Reply-To: From: Richard Guo Date: Mon, 25 Dec 2023 15:01:51 +0800 Message-ID: Subject: Re: Check lateral references within PHVs for memoize cache keys To: Tom Lane Cc: PostgreSQL-development , David Rowley Content-Type: multipart/alternative; boundary="00000000000098acfb060d5024b0" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --00000000000098acfb060d5024b0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thu, Jul 13, 2023 at 3:12=E2=80=AFPM Richard Guo wrote: > So I'm wondering if it'd be better that we move all this logic of > computing additional lateral references within PHVs to get_memoize_path, > where we can examine only PHVs that are evaluated at innerrel. And > considering that these lateral refs are only used by Memoize, it seems > more sensible to compute them there. But I'm a little worried that > doing this would make get_memoize_path too expensive. > > Please see v4 patch for this change. > I'd like to add that not checking PHVs for lateral references can lead to performance regressions with Memoize node. For instance, -- by default, enable_memoize is on regression=3D# explain (analyze, costs off) select * from tenk1 t1 left joi= n lateral (select *, t1.four as x from tenk1 t2) s on t1.two =3D s.two; QUERY PLAN ---------------------------------------------------------------------------= ---------- Nested Loop Left Join (actual time=3D0.028..105245.547 rows=3D50000000 loo= ps=3D1) -> Seq Scan on tenk1 t1 (actual time=3D0.011..3.760 rows=3D10000 loops= =3D1) -> Memoize (actual time=3D0.010..8.051 rows=3D5000 loops=3D10000) Cache Key: t1.two Cache Mode: logical Hits: 0 Misses: 10000 Evictions: 9999 Overflows: 0 Memory Usage: 1368kB -> Seq Scan on tenk1 t2 (actual time=3D0.004..3.594 rows=3D5000 loops=3D10000) Filter: (t1.two =3D two) Rows Removed by Filter: 5000 Planning Time: 1.943 ms Execution Time: 106806.043 ms (11 rows) -- turn enable_memoize off regression=3D# set enable_memoize to off; SET regression=3D# explain (analyze, costs off) select * from tenk1 t1 left joi= n lateral (select *, t1.four as x from tenk1 t2) s on t1.two =3D s.two; QUERY PLAN ---------------------------------------------------------------------------= -- Nested Loop Left Join (actual time=3D0.048..44831.707 rows=3D50000000 loop= s=3D1) -> Seq Scan on tenk1 t1 (actual time=3D0.026..2.340 rows=3D10000 loops= =3D1) -> Seq Scan on tenk1 t2 (actual time=3D0.002..3.282 rows=3D5000 loops= =3D10000) Filter: (t1.two =3D two) Rows Removed by Filter: 5000 Planning Time: 0.641 ms Execution Time: 46472.609 ms (7 rows) As we can see, when Memoize enabled (which is the default setting), the execution time increases by around 129.83%, indicating a significant performance regression. This is caused by that we fail to realize that 't1.four', which is from the PHV, should be included in the cache keys. And that makes us have to purge the entire cache every time we get a new outer tuple. This is also implied by the abnormal Memoize runtime stats: Hits: 0 Misses: 10000 Evictions: 9999 Overflows: 0 This regression can be fixed by the patch here. After applying the v4 patch, 't1.four' is added into the cache keys, and the same query runs much faster. regression=3D# explain (analyze, costs off) select * from tenk1 t1 left joi= n lateral (select *, t1.four as x from tenk1 t2) s on t1.two =3D s.two; QUERY PLAN ---------------------------------------------------------------------------= ------ Nested Loop Left Join (actual time=3D0.060..20446.004 rows=3D50000000 loop= s=3D1) -> Seq Scan on tenk1 t1 (actual time=3D0.027..5.845 rows=3D10000 loops= =3D1) -> Memoize (actual time=3D0.001..0.209 rows=3D5000 loops=3D10000) Cache Key: t1.two, t1.four Cache Mode: binary Hits: 9996 Misses: 4 Evictions: 0 Overflows: 0 Memory Usage: 5470kB -> Seq Scan on tenk1 t2 (actual time=3D0.005..3.659 rows=3D5000 loops=3D4) Filter: (t1.two =3D two) Rows Removed by Filter: 5000 Planning Time: 0.579 ms Execution Time: 21756.598 ms (11 rows) Comparing the first plan and the third plan, this query runs ~5 times faster. Thanks Richard --00000000000098acfb060d5024b0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

On Thu, Jul 13, 2023 at 3:12=E2=80=AFPM R= ichard Guo <guofenglinux@gmail= .com> wrote:
=
So I'm wondering if it= 'd be better that we move all this logic of
computing additional lat= eral references within PHVs to get_memoize_path,
where we can examine on= ly PHVs that are evaluated at innerrel.=C2=A0 And
considering that these= lateral refs are only used by Memoize, it seems
more sensible to comput= e them there.=C2=A0 But I'm a little worried that
doing this would m= ake get_memoize_path too expensive.

Please see v4 patch for this cha= nge.

I'd like to add = that not checking PHVs for lateral references can lead
to performance re= gressions with Memoize node.=C2=A0 For instance,

-- by default, enab= le_memoize is on
regression=3D# explain (analyze, costs off) select * fr= om tenk1 t1 left join lateral (select *, t1.four as x from tenk1 t2) s on t= 1.two =3D s.two;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0QUERY PLAN
----------------------------------------------------------= ---------------------------
=C2=A0Nested Loop Left Join (actual time=3D0= .028..105245.547 rows=3D50000000 loops=3D1)
=C2=A0 =C2=A0-> =C2=A0Seq= Scan on tenk1 t1 (actual time=3D0.011..3.760 rows=3D10000 loops=3D1)
= =C2=A0 =C2=A0-> =C2=A0Memoize (actual time=3D0.010..8.051 rows=3D5000 lo= ops=3D10000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Cache Key: t1.two
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Cache Mode: logical
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0Hits: 0 =C2=A0Misses: 10000 =C2=A0Evictions: 9999 =C2=A0Overfl= ows: 0 =C2=A0Memory Usage: 1368kB
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0->= ; =C2=A0Seq Scan on tenk1 t2 (actual time=3D0.004..3.594 rows=3D5000 loops= =3D10000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Filter:= (t1.two =3D two)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0Rows Removed by Filter: 5000
=C2=A0Planning Time: 1.943 ms
=C2=A0E= xecution Time: 106806.043 ms
(11 rows)

-- turn enable_memoize off=
regression=3D# set enable_memoize to off;
SET
regression=3D# expl= ain (analyze, costs off) select * from tenk1 t1 left join lateral (select *= , t1.four as x from tenk1 t2) s on t1.two =3D s.two;
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0QUERY PLAN
----------------------------------= -------------------------------------------
=C2=A0Nested Loop Left Join = (actual time=3D0.048..44831.707 rows=3D50000000 loops=3D1)
=C2=A0 =C2=A0= -> =C2=A0Seq Scan on tenk1 t1 (actual time=3D0.026..2.340 rows=3D10000 l= oops=3D1)
=C2=A0 =C2=A0-> =C2=A0Seq Scan on tenk1 t2 (actual time=3D0= .002..3.282 rows=3D5000 loops=3D10000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0Filter: (t1.two =3D two)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Rows Remov= ed by Filter: 5000
=C2=A0Planning Time: 0.641 ms
=C2=A0Execution Time= : 46472.609 ms
(7 rows)

As we can see, when Memoize enabled (whic= h is the default setting), the
execution time increases by around 129.83= %, indicating a significant
performance regression.

This is cause= d by that we fail to realize that 't1.four', which is from
the P= HV, should be included in the cache keys.=C2=A0 And that makes us have
t= o purge the entire cache every time we get a new outer tuple.=C2=A0 This is=
also implied by the abnormal Memoize runtime stats:

=C2=A0 =C2= =A0 Hits: 0 =C2=A0Misses: 10000 =C2=A0Evictions: 9999 =C2=A0Overflows: 0
This regression can be fixed by the patch here.=C2=A0 After applying t= he v4
patch, 't1.four' is added into the cache keys, and the sam= e query runs
much faster.

regression=3D# explain (analyze, costs = off) select * from tenk1 t1 left join lateral (select *, t1.four as x from = tenk1 t2) s on t1.two =3D s.two;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0QUERY PLAN
------------------------------------------------= ---------------------------------
=C2=A0Nested Loop Left Join (actual ti= me=3D0.060..20446.004 rows=3D50000000 loops=3D1)
=C2=A0 =C2=A0-> =C2= =A0Seq Scan on tenk1 t1 (actual time=3D0.027..5.845 rows=3D10000 loops=3D1)=
=C2=A0 =C2=A0-> =C2=A0Memoize (actual time=3D0.001..0.209 rows=3D500= 0 loops=3D10000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Cache Key: t1.two, t1= .four
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Cache Mode: binary
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0Hits: 9996 =C2=A0Misses: 4 =C2=A0Evictions: 0 =C2= =A0Overflows: 0 =C2=A0Memory Usage: 5470kB
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0-> =C2=A0Seq Scan on tenk1 t2 (actual time=3D0.005..3.659 rows=3D5= 000 loops=3D4)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Fi= lter: (t1.two =3D two)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0Rows Removed by Filter: 5000
=C2=A0Planning Time: 0.579 ms
=C2= =A0Execution Time: 21756.598 ms
(11 rows)

Comparing the first pla= n and the third plan, this query runs ~5 times
faster.

Thanks
= Richard
--00000000000098acfb060d5024b0--