While indexing, scan cumulative (non-idempotent) indexes in SNAPSHOT resolution

[jjezra]

Currently, while a cumulative index is in write only mode, we keep track of the "already indexed" ranges and maintain the index iff the updated record is in one of these ranges. This also requires, while indexing, to scan a range of records in IsolationLevel.SERIALIZABLE mode - which significantly increases the probability of conflicts.

Here's one suggestion for an algorithm to change that:

Assumptions:

• Cumulative indexes are Commutative // a+b = b+a
• Cumulative indexes are Associative // (a+b)+c = a+(b+c)
• Cumulative indexes are joinable in O(1).

Suggested indexing process

let tmp_index be a scratch index created by the indexing process
let tmp_range_record be a set of {range => tmp_index} pairs in the recordstore.
During IO, records changes within range maintain the appropriate tmp_index. 

def one_range_indexer:
    # init
    tmp_index_rec = create_a_temp_index()
    tmp_range_record = read_tmp_range_record()

    # HERE: synced block begins:
    transactin_ser = init_range_transaction(full_range, IsolationLevel.SERIALIZABLE)

    # find real limits
    real_range = transaction_ser.get_range()
    tmp_range_record += {real_range => tmp_index_rec}

    transactin_snp = init_range_transaction(real_range, IsolationLevel.SNAPSHOT)
    # at this point, if transactin_ser commits successfuly, transactin_snp 
    # will be identical to it. Is that correct?
    
    # I wonder:
    # what is the preformance penalty of this 2nd range read? Is it fully cached?
    #   Is this 2nd read request more expensive than the indexing?

    if real_range != transactin_snp.get_range():
        cleanup
        return                  # retry

    transactin_ser.add_write(tmp_range_record)
    transactin_ser.commit()
    # HERE: synced block ends 

    # Now we can take our time, especially useful if we wish to index multiple 
    # non-idempotent indices within a single records scan
    
    if transactin_ser.committed:
        cleanup
        return                  # retry

    local_index_rec = create_a_temp_index() # this is a local var
    
    # scan the SNAP
    for rec in transactin_snp:
        if rec.match(our_index_critira):
            local_index_rec.add_index(rec)

    # and add the local + tmp indexes
    while true:
        if --sanity > 0:
            # no more retries
            cleanup
            return

        cur_index_rec.        = read_current_index()
        cur_tmp_ranges_record = read_tmp_range_record()
        cur_range_record      = read_range_record()

        cur_index_rec         += cur_tmp_index_rec + local_index_rec
        cur_tmp_ranges_record -= {real_range => tmp_index_rec}
        cur_range_record      += real_range

        transactin_snp.add_write(cur_index_rec )
        transactin_snp.add_write(cur_tmp_ranges_record)
        transactin_snp.add_write(cur_range_record)

        # well, probably it shouldn't be this way but some other CAS commit.
        transactin_snp.commit()

        if transactin_snp.committed:
            return DONE