Re: Add ASCII fast path to Unicode normalization functions - Mailing list pgsql-hackers

On 2026-09-17 Th 6:46 PM, Tristan Partin wrote:
> On Mon Sep 14, 2026 at 9:55 AM CDT, Andrew Dunstan wrote:
>> Hi,
>>
>> A linkedin post comparing CedarDB's new Unicode normalization support
>> to PostgreSQL's caught my eye [1]: same results, but a claimed 30x
>> speedup on "SELECT count(*) FROM hits WHERE url IS NORMALIZED" over
>> ClickBench's hits table. Most of that turned out to be down to CedarDB
>> using all available threads by default versus our
>> max_parallel_workers_per_gather of 2. But even at the matched thread
>> count they reported a 6x edge, attributed to two things: an ASCII fast
>> path (most URLs are already normalized ASCII, so you can skip decoding
>> entirely), and vectorized byte scanning for the ASCII check itself.
>>
>> I went and looked, and unicode_is_normalized(), unicode_assigned(), and
>> normalize() all decode every string to an array of char32_t codepoints,
>> one utf8_to_unicode()/pg_utf_mblen() call at a time, before doing any
>> real work -- including on input that's already pure ASCII. The attached
>> patch adds a fast path: scan the raw bytes for anything with the high
>> bit set, using the SIMD-vectorized is_valid_ascii() we already have
>> (currently only used inside pg_utf8_verifystr()). If nothing is found,
>> the string is trivially normalized (ASCII code points have no
>> canonical or compatibility decomposition, and a combining class of
>> zero) and every code point in it is assigned, so all three functions
>> can return immediately.
>>
>> I deliberately didn't copy CedarDB's trick of comparing byte length to
>> codepoint count -- getting the codepoint count means calling
>> pg_mbstrlen_with_len(), exactly the scalar work this patch avoids.
>> Scanning raw bytes with is_valid_ascii() instead reuses SIMD
>> infrastructure we already have, and is cheaper to begin with: a single
>> reduction versus a population count.
>>
>>
>> Benchmarked with data sized to fit comfortably under shared_buffers rather
>> than triggering the seqscan ring-buffer bypass, which otherwise swamps the
>> comparison at larger table sizes: ~10x on pure ASCII, ~4x on an 85/15
>> ASCII/non-ASCII mix, and no measurable regression on non-ASCII input
>> that still needs the full decode-and-quickcheck path.
>>
>> Regression tests cover the ASCII-hit case for all three functions, plus
>> a boundary sweep that plants a non-NFC sequence at varying offsets
>> around ASCII padding, to catch any off-by-one in the SIMD-chunk/scalar-
>> remainder split.
>>
>> [1] https://lnkd.in/p/eKUqSj73
> Hey Andrew,
>
> I saw the same LinkedIn post too, and I also started working on
> a similar patch that I was benchmarking last week. So I'll provide some
> review and some results that I saw.
>
> FWIW, here is the function that I added to ascii.h:
>
>>     /*
>>      * Wrapper around is_valid_ascii() such that a string of any length can be
>>      * passed in. If you know your string to have a length of a multiple of
>>      * sizeof(Vector8), stick with is_valid_ascii(). It will avoid a few
>>      * instructions.
>>      */
>>     static inline bool
>>     is_all_valid_ascii(const unsigned char *s, int len)
>>     {
>>        int         chunk_len;
>>     
>>        Assert(len >= 0);
>>     
>>        if (len <= 0)
>>            return true;
>>     
>>        chunk_len = len - (len % sizeof(Vector8));
>>     
>>        if (chunk_len > 0 && !is_valid_ascii(s, chunk_len))
>>            return false;
>>     
>>        for (int i = chunk_len; i < len; i++)
>>        {
>>            if (s[i] == '\0' || IS_HIGHBIT_SET(s[i]))
>>                return false;
>>        }
>>     
>>        return true;
>>     }
> As you can see, it is basically the same as yours except this function
> operates on a string of unsigned chars versus you're operating on a text
> object. Not sure one is specifically better than the other, except
> is_all_valid_ascii() might be more reusable than text_is_ascii(). That
> can always be changed later though.


