The `matras_touch` function is split into two parts: `matras_need_touch`
and `matras_touch_no_check`. The first one checks if a matras block ID
needs to be touched to be modified, another one performs the touch of
the given block.

Needed for tarantool/tarantool#10183

The `matras_touch` function is split into two parts: `matras_needs_touch`
and `matras_touch_no_check`. The first one checks if a matras block ID
needs to be touched to be modified, another one performs the touch of
the given block.

Needed for tarantool/tarantool#10183

The `matras_touch` function is split into two parts: `matras_needs_touch`
and `matras_touch_no_check`. The first one checks if a matras block ID
needs to be touched to be modified, another one performs the touch of
the given block.

Needed for tarantool/tarantool#10183

Prior to this the count request had been performed in the memtx in the
traightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which may lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in tarantool#10183.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

NO_DOC=TBD when fully implemented
NO_CHANGELOG=TBD when fully implemented

Prior to this the count request had been performed in the memtx in the
straightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which could lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

Since the method does not read each counted tuple now, MVCC subsystem
would be unaware of it. In order to fix this, this patch introduces a
new entity in the memtx transaction manager to track such operations:
GAP_COUNT, and the corresponding `memtx_tx_track_count` function.

The entity (gap item) is a record that a concurrent transaction has
counted tuples matching some key and iterator type in an index.

If a transaction creates such an entity, any insertion or deletion
of a matching tuple in the index will be conflicted with it. This
works differently for inserts and deletes:

1. If a concurrent transaction inserts a new matching tuple, then
   its read_gaps list is modified like the counted transaction had
   read the exact key of the tuple and found nothing. This creates
   a conflict.

2. If a concurrent transaction deletes a matching tuple, then the
   transaction that counted the tuple is inserted into the tuple
   reader list: it pretends to have read the tuple prior to the
   deletion. This creates a conflict.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in tarantool#10183.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

NO_DOC=TBD when fully implemented
NO_CHANGELOG=TBD when fully implemented

Prior to this the count request had been performed in the memtx in the
straightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which could lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

Since the method does not read each counted tuple now, MVCC subsystem
would be unaware of it. In order to fix this, this patch introduces a
new entity in the memtx transaction manager to track such operations:
GAP_COUNT, and the corresponding `memtx_tx_track_count` function.

The entity (gap item) is a record that a concurrent transaction has
counted tuples matching some key and iterator type in an index.

If a transaction creates such an entity, any insertion or deletion
of a matching tuple in the index will be conflicted with it. This
works differently for inserts and deletes:

1. If a concurrent transaction inserts a new matching tuple, then
   its read_gaps list is modified like the counted transaction had
   read the exact key of the tuple and found nothing. This creates
   a conflict.

2. If a concurrent transaction deletes a matching tuple, then the
   transaction that counted the tuple is inserted into the tuple
   reader list: it pretends to have read the tuple prior to the
   deletion. This creates a conflict.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in tarantool#10183.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

NO_DOC=TBD when fully implemented
NO_CHANGELOG=TBD when fully implemented

Prior to this the count request had been performed in the memtx in the
straightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which could lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

Since the method does not read each counted tuple now, MVCC subsystem
would be unaware of it. In order to fix this, this patch introduces a
new entity in the memtx transaction manager to track such operations:
GAP_COUNT, and the corresponding `memtx_tx_track_count` function.

The entity (gap item) is a record that a concurrent transaction has
counted tuples matching some key and iterator type in an index.

If a transaction creates such an entity, any insertion or deletion
of a matching tuple in the index will be conflicted with it. This
works differently for inserts and deletes:

1. If a concurrent transaction inserts a new matching tuple, then
   its read_gaps list is modified like the counted transaction had
   read the exact key of the tuple and found nothing. This creates
   a conflict.

2. If a concurrent transaction deletes a matching tuple, then the
   transaction that counted the tuple is inserted into the tuple
   reader list: it pretends to have read the tuple prior to the
   deletion. This creates a conflict.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in tarantool#10183.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

NO_DOC=TBD when fully implemented
NO_CHANGELOG=TBD when fully implemented

Prior to this the count request had been performed in the memtx in the
straightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which could lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

Since the method does not read each counted tuple now, MVCC subsystem
would be unaware of it. In order to fix this, this patch introduces a
new entity in the memtx transaction manager to track such operations:
GAP_COUNT, and the corresponding `memtx_tx_track_count` function.

The entity (gap item) is a record that a concurrent transaction has
counted tuples matching some key and iterator type in an index.

If a transaction creates such an entity, any insertion or deletion
of a matching tuple in the index will be conflicted with it. This
works differently for inserts and deletes:

1. If a concurrent transaction inserts a new matching tuple, then
   its read_gaps list is modified like the counted transaction had
   read the exact key of the tuple and found nothing. This creates
   a conflict.

2. If a concurrent transaction deletes a matching tuple, then the
   transaction that counted the tuple is inserted into the tuple
   reader list: it pretends to have read the tuple prior to the
   deletion. This creates a conflict.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in the tarantool#10183 and in the scope of tarantool#10322.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

Part of tarantool#8204

NO_DOC=perf improvement
NO_CHANGELOG=TBD when fully implemented

Prior to this the count request had been performed in the memtx in the
straightforward way: we created an iterator by a type and key and simply
called its `next` method until it's exhausted. That means the operation
had a linear complexity, which could lead to DoS situations.

This patch makes the memtx tree index use a version of BPS tree with
the cardinality information enabled and takes advantage of its offset
based API to implement the count operation using tree lookups.

Since the method does not read each counted tuple now, MVCC subsystem
would be unaware of it. In order to fix this, this patch introduces a
new entity in the memtx transaction manager to track such operations:
GAP_COUNT, and the corresponding `memtx_tx_track_count` function.

The entity (gap item) is a record that a concurrent transaction has
counted tuples matching some key and iterator type in an index.

If a transaction creates such an entity, any insertion or deletion
of a matching tuple in the index will be conflicted with it. This
works differently for inserts and deletes:

1. If a concurrent transaction inserts a new matching tuple, then
   its read_gaps list is modified like the counted transaction had
   read the exact key of the tuple and found nothing. This creates
   a conflict.

2. If a concurrent transaction deletes a matching tuple, then the
   transaction that counted the tuple is inserted into the tuple
   reader list: it pretends to have read the tuple prior to the
   deletion. This creates a conflict.

One thing to be noted is that using the cardinality config introduces
a performance regression against the current version of memtx, this is
mitigated in the tarantool#10183 and in the scope of tarantool#10322.

Another thinig is about the memtx_tx_handle_gap_write update.

Prior to this patch, any failed lookup of a full key using EQ or REQ
iterators had been recorded using memtx_tx_track_point instead of the
memtx_tx_track_gap, so it was impossible to find a GAP_NEARBY item
with full key and EQ/REQ iterator type in the read_gaps list.

But in the fast count implementation only memtx_tx_track_gap is used
(for the sake of readability), so the memtx_tx_handle_gap_write is
modified to take it into account.

Part of tarantool#8204

NO_DOC=perf improvement
NO_CHANGELOG=TBD when fully implemented