Quadratic @name placeholder rewriting makes large multi-row parameterized INSERTs very slow #696

Description

SqlPlaceholderRewriter.ReplacePlaceholders (used on every command that carries parameters, via ClickHouseParameterCollection.ReplacePlaceholders → ClickHouseClient.PostSqlQueryAsync) scans the SQL once, but at every @ character it calls MatchPlaceholder, which linearly walks the entire array of registered placeholders:

https://github.com/ClickHouse/clickhouse-cs/blob/main/ClickHouse.Driver/ADO/Parameters/SqlPlaceholderRewriter.cs#L88-L105

private static string MatchPlaceholder(string sql, int startIndex, string[] placeholders)
{
    foreach (var placeholder in placeholders)   // O(number of parameters), per '@'
    {
        ...
    }
    return null;
}

For a multi-row parameterized INSERT ... VALUES (@p0, @p1, ...), (@p18, ...) the number of @ occurrences and the number of placeholders both grow with the row count, so the rewrite is O(rows²). The work happens entirely client-side, before anything is sent to the server, and it burns CPU on the calling thread.

The {name:Type} hint scanner (SqlParameterTypeExtractor.ExtractTypeHints) is not affected — it is a genuine single pass and measures linear. Only the ADO.NET-style @name rewrite path is quadratic, which is the path ORMs such as Dapper go through, since they emit @-style placeholders.

A secondary contributor on the same call is replacements.Keys.OrderByDescending(k => k.Length).ToArray() on line 25, which re-sorts the full placeholder set (O(P log P) string comparisons) on every single call.

ClickHouse server version

26.9.19.9 — though the server is never reached: this is pure client-side CPU time measured before the request is built.

Reproduction

Drop this into ClickHouse.Driver.Tests (no server needed) and run with
dotnet test ClickHouse.Driver.Tests -c Release --framework net9.0 --property WarningLevel=0 --filter "FullyQualifiedName~QuadraticPlaceholderTests":

using System.Diagnostics;
using System.Text;
using ClickHouse.Driver.ADO.Parameters;
using NUnit.Framework;

namespace ClickHouse.Driver.Tests;

public class QuadraticPlaceholderTests
{
    private const int Columns = 18;

    private static (string sql, ClickHouseParameterCollection parameters) Build(int rows)
    {
        var sql = new StringBuilder("INSERT INTO test_table VALUES ");
        var parameters = new ClickHouseParameterCollection();
        var n = 0;
        for (var r = 0; r < rows; r++)
        {
            if (r > 0)
                sql.Append(",\n");
            sql.Append('(');
            for (var c = 0; c < Columns; c++)
            {
                if (c > 0)
                    sql.Append(", ");
                sql.Append("@p").Append(n);
                parameters.Add(new ClickHouseDbParameter { ParameterName = "p" + n, Value = n });
                n++;
            }
            sql.Append(')');
        }
        return (sql.ToString(), parameters);
    }

    [Test]
    public void ReplacePlaceholders_LargeMultiRowInsert_ScalesLinearly()
    {
        var (w, wp) = Build(100);
        wp.ReplacePlaceholders(w, wp.ResolveTypeNames(w, null)); // warmup

        foreach (var rows in new[] { 500, 1000, 2000, 4000 })
        {
            var (sql, parameters) = Build(rows);
            var resolved = parameters.ResolveTypeNames(sql, null);
            var sw = Stopwatch.StartNew();
            var result = parameters.ReplacePlaceholders(sql, resolved);
            sw.Stop();
            Assert.That(result, Does.Contain("{p0:Int32}"));
            TestContext.Out.WriteLine($"rows={rows} params={rows * Columns} time={sw.Elapsed.TotalMilliseconds:F1} ms");
        }
    }
}

Measured output (Release, net9.0)

Expected: roughly linear — 8× the rows should cost roughly 8× the time (~2.3 s at 4,000 rows).
Actual: 8× the rows costs 32× the time. Each doubling of the row count roughly triples-to-quadruples the time.

For contrast, the same shape written with native hints ({p0:Int32}, {p1:Int32}, ...) through SqlParameterTypeExtractor.ExtractTypeHints is linear: 1,000 rows 7.6 ms → 8,000 rows 51.0 ms.

Suggested fix

In ClickHouse.Driver/ADO/Parameters/SqlPlaceholderRewriter.cs:

• Replace the per-@ linear scan in MatchPlaceholder (lines 88–105) with a direct lookup: at an @, read the maximal run of IsWordChar characters that follows, then do a single dictionary lookup of "@" + name in replacements. That makes the whole rewrite one pass, O(sql.Length), and also removes the need for the longest-first ordering (the maximal-munch read already prevents @id from shadowing @id_2).
• With that change the OrderByDescending(...).ToArray() on line 25 becomes unnecessary and can be dropped.

I have not attempted the fix.

Link

Analogous to ClickHouse/clickhouse-java#3249 (quadratic parameter scanning in prepareStatement() for multi-row INSERT). The mechanism differs — clickhouse-java re-scans the SQL suffix per ?, while this driver re-scans the placeholder list per @ — but the user-visible symptom is the same: client-side parse/rewrite time grows quadratically with the number of VALUES rows.