Range query estimation

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

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.
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.
LIBMDBX_API int	mdbx_estimate_range (const MDBX_txn *txn, MDBX_dbi dbi, const MDBX_val *begin_key, const MDBX_val *begin_data, const MDBX_val *end_key, const MDBX_val *end_data, ptrdiff_t *distance_items)
	Estimates the size of a range as a number of elements.

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 table and the same transaction.

Parameters

[in]	first	The first cursor for estimation.
[in]	last	The second cursor for estimation.
[out]	distance_items	The 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]	cursor	Cursor for estimation.
[in,out]	key	The key for a retrieved item.
[in,out]	data	The data of a retrieved item.
[in]	move_op	A cursor operation MDBX_cursor_op.
[out]	distance_items	A 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	(	const MDBX_txn *	txn,
		MDBX_dbi	dbi,
		const MDBX_val *	begin_key,
		const MDBX_val *	begin_data,
		const MDBX_val *	end_key,
		const 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]	txn	A transaction handle returned by mdbx_txn_begin().
[in]	dbi	A table handle returned by mdbx_dbi_open().
[in]	begin_key	The key of range beginning or NULL for explicit FIRST.
[in]	begin_data	Optional additional data to seeking among sorted duplicates. Only for MDBX_DUPSORT, NULL otherwise.
[in]	end_key	The key of range ending or NULL for explicit LAST.
[in]	end_data	Optional additional data to seeking among sorted duplicates. Only for MDBX_DUPSORT, NULL otherwise.
[out]	distance_items	A pointer to store range estimation result.

Returns

A non-zero error value on failure and 0 on success.