Re: Row pattern recognition - Mailing list pgsql-hackers
| From | Henson Choi |
|---|---|
| Subject | Re: Row pattern recognition |
| Date | |
| Msg-id | CAAAe_zDsYugq506ou49PU+Ok+4Umn5n59Qs5wYofvKyfEpvZJQ@mail.gmail.com Whole thread |
| In response to | Re: Row pattern recognition (Henson Choi <assam258@gmail.com>) |
| Responses |
Re: Row pattern recognition
Re: Row pattern recognition Re: Row pattern recognition Re: Row pattern recognition |
| List | pgsql-hackers |
Hi hackers,
This is an increment on top of v53. It is ten patches, named
nocfbot-XXXX-*.txt as before.
The fixed branch for this posting, which I will not rewrite, is:
https://github.com/assam258-5892/postgres/tree/RPR-20260930
The base is v53 as Tatsuo posted it on 09-17 on top of master
999ce9bcd80, moved onto master 5bd2e236e21 of 09-28. The ten patches
apply on it in number order, with nothing in between.
The 09-07 increment and the wip patches I attached to later mails are
included selectively: what is still needed is in these ten, some of it
in a different form.
The main change is structural. DEFINE is now handled the way HAVING
is: the planner, not the parser, works out which columns it reads. On
the deparse side I stopped working around the existing column-naming
machinery and fixed it at query level. That replaced a series of
scattered fixes with a few changes at the root.
Each entry says what v53 gets wrong and what the patch does about it,
and the tag in brackets says what kind of problem it is. The commit
messages have the details. Five of the ten fix defects in today's
v53: wrong answers or false errors, input that the standard rejects,
and a view that cannot be dumped and restored. With them in, our
tests find no wrong answer or false error left in this feature, apart
from the three defects the fourth mail reports and the window-name
deparse case under "Known issues"; what else remains is quality, and
is under "Known issues" at the end.
Those five are:
- 0001 a window over grouped input fails with an internal error when
a grouping set nulls a column its DEFINE reads
- 0002 a DEFINE clause accepts a whole-row reference, ROW(t.*), or a
name qualified by a function name or block label, which the
standard reserves for a pattern variable
- 0003 some patterns match different rows than the standard and Perl
give
- 0004 a DEFINE over subquery pull-up fails at plan time, or reads a
constant where a navigation argument means the target row
- 0005 a view holding a DEFINE clause can fail to dump and restore
once another column carries a name that DEFINE reads
0001 and 0004 change planner code that other queries share, though
only row pattern queries behave differently there. 0005 changes the
deparser, and its output also changes for some queries without row
pattern recognition. The commit messages say what and why. For a
reader who knows those areas but not RPR, I will send the longer
reasoning as two separate mails, one on the planner changes and one on
the deparse changes, each as its own thread. A third mail, as a reply
in this thread, explains the structure change in 0003, which changes
how a group is compiled. What this mail says about these changes
stays as it is. A fourth mail reports three defects found in these
ten after they were cut; this mail does not describe them.
Numbering
Numbers are reissued whenever the base version changes. This one is
cut against v53 and does not continue the numbers of the 09-07 mail;
there the same number points at a different commit.
Application order is number order.
On authorship: all ten carry me as author, and five of them -- 0001,
0002, 0003, 0004 and 0009 -- also carry Jian as co-author, because
patches he wrote are merged into them. I rebased and verified them
and wrote the messages.
What changed in the code
Removed because it was not needed:
- the parser planting DEFINE's Vars into the target list
- the RPR exception in remove_unused_subquery_outputs() (back to
upstream)
- rprPatternEqual() and rprPatternChildrenEqual(), which did what
equal() does
- four separate frame checks, now one (EXCLUDE is reported on its
own)
- two copies of the navigation name list, now one
- ExecRPRGetHeadContext(), a small helper folded into its one caller
- an unreachable overflow check, and a goto
Added, the key pieces:
- add_define_inputs_walker(), called from
make_window_input_target(), asks for what DEFINE reads, as for
havingQual
- mark_define_columns() and collapse_define_join_vars() in the
deparser
- ParseState.p_rpr_define and rpr_frame_is_supported()
- nfa_mark_group_entered() and nfa_prune_skipped_contexts()
- BEGIN.jump names the group's own END
Refactored:
- RPRPattern copy, out and read share one contract
- existing helpers replace hand-written code
- the two RPRNavExpr_walker() functions are renamed
- a few functions and macros are renamed or introduced
Where the 09-07 patches went:
- 2008 (grouping) is in 0001
- 2004, 2005, 2010, 2011, 2017, 2018 (name rules, diagnostics,
cleanups) are in 0002
- 2003 (frame report) is in 0002, rewritten
- 2013-2016, 2019 (executor cleanups) are in 0003
- 2002 (DEFINE context) is in 0003, done with ExecQual() instead
- 2012 (navigation argument) is in 0004
- 2009 (unreferenced window) is in 0004, in a different form: the
RPR exception in remove_unused_subquery_outputs() is removed
instead
- 2001 (pinned column names) is in 0005
- 2006 (RPRPattern contract) is in 0006
- 2021, 2022 (comments, the two costs) are in 0007
- 2007, 2020 (documentation) are in 0009
- 9001 (EXCLUDE TIES test) is in 0008
- 9002 (column names of relation RTEs outside FROM) is in 0005
0001 Let a row pattern DEFINE clause take part in grouping
[wrong result]
v53 left DEFINE out of the GROUP BY substitution, so a grouping
set that nulls a column made setrefs.c fail with "wrong
varnullingrels". DEFINE now goes through the same steps as the
target list. Also fixes PREV(k / 0) failing at plan time when
k is a USING column of mixed types.
0002 Tighten parse analysis of DEFINE clauses and row pattern
syntax [wrong result]
Whole-row references, ROW(t.*), names qualified by a function
name or block label, and the FILTER or ORDER BY of an aggregate
got around the qualifier rule of ISO/IEC 19075-5 6.5. They
are rejected now, and a few SQLSTATEs change.
0003 Fix DEFINE memory leak and empty-iteration looping in RPR
executor [wrong result]
An empty first iteration kept a derivation the standard
excludes, so some patterns matched different rows than Perl;
query results change for such patterns. Also fixes the DEFINE
memory leak (94MB down to 18MB on 300k rows) and adds an
interrupt check.
0004 Move DEFINE input tracking from parse analysis to the planner
[wrong result]
Parse analysis planted DEFINE's Vars in the target list, and
planning could fail with "variable not found in subplan target
list". DEFINE is now handled the way havingQual is. Also
stops subquery pull-up from folding a navigation argument, and
fixes a crash on a navigation offset.
0005 Make a deparsed DEFINE clause re-parse as written
[wrong result]
A view holding a DEFINE clause could not be dumped and restored
once another column carried the same name. The names DEFINE
reads are now settled first and reserved. Also changes
pg_get_viewdef() output for some queries without row pattern
recognition; the commit message lists them.
0006 Tighten RPRPattern node I/O and reuse existing helpers in RPR
code [latent]
A malformed node string now fails with an internal error
instead of being misread. Existing helpers replace
hand-written code.
0007 Record two RPR costs and correct comments the code no longer
matches [comments, asserts]
Comments, plus five checks the executor cannot reach, now
Asserts: two elog(ERROR) calls and three early returns.
Records two known costs as XXX: the state comparison in
nfa_states_equal(), and nav_winobj's shared read pointer.
0008 Tidy and extend the row pattern recognition regression tests
[tests]
Tests only: rpr_ prefixes, fewer redundant ORDER BY, new tests,
and fixes for tests that tested less than their comments said.
0009 Bring the row pattern recognition documentation up to date
[docs]
Documentation only: SGML and README.rpr checked against the
code.
0010 Reorder README.rpr by processing order [docs]
Moves the chapters into the order a query goes through the
code: parsing, DEFINE planning, PATTERN compilation, the
executor, the worked example, deparse and EXPLAIN, and the
summary last. Text moves; section numbers and cross references
follow, and the Chapter IV title is reworded.
Open questions
Tatsuo, four items need your decision on the direction or on whether
to go ahead:
- State explosion. To keep the preference order from giving wrong
answers, the cycle guard marks only a nullable END, since marking
anything else loses legitimate matches. That bounds cycles but not
cost: alternations whose branches are all nullable enumerate paths
rather than states, as an XXX in nfa_advance_state() records. A
runtime bound, on the work in one expansion or on the states held,
is the first answer; rejecting quantified subpatterns that can
match empty, as Oracle does with ORA-62513, is the alternative.
- Names. You accepted the RPR* policy for the typedefs on 07-14 [1]
and asked whether it reaches struct members too. I would say yes:
rpSkipTo becomes rprSkipTo along with the types, in one mechanical
patch after the defects are settled.
- WindowAggState. On 05-31 [2] you agreed with Jian's idea [3] of
putting the row pattern members behind one struct, for the size
and for the move to R010, but not for v48. On 07-14 [1] you asked
when to do it, saying it has to be done to make the code
committable. I would group the members before the commit, since
that only changes structure, and leave the R010 redesign for
after. The struct needs a name other than RPRContext, since
rprContext is already the ExprContext DEFINE runs in.
- sql_features.txt still says R020 is NO although the patch
implements it. It has to change before the commit. Whether it
says YES with a note or NO, partially supported is your call.
None of these is urgent, and none is a structural problem that puts
the quality of the patch at risk. Each is a matter of direction or
timing that can wait until the code has settled, and I will follow
whichever way you decide.
Testing
All of this ran on the tip of RPR-20260930.
- make check-world passes on two setups:
Linux, gcc, --enable-coverage --with-llvm
macOS, clang, --enable-coverage --with-llvm
On both the node-support GUCs debug_copy_parse_plan_trees,
debug_write_read_parse_plan_trees and
debug_raw_expression_coverage_test were on, and so was
debug_parallel_query = regress.
- A third build, macOS with clang and AddressSanitizer + UBSan, ran
166 suites, and neither sanitizer reports anything.
- Coverage of the modified lines, by gcov:
whole feature, against master Linux 98.6% (2,795 / 2,836)
macOS 98.3% (3,145 / 3,201)
The figure in my mail of 06-23 was 98.4% (2,635 / 2,679). The
two compilers count executable lines differently, so compare
within a platform.
- The generated node-support functions for the RPR and window nodes
(copy, equal, out, read and query jumble) all ran. Both the JIT
and the interpreted path of the navigation steps ran; JIT is
reached through the two tests in rpr.sql that turn it on.
Known issues
The interplay with the planner, the deparser and the rest of the
surrounding code was found test by test, and I believe it is in good
shape now, but I cannot be sure of it. So I will spend the next
several months studying the related planner code, and I will keep
quiet on this thread meanwhile, apart from replying to reviews and
posting the fixes for the three defects in the fourth mail.
One item waits for another CF entry. CF 7056 (quoting of unreserved
keywords used as window names, such as "rows") has to be committed
first. Row pattern recognition then adds pattern, after, initial
and seek to the list that patch builds in appendWindowRefName(),
with a round-trip test for each. Until then a window named
"pattern" that another window inherits deparses to text that does
not re-parse.
Separate submissions
Already in these ten. I will submit them upstream as one patch, in
its own thread and CF entry, and send another patch that reconciles
the series with the submitted one:
- deparse: column alias lists for TABLEFUNC RTEs, column names of
relation RTEs outside FROM, and column alias lists of function
RTEs (all from 0005). The TABLEFUNC part
reproduces without row pattern recognition on released
branches (JSON_TABLE on 17 and later, XMLTABLE since 10); it
comes from the printaliases = false exception that
arrived with XMLTABLE (fcec6caafa2, 2017)
Not in these ten, each to be posted in its own thread:
- grouping sets do not null a grouping expression that has no Var
(reproduces without row pattern recognition)
- make_placeholder_expr() is not memoized across calls, so the
same join alias expression can get two PlaceHolderVars (I expect
it to reproduce without row pattern recognition, but I have not
yet built a query that shows it)
- Retry open() when it fails with EINTR
- Put two typedefs.list entries back in sorted order
[1] https://postgr.es/m/20260714.212047.525303007784395461.ishii@postgresql.org
[2] https://postgr.es/m/20260531.091119.2213733238436650503.ishii@postgresql.org
[3] https://postgr.es/m/CACJufxGX17thWuEOq1tM5xbRHz2HXm1asooZC3GV25MYGmYqLQ@mail.gmail.com
Best regards,
Henson
This is an increment on top of v53. It is ten patches, named
nocfbot-XXXX-*.txt as before.
The fixed branch for this posting, which I will not rewrite, is:
https://github.com/assam258-5892/postgres/tree/RPR-20260930
The base is v53 as Tatsuo posted it on 09-17 on top of master
999ce9bcd80, moved onto master 5bd2e236e21 of 09-28. The ten patches
apply on it in number order, with nothing in between.
The 09-07 increment and the wip patches I attached to later mails are
included selectively: what is still needed is in these ten, some of it
in a different form.
The main change is structural. DEFINE is now handled the way HAVING
is: the planner, not the parser, works out which columns it reads. On
the deparse side I stopped working around the existing column-naming
machinery and fixed it at query level. That replaced a series of
scattered fixes with a few changes at the root.
Each entry says what v53 gets wrong and what the patch does about it,
and the tag in brackets says what kind of problem it is. The commit
messages have the details. Five of the ten fix defects in today's
v53: wrong answers or false errors, input that the standard rejects,
and a view that cannot be dumped and restored. With them in, our
tests find no wrong answer or false error left in this feature, apart
from the three defects the fourth mail reports and the window-name
deparse case under "Known issues"; what else remains is quality, and
is under "Known issues" at the end.
Those five are:
- 0001 a window over grouped input fails with an internal error when
a grouping set nulls a column its DEFINE reads
- 0002 a DEFINE clause accepts a whole-row reference, ROW(t.*), or a
name qualified by a function name or block label, which the
standard reserves for a pattern variable
- 0003 some patterns match different rows than the standard and Perl
give
- 0004 a DEFINE over subquery pull-up fails at plan time, or reads a
constant where a navigation argument means the target row
- 0005 a view holding a DEFINE clause can fail to dump and restore
once another column carries a name that DEFINE reads
0001 and 0004 change planner code that other queries share, though
only row pattern queries behave differently there. 0005 changes the
deparser, and its output also changes for some queries without row
pattern recognition. The commit messages say what and why. For a
reader who knows those areas but not RPR, I will send the longer
reasoning as two separate mails, one on the planner changes and one on
the deparse changes, each as its own thread. A third mail, as a reply
in this thread, explains the structure change in 0003, which changes
how a group is compiled. What this mail says about these changes
stays as it is. A fourth mail reports three defects found in these
ten after they were cut; this mail does not describe them.
Numbering
Numbers are reissued whenever the base version changes. This one is
cut against v53 and does not continue the numbers of the 09-07 mail;
there the same number points at a different commit.
Application order is number order.
On authorship: all ten carry me as author, and five of them -- 0001,
0002, 0003, 0004 and 0009 -- also carry Jian as co-author, because
patches he wrote are merged into them. I rebased and verified them
and wrote the messages.
What changed in the code
Removed because it was not needed:
- the parser planting DEFINE's Vars into the target list
- the RPR exception in remove_unused_subquery_outputs() (back to
upstream)
- rprPatternEqual() and rprPatternChildrenEqual(), which did what
equal() does
- four separate frame checks, now one (EXCLUDE is reported on its
own)
- two copies of the navigation name list, now one
- ExecRPRGetHeadContext(), a small helper folded into its one caller
- an unreachable overflow check, and a goto
Added, the key pieces:
- add_define_inputs_walker(), called from
make_window_input_target(), asks for what DEFINE reads, as for
havingQual
- mark_define_columns() and collapse_define_join_vars() in the
deparser
- ParseState.p_rpr_define and rpr_frame_is_supported()
- nfa_mark_group_entered() and nfa_prune_skipped_contexts()
- BEGIN.jump names the group's own END
Refactored:
- RPRPattern copy, out and read share one contract
- existing helpers replace hand-written code
- the two RPRNavExpr_walker() functions are renamed
- a few functions and macros are renamed or introduced
Where the 09-07 patches went:
- 2008 (grouping) is in 0001
- 2004, 2005, 2010, 2011, 2017, 2018 (name rules, diagnostics,
cleanups) are in 0002
- 2003 (frame report) is in 0002, rewritten
- 2013-2016, 2019 (executor cleanups) are in 0003
- 2002 (DEFINE context) is in 0003, done with ExecQual() instead
- 2012 (navigation argument) is in 0004
- 2009 (unreferenced window) is in 0004, in a different form: the
RPR exception in remove_unused_subquery_outputs() is removed
instead
- 2001 (pinned column names) is in 0005
- 2006 (RPRPattern contract) is in 0006
- 2021, 2022 (comments, the two costs) are in 0007
- 2007, 2020 (documentation) are in 0009
- 9001 (EXCLUDE TIES test) is in 0008
- 9002 (column names of relation RTEs outside FROM) is in 0005
0001 Let a row pattern DEFINE clause take part in grouping
[wrong result]
v53 left DEFINE out of the GROUP BY substitution, so a grouping
set that nulls a column made setrefs.c fail with "wrong
varnullingrels". DEFINE now goes through the same steps as the
target list. Also fixes PREV(k / 0) failing at plan time when
k is a USING column of mixed types.
0002 Tighten parse analysis of DEFINE clauses and row pattern
syntax [wrong result]
Whole-row references, ROW(t.*), names qualified by a function
name or block label, and the FILTER or ORDER BY of an aggregate
got around the qualifier rule of ISO/IEC 19075-5 6.5. They
are rejected now, and a few SQLSTATEs change.
0003 Fix DEFINE memory leak and empty-iteration looping in RPR
executor [wrong result]
An empty first iteration kept a derivation the standard
excludes, so some patterns matched different rows than Perl;
query results change for such patterns. Also fixes the DEFINE
memory leak (94MB down to 18MB on 300k rows) and adds an
interrupt check.
0004 Move DEFINE input tracking from parse analysis to the planner
[wrong result]
Parse analysis planted DEFINE's Vars in the target list, and
planning could fail with "variable not found in subplan target
list". DEFINE is now handled the way havingQual is. Also
stops subquery pull-up from folding a navigation argument, and
fixes a crash on a navigation offset.
0005 Make a deparsed DEFINE clause re-parse as written
[wrong result]
A view holding a DEFINE clause could not be dumped and restored
once another column carried the same name. The names DEFINE
reads are now settled first and reserved. Also changes
pg_get_viewdef() output for some queries without row pattern
recognition; the commit message lists them.
0006 Tighten RPRPattern node I/O and reuse existing helpers in RPR
code [latent]
A malformed node string now fails with an internal error
instead of being misread. Existing helpers replace
hand-written code.
0007 Record two RPR costs and correct comments the code no longer
matches [comments, asserts]
Comments, plus five checks the executor cannot reach, now
Asserts: two elog(ERROR) calls and three early returns.
Records two known costs as XXX: the state comparison in
nfa_states_equal(), and nav_winobj's shared read pointer.
0008 Tidy and extend the row pattern recognition regression tests
[tests]
Tests only: rpr_ prefixes, fewer redundant ORDER BY, new tests,
and fixes for tests that tested less than their comments said.
0009 Bring the row pattern recognition documentation up to date
[docs]
Documentation only: SGML and README.rpr checked against the
code.
0010 Reorder README.rpr by processing order [docs]
Moves the chapters into the order a query goes through the
code: parsing, DEFINE planning, PATTERN compilation, the
executor, the worked example, deparse and EXPLAIN, and the
summary last. Text moves; section numbers and cross references
follow, and the Chapter IV title is reworded.
Open questions
Tatsuo, four items need your decision on the direction or on whether
to go ahead:
- State explosion. To keep the preference order from giving wrong
answers, the cycle guard marks only a nullable END, since marking
anything else loses legitimate matches. That bounds cycles but not
cost: alternations whose branches are all nullable enumerate paths
rather than states, as an XXX in nfa_advance_state() records. A
runtime bound, on the work in one expansion or on the states held,
is the first answer; rejecting quantified subpatterns that can
match empty, as Oracle does with ORA-62513, is the alternative.
- Names. You accepted the RPR* policy for the typedefs on 07-14 [1]
and asked whether it reaches struct members too. I would say yes:
rpSkipTo becomes rprSkipTo along with the types, in one mechanical
patch after the defects are settled.
- WindowAggState. On 05-31 [2] you agreed with Jian's idea [3] of
putting the row pattern members behind one struct, for the size
and for the move to R010, but not for v48. On 07-14 [1] you asked
when to do it, saying it has to be done to make the code
committable. I would group the members before the commit, since
that only changes structure, and leave the R010 redesign for
after. The struct needs a name other than RPRContext, since
rprContext is already the ExprContext DEFINE runs in.
- sql_features.txt still says R020 is NO although the patch
implements it. It has to change before the commit. Whether it
says YES with a note or NO, partially supported is your call.
None of these is urgent, and none is a structural problem that puts
the quality of the patch at risk. Each is a matter of direction or
timing that can wait until the code has settled, and I will follow
whichever way you decide.
Testing
All of this ran on the tip of RPR-20260930.
- make check-world passes on two setups:
Linux, gcc, --enable-coverage --with-llvm
macOS, clang, --enable-coverage --with-llvm
On both the node-support GUCs debug_copy_parse_plan_trees,
debug_write_read_parse_plan_trees and
debug_raw_expression_coverage_test were on, and so was
debug_parallel_query = regress.
- A third build, macOS with clang and AddressSanitizer + UBSan, ran
166 suites, and neither sanitizer reports anything.
- Coverage of the modified lines, by gcov:
whole feature, against master Linux 98.6% (2,795 / 2,836)
macOS 98.3% (3,145 / 3,201)
The figure in my mail of 06-23 was 98.4% (2,635 / 2,679). The
two compilers count executable lines differently, so compare
within a platform.
- The generated node-support functions for the RPR and window nodes
(copy, equal, out, read and query jumble) all ran. Both the JIT
and the interpreted path of the navigation steps ran; JIT is
reached through the two tests in rpr.sql that turn it on.
Known issues
The interplay with the planner, the deparser and the rest of the
surrounding code was found test by test, and I believe it is in good
shape now, but I cannot be sure of it. So I will spend the next
several months studying the related planner code, and I will keep
quiet on this thread meanwhile, apart from replying to reviews and
posting the fixes for the three defects in the fourth mail.
One item waits for another CF entry. CF 7056 (quoting of unreserved
keywords used as window names, such as "rows") has to be committed
first. Row pattern recognition then adds pattern, after, initial
and seek to the list that patch builds in appendWindowRefName(),
with a round-trip test for each. Until then a window named
"pattern" that another window inherits deparses to text that does
not re-parse.
Separate submissions
Already in these ten. I will submit them upstream as one patch, in
its own thread and CF entry, and send another patch that reconciles
the series with the submitted one:
- deparse: column alias lists for TABLEFUNC RTEs, column names of
relation RTEs outside FROM, and column alias lists of function
RTEs (all from 0005). The TABLEFUNC part
reproduces without row pattern recognition on released
branches (JSON_TABLE on 17 and later, XMLTABLE since 10); it
comes from the printaliases = false exception that
arrived with XMLTABLE (fcec6caafa2, 2017)
Not in these ten, each to be posted in its own thread:
- grouping sets do not null a grouping expression that has no Var
(reproduces without row pattern recognition)
- make_placeholder_expr() is not memoized across calls, so the
same join alias expression can get two PlaceHolderVars (I expect
it to reproduce without row pattern recognition, but I have not
yet built a query that shows it)
- Retry open() when it fails with EINTR
- Put two typedefs.list entries back in sorted order
[1] https://postgr.es/m/20260714.212047.525303007784395461.ishii@postgresql.org
[2] https://postgr.es/m/20260531.091119.2213733238436650503.ishii@postgresql.org
[3] https://postgr.es/m/CACJufxGX17thWuEOq1tM5xbRHz2HXm1asooZC3GV25MYGmYqLQ@mail.gmail.com
Best regards,
Henson
Attachment
- nocfbot-0001-define-in-grouping.txt
- nocfbot-0002-define-parse-analysis.txt
- nocfbot-0003-empty-iteration-and-define-leak.txt
- nocfbot-0004-define-inputs-in-planner.txt
- nocfbot-0005-deparse-define-reparse.txt
- nocfbot-0006-rprpattern-node-io-helpers.txt
- nocfbot-0007-record-costs-fix-comments.txt
- nocfbot-0008-tidy-extend-tests.txt
- nocfbot-0009-update-documentation.txt
- nocfbot-0010-reorder-readme.txt
pgsql-hackers by date: