| Lists: | pgsql-hackers |
|---|
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Unicode normalization SQL functions |
| Date: | 2019-12-12 11:46:21 |
| Message-ID: | c1909f27-c269-2ed9-12f8-3ab72c8caf7a@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Here are patches to add support for Unicode normalization into SQL, per
SQL standard:
normalize($string [, form])
$string is [form] normalized
(comment about silly SQL syntax here)
We already have all the infrastructure for Unicode normalization for the
SASLprep functionality. The first patch extends the internal APIs to
support all four normal forms instead of only NFKC used by SASLprep.
The second patch adds the SQL layer on top of it.
This could be used to preprocess or check strings before using them with
deterministic collations or locale implementations that don't deal with
non-NFC data correctly, perhaps using triggers, generated columns, or
domains. The NFKC and NFKD normalizations could also be used for
general data cleaning, similar to what SASLprep does.
As a future idea, I think we could also hook Unicode normalization into
the protocol-level encoding conversion.
Also, there is a way to optimize the "is normalized" test for common
cases, described in UTR #15. For that we'll need an additional data
file from Unicode. In order to simplify that, I would like my patch
"Add support for automatically updating Unicode derived files"
integrated first.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| Attachment | Content-Type | Size |
|---|---|---|
| v1-0001-Add-support-for-other-normal-forms-to-Unicode-nor.patch | text/plain | 369.9 KB |
| v1-0002-Add-SQL-functions-for-Unicode-normalization.patch | text/plain | 18.3 KB |
| From: | "Daniel Verite" <daniel(at)manitou-mail(dot)org> |
|---|---|
| To: | "Peter Eisentraut" <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | "pgsql-hackers" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-01-06 16:00:11 |
| Message-ID: | 3348a374-0325-4768-bff6-736eb76a5f9c@manitou-mail.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Peter Eisentraut wrote:
> Also, there is a way to optimize the "is normalized" test for common
> cases, described in UTR #15. For that we'll need an additional data
> file from Unicode. In order to simplify that, I would like my patch
> "Add support for automatically updating Unicode derived files"
> integrated first.
Would that explain that the NFC/NFKC normalization and "is normalized"
check seem abnormally slow with the current patch, or should
it be regarded independently of the other patch?
For instance, testing 10000 short ASCII strings:
postgres=# select count(*) from (select md5(i::text) as t from
generate_series(1,10000) as i) s where t is nfc normalized ;
count
-------
10000
(1 row)
Time: 2573,859 ms (00:02,574)
By comparison, the NFD/NFKD case is faster by two orders of magnitude:
postgres=# select count(*) from (select md5(i::text) as t from
generate_series(1,10000) as i) s where t is nfd normalized ;
count
-------
10000
(1 row)
Time: 29,962 ms
Although NFC/NFKC has a recomposition step that NFD/NFKD
doesn't have, such a difference is surprising.
I've tried an alternative implementation based on ICU's
unorm2_isNormalized() /unorm2_normalize() functions (which I'm
currently adding to the icu_ext extension to be exposed in SQL).
With these, the 4 normal forms are in the 20ms ballpark with the above
test case, without a clear difference between composed and decomposed
forms.
Independently of the performance, I've compared the results
of the ICU implementation vs this patch on large series of strings
with all normal forms and could not find any difference.
Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-01-09 09:20:14 |
| Message-ID: | 2309023a-6f69-f049-70e5-3c70b4fb9672@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-01-06 17:00, Daniel Verite wrote:
> Peter Eisentraut wrote:
>
>> Also, there is a way to optimize the "is normalized" test for common
>> cases, described in UTR #15. For that we'll need an additional data
>> file from Unicode. In order to simplify that, I would like my patch
>> "Add support for automatically updating Unicode derived files"
>> integrated first.
>
> Would that explain that the NFC/NFKC normalization and "is normalized"
> check seem abnormally slow with the current patch, or should
> it be regarded independently of the other patch?
That's unrelated.
> For instance, testing 10000 short ASCII strings:
>
> postgres=# select count(*) from (select md5(i::text) as t from
> generate_series(1,10000) as i) s where t is nfc normalized ;
> count
> -------
> 10000
> (1 row)
>
> Time: 2573,859 ms (00:02,574)
>
> By comparison, the NFD/NFKD case is faster by two orders of magnitude:
>
> postgres=# select count(*) from (select md5(i::text) as t from
> generate_series(1,10000) as i) s where t is nfd normalized ;
> count
> -------
> 10000
> (1 row)
>
> Time: 29,962 ms
>
> Although NFC/NFKC has a recomposition step that NFD/NFKD
> doesn't have, such a difference is surprising.
It's very likely that this is because the recomposition calls
recompose_code() which does a sequential scan of UnicodeDecompMain for
each character. To optimize that, we should probably build a bespoke
reverse mapping table that can be accessed more efficiently.
> I've tried an alternative implementation based on ICU's
> unorm2_isNormalized() /unorm2_normalize() functions (which I'm
> currently adding to the icu_ext extension to be exposed in SQL).
> With these, the 4 normal forms are in the 20ms ballpark with the above
> test case, without a clear difference between composed and decomposed
> forms.
That's good feedback.
> Independently of the performance, I've compared the results
> of the ICU implementation vs this patch on large series of strings
> with all normal forms and could not find any difference.
And that too.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Cc: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-01-20 09:17:50 |
| Message-ID: | 014866c8-d7ff-2a4f-c185-cf7e3ceb7028@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Here is an updated patch set that now also implements the "quick check"
algorithm from UTR #15 for making IS NORMALIZED very fast in many cases,
which I had mentioned earlier in the thread.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| Attachment | Content-Type | Size |
|---|---|---|
| v2-0001-Add-support-for-other-normal-forms-to-Unicode-nor.patch | text/plain | 370.0 KB |
| v2-0002-Add-SQL-functions-for-Unicode-normalization.patch | text/plain | 1.1 MB |
| From: | "Daniel Verite" <daniel(at)manitou-mail(dot)org> |
|---|---|
| To: | "Peter Eisentraut" <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | "pgsql-hackers" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-01-28 09:48:45 |
| Message-ID: | 623fa07e-348f-4273-afa4-7110ad43ca57@manitou-mail.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Peter Eisentraut wrote:
> Here is an updated patch set that now also implements the "quick check"
> algorithm from UTR #15 for making IS NORMALIZED very fast in many cases,
> which I had mentioned earlier in the thread.
I found a bug in unicode_is_normalized_quickcheck() which is
triggered when the last codepoint of the string is beyond
U+10000. On encountering it, it does:
+ if (is_supplementary_codepoint(ch))
+ p++;
When ch is the last codepoint, it makes p point to
the ending zero, but the subsequent p++ done by
the for loop makes it miss the exit and go into over-reading.
But anyway, what's the reason for skipping the codepoint
following a codepoint outside of the BMP?
I've figured that it comes from porting the Java code in UAX#15:
public int quickCheck(String source) {
short lastCanonicalClass = 0;
int result = YES;
for (int i = 0; i < source.length(); ++i) {
int ch = source.codepointAt(i);
if (Character.isSupplementaryCodePoint(ch)) ++i;
short canonicalClass = getCanonicalClass(ch);
if (lastCanonicalClass > canonicalClass && canonicalClass != 0) {
return NO; }
int check = isAllowed(ch);
if (check == NO) return NO;
if (check == MAYBE) result = MAYBE;
lastCanonicalClass = canonicalClass;
}
return result;
}
source.length() is the length in UTF-16 code units, in which a surrogate
pair counts for 2. This would be why it does
if (Character.isSupplementaryCodePoint(ch)) ++i;
it's meant to skip the 2nd UTF-16 code of the pair.
As this does not apply to the 32-bit pg_wchar, I think the two lines above
in the C implementation should just be removed.
Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-01-28 20:21:18 |
| Message-ID: | 43f13518-010a-8319-8013-f319522ea719@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-01-28 10:48, Daniel Verite wrote:
> I found a bug in unicode_is_normalized_quickcheck() which is
> triggered when the last codepoint of the string is beyond
> U+10000. On encountering it, it does:
> + if (is_supplementary_codepoint(ch))
> + p++;
> When ch is the last codepoint, it makes p point to
> the ending zero, but the subsequent p++ done by
> the for loop makes it miss the exit and go into over-reading.
>
> But anyway, what's the reason for skipping the codepoint
> following a codepoint outside of the BMP?
You're right, this didn't make any sense. Here is a new patch set with
that fixed.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| Attachment | Content-Type | Size |
|---|---|---|
| v3-0001-Add-support-for-other-normal-forms-to-Unicode-nor.patch | text/plain | 370.0 KB |
| v3-0002-Add-SQL-functions-for-Unicode-normalization.patch | text/plain | 1.1 MB |
| From: | Andreas Karlsson <andreas(at)proxel(dot)se> |
|---|---|
| To: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com>, Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-13 00:23:41 |
| Message-ID: | 26150b35-240f-941c-e5a7-24f2d489b316@proxel.se |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 1/28/20 9:21 PM, Peter Eisentraut wrote:
> You're right, this didn't make any sense. Here is a new patch set with
> that fixed.
Thanks for this patch. This is a feature which has been on my personal
todo list for a while and something which I have wished to have a couple
of times.
I took a quick look at the patch and here is some feedback:
A possible concern is increased binary size from the new tables for the
quickcheck but personally I think they are worth it.
A potential optimization would be to merge utf8_to_unicode() and
pg_utf_mblen() into one function in unicode_normalize_func() since
utf8_to_unicode() already knows length of the character. Probably not
worth it though.
It feels a bit wasteful to measure output_size in
unicode_is_normalized() since unicode_normalize() actually already knows
the length of the buffer, it just does not return it.
A potential optimization for the normalized case would be to abort the
quick check on the first maybe and normalize from that point on only. If
I can find the time I might try this out and benchmark it.
Nitpick: "split/\s*;\s*/, $line" in generate-unicode_normprops_table.pl
should be "split /\s*;\s*/, $line".
What about using else if in the code below for clarity?
+ if (check == UNICODE_NORM_QC_NO)
+ return UNICODE_NORM_QC_NO;
+ if (check == UNICODE_NORM_QC_MAYBE)
+ result = UNICODE_NORM_QC_MAYBE;
Remove extra space in the line below.
+ else if (quickcheck == UNICODE_NORM_QC_NO )
Andreas
| From: | Michael Paquier <michael(at)paquier(dot)xyz> |
|---|---|
| To: | Andreas Karlsson <andreas(at)proxel(dot)se> |
| Cc: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com>, Daniel Verite <daniel(at)manitou-mail(dot)org>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-13 03:40:59 |
| Message-ID: | 20200213034059.GD1520@paquier.xyz |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On Thu, Feb 13, 2020 at 01:23:41AM +0100, Andreas Karlsson wrote:
> On 1/28/20 9:21 PM, Peter Eisentraut wrote:
>> You're right, this didn't make any sense. Here is a new patch set with
>> that fixed.
>
> Thanks for this patch. This is a feature which has been on my personal todo
> list for a while and something which I have wished to have a couple of
> times.
(The size of the patch set may justify compressing it)
--
Michael
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Andreas Karlsson <andreas(at)proxel(dot)se>, Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-17 15:56:01 |
| Message-ID: | bba8933e-44ef-761d-55fb-076f2b6b5650@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-02-13 01:23, Andreas Karlsson wrote:
> A potential optimization would be to merge utf8_to_unicode() and
> pg_utf_mblen() into one function in unicode_normalize_func() since
> utf8_to_unicode() already knows length of the character. Probably not
> worth it though.
This would also require untangling the entire encoding API.
> It feels a bit wasteful to measure output_size in
> unicode_is_normalized() since unicode_normalize() actually already knows
> the length of the buffer, it just does not return it.
Sure, but really most string APIs work like that. They surely know the
string length internally, but afterwards you often have to call strlen()
again.
> A potential optimization for the normalized case would be to abort the
> quick check on the first maybe and normalize from that point on only. If
> I can find the time I might try this out and benchmark it.
Are you sure this would always be valid? The fact that this wasn't
mentioned in UTR #15 makes me suspicious.
> Nitpick: "split/\s*;\s*/, $line" in generate-unicode_normprops_table.pl
> should be "split /\s*;\s*/, $line".
done
> What about using else if in the code below for clarity?
>
> + if (check == UNICODE_NORM_QC_NO)
> + return UNICODE_NORM_QC_NO;
> + if (check == UNICODE_NORM_QC_MAYBE)
> + result = UNICODE_NORM_QC_MAYBE;
done
> Remove extra space in the line below.
>
> + else if (quickcheck == UNICODE_NORM_QC_NO )
I didn't find this in my local copy.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | "Daniel Verite" <daniel(at)manitou-mail(dot)org> |
|---|---|
| To: | "Peter Eisentraut" <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | "Andreas Karlsson" <andreas(at)proxel(dot)se>,"pgsql-hackers" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-17 19:08:00 |
| Message-ID: | 2c5e8df9-43b8-41fa-88e6-286e8634f00a@manitou-mail.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Hi,
I've checked the v3 patch against the results of the normalization
done by ICU [1] on my test data again, and they're identical
(as they were with v1; v2 had the bug discussed upthread, now fixed).
Concerning execution speed, there's an excessive CPU usage when
normalizing into NFC or NFKC. Looking at pre-existing code, it looks
like recompose_code() in unicode_norm.c looping over the
UnicodeDecompMain array might be very costly.
Another point is that the ICU-based implementation appears
to be significantly faster in all cases, which makes me wonder
why ICU builds should not just use ICU instead of the PG-core
implementation.
To illustrate this, here are the execution times reported by psql for
the queries below exercising the normalization code, both with the
functions provided by the patch and with the equivalent functions
implemented with ICU.
The dataset is ~10 million unique short strings
extracted from real data, and the number is a median execution time in
millisecs, for 10 successive runs with query parallelism off
(stddev in parentheses).
operation | core | icu
------------+--------------+-----------
nfc check | 4398 (20) | 3088 (27)
nfc conv | 771502 (414) | 5503 (19)
nfd check | 4510 (10) | 2898 (8)
nfd conv | 9102 (1) | 5569 (6)
nfkc check | 4825 (51) | 3273 (4)
nfkc conv | 772240 (340) | 5763 (8)
nfkd check | 4794 (4) | 3170 (39)
nfkd conv | 9229 (4) | 5824 (9)
The queries:
check w/core:
select count(*) from words where w is $NORM normalized;
conversion w/core:
select sum(length(normalize(w, $NORM))) from words;
check w/icu:
select count(*) from words where icu_is_normalized(w, '$NORM');
conversion w/icu:
select sum(length(icu_normalize(w, '$NORM'))) from words;
[1] https://github.com/dverite/icu_ext/blob/master/icu_normalize.c
Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite
| From: | "Daniel Verite" <daniel(at)manitou-mail(dot)org> |
|---|---|
| To: | "Peter Eisentraut" <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | "Andreas Karlsson" <andreas(at)proxel(dot)se>,"pgsql-hackers" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-17 19:14:03 |
| Message-ID: | dd16d2c4-e7cb-4e6d-a92d-40e8dc1cf8a6@manitou-mail.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
One nitpick:
Around this hunk:
- * unicode_normalize_kc - Normalize a Unicode string to NFKC form.
+ * unicode_normalize - Normalize a Unicode string to the specified form.
*
* The input is a 0-terminated array of codepoints.
*
@@ -304,8 +306,10 @@ decompose_code(pg_wchar code, pg_wchar **result, int
*current)
* string is palloc'd instead, and OOM is reported with ereport().
*/
The comment in full says:
/*
* unicode_normalize - Normalize a Unicode string to the specified form.
*
* The input is a 0-terminated array of codepoints.
*
* In frontend, returns a 0-terminated array of codepoints, allocated with
* malloc. Or NULL if we run out of memory. In frontend, the returned
* string is palloc'd instead, and OOM is reported with ereport().
*/
It looks like the 2nd occurrence of "frontend" was meant to be "backend".
Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | Andreas Karlsson <andreas(at)proxel(dot)se>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-19 20:09:42 |
| Message-ID: | 1842c35f-2933-345c-b69f-03c40937a064@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-02-17 20:14, Daniel Verite wrote:
> The comment in full says:
>
> /*
> * unicode_normalize - Normalize a Unicode string to the specified form.
> *
> * The input is a 0-terminated array of codepoints.
> *
> * In frontend, returns a 0-terminated array of codepoints, allocated with
> * malloc. Or NULL if we run out of memory. In frontend, the returned
> * string is palloc'd instead, and OOM is reported with ereport().
> */
>
> It looks like the 2nd occurrence of "frontend" was meant to be "backend".
This was a pre-existing problem, so I have fixed that separately.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | Andreas Karlsson <andreas(at)proxel(dot)se>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-02-19 20:23:12 |
| Message-ID: | b0c0dbbd-9142-6bf8-4483-3a46360c55d3@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-02-17 20:08, Daniel Verite wrote:
> Concerning execution speed, there's an excessive CPU usage when
> normalizing into NFC or NFKC. Looking at pre-existing code, it looks
> like recompose_code() in unicode_norm.c looping over the
> UnicodeDecompMain array might be very costly.
Yes, this is a known issue and I think room for future optimization work.
> Another point is that the ICU-based implementation appears
> to be significantly faster in all cases, which makes me wonder
> why ICU builds should not just use ICU instead of the PG-core
> implementation.
That would require linking libpq to ICU (for SASLprep), and in general
would either make ICU required or require maintaining multiple
implementations. I don't think we're there yet.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | Andreas Karlsson <andreas(at)proxel(dot)se>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-19 14:41:13 |
| Message-ID: | c08a47e4-45c4-52d8-f1d2-babe4000e564@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
What is that status of this patch set? I think we have nailed down the
behavior, but there were some concerns about certain performance
characteristics. Do people feel that those are required to be addressed
in this cycle?
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Andreas Karlsson <andreas(at)proxel(dot)se> |
|---|---|
| To: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com>, Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-19 17:01:12 |
| Message-ID: | 9a8d5981-ca84-c012-ca77-6617f6d55f96@proxel.se |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 3/19/20 3:41 PM, Peter Eisentraut wrote:
> What is that status of this patch set? I think we have nailed down the
> behavior, but there were some concerns about certain performance
> characteristics. Do people feel that those are required to be addressed
> in this cycle?
Personally I would rather see it merged if the code is correct (which it
seems like it is from what I can tell) as the performance seems to be
good enough for it to be useful.
Unicode normalization is a feature which I have wished and at least for
my use cases the current implementation is more than fast enough.
Andreas
| From: | "Daniel Verite" <daniel(at)manitou-mail(dot)org> |
|---|---|
| To: | "Peter Eisentraut" <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | "Andreas Karlsson" <andreas(at)proxel(dot)se>,"pgsql-hackers" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-23 16:26:20 |
| Message-ID: | 6d55838c-9353-486f-a508-77ee07d59667@manitou-mail.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
Peter Eisentraut wrote:
> What is that status of this patch set? I think we have nailed down the
> behavior, but there were some concerns about certain performance
> characteristics. Do people feel that those are required to be addressed
> in this cycle?
Not finding any other issue with v3 or objections in the thread,
I've set the status to Ready For Committer in the CF.
Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | Daniel Verite <daniel(at)manitou-mail(dot)org> |
| Cc: | Andreas Karlsson <andreas(at)proxel(dot)se>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-24 09:20:54 |
| Message-ID: | 620b155b-a89c-d8e0-3cbb-315c3ca538f4@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-03-23 17:26, Daniel Verite wrote:
> Peter Eisentraut wrote:
>
>> What is that status of this patch set? I think we have nailed down the
>> behavior, but there were some concerns about certain performance
>> characteristics. Do people feel that those are required to be addressed
>> in this cycle?
>
> Not finding any other issue with v3 or objections in the thread,
> I've set the status to Ready For Committer in the CF.
I have committed the 0001 patch.
Now I have some concerns about the size of the new table in
unicode_normprops_table.h, and the resulting binary size. At the very
least, we should probably make that #ifndef FRONTEND or something like
that so libpq isn't bloated by it unnecessarily. Perhaps there is a
better format for that table? Any ideas?
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Cc: | Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-26 07:25:46 |
| Message-ID: | 7052cc8f-0164-72a8-d9a4-fd32066c938e@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-03-24 10:20, Peter Eisentraut wrote:
> Now I have some concerns about the size of the new table in
> unicode_normprops_table.h, and the resulting binary size. At the very
> least, we should probably make that #ifndef FRONTEND or something like
> that so libpq isn't bloated by it unnecessarily. Perhaps there is a
> better format for that table? Any ideas?
I have figured this out. New patch is attached.
First, I have added #ifndef FRONTEND, as mentioned above, so libpq isn't
bloated. Second, I have changed the lookup structure to a bitfield, so
each entry is only 32 bits instead of 64. Third, I have dropped the
quickcheck tables for the NFD and NFKD forms. Those are by far the
biggest tables, and you still get okay performance if you do the
normalization check the long way, since we don't need the recomposition
step on those cases, which is by far the slowest part. The main use
case of all of this, I expect, is to check for NFC normalization, so
it's okay if the other variants are not optimized to the same extent.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| Attachment | Content-Type | Size |
|---|---|---|
| v4-0001-Add-SQL-functions-for-Unicode-normalization.patch | text/plain | 224.6 KB |
| From: | John Naylor <john(dot)naylor(at)2ndquadrant(dot)com> |
|---|---|
| To: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-26 17:41:43 |
| Message-ID: | CACPNZCsiE6qN=yc-LBNLU5b9Hy06yagOXwsWGTJTvpXcrMHNTw@mail.gmail.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On Thu, Mar 26, 2020 at 3:26 PM Peter Eisentraut
<peter(dot)eisentraut(at)2ndquadrant(dot)com> wrote:
> I have figured this out. New patch is attached.
>
> First, I have added #ifndef FRONTEND, as mentioned above, so libpq isn't
> bloated. Second, I have changed the lookup structure to a bitfield, so
> each entry is only 32 bits instead of 64. Third, I have dropped the
> quickcheck tables for the NFD and NFKD forms. Those are by far the
> biggest tables, and you still get okay performance if you do the
> normalization check the long way, since we don't need the recomposition
> step on those cases, which is by far the slowest part. The main use
> case of all of this, I expect, is to check for NFC normalization, so
> it's okay if the other variants are not optimized to the same extent.
Reading the link cited in the patch
http://www.unicode.org/reports/tr15/#Detecting_Normalization_Forms
"The data for the implementation of the isAllowed() call can be
accessed in memory with a hash table or a trie (see Section 14,
Implementation Notes); the latter will be the fastest."
We don't have a trie implementation in Postgres, but we do have a
perfect hash implementation. Doing that would bring the tables back to
64 bits per entry, but would likely be noticeably faster than binary
search. Since v4 has left out the biggest tables entirely, I think
this might be worth a look for the smaller tables remaining.
In the attached v5, when building the hash tables, we sort the code
points by NO/MAYBE, and store the index of the beginning of the NO
block:
MMMNNNNNNNNN
~~~^
That way we can tell a NO from a MAYBE by testing the result of the hash lookup.
Regression tests pass, but I haven't measured performance yet. I had
to fiddle with the hash seeds a bit to get the larger table to build.
Also, if we go with v4, I noticed the following test is present twice:
+SELECT "normalize"('abc', 'def'); -- run-time error
--
John Naylor https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| Attachment | Content-Type | Size |
|---|---|---|
| v5-Add-SQL-functions-for-Unicode-normalization.patch | application/x-patch | 193.9 KB |
| From: | John Naylor <john(dot)naylor(at)2ndquadrant(dot)com> |
|---|---|
| To: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-03-27 07:16:12 |
| Message-ID: | CACPNZCvxXeYQtgVzWu9S5fzR2chF7g9ta-s2-njVjd=Pk=n_3A@mail.gmail.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
I wrote:
>
> Regression tests pass, but I haven't measured performance yet.
Using a test similar to one upthread:
select count(*) from (select md5(i::text) as t from
generate_series(1,100000) as i) s where t is nfc normalized ;
I get (median of three)
v4 419ms
v5 310ms
with binary size
v4 HEAD + 33kB
v5 HEAD + 57kB
--
John Naylor https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Cc: | Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-04-02 07:45:09 |
| Message-ID: | b93f79b0-7ea6-4807-e993-b0b3bbe8337a@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-03-26 08:25, Peter Eisentraut wrote:
> On 2020-03-24 10:20, Peter Eisentraut wrote:
>> Now I have some concerns about the size of the new table in
>> unicode_normprops_table.h, and the resulting binary size. At the very
>> least, we should probably make that #ifndef FRONTEND or something like
>> that so libpq isn't bloated by it unnecessarily. Perhaps there is a
>> better format for that table? Any ideas?
>
> I have figured this out. New patch is attached.
>
> First, I have added #ifndef FRONTEND, as mentioned above, so libpq isn't
> bloated. Second, I have changed the lookup structure to a bitfield, so
> each entry is only 32 bits instead of 64. Third, I have dropped the
> quickcheck tables for the NFD and NFKD forms. Those are by far the
> biggest tables, and you still get okay performance if you do the
> normalization check the long way, since we don't need the recomposition
> step on those cases, which is by far the slowest part. The main use
> case of all of this, I expect, is to check for NFC normalization, so
> it's okay if the other variants are not optimized to the same extent.
I have committed this version.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
|---|---|
| To: | John Naylor <john(dot)naylor(at)2ndquadrant(dot)com> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-04-02 07:51:19 |
| Message-ID: | 2d3e7d66-0f89-a663-280b-45d5b88b196b@2ndquadrant.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On 2020-03-26 18:41, John Naylor wrote:
> We don't have a trie implementation in Postgres, but we do have a
> perfect hash implementation. Doing that would bring the tables back to
> 64 bits per entry, but would likely be noticeably faster than binary
> search. Since v4 has left out the biggest tables entirely, I think
> this might be worth a look for the smaller tables remaining.
>
> In the attached v5, when building the hash tables, we sort the code
> points by NO/MAYBE, and store the index of the beginning of the NO
> block:
This is a valuable idea, but I fear it's a bit late now in this cycle.
I have questions about some details. For example, you mention that you
had to fiddle with the hash seed. How does that affect other users of
PerfectHash? What happens when we update Unicode data and the hash
doesn't work anymore? These discussions might derail this patch at this
hour, so I have committed the previous patch. We can consider your
patch as a follow-up patch, either now or in the future.
> Also, if we go with v4, I noticed the following test is present twice:
>
> +SELECT "normalize"('abc', 'def'); -- run-time error
I think this is correct. The other test is for "is_normalized".
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
| From: | John Naylor <john(dot)naylor(at)2ndquadrant(dot)com> |
|---|---|
| To: | Peter Eisentraut <peter(dot)eisentraut(at)2ndquadrant(dot)com> |
| Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, Daniel Verite <daniel(at)manitou-mail(dot)org>, Andreas Karlsson <andreas(at)proxel(dot)se> |
| Subject: | Re: Unicode normalization SQL functions |
| Date: | 2020-04-03 04:01:47 |
| Message-ID: | CACPNZCsptwBXYGqxT8RNsYVAc0dncJkCvtchUDg=6Jbrbuo8Vw@mail.gmail.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Lists: | pgsql-hackers |
On Thu, Apr 2, 2020 at 3:51 PM Peter Eisentraut
<peter(dot)eisentraut(at)2ndquadrant(dot)com> wrote:
>
> On 2020-03-26 18:41, John Naylor wrote:
> > We don't have a trie implementation in Postgres, but we do have a
> > perfect hash implementation. Doing that would bring the tables back to
> > 64 bits per entry, but would likely be noticeably faster than binary
> > search. Since v4 has left out the biggest tables entirely, I think
> > this might be worth a look for the smaller tables remaining.
> >
> > In the attached v5, when building the hash tables, we sort the code
> > points by NO/MAYBE, and store the index of the beginning of the NO
> > block:
>
> This is a valuable idea, but I fear it's a bit late now in this cycle.
> I have questions about some details. For example, you mention that you
> had to fiddle with the hash seed. How does that affect other users of
> PerfectHash?
They would still try the same multipliers they use now, so no effect on them.
> What happens when we update Unicode data and the hash
> doesn't work anymore?
The script would choose different multipliers and/or seeds
automatically. Only if you're unlucky would you have to fiddle with
the hash parameters again. The last-resort multipliers in the v2 patch
in the other thread [1] seem very effective and easily build both the
quick check D tables, which I tried for amusement's sake.
That said, we could reduce the chances of that happening this way:
After trying all the shift-and-add multipliers, we could add another
loop to try a bunch of numbers in a range. We'd need a quick check to
weed out multiples of small primes so the number has a decent chance
of being prime. To save time, just try a few seeds and move on to the
next number. Maybe emit a warning that it exhausted the shift-and-add
multipliers in case the developer wanted to intervene.
If I resubmit this, I would split the build up into two steps: have
the current manual script build the quick check array for later commit
into the tree, and build the hash function separately from that as a
Makefile distprep target. There's no reason to have the hash functions
checked in as I did in v5, like we don't check in the keyword hash
functions.
I would also consider splitting it into two patches:
1. Keep binary search but with a more abstract array representation
(think PG_RMGR). This patch would be large but mostly mechanical.
2. Switch to hash lookup. A smaller one for ease of review.
--
John Naylor https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services