danielcweeks commented on code in PR #16972: URL: https://github.com/apache/iceberg/pull/16972#discussion_r4109325500
########## format/spec.md: ########## @@ -347,9 +348,74 @@ For example, a struct column `point` with fields `x` (default 0) and `y` (defaul Default values are attributes of fields in schemas and serialized with fields in the JSON format. See [Appendix C](#appendix-c-json-serialization). +#### Collations + +A `string` field may carry a **collation**, an attribute that changes how the field's values are compared and ordered without changing how they are stored. Collations enable case-insensitive, accent-insensitive, and locale-aware comparison and sorting. A collation only affects comparison: the stored value is returned unchanged (a value written as `'appLE'` is read back as `'appLE'`). + +This change defines exactly two things: the `collation` annotation on string fields, and collation-aware file pruning through collation bounds stored in `content_stats`. It does not give collation semantics to any other part of the table format, because collation order and equality are not stable across collation implementation versions or engines, while the rest of the format must be deterministic. Specifically: + +* Byte-order `lower_bounds`/`upper_bounds`, partition transforms (including `truncate`), and `bucket`/hash all operate on the binary UTF-8 value and are collation-unaware. Collation-equal but byte-distinct values may therefore land in different partitions or buckets, and a reader must not use partition or bucket pruning to eliminate candidates for a predicate evaluated under a collation. +* Equality-delete matching and identifier-field equality are binary value equality by field id; a `collation` annotation does not make either collation-aware. An engine that needs a collation-dependent delete must resolve it to position deletes or an explicit set of values. +* Map key identity is by stored (byte) value, not by collation. A collation on a map key does not merge keys: `map['ABC']` and `map['abc']` remain distinct entries and both may be present in the same map. A key collation affects only how predicates over keys compare — collation-aware key lookup may therefore match more than one stored key, and how that is resolved is engine-defined. +* This change does not define collation-aware sort orders. + +SQL-level comparison, equality, ordering, grouping, and distinctness are the engine's responsibility. Engines read the `collation` annotation and apply their own semantics; they must not infer broader behavior from the table-format metadata alone. + +A collation may be attached to any field of `string` type, top-level or nested: as a `collation` attribute on a struct field, or as an `element-collation`, `key-collation`, or `value-collation` attribute on an enclosing `list` or `map` (see [Appendix C](#appendix-c-json-serialization)). It may be attached only to `string` types. A string field with no collation defaults to UTF-8 byte-order comparison, the behavior of all prior versions. Nesting does not change how collation bounds work: because every nested string position has its own field id, a collation on a nested string is annotated and carries collation bounds in its own `content_stats` exactly as a top-level string field (see [Collation Bounds](#collation-bounds)). + +A collation is identified by a provider-qualified name of the form `<provider>.<name>`, for example `icu.en_US-ci`. The provider names the library that defines the collation: `icu` for collations defined by the [Unicode Collation Algorithm](https://unicode.org/reports/tr10/) over [CLDR](https://cldr.unicode.org/) locale data. Providers are a fixed set defined by this spec (`icu`, and the reserved `utf8` below); new providers are added by spec change rather than ad hoc, so that a collation means the same thing on every engine. An engine that does not recognize a provider must not use the collation or its bounds. + +The name is a locale with optional modifiers, per the grammar below. Modifier order and letter case are fixed, so the specifier has a canonical form comparable as a string: + +``` +specifier = icu-spec | utf8-spec +icu-spec = "icu" "." locale [ "-" case-mod ] [ "-" accent-mod ] [ "-" trim-mod ] +utf8-spec = "utf8" [ "-" trim-mod ] +locale = language [ "_" region ] ; e.g. en, de, en_US, de_DE +case-mod = "cs" | "ci" ; case sensitive (default) / insensitive +accent-mod = "as" | "ai" ; accent sensitive (default) / insensitive +trim-mod = "ltrim" | "rtrim" | "trim" ; trim leading / trailing / both spaces (U+0020) +``` + +Case- or accent-insensitivity requires a locale, because the rules are language-specific — `ł` and `l` are the same character for `icu.en-ai` but distinct for `icu.pl-ai`. Case-conversion modifiers (upper / lower / casefold) are out of scope for v1. + +The bare name `utf8` is reserved for UTF-8 byte-order comparison and is the one collation name exempt from the `<provider>.<name>` form. It is exactly equivalent to omitting the `collation` attribute: readers and writers must treat a field annotated `utf8` and a field with no collation identically, and adding or removing an explicit `utf8` on an already-uncollated field is a no-op that does not change comparison semantics. A field with collation `utf8` (or no collation) uses the byte-order `lower_bounds`/`upper_bounds` directly and carries no `collation_bounds`. + +The schema stores the collation **name without a version**, so any engine that supports the collation can read the table. UCA, DUCET, CLDR, and ICU collation orders are [not stable across versions](https://unicode.org/reports/tr10/#Non-Goals), so collation-aware metrics carry the implementation version they were produced under (see below) and a reader uses them only when it can produce the same order. + +The version is the identifier the provider uses to version its collation order, and must be a value that changes only when the collation order can change, so that a byte-exact match between two engines means they produce the same order. For the `icu` provider this is the [ICU collator version](https://unicode-org.github.io/icu/userguide/collation/architecture.html#versioning) reported for the collation (which folds in the UCA, DUCET, and CLDR versions and the tailoring), formatted as ICU reports it. Two engines built against the same collation data therefore report the same version and can share bounds; a provider release that does not change any order reports the same version, so existing bounds stay usable and no new entry is needed. The version is provider-defined and is compared as an opaque string: a reader treats bounds as usable only on an exact `(collation, version)` match and otherwise scans, so a mismatch degrades pruning but never correctness. + +##### Collation Bounds + +Because a collation can reorder values (for example `'a' < 'B'` under a case-insensitive collation, but `'a' > 'B'` in byte order), byte-order bounds — the v3 `lower_bounds`/`upper_bounds` maps and the byte-order bounds in `content_stats` — cannot be used to evaluate predicates on a collated column. Collation-aware bounds are stored instead in the collated field's own [content stats](#content-stats): the field's stats struct carries a `collation_bounds` list — one entry per collation version — plus `min_code_point` and `max_code_point` for the file. Nothing is added to the schema; the version travels with the metrics. + +Each `collation_bounds` entry holds: + +| Field | Type | Description | +|-------|------|-------------| +| `version` | `string` | Provider's collation version the bounds were produced under (for `icu`, the ICU collator version); compared as an opaque string on read | +| `lower_bound` | field type | Minimum value under the collation order, stored as the original value (not a sort key) | +| `upper_bound` | field type | Maximum value under the collation order, stored as the original value | + +The bounds are the **original values** that are the minimum and maximum under the collation order, not collation sort keys (sort keys are not stable across implementation versions). Because the version is recorded on each entry, a writer on a new version just adds an entry — no schema change — and a file may carry several entries, one per `(collation, version)`, so a single file can serve readers pinned to different versions during an upgrade. The collation itself is resolved from the field, not repeated per entry. + +`min_code_point` / `max_code_point` record the range of Unicode code points present in the file's values for this field. They are independent of the collation version and are stored once. A reader may use them to reuse a bound across versions when it can establish that the versions order that code-point range identically — for example, an ASCII-only file when a version bump only changed non-ASCII ordering. The exact set of code-point statistics is left to a follow-up. + +Collation bounds should be tight (the exact minimum and maximum). Iceberg allows truncated bounds in general, but truncating an original value under a collation order is not straightforward — there is no simple successor under an arbitrary collation — so a v1 writer that cannot compute the exact bound should omit it rather than approximate it. Collation-aware truncation is a possible later optimization; omitting a bound only falls back to a scan, so it never affects correctness. + +**Writers** are not required to write byte-order bounds for collated columns — as with any column, statistics are optional — but writing them is encouraged so collation-unaware readers can still prune. A writer that supports the field's collation should additionally write a `collation_bounds` entry tagged with the exact `(collation, version)` it used. A writer that does not support the collation or version must not write a collation bound for that field. + +**Readers** may prune a file using a `collation_bounds` entry only when its `version` matches the version the reader resolves for the field's collation — or when the reader can otherwise prove the order is unchanged for the file's code-point range; otherwise the entry must be ignored. A reader must not use byte-order bounds to prune comparison, equality, or prefix predicates on a collated column. Collation bounds support comparison and equality pruning only: prefix predicates such as `STARTS_WITH` or `LIKE 'x%'` cannot be pruned by either byte-order or collation bounds, because prefix relationships are not preserved under an arbitrary collation order. When no usable collation bound is available, the file must be scanned. A collation-unaware reader ignores the `collation` attribute and the `collation_bounds`, reading the column as a UTF-8 byte-order string. Review Comment: > A collation-unaware reader ignores the `collation` attribute Can a read who doesn't understand a specific collation apply the same behavior? An engine that knows nothing about collations would apply utf-8 byte ordering, but is there a higher requirement for engines that understand some, but not all, collations? -- 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]
