List performance
As with any index, there is a tradeoff between performance and storage. Persisting a list index consumes additional space on disk, but eliminates the CPU cost of rebuilding it on every access. This page helps developers and SREs balance CPU impact with storage capacity. When storage is available, choosing an ordered list with a persisted index can significantly reduce CPU usage.
The following 𝓞 run time performance analysis is worst-case.
| Operation | Unordered (1) | Ordered (2) | Ordered, Persisted Index (3) |
|---|---|---|---|
| Set Type Ops | |||
set_type to unordered | 1 | 1 | 1 |
set_type to ordered | N log N | 1 | 1 |
| Read Ops | |||
size | 1 | 1 | 1 |
get_by_index | N | N | 1 |
get_by_rank | 1 | R log N + N | N |
get_by_index_range | N + M | N + M | M |
get_by_value_intervalget_all_by_value | N + M | log N + N | log N + M |
get_by_rank_range | R log N + N | N + M | M |
get_by_value_rel_rank_range | R log N + N | N + M + log N | M + log N |
get_all_by_value_list | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| Modify Ops | |||
set(0, v)append(v)insert(0, v) | 1 | log N + N | log N |
insert(i > 0, v)set(i > 0, v) | N | - | - |
| ADD_UNIQUE set/append/insert | N | log N + N | log N |
append_items(m) | M | (M + N)log M + N | (M + N)log M + N |
| ADD_UNIQUE append_items/insert_items | N* x M | (M + N)log M + N | (M + N)log M + M |
increment | N | - | - |
sort | N log N | 1 | 1 |
| UNIQUE sort | N log N | N | N |
clear | 1 | 1 | 1 |
remove_by_index | N | N | 1 |
remove_by_index_range | N + M | N + M | M |
remove_by_value_intervalremove_all_by_value | N + M | log N + N | log N + M |
remove_by_rank_range | R log N + N | N + M | M |
remove_by_value_rel_rank_range | R log N + N | N + M + log N | M + log N |
remove_all_by_value_list | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| Mode Modifiers | |||
| Storage | +D + W | ||
Legend
1: Unordered list. Element access by index requires a linear walk through packed elements. The offset index is built temporarily per operation and discarded afterwards.2: Ordered list without a persisted index. The list maintains value order and uses binary search for value lookups, but the offset index is built temporarily per operation and discarded afterwards.3: Ordered list with a persisted offset index. The persist-index flag stores the offset index in the list particle, eliminating the per-operation O(N) offset index build cost. Set a persisted index usingset_orderorcreatewith thepersistIndexoption.D: Cost of loading the record from storage.W: Cost of writing the record to storage.N: Element count of the list.M: Element count of parameter, range or interval.R: For rank r, R = min(r, N - r - 1).L: For index i, L = min(i, N - i - 1).C: Cost of memcpy on packed list.
Every modify op has a +C for copy on write for allowing rollback on failure.
Notes
- Column (2) applies to ordered lists created with an ordered list policy or
set_orderbut without the persist-index flag. These lists maintain value order but do not persist the offset index. - Without a persisted index, the offset index is built temporarily for each operation and discarded afterwards. This adds an O(N) cost per operation, which is why columns (1) and (2) show higher complexity than column (3) for many operations.
- With a persisted offset index (column 3), the offset index is stored in the list particle. This eliminates the per-operation O(N) build cost, enabling O(1) index-based access. In an ordered list, index and rank are equivalent, so rank-based operations also benefit.
- The persist-index flag is set explicitly by the client and is preserved across all subsequent list operations (append, insert, remove, etc.) until changed by another
set_ordercall. - The persist-index flag is only supported for top-level lists. Nested list indexes are not supported and the flag is silently ignored.
- The replication cost is 𝓞(n), where n is the total byte size of list elements, because full records are replicated and persisted on replicas.
- Reminder: worst-case, average-case and best-case performance are different categories. You should compare like to like.
Return type performance implications
The complexities above assume the default return type. Requesting a non-default return type adds extra CPU cost. See the Performance section of each list operation for specifics.
- Index-range operations (
get_by_index_range,remove_by_index_range) incur an additional O(L*N) cost when requesting aRANKreturn type on an unordered list, where L = min(i, N - i - 1). On ordered lists (with or without a persisted index), rank equals index, so there is no extra cost.