[postgresql] a_expr_qual/a_expr_qual_op is ambiguous.

[kaby76]

Consider the test input file collate.sql. The parse is ambiguous for a_expr_qual_op. See the two parse trees in ambig.txt.

This ambiguity is a major contributor to the performance issues in the grammar. This file takes ~1.3s to parse cold start (~0.4s warm start), and it is only 276 lines long!

Note, I chose this file because it had the least number of non-zero ambiguities, which is 1. If you try to take a test input with a large number of ambiguities, trparse --ambig will take a long time. To find the file with the least non-zero number of ambiguities, I did $ dotnet trperf -c aF ../examples/*.sql | grep -v '^0' | awk '{sum[$2] += $1} END {for (key in sum) print sum[key], key}' | sort -k1 -n | head.

[kaby76]

Analysis

In the input file colate.sql.

grammars-v4/sql/postgresql/examples/collate.sql

Line 153 in 199a512

select x || y from collate_test10; -- ok, because || is not collation aware

This seemingly simple expression involving || can be parsed in two ways because qual_op appears in two places in expressions:

• grammars-v4/sql/postgresql/PostgreSQLParser.g4

  Lines 3557 to 3559 in 199a512

  	a_expr_qual
  	: a_expr_lessless qual_op?
  	;

• grammars-v4/sql/postgresql/PostgreSQLParser.g4

  Lines 3641 to 3643 in 199a512

  	a_expr_qual_op
  	: a_expr_unary_qualop (qual_op a_expr_unary_qualop)*
  	;

This is all fine, but the problem is the context target_el.

grammars-v4/sql/postgresql/PostgreSQLParser.g4

Lines 4100 to 4103 in 199a512

	target_el
	: a_expr (AS collabel | identifier |) # target_label
	| STAR # target_star
	;

We see here that || can be treated as a unary, postfix op, or a binary op. This seems quite wrong because the only postfix ops are ! and !!. https://www.postgresql.org/message-id/BE2DF53D-251A-4E26-972F-930E523580E9%40enterprisedb.com

target_el seems wrong because it does not look like https://github.com/postgres/postgres/blob/9be4e5d293b554d8a0800790c57fc707a3b5cf0f/src/backend/parser/gram.y#L17121-L17158

[kaby76]

Changing target_el : a_expr (AS collabel | identifier |) | STAR ; to target_el : a_expr (AS collabel |) | STAR ; as per the official gram.y grammar fixes the ambiguity, but breaks the parse in a few other places now. There are additional errors in the grammar.

Also, while this fixes the ambiguity for collate.sql, the parse time does not improve at all. This is because there is a huge max-k required. https://github.com/antlr/grammars-v4/blob/199a5121ece05d2f2e7eca330d0738220499e80c/sql/postgresql/examples/collate.sql#L87C9-L217C4. Rule target_list is the culprit. (There is a way to fix the grammar for fallbacks by duplication.)

First things first, though.

[kaby76]

Cloning the rule target_list in rule sql_expression (after applying #4299, #4301, #4303) has a large speed up (dotnet trparse -t ANTLRv4 PostgreSQLParser.g4 | dotnet trclonereplace " //parserRuleSpec[RULE_REF/text()='sql_expression']//RULE_REF[text()='target_list_']" -s "_1" | dotnet trsponge -c. NB: I had to remove the labels because Antlr chokes on identical # label across different rules). Before cloning, 35s. After cloning, 26s. This is because a full context is required for these elements. Rule cloning eliminates the fallbacks, but it doesn't come without a price: there are many more rules. There are still many ambiguities in the grammar, but I am confident that after resolving ambiguities and using cloning, the performance will be quite spectacular.

[kaby76]

Changing target_el : a_expr (AS collabel | identifier |) | STAR ; to target_el : a_expr (AS collabel |) | STAR ; as per the official gram.y grammar

I was in error. target_el is correct. The problem is expressions in the presence of the alias.

[kaby76]

The trick is to provide a semantic predicate before qual_op.

a_expr_qual
    : a_expr_lessless qual_op?
    ;

changed to

a_expr_qual
    : a_expr_lessless ({ this.OnlyAcceptableOps() }? qual_op | )
    ;

with

    public bool OnlyAcceptableOps()
    {
        var c = ((CommonTokenStream)this.InputStream).LT(1);
        var text = c.Text;
        return text == "!" || text == "!!";
    }

This disambiguates the use of the postfix operator, only allowing it for ! or !!. It is likely that there should be a companion semantic predicate to disallow these two operators as binary.