andygrove opened a new issue, #299:
URL: https://github.com/apache/datafusion-spark/issues/299
Part of apache/datafusion-comet#7300 (Tier 5: `collate` and collation-aware
comparison, GROUP BY and joins).
### What the function does
Spark 4.0 added collations to `STRING`. The collation is part of the type:
`StringType(collationId)`, where
`collationId` is a 32-bit id decoded by `CollationFactory` (bit 29: UTF8
family vs ICU; bit 18: RTRIM; for ICU,
bit 17 case-insensitive, bit 16 accent-insensitive, bits 0-11 the locale).
Families:
- `UTF8_BINARY` (id 0, the default): byte comparison. The only collation
with `supportsBinaryEquality`.
- `UTF8_LCASE` (id 1): compares `lowerCaseCodePoints(s)` bytes. This is
per-code-point ICU simple lowercasing, plus
`İ` (U+0130) becoming `i` + U+0307 and final `ς` becoming `σ`. It is not
Unicode case folding.
- ICU collations: `UNICODE` (root locale) or a locale (`en`, `de`, `sv`,
`tr`, `en_USA`, ...), with optional `_CI`
and/or `_AI`. They map to ICU strengths: CS+AS = `ks=level3`, CI+AS =
`level2`, CS+AI = `level1` with case level
on, CI+AI = `level1`. Equality is `collator.compare(a, b) == 0`. The sort
key is ICU `CollationKey` bytes.
- `_RTRIM` on any of the above: trailing U+0020 spaces only are removed
before comparing, hashing and searching.
Collation-aware operations (Spark routes them through `CollationSupport` or
the collation's comparator / sort key):
`=`, `<=>`, `<`, `>`, `IN`, `nullif`, `greatest`, `least`, `ORDER BY`,
`DISTINCT`, `GROUP BY`, joins, set ops
(`UNION`, `INTERSECT`, `EXCEPT`), window partitioning, `contains`,
`startswith`, `endswith`, `instr`, `locate`,
`replace`, `split_part`, `split`, `substring_index`, `find_in_set`,
`translate`, `trim` / `ltrim` / `rtrim` / `btrim`,
`upper`, `lower`, `initcap`, `str_to_map`, and the array functions that
compare elements (`array_contains`,
`array_position`, `array_distinct`, `array_union`, `array_intersect`,
`array_except`, `arrays_overlap`,
`array_min` / `array_max`, `sort_array`). Regex functions (`like`, `rlike`,
`regexp_*`) accept only `UTF8_BINARY`
and `UTF8_LCASE` (`StringTypeBinaryLcase`). Trim, `translate` and
`str_to_map` reject case-sensitive
accent-insensitive collations (`StringTypeNonCSAICollation`). Collated map
keys are rejected unless
`spark.sql.collation.allowInMapKeys` is set
(`UNSUPPORTED_FEATURE.COLLATIONS_IN_MAP_KEYS`).
Which collation an expression uses comes from `CollationTypeCoercion`, by
strength: `Explicit` (`COLLATE`) beats
`Implicit` (column, cast of a string), which beats `Default` (literal). Two
different explicit collations fail with
`COLLATION_MISMATCH.EXPLICIT` (42P21). Two different implicit ones give an
indeterminate collation. That fails with
`INDETERMINATE_COLLATION` / `INDETERMINATE_COLLATION_IN_EXPRESSION` (42P22)
in operations that need a comparator,
and is allowed in pass-through ones such as `concat`.
### Examples
From `collations-basic.sql.out`, `collations-padding-trim.sql.out` and
`CollationSuite`:
```sql
-- t1(utf8_binary STRING COLLATE UTF8_BINARY, utf8_lcase STRING COLLATE
UTF8_LCASE)
-- rows: ('aaa','aaa'), ('AAA','AAA'), ('bbb','bbb'), ('BBB','BBB')
SELECT count(*) FROM t1 GROUP BY utf8_lcase; -- 2 | 2
SELECT * FROM t1 WHERE utf8_lcase = 'aaa' COLLATE utf8_lcase; -- AAA
AAA | aaa aaa
SELECT * FROM t1 WHERE utf8_lcase < 'bbb' COLLATE utf8_lcase; -- AAA
AAA | aaa aaa
SELECT * FROM t1 WHERE utf8_binary < 'bbb'; -- AAA
AAA | BBB BBB | aaa aaa
SELECT 'aaa' COLLATE utf8_lcase = 'AAA' COLLATE utf8_lcase; -- true
SELECT 'aaa' COLLATE utf8_binary_rtrim = 'aaa ' COLLATE utf8_binary_rtrim;
-- true
SELECT 'aaa ' COLLATE unicode_ci_rtrim = 'AAA ' COLLATE unicode_ci_rtrim;
-- true
SELECT 'a' COLLATE unicode < 'A'; -- true
SELECT 'aaa' COLLATE unicode < 'BBB' COLLATE unicode; -- true
SELECT 'a' COLLATE unicode_ai = 'å'; -- true
SELECT 'a' COLLATE unicode_ci_ai = 'Å'; -- true
SELECT 'Kypper' COLLATE sv < 'Köpfe'; -- true
SELECT 'Kypper' COLLATE de > 'Köpfe'; -- true
SELECT 'I' COLLATE tr_ci = 'ı'; -- true
SELECT least('aaa' COLLATE utf8_lcase, 'AAA' COLLATE utf8_lcase, 'a' COLLATE
utf8_lcase); -- a
SELECT nullif('aaa' COLLATE utf8_lcase, 'AAA' COLLATE utf8_lcase); -- NULL
SELECT array_contains(ARRAY('aaa' COLLATE utf8_lcase), 'AAA' COLLATE
utf8_lcase); -- true
SELECT array_distinct(array('aaa' COLLATE utf8_lcase, 'AAA' COLLATE
utf8_lcase)); -- ["aaa"]
SELECT array_except(array('aaa' COLLATE utf8_lcase), array('AAA' COLLATE
utf8_lcase)); -- []
SELECT col1 COLLATE utf8_lcase FROM VALUES
('aaa'),('AAA'),('bbb'),('BBB'),('zzz'),('ZZZ')
EXCEPT SELECT col1 COLLATE utf8_lcase FROM VALUES ('aaa'),('bbb'); -- zzz
SELECT ... UNION SELECT col1 COLLATE unicode_ci ...; --
error: INCOMPATIBLE_COLUMN_TYPE (UTF8_LCASE vs UNICODE_CI)
SELECT contains(collate('abc', 'UNICODE_CI'), collate('b', 'UNICODE')); --
error: COLLATION_MISMATCH.EXPLICIT
SELECT TRIM(utf8_binary, utf8_lcase) FROM t1; --
error: INDETERMINATE_COLLATION_IN_EXPRESSION
SELECT TRIM(utf8_binary COLLATE unicode_ai, utf8_lcase COLLATE unicode_ai)
FROM t1; -- error: DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE
```
`CollationSupportSuite` cases for `UTF8_LCASE`: `contains('The Kelvin.',
'Kelvin')` is true (KELVIN SIGN
lowercases to `k`); `contains('i̇', 'İ')` is true; `contains('İ', 'i')` is
false; `σ`, `ς` and `Σ` all match each
other. For `UTF8_BINARY`, `UTF8_LCASE`, `UNICODE` and `UNICODE_CI`,
`upper('ß fi ffi')` gives `SS FI FFI` and
`lower` leaves it unchanged.
### Edge cases to test
- Lowercasing vs case folding: `UTF8_LCASE` does not fold `ß` to `ss`, and
`ſ` (U+017F, already lowercase) is not
equal to `s` (code reading). `İ` expands to two code points, so lengths
and match positions shift
(`instr`, `locate`, `substring_index` report positions in the original
string).
- Accent insensitivity (`_AI`): `a` = `å`, but `trim`, `translate` and
`str_to_map` reject CS_AI collations.
- Ties in ordering: values equal under the collation (`aaa`, `AAA`) have no
defined order between them. The
representative a `GROUP BY` / `DISTINCT` / set op returns is whichever row
comes first (`aaa` in the examples
above). Tests should not depend on it.
- Hashing must agree with equality. Spark's shuffle partitioning uses
`CollationAwareMurmur3Hash` (Murmur3 over the
collation key bytes). Hash joins compare `CollationKey(col)`, injected by
`RewriteCollationJoin`. Hash aggregation
is disabled for non-binary-stable keys
(`Aggregate.supportsHashAggregate`), so Spark sort-aggregates with the
collation ordering. The user-facing `hash()` / `xxhash64()` hash raw bytes
since 4.0.1, unless
`spark.sql.legacy.collationAwareHashFunctions=true`.
- Nested types: structs and arrays of collated strings in `GROUP BY`, joins
and `=` (Spark recurses through
`CreateNamedStruct` / `ArrayTransform` when building keys). Group by
`c1.utf8_lcase` gives 1 row for `aaa`/`AAA`.
- RTRIM trims only U+0020. Tabs and NBSP are significant. Output values keep
their trailing spaces.
- Invalid UTF-8 is replaced (`toValidString` /
`CODE_POINT_ITERATOR_MAKE_VALID`) before ICU or lowercase comparison.
- Mixed strengths: column vs literal (implicit wins), explicit vs column
(explicit wins), two columns with different
collations (indeterminate), `CAST(x AS STRING COLLATE ...)`.
- `upper` / `lower` with ICU locale collations use the collator's locale
(`UCharacter.toUpperCase(locale, s)`),
but an all-ASCII input takes an ASCII fast path first. So under `tr`,
`upper('i')` gives `I`, while a string
with any non-ASCII character gets Turkish rules (`i` becomes `İ`) (code
reading of `CollationAwareUTF8String`).
`spark.sql.icu.caseMappings.enabled` (default true) switches `UTF8_BINARY`
case mapping to ICU.
- Empty strings, NULLs, and an empty search string in `contains` / `instr` /
`replace` for ICU collations
(`contains` returns true for an empty pattern).
### Differences across Spark versions
- 3.4 / 3.5: no collations.
- 4.0: collations introduced. Trim collations behind
`spark.sql.collation.trim.enabled` (default false outside
tests). `hash()` / `xxhash64()` stopped being collation-aware in 4.0.1
(legacy config above).
- 4.1: trim collations on by default;
`spark.sql.collation.schemaLevel.enabled` added. 4.2: trim config removed.
- `icu4j` is 76.1 in 4.0.4, 77.1 in 4.1.3 and 78.3 in 4.2.0. ICU-collation
results and sort keys can change between
these versions.
### Implementation notes
- Spark:
`common/unsafe/src/main/java/org/apache/spark/sql/catalyst/util/CollationFactory.java`
(ids, names,
comparators, `getCollationKeyBytes`), `CollationSupport.java`
(per-function `execBinary` / `execLowercase` /
`execICU`), `CollationAwareUTF8String.java` (lowercase search,
`lowerCaseCodePoints`, case mapping),
`sql/catalyst/.../analysis/CollationTypeCoercion.scala`,
`analysis/RewriteCollationJoin.scala`,
`expressions/CollationKey.scala`, `expressions/hash.scala`
(`CollationAwareMurmur3Hash`),
`sql/api/.../internal/types/AbstractStringType.scala`
(`StringTypeWithCollation`, `StringTypeBinaryLcase`,
`StringTypeNonCSAICollation`).
- DataFusion has no collation support. Arrow string types have no collation.
The proposal is to carry it as
Arrow field metadata (a key such as `spark.collation` = normalized name)
on `Utf8` / `LargeUtf8` / `Utf8View`
fields, including nested list element, struct child and map fields. UDFs
read it via `return_field_from_args` /
`ScalarFunctionArgs::arg_fields`. A missing key means `UTF8_BINARY`. Comet
would need to put the collation into
its serialized types.
- Operators (sort, hash join, aggregate, distinct) in DataFusion compare raw
bytes. Following Spark, the planner
(Comet or a DataFusion rewrite) can wrap keys in a `collation_key(str) ->
Binary` UDF whose bytes order and compare
like the collation, and keep the original column for output. This needs no
changes to DataFusion operators.
- Staged plan:
1. Shared infrastructure: collation name parsing and normalization, the
metadata convention, `collate` /
`collation` (separate issue), and `collation_key`.
2. `UTF8_LCASE` (and `_RTRIM` variants) in pure Rust: `char::to_lowercase`
(full mapping, so `İ` becomes `i̇`)
plus `ς` to `σ` matches ICU simple lowercasing code point by code
point, subject to the Unicode version.
Then add comparisons, `IN`, `greatest` / `least`, the string search
functions, `upper` / `lower` / `initcap`,
and the array functions.
3. ICU collations through the `icu_collator` / `icu_casemap` crates
(ICU4X) or `rust_icu` (ICU4C bindings).
- Risk: bit-exact results for ICU collations depend on the ICU / CLDR
version and implementation. ICU4X is not
ICU4J, and Spark's version changes per release. Ordering and equality may
differ on edge cases, and sort-key bytes
will not match ICU4J `CollationKey` bytes. That matters wherever keys are
shared with the JVM, for example
Murmur3 partition ids when one side of a join is shuffled by Spark and the
other natively. Gate ICU collations
behind a compatibility flag and test against Spark-generated vectors per
supported version.
- Tests: `.slt` files per function under `crates/sqllogictest/test_files/`
(function forms only, since the SQL parser
does not handle `COLLATE`). Port the literal cases from
`CollationSupportSuite.java`, `CollationFactorySuite.scala`
and `collations-*.sql.out`. Document new UDFs with `#[user_doc]`.
---
_This issue was generated by an LLM (Claude) from the Apache Spark source
code and tests. Examples come from Spark's `ExpressionDescription` examples,
test suites and `.sql.out` golden files, but please verify them against Spark
before relying on them._
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]