[PATCH v4 0/3] box: introduce hint option for memtx tree index

[Vladimir Davydov]

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 <small/mempool.h>
 
 /**
+ * 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 *