Observed with 8.0.0-alpha11 (follow-up of #29797) in the ETS import of E-Home (haumacher/ehome, doc/tl-todo.md).

<resolve-existing> builds one index of all objects of the listed types at the first ID it misses. For the parts of the KNX application programs (about 10,000 per program, many programs in a database), this loads every part of every program into each import, although an import only needs the parts of the programs it references.

Wanted: a lookup partitioned by a key derived from the ID (e.g. the prefix up to a separator, here the program ID before _) that loads one partition on demand.

Workaround in E-Home: SharedObjects, an own IdLookup installed with ImportContext#withIdLookup.

Side note (#29889): the link-once check of alpha11 (AbstractModelBinding.addValue()) reads the whole value of a multiple reference on each added element, so linking n elements one by one into a reference reads O(n^2^) elements.

Lösung

• partition on <resolve-existing> (optional): a function computing the partition key of an ID that is not known to the import, e.g. id -> $id.split("_", limit: 2).firstElement(). With it, the existing objects are indexed per partition: when an ID of a partition misses for the first time, objects is evaluated with the value of argument-var and the partition key as arguments (e.g. scope -> program -> ...) and its result is indexed by key; the index of each partition (also an empty one) is kept for the rest of the import. A partition key that is not a string is converted to its string representation; an ID with an empty partition key is not looked up. Objects of partitions the import does not reference are never computed. Without partition, the behavior is unchanged (one index of all objects, objects with one argument). <unless-known> uses the same lookup and works with partitions as well.
• TLObject.tContains(part, value) (and tContainsByName): whether a multiple reference contains an element (for a single-valued part: whether its value equals the element; null is never contained). The default reads the value. Persistent objects route the check to the attribute storage (StorageDetail.containsAttributeValue, default: read the value). ** SetStorage answers it from the indexed live link map at constant cost per element (as it does for add/remove since #29889). ** ListStorage (ordered references) answers it the same way for a reference that is no bag (bag="false", the default, i.e. an ordered set); for a bag it reads the list.
• ListStorage update without transient duplicate links: setting the value of an ordered reference (tUpdate) keeps the same links as before (the longest prefix of the current links that occurs in the new value in the same order), but now deletes all other links (with cleared references, so that a composite part is not deleted with its link) before creating the links of the new elements. Before, the link of a moved element was created before its old link was deleted, so two links to the same element existed in between, which the destination index cannot represent.
• AbstractModelBinding.addValue() uses tContains for its link-once check, so linking n elements one by one into a set or an ordered (non-bag) reference is linear.

Test

• test.com.top_logic.xio.importer.TestXmlImporter#testResolveExistingPartitions: objects is evaluated exactly once per referenced partition (also an empty one), never for an unreferenced partition or an ID with an empty partition key; existing objects are joined and linked once, references resolve within their partition.
• test.com.top_logic.element.meta.kbbased.storage.TestSetStorage: tContains within and after a transaction, and a CPU-time guard checking and adding 10,000 elements one by one within 3 s (about 18.5 s without the indexed check).
• test.com.top_logic.element.meta.kbbased.storage.TestListStorage: tContains after add, reorder, replace and remove, within the transaction, after commit and after rollback; a bag reference (default path); data with duplicate links; reordering a composite reference keeps the moved parts; CPU-time guard checking and adding 10,000 elements one by one within 3 s (about 10 s without the index).