public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v48 2/3] Filling gaps in jsonb
26+ messages / 7 participants
[nested] [flat]
* [PATCH v48 2/3] Filling gaps in jsonb
@ 2020-12-31 14:19 Dmitrii Dolgov <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Dmitrii Dolgov @ 2020-12-31 14:19 UTC (permalink / raw)
Introduces two new modes for jsonb assignment:
* Appending array elements on the specified position, gaps filled with
nulls (similar to JavaScript behavior). This mode also instructs to
create the whole path in a jsonb object if some part of the path (more
than just the last element) is not present.
* Assigning keeps array positions consistent by prevent prepending of
elements.
Originally proposed by Nikita Glukhov based on polymorphic subscripting
patch, but transformed into an independent change.
---
doc/src/sgml/json.sgml | 24 +++
src/backend/utils/adt/jsonfuncs.c | 226 ++++++++++++++++++++++++++--
src/test/regress/expected/jsonb.out | 135 +++++++++++++++++
src/test/regress/sql/jsonb.sql | 81 ++++++++++
4 files changed, 451 insertions(+), 15 deletions(-)
diff --git a/doc/src/sgml/json.sgml b/doc/src/sgml/json.sgml
index 3ace5e444b..07bd19f974 100644
--- a/doc/src/sgml/json.sgml
+++ b/doc/src/sgml/json.sgml
@@ -648,6 +648,30 @@ UPDATE table_name SET jsonb_field['a'] = '1';
-- Where jsonb_field was NULL, it is now [1]
UPDATE table_name SET jsonb_field[0] = '1';
+</programlisting>
+
+ If an index is specified for an array containing too few elements,
+ <literal>NULL</literal> elements will be appended until the index is reachable
+ and the value can be set.
+
+<programlisting>
+-- Where jsonb_field was [], it is now [null, null, 2];
+-- where jsonb_field was [0], it is now [0, null, 2]
+UPDATE table_name SET jsonb_field[2] = '2';
+</programlisting>
+
+ A <type>jsonb</type> value will accept assignments to nonexistent subscript
+ paths as long as the last existing path key is an object or an array. Since
+ the final subscript is not traversed, it may be an object key. Nested arrays
+ will be created and <literal>NULL</literal>-padded according to the path until
+ the value can be placed appropriately.
+
+<programlisting>
+-- Where jsonb_field was {}, it is now {'a': [{'b': 1}]}
+UPDATE table_name SET jsonb_field['a'][0]['b'] = '1';
+
+-- Where jsonb_field was [], it is now [{'a': 1}]
+UPDATE table_name SET jsonb_field[0]['a'] = '1';
</programlisting>
</para>
diff --git a/src/backend/utils/adt/jsonfuncs.c b/src/backend/utils/adt/jsonfuncs.c
index 5a0ba6b220..f14f6c3191 100644
--- a/src/backend/utils/adt/jsonfuncs.c
+++ b/src/backend/utils/adt/jsonfuncs.c
@@ -44,6 +44,8 @@
#define JB_PATH_INSERT_AFTER 0x0010
#define JB_PATH_CREATE_OR_INSERT \
(JB_PATH_INSERT_BEFORE | JB_PATH_INSERT_AFTER | JB_PATH_CREATE)
+#define JB_PATH_FILL_GAPS 0x0020
+#define JB_PATH_CONSISTENT_POSITION 0x0040
/* state for json_object_keys */
typedef struct OkeysState
@@ -1634,14 +1636,116 @@ jsonb_set_element(Jsonb* jb, Datum *path, int path_len,
it = JsonbIteratorInit(&jb->root);
- res = setPath(&it, path, path_nulls, path_len, &state, 0,
- newval, JB_PATH_CREATE);
+ res = setPath(&it, path, path_nulls, path_len, &state, 0, newval,
+ JB_PATH_CREATE | JB_PATH_FILL_GAPS |
+ JB_PATH_CONSISTENT_POSITION);
pfree(path_nulls);
PG_RETURN_JSONB_P(JsonbValueToJsonb(res));
}
+static void
+push_null_elements(JsonbParseState **ps, int num)
+{
+ JsonbValue null;
+
+ null.type = jbvNull;
+
+ while (num-- > 0)
+ pushJsonbValue(ps, WJB_ELEM, &null);
+}
+
+/*
+ * Prepare a new structure containing nested empty objects and arrays
+ * corresponding to the specified path, and assign a new value at the end of
+ * this path. E.g. the path [a][0][b] with the new value 1 will produce the
+ * structure {a: [{b: 1}]}.
+ *
+ * Called is responsible to make sure such path does not exist yet.
+ */
+static void
+push_path(JsonbParseState **st, int level, Datum *path_elems,
+ bool *path_nulls, int path_len, JsonbValue *newval)
+{
+ /*
+ * tpath contains expected type of an empty jsonb created at each level
+ * higher or equal than the current one, either jbvObject or jbvArray.
+ * Since it contains only information about path slice from level to the
+ * end, the access index must be normalized by level.
+ */
+ enum jbvType *tpath = palloc0((path_len - level) * sizeof(enum jbvType));
+ long lindex;
+ JsonbValue newkey;
+
+ /*
+ * Create first part of the chain with beginning tokens. For the current
+ * level WJB_BEGIN_OBJECT/WJB_BEGIN_ARRAY was already created, so start
+ * with the next one.
+ */
+ for(int i = level + 1; i < path_len; i++)
+ {
+ char *c, *badp;
+
+ if (path_nulls[i])
+ break;
+
+ /*
+ * Try to convert to an integer to find out the expected type,
+ * object or array.
+ */
+ c = TextDatumGetCString(path_elems[i]);
+ errno = 0;
+ lindex = strtol(c, &badp, 10);
+ if (errno != 0 || badp == c || *badp != '\0' || lindex > INT_MAX ||
+ lindex < INT_MIN)
+ {
+ /* text, an object is expected */
+ newkey.type = jbvString;
+ newkey.val.string.len = VARSIZE_ANY_EXHDR(path_elems[i]);
+ newkey.val.string.val = VARDATA_ANY(path_elems[i]);
+
+ (void) pushJsonbValue(st, WJB_BEGIN_OBJECT, NULL);
+ (void) pushJsonbValue(st, WJB_KEY, &newkey);
+
+ tpath[i - level] = jbvObject;
+ }
+ else
+ {
+ /* integer, an array is expected */
+ (void) pushJsonbValue(st, WJB_BEGIN_ARRAY, NULL);
+
+ push_null_elements(st, lindex);
+
+ tpath[i - level] = jbvArray;
+ }
+
+ }
+
+ /* Insert an actual value for either an object or array */
+ if (tpath[(path_len - level) - 1] == jbvArray)
+ {
+ (void) pushJsonbValue(st, WJB_ELEM, newval);
+ }
+ else
+ (void) pushJsonbValue(st, WJB_VALUE, newval);
+
+ /*
+ * Close everything up to the last but one level. The last one will be
+ * closed outside of this function.
+ */
+ for(int i = path_len - 1; i > level; i--)
+ {
+ if (path_nulls[i])
+ break;
+
+ if (tpath[i - level] == jbvObject)
+ (void) pushJsonbValue(st, WJB_END_OBJECT, NULL);
+ else
+ (void) pushJsonbValue(st, WJB_END_ARRAY, NULL);
+ }
+}
+
/*
* Return the text representation of the given JsonbValue.
*/
@@ -4782,6 +4886,21 @@ IteratorConcat(JsonbIterator **it1, JsonbIterator **it2,
* Bits JB_PATH_INSERT_BEFORE and JB_PATH_INSERT_AFTER in op_type
* behave as JB_PATH_CREATE if new value is inserted in JsonbObject.
*
+ * If JB_PATH_FILL_GAPS bit is set, this will change an assignment logic in
+ * case if target is an array. The assignment index will not be restricted by
+ * number of elements in the array, and if there are any empty slots between
+ * last element of the array and a new one they will be filled with nulls. If
+ * the index is negative, it still will be considered an an index from the end
+ * of the array. Of a part of the path is not present and this part is more
+ * than just one last element, this flag will instruct to create the whole
+ * chain of corresponding objects and insert the value.
+ *
+ * JB_PATH_CONSISTENT_POSITION for an array indicates that the called wants to
+ * keep values with fixed indices. Indices for existing elements could be
+ * changed (shifted forward) in case if the array is prepended with a new value
+ * and a negative index out of the range, so this behavior will be prevented
+ * and return an error.
+ *
* All path elements before the last must already exist
* whatever bits in op_type are set, or nothing is done.
*/
@@ -4876,6 +4995,8 @@ setPathObject(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
memcmp(k.val.string.val, VARDATA_ANY(path_elems[level]),
k.val.string.len) == 0)
{
+ done = true;
+
if (level == path_len - 1)
{
/*
@@ -4895,7 +5016,6 @@ setPathObject(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
(void) pushJsonbValue(st, WJB_KEY, &k);
(void) pushJsonbValue(st, WJB_VALUE, newval);
}
- done = true;
}
else
{
@@ -4940,6 +5060,31 @@ setPathObject(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
}
}
}
+
+ /*
+ * If we got here there are only few possibilities:
+ * - no target path was found, and an open object with some keys/values was
+ * pushed into the state
+ * - an object is empty, only WJB_BEGIN_OBJECT is pushed
+ *
+ * In both cases if instructed to create the path when not present,
+ * generate the whole chain of empty objects and insert the new value
+ * there.
+ */
+ if (!done && (op_type & JB_PATH_FILL_GAPS) && (level < path_len - 1))
+ {
+ JsonbValue newkey;
+
+ newkey.type = jbvString;
+ newkey.val.string.len = VARSIZE_ANY_EXHDR(path_elems[level]);
+ newkey.val.string.val = VARDATA_ANY(path_elems[level]);
+
+ (void) pushJsonbValue(st, WJB_KEY, &newkey);
+ (void) push_path(st, level, path_elems, path_nulls,
+ path_len, newval);
+
+ /* Result is closed with WJB_END_OBJECT outside of this function */
+ }
}
/*
@@ -4978,25 +5123,48 @@ setPathArray(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
if (idx < 0)
{
if (-idx > nelems)
- idx = INT_MIN;
+ {
+ /*
+ * If asked to keep elements position consistent, it's not allowed
+ * to prepend the array.
+ */
+ if (op_type & JB_PATH_CONSISTENT_POSITION)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("path element at position %d is out of range: %d",
+ level + 1, idx)));
+ else
+ idx = INT_MIN;
+ }
else
idx = nelems + idx;
}
- if (idx > 0 && idx > nelems)
- idx = nelems;
+ /*
+ * Filling the gaps means there are no limits on the positive index are
+ * imposed, we can set any element. Otherwise limit the index by nelems.
+ */
+ if (!(op_type & JB_PATH_FILL_GAPS))
+ {
+ if (idx > 0 && idx > nelems)
+ idx = nelems;
+ }
/*
* if we're creating, and idx == INT_MIN, we prepend the new value to the
* array also if the array is empty - in which case we don't really care
* what the idx value is
*/
-
if ((idx == INT_MIN || nelems == 0) && (level == path_len - 1) &&
(op_type & JB_PATH_CREATE_OR_INSERT))
{
Assert(newval != NULL);
+
+ if (op_type & JB_PATH_FILL_GAPS && nelems == 0 && idx > 0)
+ push_null_elements(st, idx);
+
(void) pushJsonbValue(st, WJB_ELEM, newval);
+
done = true;
}
@@ -5007,6 +5175,8 @@ setPathArray(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
if (i == idx && level < path_len)
{
+ done = true;
+
if (level == path_len - 1)
{
r = JsonbIteratorNext(it, &v, true); /* skip */
@@ -5024,8 +5194,6 @@ setPathArray(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
if (op_type & (JB_PATH_INSERT_AFTER | JB_PATH_REPLACE))
(void) pushJsonbValue(st, WJB_ELEM, newval);
-
- done = true;
}
else
(void) setPath(it, path_elems, path_nulls, path_len,
@@ -5053,14 +5221,42 @@ setPathArray(JsonbIterator **it, Datum *path_elems, bool *path_nulls,
(void) pushJsonbValue(st, r, r < WJB_BEGIN_ARRAY ? &v : NULL);
}
}
-
- if ((op_type & JB_PATH_CREATE_OR_INSERT) && !done &&
- level == path_len - 1 && i == nelems - 1)
- {
- (void) pushJsonbValue(st, WJB_ELEM, newval);
- }
}
}
+
+ if ((op_type & JB_PATH_CREATE_OR_INSERT) && !done && level == path_len - 1)
+ {
+ /*
+ * If asked to fill the gaps, idx could be bigger than nelems,
+ * so prepend the new element with nulls if that's the case.
+ */
+ if (op_type & JB_PATH_FILL_GAPS && idx > nelems)
+ push_null_elements(st, idx - nelems);
+
+ (void) pushJsonbValue(st, WJB_ELEM, newval);
+ done = true;
+ }
+
+ /*
+ * If we got here there are only few possibilities:
+ * - no target path was found, and an open array with some keys/values was
+ * pushed into the state
+ * - an array is empty, only WJB_BEGIN_ARRAY is pushed
+ *
+ * In both cases if instructed to create the path when not present,
+ * generate the whole chain of empty objects and insert the new value
+ * there.
+ */
+ if (!done && (op_type & JB_PATH_FILL_GAPS) && (level < path_len - 1))
+ {
+ if (idx > 0)
+ push_null_elements(st, idx - nelems);
+
+ (void) push_path(st, level, path_elems, path_nulls,
+ path_len, newval);
+
+ /* Result is closed with WJB_END_OBJECT outside of this function */
+ }
}
/*
diff --git a/src/test/regress/expected/jsonb.out b/src/test/regress/expected/jsonb.out
index 46bf2e2353..5b5510c4fd 100644
--- a/src/test/regress/expected/jsonb.out
+++ b/src/test/regress/expected/jsonb.out
@@ -4999,6 +4999,141 @@ select * from test_jsonb_subscript;
3 | [1]
(3 rows)
+-- Fill the gaps logic
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[0]');
+update test_jsonb_subscript set test_json[5] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+--------------------------------
+ 1 | [0, null, null, null, null, 1]
+(1 row)
+
+update test_jsonb_subscript set test_json[-4] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+-----------------------------
+ 1 | [0, null, 1, null, null, 1]
+(1 row)
+
+update test_jsonb_subscript set test_json[-8] = '1';
+ERROR: path element at position 1 is out of range: -8
+select * from test_jsonb_subscript;
+ id | test_json
+----+-----------------------------
+ 1 | [0, null, 1, null, null, 1]
+(1 row)
+
+-- keep consistent values position
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+update test_jsonb_subscript set test_json[5] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+-----------------------------------
+ 1 | [null, null, null, null, null, 1]
+(1 row)
+
+-- create the whole path
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a'][0]['b'][0]['c'] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+----------------------------
+ 1 | {"a": [{"b": [{"c": 1}]}]}
+(1 row)
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a'][2]['b'][2]['c'][2] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+------------------------------------------------------------------
+ 1 | {"a": [null, null, {"b": [null, null, {"c": [null, null, 1]}]}]}
+(1 row)
+
+-- create the whole path with already existing keys
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"b": 1}');
+update test_jsonb_subscript set test_json['a'][0] = '2';
+select * from test_jsonb_subscript;
+ id | test_json
+----+--------------------
+ 1 | {"a": [2], "b": 1}
+(1 row)
+
+-- the start jsonb is an object, first subscript is treated as a key
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json[0]['a'] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+-----------------
+ 1 | {"0": {"a": 1}}
+(1 row)
+
+-- the start jsonb is an array
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+update test_jsonb_subscript set test_json[0]['a'] = '1';
+update test_jsonb_subscript set test_json[2]['b'] = '2';
+select * from test_jsonb_subscript;
+ id | test_json
+----+----------------------------
+ 1 | [{"a": 1}, null, {"b": 2}]
+(1 row)
+
+-- overwriting an existing path
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a']['b'][1] = '1';
+update test_jsonb_subscript set test_json['a']['b'][10] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+----------------------------------------------------------------------------
+ 1 | {"a": {"b": [null, 1, null, null, null, null, null, null, null, null, 1]}}
+(1 row)
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+update test_jsonb_subscript set test_json[0][0][0] = '1';
+update test_jsonb_subscript set test_json[0][0][1] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+------------
+ 1 | [[[1, 1]]]
+(1 row)
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a']['b'][10] = '1';
+update test_jsonb_subscript set test_json['a'][10][10] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+------------------------------------------------------------------------------------------------------------------------------------------------------
+ 1 | {"a": {"b": [null, null, null, null, null, null, null, null, null, null, 1], "10": [null, null, null, null, null, null, null, null, null, null, 1]}}
+(1 row)
+
+-- an empty sub element
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"a": {}}');
+update test_jsonb_subscript set test_json['a']['b']['c'][2] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+--------------------------------------
+ 1 | {"a": {"b": {"c": [null, null, 1]}}}
+(1 row)
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"a": []}');
+update test_jsonb_subscript set test_json['a'][1]['c'][2] = '1';
+select * from test_jsonb_subscript;
+ id | test_json
+----+---------------------------------------
+ 1 | {"a": [null, {"c": [null, null, 1]}]}
+(1 row)
+
-- jsonb to tsvector
select to_tsvector('{"a": "aaa bbb ddd ccc", "b": ["eee fff ggg"], "c": {"d": "hhh iii"}}'::jsonb);
to_tsvector
diff --git a/src/test/regress/sql/jsonb.sql b/src/test/regress/sql/jsonb.sql
index 20aa8fe0e2..0320db0ea4 100644
--- a/src/test/regress/sql/jsonb.sql
+++ b/src/test/regress/sql/jsonb.sql
@@ -1290,6 +1290,87 @@ update test_jsonb_subscript set test_json = NULL where id = 3;
update test_jsonb_subscript set test_json[0] = '1';
select * from test_jsonb_subscript;
+-- Fill the gaps logic
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[0]');
+
+update test_jsonb_subscript set test_json[5] = '1';
+select * from test_jsonb_subscript;
+
+update test_jsonb_subscript set test_json[-4] = '1';
+select * from test_jsonb_subscript;
+
+update test_jsonb_subscript set test_json[-8] = '1';
+select * from test_jsonb_subscript;
+
+-- keep consistent values position
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+
+update test_jsonb_subscript set test_json[5] = '1';
+select * from test_jsonb_subscript;
+
+-- create the whole path
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a'][0]['b'][0]['c'] = '1';
+select * from test_jsonb_subscript;
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a'][2]['b'][2]['c'][2] = '1';
+select * from test_jsonb_subscript;
+
+-- create the whole path with already existing keys
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"b": 1}');
+update test_jsonb_subscript set test_json['a'][0] = '2';
+select * from test_jsonb_subscript;
+
+-- the start jsonb is an object, first subscript is treated as a key
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json[0]['a'] = '1';
+select * from test_jsonb_subscript;
+
+-- the start jsonb is an array
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+update test_jsonb_subscript set test_json[0]['a'] = '1';
+update test_jsonb_subscript set test_json[2]['b'] = '2';
+select * from test_jsonb_subscript;
+
+-- overwriting an existing path
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a']['b'][1] = '1';
+update test_jsonb_subscript set test_json['a']['b'][10] = '1';
+select * from test_jsonb_subscript;
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '[]');
+update test_jsonb_subscript set test_json[0][0][0] = '1';
+update test_jsonb_subscript set test_json[0][0][1] = '1';
+select * from test_jsonb_subscript;
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{}');
+update test_jsonb_subscript set test_json['a']['b'][10] = '1';
+update test_jsonb_subscript set test_json['a'][10][10] = '1';
+select * from test_jsonb_subscript;
+
+-- an empty sub element
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"a": {}}');
+update test_jsonb_subscript set test_json['a']['b']['c'][2] = '1';
+select * from test_jsonb_subscript;
+
+delete from test_jsonb_subscript;
+insert into test_jsonb_subscript values (1, '{"a": []}');
+update test_jsonb_subscript set test_json['a'][1]['c'][2] = '1';
+select * from test_jsonb_subscript;
+
-- jsonb to tsvector
select to_tsvector('{"a": "aaa bbb ddd ccc", "b": ["eee fff ggg"], "c": {"d": "hhh iii"}}'::jsonb);
--
2.21.0
--m4t3wpskod5t4yye
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="v48-0003-Replace-assuming-a-composite-object-on-a-scalar.patch"
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-19 17:15 Andrei Lepikhov <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Andrei Lepikhov @ 2025-03-19 17:15 UTC (permalink / raw)
To: pgsql-hackers
On 6/3/2025 14:08, Andrei Lepikhov wrote:
> Hi,
>
> In case of NestLoop with parameterised inner semi-join for each outer
> tuple requires only a single tuple from its inner relation to produce a
> result. It seems that the same principle applies to an anti-join. This
> approach could effectively allow the Memoize node to enhance the
> performance of pulled-up EXISTS and NOT EXISTS sublinks.
>
> In attachment see a sketch of the feature. Since we are using single_row
> mode, adapting this method to cache semi-join inner results should not
> be extremely complex. However, I am unsure about potential corner cases
> and would appreciate any feedback or criticisms regarding this approach.
I found a corner case that breaks this approach: when NestLoop has a
join clause or a filter, it may filter inner tuples, thus scanning more
than only one time for each outer. You can see the reproduction script
in the attachment. Each of the reproduction queries throws the error:
ERROR: cache entry already complete
How can we be sure that semi or anti-join needs only one tuple? I think
it would be enough to control the absence of join clauses and filters in
the join. Unfortunately, we only have such a guarantee in the plan
creation stage (maybe even setrefs.c). So, it seems we need to invent an
approach like AlternativeSubplan.
--
regards, Andrei Lepikhov
Attachments:
[application/sql] repro.sql (1.3K, ../../[email protected]/2-repro.sql)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-20 06:02 David Rowley <[email protected]>
parent: Andrei Lepikhov <[email protected]>
0 siblings, 3 replies; 26+ messages in thread
From: David Rowley @ 2025-03-20 06:02 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: pgsql-hackers
On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <[email protected]> wrote:
> How can we be sure that semi or anti-join needs only one tuple? I think
> it would be enough to control the absence of join clauses and filters in
> the join. Unfortunately, we only have such a guarantee in the plan
> creation stage (maybe even setrefs.c). So, it seems we need to invent an
> approach like AlternativeSubplan.
I suggest looking at what 9e215378d did. You might be able to also
allow semi and anti-joins providing the cache keys cover the entire
join condition. I think this might be safe as Nested Loop will only
ask its inner subnode for the first match before skipping to the next
outer row and with anti-join, there's no reason to look for additional
rows after the first. Semi-join and unique joins do the same thing in
nodeNestloop.c. To save doing additional checks at run-time, the code
does:
nlstate->js.single_match = (node->join.inner_unique ||
node->join.jointype == JOIN_SEMI);
For making this work, I think the attached should be about the guts of
the code changes. I didn't look at the comments. Right now I can't
think of any reason why this can't be done, but some experimentation
might reveal some reason that it can't.
David
Attachments:
[application/octet-stream] memoize_semi_and_anti_joins_experiment.patch (1.7K, ../../CAApHDvr2NRbjLXEUXvvKNCDcHfhC6UBL6ZmJzXZ29MBPi3+y8g@mail.gmail.com/2-memoize_semi_and_anti_joins_experiment.patch)
download | inline diff:
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..03b4506e873 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -714,19 +714,6 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ph_lateral_vars == NIL)
return NULL;
- /*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
- *
- * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
- * = true. Should we? See add_paths_to_joinrel()
- */
- if (!extra->inner_unique && (jointype == JOIN_SEMI ||
- jointype == JOIN_ANTI))
- return NULL;
-
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
@@ -753,7 +740,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +795,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || jointype == JOIN_SEMI || jointype == JOIN_ANTI,
binary_mode,
outer_path->rows);
}
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-21 15:56 Andrei Lepikhov <[email protected]>
parent: David Rowley <[email protected]>
2 siblings, 1 reply; 26+ messages in thread
From: Andrei Lepikhov @ 2025-03-21 15:56 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: pgsql-hackers
On 20/3/2025 07:02, David Rowley wrote:
> On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <[email protected]> wrote:
>> How can we be sure that semi or anti-join needs only one tuple? I think
>> it would be enough to control the absence of join clauses and filters in
>> the join. Unfortunately, we only have such a guarantee in the plan
>> creation stage (maybe even setrefs.c). So, it seems we need to invent an
>> approach like AlternativeSubplan.
>
> I suggest looking at what 9e215378d did. You might be able to also
> allow semi and anti-joins providing the cache keys cover the entire
> join condition. I think this might be safe as Nested Loop will only
> ask its inner subnode for the first match before skipping to the next
> outer row and with anti-join, there's no reason to look for additional
> rows after the first. Semi-join and unique joins do the same thing in
> nodeNestloop.c. To save doing additional checks at run-time, the code
> does:
Thank you for the clue! I almost took the wrong direction.
I have attached the new patch, which includes corrected comments for
better clarification of the changes, as well as some additional tests.
I now feel much more confident about this version since I have resolved
that concern.
--
regards, Andrei Lepikhov
From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email protected]>
Date: Fri, 21 Mar 2025 15:55:40 +0100
Subject: [PATCH v1] Memoise the inner of SEMI- and ANTI-join.
To produce the result of semi-join or anti-join, we only need one tuple from
the parameterised inner. The Postgres core already includes Memoize's
single_row mode for the case when it is proved that inner returns only a single
value. Thus, implementing similar logic for semi-joins and anti-joins is
quite doable.
Usually, these types of join need only single tuple from the inner to produce
result for each outer tuple. But if after pushing parameterised clauses down to
the inner the NestLoop still have some join clauses or filters, it may reject
some inner tuples during execution and call the inner more than once. To prevent
that we check that all the restrictions have been pushed to the inner.
---
src/backend/commands/explain.c | 4 +
src/backend/optimizer/path/costsize.c | 2 +-
src/backend/optimizer/path/joinpath.c | 21 +++--
src/backend/optimizer/util/pathnode.c | 2 +-
src/test/regress/expected/join.out | 3 +-
src/test/regress/expected/memoize.out | 102 ++++++++++++++++++++++++
src/test/regress/expected/subselect.out | 3 +-
src/test/regress/sql/memoize.sql | 49 ++++++++++++
8 files changed, 174 insertions(+), 12 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 391b34a2af2..1b4b3b740ab 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3628,6 +3628,10 @@ show_memoize_info(MemoizeState *mstate, List *ancestors, ExplainState *es)
ExplainPropertyText("Cache Key", keystr.data, es);
ExplainPropertyText("Cache Mode", mstate->binary_mode ? "binary" : "logical", es);
+ /* Report only in the single mode case to not break current tests */
+ if (mstate->singlerow)
+ ExplainPropertyText("Store Mode", "singlerow", es);
+
pfree(keystr.data);
if (!es->analyze)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f6f77b8fe19..941ba6e1d49 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2545,7 +2545,7 @@ cost_memoize_rescan(PlannerInfo *root, MemoizePath *mpath,
ListCell *lc;
Cost input_startup_cost = mpath->subpath->startup_cost;
Cost input_total_cost = mpath->subpath->total_cost;
- double tuples = mpath->subpath->rows;
+ double tuples = mpath->singlerow ? 1 : mpath->subpath->rows;
double calls = mpath->calls;
int width = mpath->subpath->pathtarget->width;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..c75408f552b 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -682,6 +682,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ListCell *lc;
bool binary_mode;
List *ph_lateral_vars;
+ bool single_mode = false;
/* Obviously not if it's disabled */
if (!enable_memoize)
@@ -715,23 +716,27 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
+ * We may do this for SEMI or ANTI joins when they need only one tuple from
+ * the inner side to produce the result. Following if condition checks that
+ * rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if (!extra->inner_unique && (jointype == JOIN_SEMI ||
jointype == JOIN_ANTI))
- return NULL;
+ single_mode = true;
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
* Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. This means that we may not read the inner side of the
+ * inner tuple. Another case is a semi or anti join. If number of join
+ * clauses, pushed to the inner as parameterised filter no less than the
+ * number of join clauses, that means all the clauses have been pushed to
+ * the inner and any tuple coming from the inner side will be successfully
+ * used to build the join result.
+ * This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
* automatically mark cache entries as complete after fetching the first
@@ -753,7 +758,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || single_mode) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +813,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || single_mode,
binary_mode,
outer_path->rows);
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 93e73cb44db..9b4c0f96193 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1707,7 +1707,7 @@ create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
*/
pathnode->path.startup_cost = subpath->startup_cost + cpu_tuple_cost;
pathnode->path.total_cost = subpath->total_cost + cpu_tuple_cost;
- pathnode->path.rows = subpath->rows;
+ pathnode->path.rows = (pathnode->singlerow) ? 1 : subpath->rows;
return pathnode;
}
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24f..e8293c3c87d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6469,10 +6469,11 @@ select * from sj t1
-> Memoize
Cache Key: t1.a, t1.b
Cache Mode: binary
+ Store Mode: singlerow
-> Sample Scan on sj
Sampling: system (t1.b)
Filter: (t1.a = a)
-(8 rows)
+(9 rows)
-- Ensure that SJE does not form a self-referential lateral dependency
explain (costs off)
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..3ad473b211d 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,105 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ Join Filter: ((c.x = a.x) AND (c.z = a.z))
+ -> Nested Loop
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = b.x)
+ Filter: (y = b.y)
+(13 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ Join Filter: (c.y = b.y)
+ -> Nested Loop Left Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: ((x = a.x) AND (z = a.z))
+(12 rows)
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d0db8a412ff..5ab56f8d71f 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2642,6 +2642,7 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Memoize
Cache Key: b.hundred, b.odd
Cache Mode: binary
+ Store Mode: singlerow
-> Subquery Scan on "ANY_subquery"
Filter: (b.hundred = "ANY_subquery".min)
-> Result
@@ -2650,5 +2651,5 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Index Scan using tenk2_hundred on tenk2 c
Index Cond: (hundred IS NOT NULL)
Filter: (odd = b.odd)
-(16 rows)
+(17 rows)
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..048c8e90ad0 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,52 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
--
2.48.1
Attachments:
[text/plain] v1-0001-Memoise-the-inner-of-SEMI-and-ANTI-join.patch (14.2K, ../../[email protected]/2-v1-0001-Memoise-the-inner-of-SEMI-and-ANTI-join.patch)
download | inline diff:
From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email protected]>
Date: Fri, 21 Mar 2025 15:55:40 +0100
Subject: [PATCH v1] Memoise the inner of SEMI- and ANTI-join.
To produce the result of semi-join or anti-join, we only need one tuple from
the parameterised inner. The Postgres core already includes Memoize's
single_row mode for the case when it is proved that inner returns only a single
value. Thus, implementing similar logic for semi-joins and anti-joins is
quite doable.
Usually, these types of join need only single tuple from the inner to produce
result for each outer tuple. But if after pushing parameterised clauses down to
the inner the NestLoop still have some join clauses or filters, it may reject
some inner tuples during execution and call the inner more than once. To prevent
that we check that all the restrictions have been pushed to the inner.
---
src/backend/commands/explain.c | 4 +
src/backend/optimizer/path/costsize.c | 2 +-
src/backend/optimizer/path/joinpath.c | 21 +++--
src/backend/optimizer/util/pathnode.c | 2 +-
src/test/regress/expected/join.out | 3 +-
src/test/regress/expected/memoize.out | 102 ++++++++++++++++++++++++
src/test/regress/expected/subselect.out | 3 +-
src/test/regress/sql/memoize.sql | 49 ++++++++++++
8 files changed, 174 insertions(+), 12 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 391b34a2af2..1b4b3b740ab 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3628,6 +3628,10 @@ show_memoize_info(MemoizeState *mstate, List *ancestors, ExplainState *es)
ExplainPropertyText("Cache Key", keystr.data, es);
ExplainPropertyText("Cache Mode", mstate->binary_mode ? "binary" : "logical", es);
+ /* Report only in the single mode case to not break current tests */
+ if (mstate->singlerow)
+ ExplainPropertyText("Store Mode", "singlerow", es);
+
pfree(keystr.data);
if (!es->analyze)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f6f77b8fe19..941ba6e1d49 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2545,7 +2545,7 @@ cost_memoize_rescan(PlannerInfo *root, MemoizePath *mpath,
ListCell *lc;
Cost input_startup_cost = mpath->subpath->startup_cost;
Cost input_total_cost = mpath->subpath->total_cost;
- double tuples = mpath->subpath->rows;
+ double tuples = mpath->singlerow ? 1 : mpath->subpath->rows;
double calls = mpath->calls;
int width = mpath->subpath->pathtarget->width;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..c75408f552b 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -682,6 +682,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ListCell *lc;
bool binary_mode;
List *ph_lateral_vars;
+ bool single_mode = false;
/* Obviously not if it's disabled */
if (!enable_memoize)
@@ -715,23 +716,27 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
+ * We may do this for SEMI or ANTI joins when they need only one tuple from
+ * the inner side to produce the result. Following if condition checks that
+ * rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if (!extra->inner_unique && (jointype == JOIN_SEMI ||
jointype == JOIN_ANTI))
- return NULL;
+ single_mode = true;
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
* Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. This means that we may not read the inner side of the
+ * inner tuple. Another case is a semi or anti join. If number of join
+ * clauses, pushed to the inner as parameterised filter no less than the
+ * number of join clauses, that means all the clauses have been pushed to
+ * the inner and any tuple coming from the inner side will be successfully
+ * used to build the join result.
+ * This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
* automatically mark cache entries as complete after fetching the first
@@ -753,7 +758,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || single_mode) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +813,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || single_mode,
binary_mode,
outer_path->rows);
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 93e73cb44db..9b4c0f96193 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1707,7 +1707,7 @@ create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
*/
pathnode->path.startup_cost = subpath->startup_cost + cpu_tuple_cost;
pathnode->path.total_cost = subpath->total_cost + cpu_tuple_cost;
- pathnode->path.rows = subpath->rows;
+ pathnode->path.rows = (pathnode->singlerow) ? 1 : subpath->rows;
return pathnode;
}
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24f..e8293c3c87d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6469,10 +6469,11 @@ select * from sj t1
-> Memoize
Cache Key: t1.a, t1.b
Cache Mode: binary
+ Store Mode: singlerow
-> Sample Scan on sj
Sampling: system (t1.b)
Filter: (t1.a = a)
-(8 rows)
+(9 rows)
-- Ensure that SJE does not form a self-referential lateral dependency
explain (costs off)
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..3ad473b211d 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,105 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ Join Filter: ((c.x = a.x) AND (c.z = a.z))
+ -> Nested Loop
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = b.x)
+ Filter: (y = b.y)
+(13 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ Join Filter: (c.y = b.y)
+ -> Nested Loop Left Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: ((x = a.x) AND (z = a.z))
+(12 rows)
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d0db8a412ff..5ab56f8d71f 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2642,6 +2642,7 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Memoize
Cache Key: b.hundred, b.odd
Cache Mode: binary
+ Store Mode: singlerow
-> Subquery Scan on "ANY_subquery"
Filter: (b.hundred = "ANY_subquery".min)
-> Result
@@ -2650,5 +2651,5 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Index Scan using tenk2_hundred on tenk2 c
Index Cond: (hundred IS NOT NULL)
Filter: (odd = b.odd)
-(16 rows)
+(17 rows)
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..048c8e90ad0 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,52 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
--
2.48.1
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 02:33 Alena Rybakina <[email protected]>
parent: Andrei Lepikhov <[email protected]>
0 siblings, 2 replies; 26+ messages in thread
From: Alena Rybakina @ 2025-03-31 02:33 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
Hi!
On 21.03.2025 18:56, Andrei Lepikhov wrote:
> On 20/3/2025 07:02, David Rowley wrote:
>> On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <[email protected]> wrote:
>>> How can we be sure that semi or anti-join needs only one tuple? I think
>>> it would be enough to control the absence of join clauses and
>>> filters in
>>> the join. Unfortunately, we only have such a guarantee in the plan
>>> creation stage (maybe even setrefs.c). So, it seems we need to
>>> invent an
>>> approach like AlternativeSubplan.
>>
>> I suggest looking at what 9e215378d did. You might be able to also
>> allow semi and anti-joins providing the cache keys cover the entire
>> join condition. I think this might be safe as Nested Loop will only
>> ask its inner subnode for the first match before skipping to the next
>> outer row and with anti-join, there's no reason to look for additional
>> rows after the first. Semi-join and unique joins do the same thing in
>> nodeNestloop.c. To save doing additional checks at run-time, the code
>> does:
> Thank you for the clue! I almost took the wrong direction.
> I have attached the new patch, which includes corrected comments for
> better clarification of the changes, as well as some additional tests.
> I now feel much more confident about this version since I have
> resolved that concern.
>
I reviewed your patch and made a couple of suggestions.
The first change is related to your comment (and the one before it). I
fixed some grammar issues and simplified the wording to make it clearer
and easier to understand.
The second change involves adding an Assert when generating the Memoize
path. Based on the existing comment and the surrounding logic (shown
below),
I believe it's worth asserting that both inner_unique and single_mode
are not true at the same time — just as a safety check.
/*
* We may do this for SEMI or ANTI joins when they need only one tuple from
* the inner side to produce the result. Following if condition checks that
* rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if(!extra->inner_unique&& (jointype== JOIN_SEMI||
jointype== JOIN_ANTI))
single_mode= true;
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] memoize.diff (2.0K, ../../[email protected]/3-memoize.diff)
download | inline diff:
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed to
- * the inner and any tuple coming from the inner side will be successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
@@ -808,6 +810,8 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
&hash_operators,
&binary_mode))
{
+ Assert(!(extra->inner_unique && single_mode));
+
return (Path *) create_memoize_path(root,
innerrel,
inner_path,
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 02:50 Alena Rybakina <[email protected]>
parent: Alena Rybakina <[email protected]>
1 sibling, 0 replies; 26+ messages in thread
From: Alena Rybakina @ 2025-03-31 02:50 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
I realized that I uploaded my diff file with a small mistake - sorry
about that. I've corrected it with this message so your tests can pass
in the CI.
On 31.03.2025 05:33, Alena Rybakina wrote:
>
> Hi!
>
> On 21.03.2025 18:56, Andrei Lepikhov wrote:
>> On 20/3/2025 07:02, David Rowley wrote:
>>> On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <[email protected]>
>>> wrote:
>>>> How can we be sure that semi or anti-join needs only one tuple? I
>>>> think
>>>> it would be enough to control the absence of join clauses and
>>>> filters in
>>>> the join. Unfortunately, we only have such a guarantee in the plan
>>>> creation stage (maybe even setrefs.c). So, it seems we need to
>>>> invent an
>>>> approach like AlternativeSubplan.
>>>
>>> I suggest looking at what 9e215378d did. You might be able to also
>>> allow semi and anti-joins providing the cache keys cover the entire
>>> join condition. I think this might be safe as Nested Loop will only
>>> ask its inner subnode for the first match before skipping to the next
>>> outer row and with anti-join, there's no reason to look for additional
>>> rows after the first. Semi-join and unique joins do the same thing in
>>> nodeNestloop.c. To save doing additional checks at run-time, the code
>>> does:
>> Thank you for the clue! I almost took the wrong direction.
>> I have attached the new patch, which includes corrected comments for
>> better clarification of the changes, as well as some additional tests.
>> I now feel much more confident about this version since I have
>> resolved that concern.
>>
>
> I reviewed your patch and made a couple of suggestions.
>
> The first change is related to your comment (and the one before it). I
> fixed some grammar issues and simplified the wording to make it
> clearer and easier to understand.
>
> The second change involves adding an Assert when generating the
> Memoize path. Based on the existing comment and the surrounding logic
> (shown below),
> I believe it's worth asserting that both inner_unique and single_mode
> are not true at the same time — just as a safety check.
> /*
> * We may do this for SEMI or ANTI joins when they need only one tuple from
> * the inner side to produce the result. Following if condition checks that
> * rule.
> *
> * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
> * = true. Should we? See add_paths_to_joinrel()
> */
> if(!extra->inner_unique&& (jointype== JOIN_SEMI||
> jointype== JOIN_ANTI))
> single_mode= true;
--
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed to
- * the inner and any tuple coming from the inner side will be successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
@@ -808,6 +810,8 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
&hash_operators,
&binary_mode))
{
+ Assert(!(extra->inner_unique && single_mode));
+
return (Path *) create_memoize_path(root,
innerrel,
inner_path,
Attachments:
[text/plain] memoize.diff.no-cfbot (2.0K, ../../[email protected]/3-memoize.diff.no-cfbot)
download | inline diff:
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed to
- * the inner and any tuple coming from the inner side will be successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
@@ -808,6 +810,8 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
&hash_operators,
&binary_mode))
{
+ Assert(!(extra->inner_unique && single_mode));
+
return (Path *) create_memoize_path(root,
innerrel,
inner_path,
[text/x-patch] v1-0001-Memoise-the-inner-of-SEMI-and-ANTI-join.patch (14.2K, ../../[email protected]/4-v1-0001-Memoise-the-inner-of-SEMI-and-ANTI-join.patch)
download | inline diff:
From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email protected]>
Date: Fri, 21 Mar 2025 15:55:40 +0100
Subject: [PATCH v1] Memoise the inner of SEMI- and ANTI-join.
To produce the result of semi-join or anti-join, we only need one tuple from
the parameterised inner. The Postgres core already includes Memoize's
single_row mode for the case when it is proved that inner returns only a single
value. Thus, implementing similar logic for semi-joins and anti-joins is
quite doable.
Usually, these types of join need only single tuple from the inner to produce
result for each outer tuple. But if after pushing parameterised clauses down to
the inner the NestLoop still have some join clauses or filters, it may reject
some inner tuples during execution and call the inner more than once. To prevent
that we check that all the restrictions have been pushed to the inner.
---
src/backend/commands/explain.c | 4 +
src/backend/optimizer/path/costsize.c | 2 +-
src/backend/optimizer/path/joinpath.c | 21 +++--
src/backend/optimizer/util/pathnode.c | 2 +-
src/test/regress/expected/join.out | 3 +-
src/test/regress/expected/memoize.out | 102 ++++++++++++++++++++++++
src/test/regress/expected/subselect.out | 3 +-
src/test/regress/sql/memoize.sql | 49 ++++++++++++
8 files changed, 174 insertions(+), 12 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 391b34a2af2..1b4b3b740ab 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3628,6 +3628,10 @@ show_memoize_info(MemoizeState *mstate, List *ancestors, ExplainState *es)
ExplainPropertyText("Cache Key", keystr.data, es);
ExplainPropertyText("Cache Mode", mstate->binary_mode ? "binary" : "logical", es);
+ /* Report only in the single mode case to not break current tests */
+ if (mstate->singlerow)
+ ExplainPropertyText("Store Mode", "singlerow", es);
+
pfree(keystr.data);
if (!es->analyze)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f6f77b8fe19..941ba6e1d49 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2545,7 +2545,7 @@ cost_memoize_rescan(PlannerInfo *root, MemoizePath *mpath,
ListCell *lc;
Cost input_startup_cost = mpath->subpath->startup_cost;
Cost input_total_cost = mpath->subpath->total_cost;
- double tuples = mpath->subpath->rows;
+ double tuples = mpath->singlerow ? 1 : mpath->subpath->rows;
double calls = mpath->calls;
int width = mpath->subpath->pathtarget->width;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..c75408f552b 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -682,6 +682,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ListCell *lc;
bool binary_mode;
List *ph_lateral_vars;
+ bool single_mode = false;
/* Obviously not if it's disabled */
if (!enable_memoize)
@@ -715,23 +716,27 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
+ * We may do this for SEMI or ANTI joins when they need only one tuple from
+ * the inner side to produce the result. Following if condition checks that
+ * rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if (!extra->inner_unique && (jointype == JOIN_SEMI ||
jointype == JOIN_ANTI))
- return NULL;
+ single_mode = true;
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
* Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. This means that we may not read the inner side of the
+ * inner tuple. Another case is a semi or anti join. If number of join
+ * clauses, pushed to the inner as parameterised filter no less than the
+ * number of join clauses, that means all the clauses have been pushed to
+ * the inner and any tuple coming from the inner side will be successfully
+ * used to build the join result.
+ * This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
* automatically mark cache entries as complete after fetching the first
@@ -753,7 +758,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || single_mode) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +813,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || single_mode,
binary_mode,
outer_path->rows);
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 93e73cb44db..9b4c0f96193 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1707,7 +1707,7 @@ create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
*/
pathnode->path.startup_cost = subpath->startup_cost + cpu_tuple_cost;
pathnode->path.total_cost = subpath->total_cost + cpu_tuple_cost;
- pathnode->path.rows = subpath->rows;
+ pathnode->path.rows = (pathnode->singlerow) ? 1 : subpath->rows;
return pathnode;
}
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24f..e8293c3c87d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6469,10 +6469,11 @@ select * from sj t1
-> Memoize
Cache Key: t1.a, t1.b
Cache Mode: binary
+ Store Mode: singlerow
-> Sample Scan on sj
Sampling: system (t1.b)
Filter: (t1.a = a)
-(8 rows)
+(9 rows)
-- Ensure that SJE does not form a self-referential lateral dependency
explain (costs off)
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..3ad473b211d 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,105 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ Join Filter: ((c.x = a.x) AND (c.z = a.z))
+ -> Nested Loop
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = b.x)
+ Filter: (y = b.y)
+(13 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ Join Filter: (c.y = b.y)
+ -> Nested Loop Left Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: ((x = a.x) AND (z = a.z))
+(12 rows)
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d0db8a412ff..5ab56f8d71f 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2642,6 +2642,7 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Memoize
Cache Key: b.hundred, b.odd
Cache Mode: binary
+ Store Mode: singlerow
-> Subquery Scan on "ANY_subquery"
Filter: (b.hundred = "ANY_subquery".min)
-> Result
@@ -2650,5 +2651,5 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Index Scan using tenk2_hundred on tenk2 c
Index Cond: (hundred IS NOT NULL)
Filter: (odd = b.odd)
-(16 rows)
+(17 rows)
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..048c8e90ad0 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,52 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
--
2.48.1
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 03:04 David Rowley <[email protected]>
parent: Alena Rybakina <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: David Rowley @ 2025-03-31 03:04 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Mon, 31 Mar 2025 at 15:33, Alena Rybakina <[email protected]> wrote:
> I believe it's worth asserting that both inner_unique and single_mode are not true at the same time — just as a safety check.
add_paths_to_joinrel() just chooses not to populate inner_unique for
SEMI and ANTI joins because, as of today's master, it's pretty
pointless to determine that because the executor will short-circuit
and skip to the next outer tuple for those join types anyway. I don't
follow why having both these flags set would cause trouble. It seems
perfectly legitimate that add_paths_to_joinrel() could choose to set
the inner_unique flag for these join types, and if it did, the Assert
you're proposing would fail for no good reason.
David
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 03:21 Alena Rybakina <[email protected]>
parent: David Rowley <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Alena Rybakina @ 2025-03-31 03:21 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On 31.03.2025 06:04, David Rowley wrote:
> On Mon, 31 Mar 2025 at 15:33, Alena Rybakina<[email protected]> wrote:
>> I believe it's worth asserting that both inner_unique and single_mode are not true at the same time — just as a safety check.
> add_paths_to_joinrel() just chooses not to populate inner_unique for
> SEMI and ANTI joins because, as of today's master, it's pretty
> pointless to determine that because the executor will short-circuit
> and skip to the next outer tuple for those join types anyway. I don't
> follow why having both these flags set would cause trouble. It seems
> perfectly legitimate that add_paths_to_joinrel() could choose to set
> the inner_unique flag for these join types, and if it did, the Assert
> you're proposing would fail for no good reason.
>
I tend to agree with you that someone might set this flag to true for
these join types in the future.
However, is it necessary to check that extra->inner_unique must be false
for SEMI/ANTI joins here, or am I missing something? It looks a little
confusing at this point.
if(!extra->inner_unique&& (jointype== JOIN_SEMI|| jointype== JOIN_ANTI))
single_mode= true;
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 03:33 David Rowley <[email protected]>
parent: Alena Rybakina <[email protected]>
0 siblings, 2 replies; 26+ messages in thread
From: David Rowley @ 2025-03-31 03:33 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Mon, 31 Mar 2025 at 16:21, Alena Rybakina <[email protected]> wrote:
> However, is it necessary to check that extra->inner_unique must be false for SEMI/ANTI joins here, or am I missing something? It looks a little confusing at this point.
If it is necessary, I don't see the reason for it. It was me that
worked on unique joins and I see no reason why a SEMI or ANTI join
couldn't be marked as unique. The reason they're not today is that the
only point of the unique join optimisation is so that during
execution, the join nodes could skip to the next outer tuple after
matching the current outer to an inner. If the join is unique, then
there are no more join partners to find for the current outer after
matching it up once. With SEMI and ANTI joins, we skip to the next
outer tuple after finding a match anyway, so there's no point in going
to the trouble of setting the inner_unique flag.
I can't say definitively that we won't find a reason in the future
that we should set inner_unique for SEMI/ANTI joins, so I don't follow
the need for the Assert.
Maybe you're seeing something that I'm not. What do you think will
break if both flags are true?
David
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 06:34 Alena Rybakina <[email protected]>
parent: David Rowley <[email protected]>
1 sibling, 0 replies; 26+ messages in thread
From: Alena Rybakina @ 2025-03-31 06:34 UTC (permalink / raw)
To: David Rowley <[email protected]>; Andrei Lepikhov <[email protected]>; +Cc: pgsql-hackers
On 31.03.2025 06:33, David Rowley wrote:
> On Mon, 31 Mar 2025 at 16:21, Alena Rybakina <[email protected]> wrote:
>> However, is it necessary to check that extra->inner_unique must be false for SEMI/ANTI joins here, or am I missing something? It looks a little confusing at this point.
> If it is necessary, I don't see the reason for it. It was me that
> worked on unique joins and I see no reason why a SEMI or ANTI join
> couldn't be marked as unique. The reason they're not today is that the
> only point of the unique join optimisation is so that during
> execution, the join nodes could skip to the next outer tuple after
> matching the current outer to an inner. If the join is unique, then
> there are no more join partners to find for the current outer after
> matching it up once. With SEMI and ANTI joins, we skip to the next
> outer tuple after finding a match anyway, so there's no point in going
> to the trouble of setting the inner_unique flag.
>
> I can't say definitively that we won't find a reason in the future
> that we should set inner_unique for SEMI/ANTI joins, so I don't follow
> the need for the Assert.
>
> Maybe you're seeing something that I'm not. What do you think will
> break if both flags are true?
>
Actually, I was mainly confused by the code itself - the check seemed to
contradict the explanation. It looked like we were enforcing that
inner_unique must be false for SEMI/ANTI joins, even though it's not
actually important for those join types.
That’s why I originally proposed either adding an Assert or removing
this flag from check altogether, just to make it more explicit.
So, I agree with your explanation — by the definition of SEMI and ANTI
joins, there's no need to set inner_unique, and also no need to assert
against it.
These joins skip to the next outer tuple once they find a match (or fail
to find one, in the case of ANTI).
I updated the diff, where I left changes only in the code comment.
--
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed to
- * the inner and any tuple coming from the inner side will be successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
Attachments:
[text/plain] memoize.diff.no-cfbot (1.7K, ../../[email protected]/2-memoize.diff.no-cfbot)
download | inline diff:
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed to
- * the inner and any tuple coming from the inner side will be successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 07:45 Andrei Lepikhov <[email protected]>
parent: David Rowley <[email protected]>
1 sibling, 0 replies; 26+ messages in thread
From: Andrei Lepikhov @ 2025-03-31 07:45 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: pgsql-hackers; Alena Rybakina <[email protected]>
On 3/31/25 05:33, David Rowley wrote:
> I can't say definitively that we won't find a reason in the future
> that we should set inner_unique for SEMI/ANTI joins, so I don't follow
> the need for the Assert.
>
> Maybe you're seeing something that I'm not. What do you think will
> break if both flags are true?
I considered targeting PG 19 and July Comitfest for this feature, but
currently, I don't see any further development needed here. What are
your thoughts, David? Does it make sense to commit this to PG 18?
I have no reason to rush the process, but this feature seems beneficial
for practice. When the internal structure is a bushy join tree,
producing even a single tuple can be costly. SQL Server's Spool node
addresses this issue, and people sometimes experience confusion
detecting degradation during migration with specific queries.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 09:03 Richard Guo <[email protected]>
parent: David Rowley <[email protected]>
2 siblings, 2 replies; 26+ messages in thread
From: Richard Guo @ 2025-03-31 09:03 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Thu, Mar 20, 2025 at 3:02 PM David Rowley <[email protected]> wrote:
> For making this work, I think the attached should be about the guts of
> the code changes. I didn't look at the comments. Right now I can't
> think of any reason why this can't be done, but some experimentation
> might reveal some reason that it can't.
I reviewed this patch and I have some concerns about the following
code:
if (extra->inner_unique &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
return NULL;
I understand that this check is used to ensure that the entire join
condition is parameterized in the case of unique joins, so that we can
safely mark the cache entry as complete after reading the first tuple.
However, ppi_clauses includes join clauses available from all outer
rels, not just the current outer rel, while extra->restrictlist only
includes the restriction clauses for the current join. This means the
check could pass even if a restriction clause isn't parameterized, as
long as another join clause, which doesn't belong to the current join,
is included in ppi_clauses.
Thanks
Richard
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 09:39 David Rowley <[email protected]>
parent: Richard Guo <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: David Rowley @ 2025-03-31 09:39 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Mon, 31 Mar 2025 at 22:03, Richard Guo <[email protected]> wrote:
> I reviewed this patch and I have some concerns about the following
> code:
>
> if (extra->inner_unique &&
> (inner_path->param_info == NULL ||
> bms_num_members(inner_path->param_info->ppi_serials) <
> list_length(extra->restrictlist)))
> return NULL;
>
> I understand that this check is used to ensure that the entire join
> condition is parameterized in the case of unique joins, so that we can
> safely mark the cache entry as complete after reading the first tuple.
> However, ppi_clauses includes join clauses available from all outer
> rels, not just the current outer rel, while extra->restrictlist only
> includes the restriction clauses for the current join. This means the
> check could pass even if a restriction clause isn't parameterized, as
> long as another join clause, which doesn't belong to the current join,
> is included in ppi_clauses.
Shouldn't you be more concerned about master here than the patch given
that the code you pasted is from master?
David
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 09:46 Andrei Lepikhov <[email protected]>
parent: Richard Guo <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: Andrei Lepikhov @ 2025-03-31 09:46 UTC (permalink / raw)
To: Richard Guo <[email protected]>; David Rowley <[email protected]>; +Cc: pgsql-hackers
On 3/31/25 11:03, Richard Guo wrote:
> On Thu, Mar 20, 2025 at 3:02 PM David Rowley <[email protected]> wrote:
>> For making this work, I think the attached should be about the guts of
>> the code changes. I didn't look at the comments. Right now I can't
>> think of any reason why this can't be done, but some experimentation
>> might reveal some reason that it can't.
>
> I reviewed this patch and I have some concerns about the following
> code:
>
> if (extra->inner_unique &&
> (inner_path->param_info == NULL ||
> bms_num_members(inner_path->param_info->ppi_serials) <
> list_length(extra->restrictlist)))
> return NULL;
>
> I understand that this check is used to ensure that the entire join
> condition is parameterized in the case of unique joins, so that we can
> safely mark the cache entry as complete after reading the first tuple.
> However, ppi_clauses includes join clauses available from all outer
> rels, not just the current outer rel, while extra->restrictlist only
> includes the restriction clauses for the current join. This means the
> check could pass even if a restriction clause isn't parameterized, as
> long as another join clause, which doesn't belong to the current join,
> is included in ppi_clauses.
Initially, I had the same concern. But if ppi_clauses contains a qual,
it should refer to this join and, as a result, be in the
extra->restrictlist, isn't it?
I thought about references to the other side of an OUTER JOIN, but if
the subquery refers to LHS, it just not be transformed to the SEMI/ANTI
join.
Anyway, if you provide an example or just a sketch, I will be happy to
discover it.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 09:50 Richard Guo <[email protected]>
parent: David Rowley <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Richard Guo @ 2025-03-31 09:50 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Mon, Mar 31, 2025 at 6:39 PM David Rowley <[email protected]> wrote:
> On Mon, 31 Mar 2025 at 22:03, Richard Guo <[email protected]> wrote:
> > I reviewed this patch and I have some concerns about the following
> > code:
> >
> > if (extra->inner_unique &&
> > (inner_path->param_info == NULL ||
> > bms_num_members(inner_path->param_info->ppi_serials) <
> > list_length(extra->restrictlist)))
> > return NULL;
> >
> > I understand that this check is used to ensure that the entire join
> > condition is parameterized in the case of unique joins, so that we can
> > safely mark the cache entry as complete after reading the first tuple.
> > However, ppi_clauses includes join clauses available from all outer
> > rels, not just the current outer rel, while extra->restrictlist only
> > includes the restriction clauses for the current join. This means the
> > check could pass even if a restriction clause isn't parameterized, as
> > long as another join clause, which doesn't belong to the current join,
> > is included in ppi_clauses.
>
> Shouldn't you be more concerned about master here than the patch given
> that the code you pasted is from master?
Right. This code is from the master branch, not the patch. It caught
my attention while I was reviewing the patch and noticed it modifies
this code.
Thanks
Richard
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 10:18 Richard Guo <[email protected]>
parent: Andrei Lepikhov <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Richard Guo @ 2025-03-31 10:18 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
On Mon, Mar 31, 2025 at 6:46 PM Andrei Lepikhov <[email protected]> wrote:
> On 3/31/25 11:03, Richard Guo wrote:
> > I reviewed this patch and I have some concerns about the following
> > code:
> >
> > if (extra->inner_unique &&
> > (inner_path->param_info == NULL ||
> > bms_num_members(inner_path->param_info->ppi_serials) <
> > list_length(extra->restrictlist)))
> > return NULL;
> >
> > I understand that this check is used to ensure that the entire join
> > condition is parameterized in the case of unique joins, so that we can
> > safely mark the cache entry as complete after reading the first tuple.
> > However, ppi_clauses includes join clauses available from all outer
> > rels, not just the current outer rel, while extra->restrictlist only
> > includes the restriction clauses for the current join. This means the
> > check could pass even if a restriction clause isn't parameterized, as
> > long as another join clause, which doesn't belong to the current join,
> > is included in ppi_clauses.
> Initially, I had the same concern. But if ppi_clauses contains a qual,
> it should refer to this join and, as a result, be in the
> extra->restrictlist, isn't it?
Hmm, I don't think so. As I mentioned upthread, ppi_clauses includes
join clauses available from all outer rels, not just the current one.
So a clause included in ppi_clauses is not necessarily included in
extra->restrictlist. As an example, consider
create table t (a int, b int);
explain (costs off)
select * from t t1 join t t2 join
lateral (select *, t1.a+t2.a as x from t t3 offset 0) t3
on t2.a = t3.a
on t1.b = t3.b;
QUERY PLAN
---------------------------------------------------------
Nested Loop
-> Seq Scan on t t2
-> Nested Loop
-> Seq Scan on t t1
-> Subquery Scan on t3
Filter: ((t2.a = t3.a) AND (t1.b = t3.b))
-> Seq Scan on t t3_1
(7 rows)
t3's ppi_clauses includes "t2.a = t3.a" and "t1.b = t3.b", while t1/t3
join's restrictlist only includes "t1.b = t3.b".
Thanks
Richard
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-03-31 10:33 Andrei Lepikhov <[email protected]>
parent: Richard Guo <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Andrei Lepikhov @ 2025-03-31 10:33 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
On 3/31/25 12:18, Richard Guo wrote:
> On Mon, Mar 31, 2025 at 6:46 PM Andrei Lepikhov <[email protected]> wrote:
> Nested Loop
> -> Seq Scan on t t2
> -> Nested Loop
> -> Seq Scan on t t1
> -> Subquery Scan on t3
> Filter: ((t2.a = t3.a) AND (t1.b = t3.b))
> -> Seq Scan on t t3_1
> (7 rows)
>
> t3's ppi_clauses includes "t2.a = t3.a" and "t1.b = t3.b", while t1/t3
> join's restrictlist only includes "t1.b = t3.b".
I attempted to make your query ab it closer to our case:
SET enable_mergejoin = f;
SET enable_hashjoin = f;
SET enable_material = f;
CREATE INDEX ON t(a);
explain (costs off)
select * from t t1 join t t2
on EXISTS (select *, t1.a+t2.a as x from t t3
WHERE t2.a = t3.a AND t1.b = t3.b);
and I don't get the case. As I see, ANTI/SEMI join just transforms to
the regular join and it is still not the case. May you be more specific?
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-04-01 07:18 Richard Guo <[email protected]>
parent: Andrei Lepikhov <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Richard Guo @ 2025-04-01 07:18 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
On Mon, Mar 31, 2025 at 7:33 PM Andrei Lepikhov <[email protected]> wrote:
> and I don't get the case. As I see, ANTI/SEMI join just transforms to
> the regular join and it is still not the case. May you be more specific?
Upthread, you said that a qual contained in ppi_clauses will also be
included in extra->restrictlist. I provided this example to show that
this is not true. And it seems to me that this discrepancy makes the
check I mentioned earlier not reliable in all cases. As I explained
earlier, this check could pass even if a restriction clause isn't
parameterized, as long as another join clause, which doesn't belong to
the current join, is included in ppi_clauses. This is not correct.
This isn't about your patch, but about the master code. However, if
this code is incorrect, your patch will also behave incorrectly, since
you patch relies on and extends this check.
Thanks
Richard
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-04-09 06:48 Richard Guo <[email protected]>
parent: David Rowley <[email protected]>
2 siblings, 1 reply; 26+ messages in thread
From: Richard Guo @ 2025-04-09 06:48 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Thu, Mar 20, 2025 at 3:02 PM David Rowley <[email protected]> wrote:
> For making this work, I think the attached should be about the guts of
> the code changes. I didn't look at the comments. Right now I can't
> think of any reason why this can't be done, but some experimentation
> might reveal some reason that it can't.
I conducted some experiments, and I'm afraid it's not safe to consider
Memoize for semi or anti joins, unless the inner side is provably
unique. As an example, please consider:
create table t (a int, b boolean);
insert into t select i%3, false from generate_series(1,100)i;
analyze t;
select * from t t1 where t1.a in
(select a from t t2 where t2.b in
(select t1.b from t t3 where t2.a > 1 offset 0));
ERROR: cache entry already complete
With the proposed patch, this query results in an error.
The problem is that join clauses from the upper level may be moved to
the semi join. For a given outer tuple, the first inner tuple that
satisfies the current parameters will mark the cache entry as complete
because singlerow is set to true. However, if that inner tuple and
the current outer tuple don't satisfy the join clauses, the second
inner tuple that satisfies the parameters will complain that the cache
entry is already marked as complete.
If the inner side is provably unique, there will be no such problem,
as there won't be a second matching tuple. OTOH, in this case, the
semi join will be reduced to an inner join by reduce_unique_semijoins.
Therefore, it doesn't make much sense to prove inner_unique for semi
joins in add_paths_to_joinrel.
Perhaps we could spend some planner cycles proving inner_unique for
anti joins, so that Memoize nodes can be considered for them?
Thanks
Richard
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-04-09 09:18 David Rowley <[email protected]>
parent: Richard Guo <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: David Rowley @ 2025-04-09 09:18 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email protected]> wrote:
>
> On Thu, Mar 20, 2025 at 3:02 PM David Rowley <[email protected]> wrote:
> > For making this work, I think the attached should be about the guts of
> > the code changes. I didn't look at the comments. Right now I can't
> > think of any reason why this can't be done, but some experimentation
> > might reveal some reason that it can't.
>
> I conducted some experiments, and I'm afraid it's not safe to consider
> Memoize for semi or anti joins, unless the inner side is provably
> unique. As an example, please consider:
Thanks for checking that. I was just looking at the spot you'd need to
adjust to prove the inner_unique for anti joins and found I'd written:
/*
* XXX it may be worth proving this to allow a Memoize to be
* considered for Nested Loop Semi/Anti Joins.
*/
Looks like I must have known that at one point in time...
> Perhaps we could spend some planner cycles proving inner_unique for
> anti joins, so that Memoize nodes can be considered for them?
Worth a try. It should be pretty easy to enable, as far as I can see.
It might just be a case of shuffling the cases around in the switch
statement in add_paths_to_joinrel().
David
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-04-10 10:36 Richard Guo <[email protected]>
parent: David Rowley <[email protected]>
0 siblings, 2 replies; 26+ messages in thread
From: Richard Guo @ 2025-04-10 10:36 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Wed, Apr 9, 2025 at 6:18 PM David Rowley <[email protected]> wrote:
> On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email protected]> wrote:
> > Perhaps we could spend some planner cycles proving inner_unique for
> > anti joins, so that Memoize nodes can be considered for them?
> Worth a try. It should be pretty easy to enable, as far as I can see.
> It might just be a case of shuffling the cases around in the switch
> statement in add_paths_to_joinrel().
Right. Here is a patch for that.
Thanks
Richard
Attachments:
[application/octet-stream] v1-0001-Enable-use-of-Memoize-for-ANTI-joins.patch (9.1K, ../../CAMbWs48FdLiMNrmJL-g6mDvoQVt0yNyJAqMkv4e2Pk-5GKCZLA@mail.gmail.com/2-v1-0001-Enable-use-of-Memoize-for-ANTI-joins.patch)
download | inline diff:
From 942b88bdb6a2dd789e49fdcc947c748cac259a76 Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v1] Enable use of Memoize for ANTI joins
Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete. One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.
However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple. That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.
Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
src/test/regress/expected/memoize.out | 59 +++++++++++++++++++++++++++
src/test/regress/sql/memoize.sql | 26 ++++++++++++
3 files changed, 110 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..064e73cc862 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
/*
* See if the inner relation is provably unique for this outer rel.
*
- * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
- * matter since the executor can make the equivalent optimization anyway;
- * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
- * must be considering a semijoin whose inner side is not provably unique
- * (else reduce_unique_semijoins would've simplified it), so there's no
- * point in calling innerrel_is_unique. However, if the LHS covers all of
- * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+ * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+ * executor can make the equivalent optimization anyway. It also doesn't
+ * help enable use of Memoize, since a semijoin with a provably unique
+ * inner side should have been reduced to an inner join in that case.
+ * Therefore, we need not expend planner cycles on proofs. (For
+ * JOIN_ANTI, although it doesn't help the executor for the same reason,
+ * it can benefit Memoize paths.) For JOIN_UNIQUE_INNER, we must be
+ * considering a semijoin whose inner side is not provably unique (else
+ * reduce_unique_semijoins would've simplified it), so there's no point in
+ * calling innerrel_is_unique. However, if the LHS covers all of the
+ * semijoin's min_lefthand, then it's appropriate to set inner_unique
* because the path produced by create_unique_path will be unique relative
* to the LHS. (If we have an LHS that's only part of the min_lefthand,
* that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
switch (jointype)
{
case JOIN_SEMI:
- case JOIN_ANTI:
-
- /*
- * XXX it may be worth proving this to allow a Memoize to be
- * considered for Nested Loop Semi/Anti Joins.
- */
extra.inner_unique = false; /* well, unproven */
break;
case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
- *
- * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
- * = true. Should we? See add_paths_to_joinrel()
+ * Currently we don't do this for SEMI and ANTI joins, because nested loop
+ * SEMI/ANTI joins don't scan the inner node to completion, which means
+ * memoize cannot mark the cache entry as complete. Nor can we mark the
+ * cache entry as complete after fetching the first inner tuple, because
+ * if that tuple and the current outer tuple don't satisfy the join
+ * clauses, a second inner tuple that satisfies the parameters would find
+ * the cache entry already marked as complete. The only exception is when
+ * the inner relation is provably unique, as in that case, there won't be
+ * a second matching tuple and we can safely mark the cache entry as
+ * complete after fetching the first inner tuple. Note that in such
+ * cases, the SEMI join should have been reduced to an inner join by
+ * reduce_unique_semijoins.
*/
- if (!extra->inner_unique && (jointype == JOIN_SEMI ||
- jointype == JOIN_ANTI))
+ if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+ !extra->inner_unique)
return NULL;
/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..73ced02e65b 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,62 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+ explain_memoize
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+ -> Nested Loop Anti Join (actual rows=33.00 loops=N)
+ -> Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+ -> Memoize (actual rows=0.67 loops=N)
+ Cache Key: (t1.a + 1), t1.a
+ Cache Mode: binary
+ Hits: 97 Misses: 3 Evictions: Zero Overflows: 0 Memory Usage: NkB
+ -> Subquery Scan on t2 (actual rows=0.67 loops=N)
+ Filter: ((t1.a + 1) = t2.a)
+ Rows Removed by Filter: 2
+ -> Unique (actual rows=2.67 loops=N)
+ -> Sort (actual rows=67.33 loops=N)
+ Sort Key: t2_1.a
+ Sort Method: quicksort Memory: 27kB
+ -> Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count
+-------
+ 33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on tab_anti t1
+ -> Nested Loop Semi Join
+ Join Filter: (t1.a = t2.a)
+ -> Seq Scan on tab_anti t2
+ -> Subquery Scan on "ANY_subquery"
+ Filter: (t2.b = "ANY_subquery".b)
+ -> Result
+ One-Time Filter: (t2.a > 1)
+ -> Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..1370d2c9cfc 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,29 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
--
2.43.0
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-05-13 13:51 Andres Freund <[email protected]>
parent: Richard Guo <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: Andres Freund @ 2025-05-13 13:51 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: David Rowley <[email protected]>; Andrei Lepikhov <[email protected]>; pgsql-hackers
Hi,
On 2025-04-10 19:36:14 +0900, Richard Guo wrote:
> On Wed, Apr 9, 2025 at 6:18 PM David Rowley <[email protected]> wrote:
> > On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email protected]> wrote:
> > > Perhaps we could spend some planner cycles proving inner_unique for
> > > anti joins, so that Memoize nodes can be considered for them?
>
> > Worth a try. It should be pretty easy to enable, as far as I can see.
> > It might just be a case of shuffling the cases around in the switch
> > statement in add_paths_to_joinrel().
>
> Right. Here is a patch for that.
This is failing on CI:
https://cirrus-ci.com/github/postgresql-cfbot/postgresql/cf%2F5636
https://api.cirrus-ci.com/v1/artifact/task/5411026402803712/testrun/build-32/testrun/regress/regress...
diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out
--- /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out 2025-04-12 11:24:10.866868945 +0000
+++ /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out 2025-04-12 11:32:44.454864476 +0000
@@ -525,7 +525,7 @@
-> Unique (actual rows=2.67 loops=N)
-> Sort (actual rows=67.33 loops=N)
Sort Key: t2_1.a
- Sort Method: quicksort Memory: 27kB
+ Sort Method: quicksort Memory: 18kB
-> Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
(15 rows)
There shouldn't be Memory mentioned in tests added to the tree.
Greetings,
Andres
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-05-14 02:13 Richard Guo <[email protected]>
parent: Andres Freund <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Richard Guo @ 2025-05-14 02:13 UTC (permalink / raw)
To: Andres Freund <[email protected]>; +Cc: David Rowley <[email protected]>; Andrei Lepikhov <[email protected]>; pgsql-hackers
On Tue, May 13, 2025 at 10:51 PM Andres Freund <[email protected]> wrote:
> This is failing on CI:
> https://cirrus-ci.com/github/postgresql-cfbot/postgresql/cf%2F5636
> https://api.cirrus-ci.com/v1/artifact/task/5411026402803712/testrun/build-32/testrun/regress/regress...
>
> diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out
> --- /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out 2025-04-12 11:24:10.866868945 +0000
> +++ /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out 2025-04-12 11:32:44.454864476 +0000
> @@ -525,7 +525,7 @@
> -> Unique (actual rows=2.67 loops=N)
> -> Sort (actual rows=67.33 loops=N)
> Sort Key: t2_1.a
> - Sort Method: quicksort Memory: 27kB
> + Sort Method: quicksort Memory: 18kB
> -> Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
> (15 rows)
>
>
> There shouldn't be Memory mentioned in tests added to the tree.
Thanks for pointing this out. You're right — Memory usage should be
hidden from the output of EXPLAIN ANALYZE. I'm a bit surprised the
existing explain_memoize function doesn't already handle that; I
guess it's because the plans in memoize.sql don't currently include
any Sort nodes. In any case, I've added a regexp_replace to filter
out 'Memory: \d+kB' in explain_memoize.
Thanks
Richard
Attachments:
[application/octet-stream] v2-0001-Enable-use-of-Memoize-for-ANTI-joins.patch (9.8K, ../../CAMbWs48g0Q_mWJip_dDEcgaCHZw71MRB=pkz4B6PzWyfVWWaCA@mail.gmail.com/2-v2-0001-Enable-use-of-Memoize-for-ANTI-joins.patch)
download | inline diff:
From 3b1dd3d81b4b7db068d8f7bdf40854c8d0d3edfb Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v2] Enable use of Memoize for ANTI joins
Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete. One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.
However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple. That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.
Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
src/test/regress/expected/memoize.out | 60 +++++++++++++++++++++++++++
src/test/regress/sql/memoize.sql | 27 ++++++++++++
3 files changed, 112 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 26f0336f1e4..b9e46a40e1f 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
/*
* See if the inner relation is provably unique for this outer rel.
*
- * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
- * matter since the executor can make the equivalent optimization anyway;
- * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
- * must be considering a semijoin whose inner side is not provably unique
- * (else reduce_unique_semijoins would've simplified it), so there's no
- * point in calling innerrel_is_unique. However, if the LHS covers all of
- * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+ * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+ * executor can make the equivalent optimization anyway. It also doesn't
+ * help enable use of Memoize, since a semijoin with a provably unique
+ * inner side should have been reduced to an inner join in that case.
+ * Therefore, we need not expend planner cycles on proofs. (For
+ * JOIN_ANTI, although it doesn't help the executor for the same reason,
+ * it can benefit Memoize paths.) For JOIN_UNIQUE_INNER, we must be
+ * considering a semijoin whose inner side is not provably unique (else
+ * reduce_unique_semijoins would've simplified it), so there's no point in
+ * calling innerrel_is_unique. However, if the LHS covers all of the
+ * semijoin's min_lefthand, then it's appropriate to set inner_unique
* because the path produced by create_unique_path will be unique relative
* to the LHS. (If we have an LHS that's only part of the min_lefthand,
* that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
switch (jointype)
{
case JOIN_SEMI:
- case JOIN_ANTI:
-
- /*
- * XXX it may be worth proving this to allow a Memoize to be
- * considered for Nested Loop Semi/Anti Joins.
- */
extra.inner_unique = false; /* well, unproven */
break;
case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
- *
- * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
- * = true. Should we? See add_paths_to_joinrel()
+ * Currently we don't do this for SEMI and ANTI joins, because nested loop
+ * SEMI/ANTI joins don't scan the inner node to completion, which means
+ * memoize cannot mark the cache entry as complete. Nor can we mark the
+ * cache entry as complete after fetching the first inner tuple, because
+ * if that tuple and the current outer tuple don't satisfy the join
+ * clauses, a second inner tuple that satisfies the parameters would find
+ * the cache entry already marked as complete. The only exception is when
+ * the inner relation is provably unique, as in that case, there won't be
+ * a second matching tuple and we can safely mark the cache entry as
+ * complete after fetching the first inner tuple. Note that in such
+ * cases, the SEMI join should have been reduced to an inner join by
+ * reduce_unique_semijoins.
*/
- if (!extra->inner_unique && (jointype == JOIN_SEMI ||
- jointype == JOIN_ANTI))
+ if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+ !extra->inner_unique)
return NULL;
/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..150dc1b44cf 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -25,6 +25,7 @@ begin
ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+ ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
return next ln;
end loop;
end;
@@ -500,3 +501,62 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+ explain_memoize
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+ -> Nested Loop Anti Join (actual rows=33.00 loops=N)
+ -> Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+ -> Memoize (actual rows=0.67 loops=N)
+ Cache Key: (t1.a + 1), t1.a
+ Cache Mode: binary
+ Hits: 97 Misses: 3 Evictions: Zero Overflows: 0 Memory Usage: NkB
+ -> Subquery Scan on t2 (actual rows=0.67 loops=N)
+ Filter: ((t1.a + 1) = t2.a)
+ Rows Removed by Filter: 2
+ -> Unique (actual rows=2.67 loops=N)
+ -> Sort (actual rows=67.33 loops=N)
+ Sort Key: t2_1.a
+ Sort Method: quicksort Memory: NkB
+ -> Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count
+-------
+ 33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on tab_anti t1
+ -> Nested Loop Semi Join
+ Join Filter: (t1.a = t2.a)
+ -> Seq Scan on tab_anti t2
+ -> Subquery Scan on "ANY_subquery"
+ Filter: (t2.b = "ANY_subquery".b)
+ -> Result
+ One-Time Filter: (t2.a > 1)
+ -> Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..8d1cdd6990c 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -26,6 +26,7 @@ begin
ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+ ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
return next ln;
end loop;
end;
@@ -244,3 +245,29 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
--
2.43.0
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-07-02 02:08 Richard Guo <[email protected]>
parent: Richard Guo <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: Richard Guo @ 2025-07-02 02:08 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; pgsql-hackers
On Thu, Apr 10, 2025 at 7:36 PM Richard Guo <[email protected]> wrote:
> On Wed, Apr 9, 2025 at 6:18 PM David Rowley <[email protected]> wrote:
> > On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email protected]> wrote:
> > > Perhaps we could spend some planner cycles proving inner_unique for
> > > anti joins, so that Memoize nodes can be considered for them?
> > Worth a try. It should be pretty easy to enable, as far as I can see.
> > It might just be a case of shuffling the cases around in the switch
> > statement in add_paths_to_joinrel().
> Right. Here is a patch for that.
Here's a rebased version with no other changes.
David, Andrei, would you like to take another look? I'm planning to
push it soon.
Thanks
Richard
Attachments:
[application/octet-stream] v3-0001-Enable-use-of-Memoize-for-ANTI-joins.patch (9.8K, ../../CAMbWs4_pDZYK+2RGTTjsyoRkRe+Y9rT3Y6b3XtuzcPkNTeP-zw@mail.gmail.com/2-v3-0001-Enable-use-of-Memoize-for-ANTI-joins.patch)
download | inline diff:
From bd3adf290d31151d1939f3505b1846eae1300c79 Mon Sep 17 00:00:00 2001
From: Richard Guo <[email protected]>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v3] Enable use of Memoize for ANTI joins
Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete. One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.
However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple. That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.
Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
src/test/regress/expected/memoize.out | 60 +++++++++++++++++++++++++++
src/test/regress/sql/memoize.sql | 27 ++++++++++++
3 files changed, 112 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 7aa8f5d799c..ebedc5574ca 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
/*
* See if the inner relation is provably unique for this outer rel.
*
- * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
- * matter since the executor can make the equivalent optimization anyway;
- * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
- * must be considering a semijoin whose inner side is not provably unique
- * (else reduce_unique_semijoins would've simplified it), so there's no
- * point in calling innerrel_is_unique. However, if the LHS covers all of
- * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+ * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+ * executor can make the equivalent optimization anyway. It also doesn't
+ * help enable use of Memoize, since a semijoin with a provably unique
+ * inner side should have been reduced to an inner join in that case.
+ * Therefore, we need not expend planner cycles on proofs. (For
+ * JOIN_ANTI, although it doesn't help the executor for the same reason,
+ * it can benefit Memoize paths.) For JOIN_UNIQUE_INNER, we must be
+ * considering a semijoin whose inner side is not provably unique (else
+ * reduce_unique_semijoins would've simplified it), so there's no point in
+ * calling innerrel_is_unique. However, if the LHS covers all of the
+ * semijoin's min_lefthand, then it's appropriate to set inner_unique
* because the path produced by create_unique_path will be unique relative
* to the LHS. (If we have an LHS that's only part of the min_lefthand,
* that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
switch (jointype)
{
case JOIN_SEMI:
- case JOIN_ANTI:
-
- /*
- * XXX it may be worth proving this to allow a Memoize to be
- * considered for Nested Loop Semi/Anti Joins.
- */
extra.inner_unique = false; /* well, unproven */
break;
case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
- *
- * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
- * = true. Should we? See add_paths_to_joinrel()
+ * Currently we don't do this for SEMI and ANTI joins, because nested loop
+ * SEMI/ANTI joins don't scan the inner node to completion, which means
+ * memoize cannot mark the cache entry as complete. Nor can we mark the
+ * cache entry as complete after fetching the first inner tuple, because
+ * if that tuple and the current outer tuple don't satisfy the join
+ * clauses, a second inner tuple that satisfies the parameters would find
+ * the cache entry already marked as complete. The only exception is when
+ * the inner relation is provably unique, as in that case, there won't be
+ * a second matching tuple and we can safely mark the cache entry as
+ * complete after fetching the first inner tuple. Note that in such
+ * cases, the SEMI join should have been reduced to an inner join by
+ * reduce_unique_semijoins.
*/
- if (!extra->inner_unique && (jointype == JOIN_SEMI ||
- jointype == JOIN_ANTI))
+ if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+ !extra->inner_unique)
return NULL;
/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..150dc1b44cf 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -25,6 +25,7 @@ begin
ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+ ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
return next ln;
end loop;
end;
@@ -500,3 +501,62 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+ explain_memoize
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+ -> Nested Loop Anti Join (actual rows=33.00 loops=N)
+ -> Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+ -> Memoize (actual rows=0.67 loops=N)
+ Cache Key: (t1.a + 1), t1.a
+ Cache Mode: binary
+ Hits: 97 Misses: 3 Evictions: Zero Overflows: 0 Memory Usage: NkB
+ -> Subquery Scan on t2 (actual rows=0.67 loops=N)
+ Filter: ((t1.a + 1) = t2.a)
+ Rows Removed by Filter: 2
+ -> Unique (actual rows=2.67 loops=N)
+ -> Sort (actual rows=67.33 loops=N)
+ Sort Key: t2_1.a
+ Sort Method: quicksort Memory: NkB
+ -> Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count
+-------
+ 33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on tab_anti t1
+ -> Nested Loop Semi Join
+ Join Filter: (t1.a = t2.a)
+ -> Seq Scan on tab_anti t2
+ -> Subquery Scan on "ANY_subquery"
+ Filter: (t2.b = "ANY_subquery".b)
+ -> Result
+ One-Time Filter: (t2.a > 1)
+ -> Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..8d1cdd6990c 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -26,6 +26,7 @@ begin
ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+ ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
return next ln;
end loop;
end;
@@ -244,3 +245,29 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+ (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
--
2.43.0
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-07-02 03:48 wenhui qiu <[email protected]>
parent: Richard Guo <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: wenhui qiu @ 2025-07-02 03:48 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: David Rowley <[email protected]>; Andrei Lepikhov <[email protected]>; pgsql-hackers
HI
> - if (!extra->inner_unique && (jointype == JOIN_SEMI ||
> - jointype == JOIN_ANTI))
> + if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
> + !extra->inner_unique)
To be nitpicky, this change is meant to align with the earlier comment
modifications to improve code readability, right? Everything else looks
good to me."
Thanks
On Wed, Jul 2, 2025 at 10:08 AM Richard Guo <[email protected]> wrote:
> On Thu, Apr 10, 2025 at 7:36 PM Richard Guo <[email protected]>
> wrote:
> > On Wed, Apr 9, 2025 at 6:18 PM David Rowley <[email protected]>
> wrote:
> > > On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email protected]>
> wrote:
> > > > Perhaps we could spend some planner cycles proving inner_unique for
> > > > anti joins, so that Memoize nodes can be considered for them?
>
> > > Worth a try. It should be pretty easy to enable, as far as I can see.
> > > It might just be a case of shuffling the cases around in the switch
> > > statement in add_paths_to_joinrel().
>
> > Right. Here is a patch for that.
>
> Here's a rebased version with no other changes.
>
> David, Andrei, would you like to take another look? I'm planning to
> push it soon.
>
> Thanks
> Richard
>
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Memoize ANTI and SEMI JOIN inner
@ 2025-07-02 09:01 Andrei Lepikhov <[email protected]>
parent: wenhui qiu <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Andrei Lepikhov @ 2025-07-02 09:01 UTC (permalink / raw)
To: wenhui qiu <[email protected]>; Richard Guo <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
On 2/7/2025 05:48, wenhui qiu wrote:
> HI
>
> > - if (!extra->inner_unique && (jointype == JOIN_SEMI ||
> > - jointype == JOIN_ANTI))
> > + if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
> > + !extra->inner_unique)
> To be nitpicky, this change is meant to align with the earlier comment
> modifications to improve code readability, right? Everything else looks
> good to me."
Yep, I also found only this flaw.
Comments looks clear to me, test is quite stable.
May be correct the line:
INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
with a backspace or an 'AS' keyword?
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 26+ messages in thread
end of thread, other threads:[~2025-07-02 09:01 UTC | newest]
Thread overview: 26+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-12-31 14:19 [PATCH v48 2/3] Filling gaps in jsonb Dmitrii Dolgov <[email protected]>
2025-03-19 17:15 Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
2025-03-20 06:02 ` Re: Memoize ANTI and SEMI JOIN inner David Rowley <[email protected]>
2025-03-21 15:56 ` Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
2025-03-31 02:33 ` Re: Memoize ANTI and SEMI JOIN inner Alena Rybakina <[email protected]>
2025-03-31 02:50 ` Re: Memoize ANTI and SEMI JOIN inner Alena Rybakina <[email protected]>
2025-03-31 03:04 ` Re: Memoize ANTI and SEMI JOIN inner David Rowley <[email protected]>
2025-03-31 03:21 ` Re: Memoize ANTI and SEMI JOIN inner Alena Rybakina <[email protected]>
2025-03-31 03:33 ` Re: Memoize ANTI and SEMI JOIN inner David Rowley <[email protected]>
2025-03-31 06:34 ` Re: Memoize ANTI and SEMI JOIN inner Alena Rybakina <[email protected]>
2025-03-31 07:45 ` Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
2025-03-31 09:03 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-03-31 09:39 ` Re: Memoize ANTI and SEMI JOIN inner David Rowley <[email protected]>
2025-03-31 09:50 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-03-31 09:46 ` Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
2025-03-31 10:18 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-03-31 10:33 ` Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
2025-04-01 07:18 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-04-09 06:48 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-04-09 09:18 ` Re: Memoize ANTI and SEMI JOIN inner David Rowley <[email protected]>
2025-04-10 10:36 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-05-13 13:51 ` Re: Memoize ANTI and SEMI JOIN inner Andres Freund <[email protected]>
2025-05-14 02:13 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-07-02 02:08 ` Re: Memoize ANTI and SEMI JOIN inner Richard Guo <[email protected]>
2025-07-02 03:48 ` Re: Memoize ANTI and SEMI JOIN inner wenhui qiu <[email protected]>
2025-07-02 09:01 ` Re: Memoize ANTI and SEMI JOIN inner Andrei Lepikhov <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox