libmdbx  0.12.2.11 (2022-11-19T23:19:30+03:00)
One of the fastest compact embeddable key-value ACID database without WAL.
Range query estimation

Macros

#define MDBX_EPSILON   ((MDBX_val *)((ptrdiff_t)-1))
 The EPSILON value for mdbx_estimate_range() More...
 

Functions

LIBMDBX_API int mdbx_estimate_distance (const MDBX_cursor *first, const MDBX_cursor *last, ptrdiff_t *distance_items)
 Estimates the distance between cursors as a number of elements. More...
 
LIBMDBX_API int mdbx_estimate_move (const MDBX_cursor *cursor, MDBX_val *key, MDBX_val *data, MDBX_cursor_op move_op, ptrdiff_t *distance_items)
 Estimates the move distance. More...
 
LIBMDBX_API int mdbx_estimate_range (MDBX_txn *txn, MDBX_dbi dbi, MDBX_val *begin_key, MDBX_val *begin_data, MDBX_val *end_key, MDBX_val *end_data, ptrdiff_t *distance_items)
 Estimates the size of a range as a number of elements. More...
 

Detailed Description

Note
The estimation result varies greatly depending on the filling of specific pages and the overall balance of the b-tree:
  1. The number of items is estimated by analyzing the height and fullness of the b-tree. The accuracy of the result directly depends on the balance of the b-tree, which in turn is determined by the history of previous insert/delete operations and the nature of the data (i.e. variability of keys length and so on). Therefore, the accuracy of the estimation can vary greatly in a particular situation.
  2. To understand the potential spread of results, you should consider a possible situations basing on the general criteria for splitting and merging b-tree pages:
    • the page is split into two when there is no space for added data;
    • two pages merge if the result fits in half a page;
    • thus, the b-tree can consist of an arbitrary combination of pages filled both completely and only 1/4. Therefore, in the worst case, the result can diverge 4 times for each level of the b-tree excepting the first and the last.
  3. In practice, the probability of extreme cases of the above situation is close to zero and in most cases the error does not exceed a few percent. On the other hand, it's just a chance you shouldn't overestimate.

Macro Definition Documentation

◆ MDBX_EPSILON

#define MDBX_EPSILON   ((MDBX_val *)((ptrdiff_t)-1))

The EPSILON value for mdbx_estimate_range()

Function Documentation

◆ mdbx_estimate_distance()

LIBMDBX_API int mdbx_estimate_distance ( const MDBX_cursor first,
const MDBX_cursor last,
ptrdiff_t *  distance_items 
)

Estimates the distance between cursors as a number of elements.

This function performs a rough estimate based only on b-tree pages that are common for the both cursor's stacks. The results of such estimation can be used to build and/or optimize query execution plans.

Please see notes on accuracy of the result in the details of Range query estimation section.

Both cursors must be initialized for the same database and the same transaction.

Parameters
[in]firstThe first cursor for estimation.
[in]lastThe second cursor for estimation.
[out]distance_itemsThe pointer to store estimated distance value, i.e. *distance_items = distance(first, last).
Returns
A non-zero error value on failure and 0 on success.

◆ mdbx_estimate_move()

LIBMDBX_API int mdbx_estimate_move ( const MDBX_cursor cursor,
MDBX_val key,
MDBX_val data,
MDBX_cursor_op  move_op,
ptrdiff_t *  distance_items 
)

Estimates the move distance.

This function performs a rough estimate distance between the current cursor position and next position after the specified move-operation with given key and data. The results of such estimation can be used to build and/or optimize query execution plans. Current cursor position and state are preserved.

Please see notes on accuracy of the result in the details of Range query estimation section.

Parameters
[in]cursorCursor for estimation.
[in,out]keyThe key for a retrieved item.
[in,out]dataThe data of a retrieved item.
[in]move_opA cursor operation MDBX_cursor_op.
[out]distance_itemsA pointer to store estimated move distance as the number of elements.
Returns
A non-zero error value on failure and 0 on success.

◆ mdbx_estimate_range()

LIBMDBX_API int mdbx_estimate_range ( MDBX_txn txn,
MDBX_dbi  dbi,
MDBX_val begin_key,
MDBX_val begin_data,
MDBX_val end_key,
MDBX_val end_data,
ptrdiff_t *  distance_items 
)

Estimates the size of a range as a number of elements.

The results of such estimation can be used to build and/or optimize query execution plans.

Please see notes on accuracy of the result in the details of Range query estimation section.

Parameters
[in]txnA transaction handle returned by mdbx_txn_begin().
[in]dbiA database handle returned by mdbx_dbi_open().
[in]begin_keyThe key of range beginning or NULL for explicit FIRST.
[in]begin_dataOptional additional data to seeking among sorted duplicates. Only for MDBX_DUPSORT, NULL otherwise.
[in]end_keyThe key of range ending or NULL for explicit LAST.
[in]end_dataOptional additional data to seeking among sorted duplicates. Only for MDBX_DUPSORT, NULL otherwise.
[out]distance_itemsA pointer to store range estimation result.
Returns
A non-zero error value on failure and 0 on success.