Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Perf issue, Quadratic time on a string literal that contains `::` casts

Open Beginner friendly
  • Is something wrong?
#426 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
1/5
Estimated time
Under an hour
Newbie friendliness
85/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
perl
Domain
performance

Research direction

The fix is in _add_token in lib/pgFormatter/Beautify.pm. Generate the reproducer with N=1000 and time pg_format -X -s 2 to confirm the quadratic growth, then read the constant guard and the cast-splitting loop. Add the /s flag to the literal guard, or hoist the invariant _is_type($token) call, verify the output is byte-identical on the reproducer, and run the project's regression tests.

Written by the indexing model from the issue text.

Description

Version: pgFormatter 5.11 (git 35c8696); the code below is unchanged in current master (_add_token in lib/pgFormatter/Beautify.pm).

Description

A string literal that spans several lines and contains ::type casts in its text is formatted in time that grows with the square of its length. The common real-world shape is a statement text passed to a function, for example a query handed to dblink, a job body given to a scheduler, or a statement stored by an audit function.

The cause is in _add_token. The guard that keeps string constants out of the cast handling is

# Be sure that we not going to modify a constant
if ( $self->{'_is_in_create'} < 2 and $token !~ /^[E]*'.*'$/ ) {
    @cast = split( /::/, $token, -1 );
    $token = shift(@cast) if ( $#cast >= 0 );

The pattern has no /s flag, so .* cannot cross a newline and a multi-line literal is not recognised as a constant. The literal is then split on every :: in its text into @cast, and the loop that re-cases the cast parts calls _is_type($token) once per whitespace-separated word of every part, on the whole token:

foreach my $c (@cast) {
    my @words = split( /(\s+)/, $c );
    $c = '';
    foreach my $w (@words) {
        if ( !$self->_is_type($token) ) {
            $c .= $w;
        }
        ...

That is words × casts calls, each scanning the type list against a token that is the whole literal. The parts are glued back together afterwards, so the output is unaffected; only the time is.

Reproducer

A function call whose argument is a multi-line statement text with N casts in it:

SELECT foo('SELECT id, name
  FROM customers
  WHERE
    attr_0 = ''pending''::text AND
    attr_1 = ''pending''::text AND
    ...                                -- N such lines
    1 = 1');

Generate it with:

N=1000
{ printf "SELECT foo('SELECT id, name\n  FROM customers\n  WHERE"
  for i in $(seq 0 $((N-1))); do printf "\n    attr_%d = ''pending''::text AND" $i; done
  printf "\n    1 = 1');\n"; } > repro.sql
time pg_format -X -s 2 repro.sql > /dev/null

Timings

pg_format -X -s 2, wall time, one run each:

N lines input size 5.11 with /s (only fix 1) with the hoist (only fix 2)
250 9.2 K 2.4 s 0.06 s 0.05 s
500 18.5 K 9.6 s 0.12 s 0.09 s
1000 37.0 K 38.7 s 0.28 s 0.21 s
2000 75.0 K 164.4 s 0.78 s 0.68 s

Four times slower per doubling before, linear after.

Proposed fix

Fix 1, the guard. Let the constant guard see a multi-line literal for what it is, by adding /s:

-	if ( $self->{'_is_in_create'} < 2 and $token !~ /^[E]*'.*'$/ ) {
+	if ( $self->{'_is_in_create'} < 2 and $token !~ /^[E]*'.*'$/s ) {

This is the one-character change that matches the guard's stated intent: a literal is never split on its inner ::, so the loop is never entered for it.

Fix 2, complementary. The test in the loop is loop-invariant (its argument is $token, not $w), so it can be evaluated once before the loops for every token that does carry casts:

+	my $token_is_type = @cast ? $self->_is_type($token) : 0;
 	foreach my $c (@cast) {
 		my @words = split( /(\s+)/, $c );
 		$c = '';
 		foreach my $w (@words) {
-			if ( !$self->_is_type($token) ) {
+			if ( !$token_is_type ) {

Either change alone removes the quadratic behaviour, and applying both gives the same time as /s alone. With each of them, and with both, the output is byte-identical to 5.11 on the reproducer and on all our regression tests.

If $w rather than $token was the intent in that loop, that would be a separate behaviour change; both patches keep today's output.

Dominant language
PLpgSQL
Stars
2k
Forks
123
No merged PRs in 30d

Getting set up

  • Ships a Dockerfile or Docker Compose file
  • No pull request template
  • No contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from darold/pgFormatter

All issues in darold/pgFormatter

Similar issues

More Performance issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.