design document: how the query planner/executor work

[Totktonada]

• Basic planner cases and executor algorithm.
• Meaning of the query plan fields.
• What the executor will do, when both 'scan value' and 'after scan value' are present? I guess, it'll use 'after scan value' with GT/LT and transform 'scan value' to a post-filter, but I'm not completely sure.
• Whether the 'after scan value' always corresponds to the index determined by the first select condition? What if the first condition is not backed by any index? Will the 'after' condition be transformed to a post-filter (rather than GT/LT on an index) in the case?

Initially asked in https://github.com/tarantool/crud/pull/277#discussion_r878778465.

[oleg-jukovec]

At now I left a note here, but I'm going to structure it and add the documentation later.

The algorithm is not too complicated:

1. An index is selected according to a first condition with suitable fields. By default it is primary index (if there are no conditions with an index fields).
2. A traverse order is selected according to the condition (if it exists for the index). By default is ascending (GE, GT, EQ, ALL -> ASC, LE, LT, REQ -> DESC). At here we have a transformation EQ/REQ to GE/LE if after presents. 2.1 if first is negative value and after exists then we add a condition with after value as first one for the index and the traverse order.
3. A traverse start key (scan value) is selected as greater between the condition value (if it exists for the index) and after value according to the traverse order and the index. By default is nil (if there are no suitable conditions for the index and no after).
4. Start a traverse from the key (scan value).
5. Skip some tuples before after value (based on secondary + primary key fields) while tuples < after.
6. Fetch tuples + filtering by conditions (except the first one).

So cases:

1. If we have a condition (GT, GE, ALL, LT, LE) for an index + after then traverse starts from a greater one (according to traverse order). Other conditions will be used as post-filter.
2. If we have a EQ/REQ condition for an index + after then it will be full scan from the after value, EQ/REQ will be added to other conditions as post-filter.
3. If we have only non-index condition + after, then a primary index with an ascending order will be used. The non-index conditions will be used as post-filter.

So for the issue #276 and the pull request #277, we can consider after as a full scan in all cases without first <= 1000.