tarantool / tarantool / 10614108676

88%

Build Type

push

github

Committed by sergepetrenko

Commit Message

memtx: accelerate count in the tree

Prior to this patch the count request had been performed in the memtx
in a 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.

Also the count operation with ALL iterator hadn't been recorded in the
MVCC previously and had an erroneous logic (see the #10140). This is
fixed too as a side effect.

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.

The existing stories of matching dirty tuples are handled differently.
Since its's not stored directly whether the story is a product of an
insertion or a replacement, any matching visible tuple is marked as
read by the counting transaction and any matching... (continued)

Run Details

68493 of 121801 branches covered (56.23%)

97 of 99 new or added lines in 3 files covered. (97.98%)

123 existing lines in 20 files now uncovered.

101207 of 116034 relevant lines covered (87.22%)

2452965.48 hits per line