I don't have a strong opinion about it. It would just mean that you 
would migrate the VARDATA_ANY etc. stuff to the call sites.


>
> I think some of the comment for text_is_ascii() is a little verbose. For
> instance, the paragraph about unicode normalization is not really
> relevant to the text_is_ascii() function. It would probably fit better
> where we actually do unicode normalization.


Fair point


>
> I don't think text_is_ascii() is a great function name since we
> explicitly reject NUL characters. text_is_valid_ascii() is much more
> indicative of what you are actually checking, and it reuses the same
> wording as the is_valid_ascii() function. I would also maybe converge on
> either "pure ASCII" or "valid ASCII". Not really sure if they are the
> same, but I see both mentioned in the codebase.


I'm not fixed on the name, but we might want something different if we 
go with Bilal's useful optimization from upthread.


>
> Here are my benchmark findings, which concur with your analysis:
>
>> The benchmarks below use the ClickBench hits table (100M rows), sampled
>> into four tables. Times are medians (ms) of 5 timed runs after 2 warm-up
>> runs on a release build (-Dbuildtype=release -Dcassert=false), with
>> max_parallel_workers_per_gather = 0 and all data cached in memory. The
>> baseline is unpatched master as of a12600b762c.
>>
>> Three tables come from the URL column:
>>
>> - bench_ascii: 20M ASCII-only URLs.
>> - bench_nonascii: 14,963,181 URLs containing at least one non-ASCII byte.
>>    These are still mostly ASCII; a URL with one Cyrillic path segment
>>    lands here.
>> - bench_mixed: 20M URLs, unfiltered, so ~15% contain at least one
>>    non-ASCII byte, which is the natural ratio of the dataset.
>>
>> The URL column has no rows that are predominantly non-ASCII rather than
>> merely containing some, so the fourth table comes from the Title column:
>>
>> - bench_cyrillic: 5M Russian titles. This is just about the worst case
>>    for this patch. This patch optimistically looks for ASCII characters.
>>    Russian lacks ASCII characters, except for spaces and punctuation, as
>>    far as I know.
>>
>> unicode_is_normalized() - SELECT count(*) FROM <table> WHERE <text> IS NORMALIZED;
>> table             baseline (ms)  patched (ms)   speedup
>> bench_ascii             19329.5        1812.2    10.67x
>> bench_nonascii          45370.8       42319.4     1.07x
>> bench_mixed             26918.0       10218.9     2.63x
>> bench_cyrillic           4797.6        4978.1     0.96x
>> bench_cyrillic*          4827.9        4861.2     0.99x
>>
>> unicode_assigned() - SELECT count(*) FROM <table> WHERE unicode_assigned(<text>);
>> table             baseline (ms)  patched (ms)   speedup
>> bench_ascii              8889.9        1586.1     5.60x
>> bench_nonascii          24269.1       21474.7     1.13x
>> bench_mixed             13021.6        5620.4     2.32x
>> bench_cyrillic           6015.9        6210.7     0.97x
>> bench_cyrillic*          6071.0        6134.4     0.99x
>>
>> unicode_normalize_func() - SELECT count(normalize(<text>)) FROM <table>;
>> table             baseline (ms)  patched (ms)   speedup
>> bench_ascii             59292.9        1714.4    34.59x
>> bench_nonascii         147948.4      145031.3     1.02x
>> bench_mixed             86104.6       31805.2     2.71x
>> bench_cyrillic          14175.4       14553.5     0.97x
>> bench_cyrillic*         14467.5       14326.5     1.01x
>>
>> bench_cyrillic* is basically the same as bench_cyrillic, except that
>> master and the patched tree were compiled with -falign-functions=64
>> -falign-loops=64. I found that with the changes the hot loops could
>> straddle a 64-bit instruction fetch boundary.
> In essence, I completely agree with your findings. Note that I did not
> bump shared_buffers like you did, which was likely a very smart call.


When time permits I'll send a new version, incorporating your review and 
Bilal's suggestion.

Thanks for the review!


cheers


andrew


--
Andrew Dunstan
EDB: https://www.enterprisedb.com