pvary commented on code in PR #16961: URL: https://github.com/apache/iceberg/pull/16961#discussion_r4524721606
########## format/index-spec.md: ########## @@ -0,0 +1,647 @@ +--- +title: "Index Spec" +--- +<!-- + - Licensed to the Apache Software Foundation (ASF) under one or more + - contributor license agreements. See the NOTICE file distributed with + - this work for additional information regarding copyright ownership. + - The ASF licenses this file to You under the Apache License, Version 2.0 + - (the "License"); you may not use this file except in compliance with + - the License. You may obtain a copy of the License at + - + - http://www.apache.org/licenses/LICENSE-2.0 + - + - Unless required by applicable law or agreed to in writing, software + - distributed under the License is distributed on an "AS IS" BASIS, + - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + - See the License for the specific language governing permissions and + - limitations under the License. + --> +# Iceberg Index Specification + +## Background and Motivation + +An index is a secondary store of data from a table that is structured to accelerate specific access patterns. +An index is derived from the rows of a source table and is stored separately from table data, so it can be built, +refreshed, or dropped without rewriting the table. + +An index is most valuable when it is a property of the table rather than of the engine that built it. This +specification defines a common format for index metadata and a common storage architecture for index data, so that any +engine can build an index, maintain it, and use it to plan queries against the table. + +## Goals + +* **Independence** -- An index is committed as a separate object, without modifying its source table. +* **Consistency** -- An index reflects exactly the live rows of a single state of its source table. +* **Read-optimized** -- An index is structured for fast reads, at the cost of extra work when writing. +* **Incrementality** -- An index is refreshed by writing only the index data affected by the table's changes. +* **Scalability** -- An index supports any table size that the table spec supports. +* **Portability** -- An index is readable and maintainable by any engine, not only the one that wrote it. +* **Extensibility** -- An index type or ordering strategy can be added without disrupting existing indexes or + engines that do not implement it. + +## Overview + +Index state is maintained in index metadata files. All changes to index state create a new metadata file and replace +the old metadata with an atomic swap, as defined in [Commits and Concurrency](#commits-and-concurrency). An index +metadata file tracks the index definition, index properties, and extracts of a single index. A table may have +any number of indexes, including multiple indexes of the same type. + +An extract represents the state of an index for one snapshot of its source table and is used to access the +complete set of index data files for that state. The index data of an extract is organized as a +[tracking file](#tracking-file) that lists a set of [region files](#region-files). Index data files are immutable and +may be referenced by more than one extract. + +## Specification + +### Terms + +* **Index** -- A structure that accelerates retrieval of rows from a source table. +* **Extract** -- The state of an index for a single snapshot of the source table. +* **Index entry** -- The values produced by the index fields for one indexed row of the source table. +* **Ordering key** -- The tuple of values that determines the position of an index entry within an extract. +* **Tracking file** -- A file that lists the region files of an extract; one per extract. +* **Region file** -- A file that stores the index entries for a range of ordering keys; a subset of an extract. + +### Locations in Metadata + +Location strings stored in index metadata are classified and resolved as defined by +[paths in metadata](spec.md#paths-in-metadata) in the table specification. Relative locations are resolved against the +index `location`, which must be an absolute location. + +### Index Definition + +An index is defined by a source table, an index type, an [extract schema](#extract-schema), +[stats-only fields](#stats-only-fields), and an [ordering key](#ordering-key). The definition is fixed when the index is +created so that region files remain readable through every extract that references them. Only extract schema field +types and optionality, and the data types of stats-only fields, may change, as defined in +[Extract Schema Evolution](#extract-schema-evolution). Any other change requires a new index. + +Index properties configure how an index is written and maintained, such as the target size of region files. Any commit +may change properties, and readers must not depend on them. + +#### Index Type + +The index type defines the logical category of an index and the class of queries it accelerates. + +| Type | Description | +|----------|------------------------------------------------------------------------------------------------------------------------| +| `scalar` | Accelerates point lookups on ordering key fields, and range filters when the ordering expressions are order preserving | + +This specification defines a single index type, `scalar`. Future specifications may define additional types. + +Writers must write `index-type` in lower case. Readers must match it case-insensitively. + +#### Extract Schema + +The extract schema is an Iceberg [schema](spec.md#schemas-and-data-types) and follows the same rules as a table schema. +It defines the fields of an index entry and is used to read region files. It contains identity columns, which store a +value of the indexed row as is. [`identity-fields`](#identity-fields) maps each source field to its identity column. A +source field is a source table field or a [metadata column](spec.md#reserved-field-ids), except `_deleted`, +`_partition`, the changelog columns (`_change_type`, `_change_ordinal`, `_commit_snapshot_id`), and the delete file +columns (`file_path`, `pos`, `row`). + +Extract schemas are stored in `schemas`, and each extract references one by `extract-schema-id`. Each identity column +must have the type of its source field: for a table field, as defined by the schema of the extract's source table +snapshot, which must have a `schema-id`; for a metadata column, as defined by the table specification. An identity +column must be optional if its source field is optional. If no existing extract schema matches, a new one is added. +If the source field of an identity column is dropped, no new extracts can be created. + +##### Extract Schema Evolution + +Extract schemas of an index may differ only in field types and optionality. Field IDs, names, order, and nesting must +be the same in every extract schema. Compared to the most recently added extract schema, each field in a new extract +schema must have the same type or a valid [type promotion](spec.md#schema-evolution), and may change from required to +optional but not from optional to required. + +Stats-only fields are shared by all extracts. The `data-type` of a stats-only field may change only by a valid type +promotion, when a new extract schema promotes the result type of its `expr`. No other stats-only field property may +change. + +Each extract schema only widens all earlier ones, so a region file can be read with the schema it was written with +or any schema added later. An extract must not reuse a region file written with an extract schema added after its own. +For `ordering-key` fields, including stats-only fields, a promoted type must also order all values of the original type +identically. + +#### Stats-only Fields + +Stats-only fields track statistics for derived values that are not stored in region files, as defined by +[stats-only fields](spec.md#stats-only-fields) in the table specification. They are stored in the index metadata +`stats-fields` list. Writers compute their values from the identity columns of each index entry, to produce +`content_stats` in [tracking file entries](#tracking-file-entry) and, for `ordering-key` fields, to order index entries. +Readers can use these statistics to prune region files. + +Stats-only fields of an index follow the table specification, with the following additional constraints: +* `field-id` must be unique across extract schema field IDs and other stats-only field IDs. +* `type` must be `expr-value`, as an index has no partition spec. +* `expr` must be deterministic and may reference only identity columns, by extract schema field ID. + +#### Ordering Key + +`ordering-key` is a non-empty list of field IDs of extract schema fields or [stats-only fields](#stats-only-fields), +each of a primitive type. The values of the referenced fields, in list order, form the ordering key of an indexed row +and determine the row's position in the index, as defined in [Ordering](#ordering). The value of a stats-only field is +the result of its `expr` evaluated for the indexed row. + +### Index Metadata + +The index metadata file stores the index definition and extract history. It is encoded as JSON. + +#### Index Metadata File + +The index metadata file has the following fields: + +| Requirement | Field name | Type | Description | +|-------------|---------------------------|----------------------------|---------------------------------------------------------------------------------| +| _required_ | `format-version` | `int` | Index format version; must be `1` | +| _required_ | `index-uuid` | `string` | Stable UUID assigned at creation | +| _required_ | `table-uuid` | `string` | UUID of the indexed table | +| _required_ | `location` | `string` | Index root location | +| _required_ | `last-updated-ms` | `long` | Timestamp when the index was last updated (ms from epoch) [1] | +| _required_ | `index-type` | `string` | Logical index type | +| _required_ | `identity-fields` | `list<identity-field>` | Identity columns of the extract schema, see [Identity Fields](#identity-fields) | +| _required_ | `schemas` | `list<schema>` | Extract schemas, see [Extract Schema](#extract-schema) | +| _optional_ | `stats-fields` | `list<stats-field>` | Stats-only fields, see [Stats-only Fields](#stats-only-fields) | +| _required_ | `ordering-key` | `list<int>` | Field IDs that form the ordering key, see [Ordering Key](#ordering-key) | +| _optional_ | `properties` | `map<string, string>` | Index properties applicable for every extract | +| _optional_ | `extracts` | `list<extract>` | Extracts [2] | +| _optional_ | `metadata-log` | `list<metadata-log-entry>` | Previous index metadata files, see [Metadata Log](#metadata-log) | +| _optional_ | `encryption-keys` | `list<encryption-key>` | Encryption keys used by the index, see [Encryption Keys](#encryption-keys) | + +A missing optional list must be read as an empty list. + +Notes: + +1. Each index metadata file should update `last-updated-ms` just before writing. +2. An index that has not been built yet has no extracts. +3. Index names are not stored in index metadata. It is the catalog's responsibility to map index names to metadata file + locations. +4. How the indexes of a table are discovered is out of scope for this specification and is defined by the catalog + specification. + +#### Identity Fields + +Each entry in `identity-fields` maps a source field to its identity column in the [extract schema](#extract-schema), +like a partition field maps a source column to a partition field. + +| Requirement | Field name | Type | Description | +|-------------|-------------|-------|-------------------------------------------------| +| _required_ | `source-id` | `int` | ID of the source table field or metadata column | +| _required_ | `field-id` | `int` | Extract schema field ID of the identity column | + +Each `source-id` and each `field-id` must be unique within `identity-fields`. + +#### Extract + +An extract is an immutable version of the index data generated from a specific source table snapshot. It +references a complete set of index files through the location of a single [tracking file](#tracking-file). + +An extract must index exactly the live rows of the referenced table snapshot. + +| Requirement | Field name | Type | Description | +|-------------|-------------------------------|-----------------------|--------------------------------------------------------------------| +| _required_ | `extract-id` | `long` | Extract identifier | +| _required_ | `source-table-snapshot-id` | `long` | Source table snapshot | +| _required_ | `extract-schema-id` | `int` | ID of the [extract schema](#extract-schema) in `schemas` | +| _required_ | `timestamp-ms` | `long` | Timestamp when the extract was created (ms from epoch) | +| _required_ | `tracking-file` | `string` | Location of the tracking file | +| _required_ | `tracking-file-size-in-bytes` | `long` | Total size of the tracking file in bytes | +| _optional_ | `properties` | `map<string, string>` | Extract properties specific to this extract | +| _optional_ | `key-id` | `string` | ID of the encryption key that holds the tracking file key metadata | + +Each `extract-id` must be unique within the `extracts` list. Engines locate index data by matching +`source-table-snapshot-id`. More than one extract may reference the same source table snapshot, and an engine may +use any of the matching extracts. + +#### Metadata Log + +`metadata-log` records the index metadata files that preceded the current one. A commit should append an entry for the +metadata file it replaces. The number of entries to retain is controlled by the index property +`write.metadata.previous-versions-max`, and a commit drops the oldest entries beyond that limit. When +`write.metadata.delete-after-commit.enabled` is true, a commit also deletes the dropped metadata files. + +| Requirement | Field name | Type | Description | +|-------------|-----------------|----------|-----------------------------------------------------------------| +| _required_ | `metadata-file` | `string` | Location of the index metadata file | +| _required_ | `timestamp-ms` | `long` | `last-updated-ms` of the index metadata file at `metadata-file` | + +#### Encryption Keys + +An index must not store indexed values with weaker protection than its source table. If the source table snapshot that +an extract indexes is encrypted, indicated by the snapshot's `key-id` as defined by the table specification, the +tracking file and the region files of that extract must be encrypted. + +Index metadata is not encrypted, so keys are never stored in plain form. Keys used for index encryption are tracked in +index metadata as a list named `encryption-keys`, using the [encryption keys](spec.md#encryption-keys) structure defined +by the table specification. The format of encrypted key metadata is determined by the index's encryption scheme and can +be a wrapped format specific to the KMS provider. + +The `key-id` of an extract must reference a `key-id` in the index metadata `encryption-keys` list. The +`encrypted-key-metadata` of the referenced entry is the key metadata of the extract's tracking file, which in turn +holds the key metadata of the region files. + +### Commits and Concurrency + +Index metadata is immutable. Every update, whether adding an extract, dropping an extract, or changing index properties, +must produce a new index metadata file with a unique name. + +A commit replaces the current index metadata file with the new one. The swap must be atomic and must succeed only if the +current metadata file is still the file the writer started from, identified by name. If a newer metadata file has been +committed since the writer read the metadata, the commit must be rejected. + +A writer whose commit is rejected must not overwrite the newer metadata. It may re-read the latest committed metadata +and retry the update on top of it, or discard the attempted update. + +Index maintenance may be performed synchronously with the table commit that produces a new source-table snapshot, or +asynchronously by a separate maintenance process. A catalog may enforce transactional commits that atomically update +both the table and the index, guaranteeing that every committed table snapshot has a corresponding extract. When +an index is updated asynchronously, the index may lag behind the table and engines must reconcile the extract +against the source-table snapshot they intend to read. + +### Index Data + +#### Ordering + +The ordering key defines an ordering over all index entries of an extract. Index entries must be partitioned +into ranges of ordering key values that do not overlap, and each range must be stored in a separate region file. A +region boundary must fall at a change in ordering key, so all index entries that share an ordering key are stored in +the same region file. Review Comment: Thanks, this is a valid concern for hot keys. The main target is keys that are almost unique, like primary keys, where duplicates are rare. For these, the same-file rule costs nothing, and a lookup reads exactly one region file. Allowing a key to span multiple region files would change the read path in two ways: - If the matched `max_ordering_key` equals the key, the reader also has to check the next tracking file entry. This is a small cost. - A lookup may need to read an unbounded range of region files instead of one. That is a structural change, and may need a scan-like plan instead of a single file read. Indexes with hot keys can already get this flexibility by ending the ordering key with a unique field, like `[ bucket(256, user_id), user_id, _row_id ]`. Region boundaries can then split a hot key, and lookups prune on the ordering key prefix. New rows get increasing row IDs, so a refresh rewrites at most the last region file of the key. This way only these indexes pay for multi-file lookups. -- 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]
