[8pt] Describe iterator stability guarantees

[Totktonada]

Describe iterator stability guarantees

Product: Tarantool
Since: 1.7.4-420-g2160e4cbd
Audience/target: application / module developers.
Root document: TBD (a new article to be created)
SME: @alyapunov

Details

(Am I miss something? Maybe we have some article that answers all my questions?)

I want to know how exactly I can use index iterators. The motivating question is the following: if I'll open an iterator once for traversing the whole space what details I should keep in the mind? Whether the answer varies depending on an index type (tree/hash/rtree/bitset)? Depending on a space engine (memtx / vinyl)?

In fact, I unable to give a checklist. Let's consider the issue as request for such checklist.

Some examples I have in the mind. Say, if I open ALL iterator and then add a tuple that is minimal by given index, will I receive it from the iterator? Or, if I have [[1], [3]] space and open GT iterator with the key [1], fetch the first tuple ([1]), insert tuple [2] and fetch a next tuple from the iterator (will it return [2] or [3])? Are there incorrect actions that may lead to an undefined behaviour? Whether a vinyl index iterator is stable in the same sense and in the same way as a memtx tree iterator?

Please, take me right. I have partial information about those guarantees and constantly in doubt that I'm missing something. I would want to have a source of truth here: an article from an expert in the area or at least approved by the expert (from the point of comprehensiveness and correctness).

Maybe we can describe an index iterator algorithm in simple words and the description will answer all such questions.

Relevant links:

• Iterate over the space without loading all the data into lua memory expirationd#40 (motivates this issue)
• memtx: make tree iterators stable tarantool#1796 (where we makes tree iterators stable in memtx)
• https://t.me/tarantoolru/169179 (example of the question from @R-omk that is suitable for the checklist)

Definition of done

I highlighted points that're important for me. Feel free to add more if necessary.

• General guarantees.
• The list of cases one should take care about.
• (optional) Simple test cases that show the actual behaviour.
• Index types differences.
• Space engines differences.
• Tarantool versions differences.
• Approve of comprehensiveness from the expert.
• Approve of correctness from the expert.

(I guess it should be a kind of a separate article (user guide?), but don't know for sure.)

[veod32]

@Totktonada
Regarding the index iterators, we have only this as far as I can see:
https://www.tarantool.io/en/doc/latest/reference/reference_lua/box_index/pairs/

Can you please check if some of your points are covered there?
After that, we can decide what kind of content should be written additionally and where to put it.

[Totktonada]

The paragraph that starts from the 'To understand consistency of tuples' words looks more or less relevant. I propose the mental experiment here: can you answer questions above after reading it? For me the answer is 'no' (for all questions). What also doubts me: I'm not sure that the wording is perfectly correct in context of vinyl / MVCC.

[Totktonada]

I think the ideal solution would be an article (a separate page), where we'll collect all knowledge on the topic. The article will be referenced from the API documentation. Even if the article will duplicate information that spread across the documentation here and there in explicit or implicit way, there is no problem: it just presents this topic in the convenient way.

[Totktonada]

NB: Take care to the point in tarantool versions, where functional indexes became stable. See tarantool/tarantool#6786 for details.

[patiencedaur]

Related: #766