From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Wed, 6 Mar 2019 12:41:03 +0300 From: Vladimir Davydov Subject: Re: [PATCH v4 0/3] box: introduce hint option for memtx tree index Message-ID: <20190306094103.7rosi6xsblwws4lz@esperanza> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org, kostja@tarantool.org List-ID: For the record. We've discussed the issue with Kostja and agreed to try to implement comparison hints / multikey indexes with neither templates nor macros (both implementations look rather cumbersome). Something like the code below should do fine, but without 'if' in memtx_tree_elem_compare (we need to move it to key_def vtab instead). memtx_tree_index_replace, which differs for multikey and hinted tree implementations, can be overridden via index vtab. diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c index 250df7f2..3728728e 100644 --- a/src/box/memtx_tree.c +++ b/src/box/memtx_tree.c @@ -40,6 +40,25 @@ #include /** + * Struct that represents a memtrx tree element. + */ +struct memtx_tree_elem { + struct tuple *tuple; + union { + /** + * Hint to speed up tuple comparisons + * (not used for multikey indexes). + */ + uint64_t hint; + /** + * Offset of the indexed value in + * a multikey array. + */ + uint64_t multikey_offset; + }; +}; + +/** * Struct that is used as a key in BPS tree definition. */ struct memtx_tree_key_data { @@ -47,12 +66,40 @@ struct memtx_tree_key_data { const char *key; /** Number of msgpacked search fields. */ uint32_t part_count; + /** Hint to speed up comparisons. */ + uint64_t hint; }; /** + * BPS tree element comparator. + * @param elem1 - first element. + * @param elem2 - second element. + * @param def - key definition. + * @retval 0 if elem1 == elem2 in terms of def. + * @retval <0 if elem1 < elem2 in terms of def. + * @retval >0 if elem1 > elem2 in terms of def. + */ +static int +memtx_tree_compare(const struct memtx_tree_elem elem1, + const struct memtx_tree_elem elem2, + struct key_def *def) +{ + if (!def->has_multikey) { + if (elem1.hint != elem2.hint) + return elem1.hint - elem2.hint; + else + return tuple_compare(elem1.tuple, elem2.tuple, def); + } else { + return tuple_compare_multikey(elem1.tuple, elem1.mutlikey_offset, + elem2.tuple, elem2.mutlikey_offset, + def); + } +} + +/** * BPS tree element vs key comparator. * Defined in header in order to allow compiler to inline it. - * @param tuple - tuple to compare. + * @param elem - element to compare. * @param key_data - key to compare with. * @param def - key definition. * @retval 0 if tuple == key in terms of def. @@ -60,20 +107,29 @@ struct memtx_tree_key_data { * @retval >0 if tuple > key in terms of def. */ static int -memtx_tree_compare_key(const struct tuple *tuple, +memtx_tree_compare_key(const struct memtx_tree_elem elem, const struct memtx_tree_key_data *key_data, struct key_def *def) { - return tuple_compare_with_key(tuple, key_data->key, - key_data->part_count, def); + if (!def->has_multikey) { + if (elem.hint != key_data.hint) + return elem.hint - key_data.hint; + else + return tuple_compare_with_key(elem.tuple, key_data->key, + key_data->part_count, def); + } else { + return tuple_compare_with(elem.tuple, elem.multikey_offset, + key_data->key, key_data->part_count + def); + } } #define BPS_TREE_NAME memtx_tree #define BPS_TREE_BLOCK_SIZE (512) #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE -#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg) +#define BPS_TREE_COMPARE(a, b, arg) memtx_tree_compare(a, b, arg) #define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg) -#define bps_tree_elem_t struct tuple * +#define bps_tree_elem_t struct memtx_tree_elem #define bps_tree_key_t struct memtx_tree_key_data * #define bps_tree_arg_t struct key_def *