[IGNITE-17859] Update indexes on data modifications

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 3.0.0-beta1
• Labels: ignite-3
• Epic Link: SQL indexes 3.0
• Assignee: Konstantin Orlov
• Reporter: Alexander Lapin
• Reviewer: Alexander Lapin
• Created: 10/Oct/22 06:44
• Updated: 27/Oct/22 17:25
• Resolved: 27/Oct/22 15:09

Description

Motivation

For the sake of better performance and common sense, it is necessary to integrate indexes into data manipulation flow, which implies

• Integrating indexes into the process of efficient evaluation keys to rowsIds both within pure read/scan operations and as part of modification operations in order to find proper rowId of a row to be modified.
• Integrating indexes into the process of data modification itself, meaning that not only data should be updated but also all corresponding indexes should be populated with updated entries along with cleanup on transaction rollback.

Given Jira issue is about second part.

Definition of Done

• All indexes with relevant schema version are populated with modified rows.
• All pending index entries are removed on tx rollback.

Implementation Notes

1. Seems, that it has sense to introduce new Index abstractions that will manage update logic internally. Something like following:
   • Index
   • HashIndex extends Index
   • HashUniqueIndex extends HashIndex
   • SortedIndex extneds Index
   • SorteUniquedIndex extneds SortedIndex
2. In order to define which indexes to update both during update itself or during rollback it'll be useful to add extra parameter schemaVersion to each operation enlisted into transaction. All in all, that will allow to select only proper set of indexes with relevant schema versions.
3. During transaction rollback it'll be necessary  to cleanup outdated pending entries that were touched during tx lifetime. 

More details about first item.

Index itself may declare update() and other methods that will have index-type-specific lock management and uniqueness processing logic, e.g. for HashIndex.update following is suggested:

@Override
public CompletableFuture update(UUID txId, TxState txState, Tuple oldRow, Tuple newRow, VersionChain<Tuple> rowId) {
    Tuple oldVal = oldRow == Tuple.TOMBSTONE ? Tuple.TOMBSTONE : oldRow.select(col);
    Tuple newVal = newRow == Tuple.TOMBSTONE ? Tuple.TOMBSTONE : newRow.select(col);

    List<CompletableFuture> futs = new ArrayList<>();

    if (!oldVal.equals(newVal)) {
        if (oldVal.length() > 0) {
            Lock lock0 = lockTable.getOrAddEntry(oldVal);

            txState.addLock(lock0);

            futs.add(lock0.acquire(txId, LockMode.IX));

            // Do not remove bookmarks due to multi-versioning.
        }

        if (newVal.length() > 0) {
            Lock lock0 = lockTable.getOrAddEntry(newVal);

            txState.addLock(lock0);

            futs.add(lock0.acquire(txId, LockMode.IX).thenAccept(ignored0 -> {
                if (index.insert(newVal, rowId)) {
                    txState.addUndo(() -> index.remove(newVal, rowId));
                }
            }));
        }
    }

    return CompletableFuture.allOf(futs.toArray(new CompletableFuture[0]));
} 

Further details could be found in https://github.com/ascherbakoff/ai3-txn-mvp

Detailed lock management design is described in  IEP-91-Locking model See index related sections, e.g. for HashIndex following lock flow is suggested:

Non-unique locks
  // scan
  S_commit(key)

  // insert
  IX_commit(key)

  // delete
  IX_commit(key) 

More details about third item.

Please see cleanup flow described in https://issues.apache.org/jira/browse/IGNITE-17673

 

It might have sense to consider all three items as separate tickets.

It also worth to mention that index modification is triggered from PartitionListener

• handleUpdateCommand
• handleUpdateAllCommand
• handleTxCleanupCommand

Issue Links

• blocks: IGNITE-17813 Sql. Introduce sorted reducer for IndexScanNode
• split to: IGNITE-17974 Clean up indexes on rollback
• links to: GitHub Pull Request #1191
• links to: GitHub Pull Request #1261