[PATCH 11/12] vinyl: force index rebuild if indexed field type is narrowed

[Vladimir Davydov <vdavydov.dev@gmail.com>]

If the type of an indexed field is narrowed (e.g. is_nullable flag is
cleared or the type is changed from 'integer' to 'unsigned'), but the
index structure remains the same (same fields, indexed in the same
order), we won't rebuild the index, instead we will check that all
tuples stored in the space conform to the new format (CheckSpaceFormat)
and if so modify the index in-place (ModifyIndex). This is OK for memtx,
but not for Vinyl, because even if the space contains no tuples
conflicting with the new format, there may be overwritten or deleted
statements, which can't be detected by CheckSpaceFormat.

That being said, let's make index_def_change_requires_rebuild() virtual
(add it to index_vtab) and force rebuild of Vinyl indexes if the type of
any indexed field is narrowed.
---
 src/box/alter.cc        |  7 ++-----
 src/box/index.h         | 13 +++++++++++++
 src/box/index_def.c     | 21 ---------------------
 src/box/index_def.h     | 16 ----------------
 src/box/key_def.cc      | 19 -------------------
 src/box/key_def.h       | 13 -------------
 src/box/memtx_bitset.c  |  2 ++
 src/box/memtx_engine.c  | 42 ++++++++++++++++++++++++++++++++++++++++++
 src/box/memtx_engine.h  |  8 ++++++++
 src/box/memtx_hash.c    |  2 ++
 src/box/memtx_rtree.c   | 15 +++++++++++++++
 src/box/memtx_tree.c    |  2 ++
 src/box/sysview_index.c | 11 +++++++++++
 src/box/vinyl.c         | 45 +++++++++++++++++++++++++++++++++++++++++++++
 test/vinyl/ddl.result   | 28 ++++++++++++++++++++++++++++
 test/vinyl/ddl.test.lua | 11 +++++++++++
 16 files changed, 181 insertions(+), 74 deletions(-)

diff --git a/src/box/alter.cc b/src/box/alter.cc
index d05c6483..ac00d875 100644
--- a/src/box/alter.cc
+++ b/src/box/alter.cc
@@ -1476,10 +1476,7 @@ alter_space_move_indexes(struct alter_space *alter, uint32_t begin,
 					old_def->key_def, alter->pk_def);
 		index_def_update_optionality(new_def, min_field_count);
 		auto guard = make_scoped_guard([=] { index_def_delete(new_def); });
-		if (key_part_check_compatibility(old_def->cmp_def->parts,
-						 old_def->cmp_def->part_count,
-						 new_def->cmp_def->parts,
-						 new_def->cmp_def->part_count))
+		if (!index_def_change_requires_rebuild(old_index, new_def))
 			(void) new ModifyIndex(alter, new_def, old_def);
 		else
 			(void) new RebuildIndex(alter, new_def, old_def);
@@ -1852,7 +1849,7 @@ on_replace_dd_index(struct trigger * /* trigger */, void *event)
 		if (index_def_cmp(index_def, old_index->def) == 0) {
 			/* Index is not changed so just move it. */
 			(void) new MoveIndex(alter, old_index->def->iid);
-		} else if (index_def_change_requires_rebuild(old_index->def,
+		} else if (index_def_change_requires_rebuild(old_index,
 							     index_def)) {
 			/*
 			 * Operation demands an index rebuild.
diff --git a/src/box/index.h b/src/box/index.h
index f19fbd16..0aa96ade 100644
--- a/src/box/index.h
+++ b/src/box/index.h
@@ -379,6 +379,12 @@ struct index_vtab {
 	 * the primary key is modified.
 	 */
 	bool (*depends_on_pk)(struct index *);
+	/**
+	 * Return true if the change of index definition
+	 * cannot be done without rebuild.
+	 */
+	bool (*def_change_requires_rebuild)(struct index *index,
+					    const struct index_def *new_def);
 
 	ssize_t (*size)(struct index *);
 	ssize_t (*bsize)(struct index *);
@@ -517,6 +523,13 @@ index_depends_on_pk(struct index *index)
 	return index->vtab->depends_on_pk(index);
 }
 
+static inline bool
+index_def_change_requires_rebuild(struct index *index,
+				  const struct index_def *new_def)
+{
+	return index->vtab->def_change_requires_rebuild(index, new_def);
+}
+
 static inline ssize_t
 index_size(struct index *index)
 {
diff --git a/src/box/index_def.c b/src/box/index_def.c
index c503c787..38f23e0f 100644
--- a/src/box/index_def.c
+++ b/src/box/index_def.c
@@ -156,27 +156,6 @@ index_def_delete(struct index_def *index_def)
 	free(index_def);
 }
 
-bool
-index_def_change_requires_rebuild(const struct index_def *old_index_def,
-				  const struct index_def *new_index_def)
-{
-	if (old_index_def->iid != new_index_def->iid ||
-	    old_index_def->type != new_index_def->type ||
-	    (!old_index_def->opts.is_unique && new_index_def->opts.is_unique) ||
-	    !key_part_check_compatibility(old_index_def->key_def->parts,
-					  old_index_def->key_def->part_count,
-					  new_index_def->key_def->parts,
-					  new_index_def->key_def->part_count)) {
-		return true;
-	}
-	if (old_index_def->type == RTREE) {
-		if (old_index_def->opts.dimension != new_index_def->opts.dimension
-		    || old_index_def->opts.distance != new_index_def->opts.distance)
-			return true;
-	}
-	return false;
-}
-
 int
 index_def_cmp(const struct index_def *key1, const struct index_def *key2)
 {
diff --git a/src/box/index_def.h b/src/box/index_def.h
index 251506a8..eac9f06c 100644
--- a/src/box/index_def.h
+++ b/src/box/index_def.h
@@ -199,22 +199,6 @@ index_def_list_add(struct rlist *index_def_list, struct index_def *index_def)
 }
 
 /**
- * True, if the index change by alter requires an index rebuild.
- *
- * Some changes, such as a new page size or bloom_fpr do not
- * take effect immediately, so do not require a rebuild.
- *
- * Others, such as index name change, do not change the data, only
- * metadata, so do not require a rebuild either.
- *
- * Finally, changing index type or number of parts always requires
- * a rebuild.
- */
-bool
-index_def_change_requires_rebuild(const struct index_def *old_index_def,
-				  const struct index_def *new_index_def);
-
-/**
  * Create a new index definition definition.
  *
  * @param key_def  key definition, must be fully built
diff --git a/src/box/key_def.cc b/src/box/key_def.cc
index 50786913..45997ae8 100644
--- a/src/box/key_def.cc
+++ b/src/box/key_def.cc
@@ -244,25 +244,6 @@ key_part_cmp(const struct key_part *parts1, uint32_t part_count1,
 	return part_count1 < part_count2 ? -1 : part_count1 > part_count2;
 }
 
-bool
-key_part_check_compatibility(const struct key_part *old_parts,
-			     uint32_t old_part_count,
-			     const struct key_part *new_parts,
-			     uint32_t new_part_count)
-{
-	if (new_part_count != old_part_count)
-		return false;
-	for (uint32_t i = 0; i < new_part_count; i++) {
-		const struct key_part *new_part = &new_parts[i];
-		const struct key_part *old_part = &old_parts[i];
-		if (old_part->fieldno != new_part->fieldno)
-			return false;
-		if (old_part->coll != new_part->coll)
-			return false;
-	}
-	return true;
-}
-
 void
 key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 		 enum field_type type, bool is_nullable, struct coll *coll)
diff --git a/src/box/key_def.h b/src/box/key_def.h
index 84e3e1e5..12016a51 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -429,19 +429,6 @@ key_part_cmp(const struct key_part *parts1, uint32_t part_count1,
 	     const struct key_part *parts2, uint32_t part_count2);
 
 /**
- * Find out whether alteration of an index has changed it
- * substantially enough to warrant a rebuild or not. For example,
- * change of index id is not a substantial change, whereas change
- * of index type or incompatible change of key parts requires
- * a rebuild.
- */
-bool
-key_part_check_compatibility(const struct key_part *old_parts,
-			     uint32_t old_part_count,
-			     const struct key_part *new_parts,
-			     uint32_t new_part_count);
-
-/**
  * Extract key from tuple by given key definition and return
  * buffer allocated on box_txn_alloc with this key. This function
  * has O(n) complexity, where n is the number of key parts.
diff --git a/src/box/memtx_bitset.c b/src/box/memtx_bitset.c
index f67405ec..7b87560b 100644
--- a/src/box/memtx_bitset.c
+++ b/src/box/memtx_bitset.c
@@ -462,6 +462,8 @@ static const struct index_vtab memtx_bitset_index_vtab = {
 	/* .commit_drop = */ memtx_index_commit_drop,
 	/* .update_def = */ generic_index_update_def,
 	/* .depends_on_pk = */ generic_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
 	/* .size = */ memtx_bitset_index_size,
 	/* .bsize = */ memtx_bitset_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
index c183b2da..388cc4fe 100644
--- a/src/box/memtx_engine.c
+++ b/src/box/memtx_engine.c
@@ -1109,3 +1109,45 @@ memtx_index_commit_drop(struct index *index)
 {
 	memtx_index_prune(index);
 }
+
+bool
+memtx_index_def_change_requires_rebuild(struct index *index,
+					const struct index_def *new_def)
+{
+	struct index_def *old_def = index->def;
+
+	assert(old_def->iid == new_def->iid);
+	assert(old_def->space_id == new_def->space_id);
+
+	if (old_def->type != new_def->type)
+		return true;
+	if (!old_def->opts.is_unique && new_def->opts.is_unique)
+		return true;
+
+	const struct key_def *old_cmp_def, *new_cmp_def;
+	if (index_depends_on_pk(index)) {
+		old_cmp_def = old_def->cmp_def;
+		new_cmp_def = new_def->cmp_def;
+	} else {
+		old_cmp_def = old_def->key_def;
+		new_cmp_def = new_def->key_def;
+	}
+
+	/*
+	 * Compatibility of field types is verified by CheckSpaceFormat
+	 * so it suffices to check that the new key definition indexes
+	 * the same set of fields in the same order.
+	 */
+	if (old_cmp_def->part_count != new_cmp_def->part_count)
+		return true;
+
+	for (uint32_t i = 0; i < new_cmp_def->part_count; i++) {
+		const struct key_part *old_part = &old_cmp_def->parts[i];
+		const struct key_part *new_part = &new_cmp_def->parts[i];
+		if (old_part->fieldno != new_part->fieldno)
+			return true;
+		if (old_part->coll != new_part->coll)
+			return true;
+	}
+	return false;
+}
diff --git a/src/box/memtx_engine.h b/src/box/memtx_engine.h
index 3f8e7db7..c1f2652c 100644
--- a/src/box/memtx_engine.h
+++ b/src/box/memtx_engine.h
@@ -161,6 +161,14 @@ memtx_index_abort_create(struct index *index);
 void
 memtx_index_commit_drop(struct index *index);
 
+/**
+ * Generic implementation of index_vtab::def_change_requires_rebuild,
+ * common for all kinds of memtx indexes.
+ */
+bool
+memtx_index_def_change_requires_rebuild(struct index *index,
+					const struct index_def *new_def);
+
 #if defined(__cplusplus)
 } /* extern "C" */
 
diff --git a/src/box/memtx_hash.c b/src/box/memtx_hash.c
index 38027a3b..24138f42 100644
--- a/src/box/memtx_hash.c
+++ b/src/box/memtx_hash.c
@@ -386,6 +386,8 @@ static const struct index_vtab memtx_hash_index_vtab = {
 	/* .commit_drop = */ memtx_index_commit_drop,
 	/* .update_def = */ memtx_hash_index_update_def,
 	/* .depends_on_pk = */ generic_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
 	/* .size = */ memtx_hash_index_size,
 	/* .bsize = */ memtx_hash_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/src/box/memtx_rtree.c b/src/box/memtx_rtree.c
index d0dceaea..653343a7 100644
--- a/src/box/memtx_rtree.c
+++ b/src/box/memtx_rtree.c
@@ -154,6 +154,19 @@ memtx_rtree_index_destroy(struct index *base)
 	free(index);
 }
 
+static bool
+memtx_rtree_index_def_change_requires_rebuild(struct index *index,
+					      const struct index_def *new_def)
+{
+	if (memtx_index_def_change_requires_rebuild(index, new_def))
+		return true;
+	if (index->def->opts.distance != new_def->opts.distance ||
+	    index->def->opts.dimension != new_def->opts.dimension)
+		return true;
+	return false;
+
+}
+
 static ssize_t
 memtx_rtree_index_size(struct index *base)
 {
@@ -293,6 +306,8 @@ static const struct index_vtab memtx_rtree_index_vtab = {
 	/* .commit_drop = */ memtx_index_commit_drop,
 	/* .update_def = */ generic_index_update_def,
 	/* .depends_on_pk = */ generic_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_rtree_index_def_change_requires_rebuild,
 	/* .size = */ memtx_rtree_index_size,
 	/* .bsize = */ memtx_rtree_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 22177f57..073006b4 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -595,6 +595,8 @@ static const struct index_vtab memtx_tree_index_vtab = {
 	/* .commit_drop = */ memtx_index_commit_drop,
 	/* .update_def = */ memtx_tree_index_update_def,
 	/* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
 	/* .size = */ memtx_tree_index_size,
 	/* .bsize = */ memtx_tree_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/src/box/sysview_index.c b/src/box/sysview_index.c
index 72961401..38ef8108 100644
--- a/src/box/sysview_index.c
+++ b/src/box/sysview_index.c
@@ -90,6 +90,15 @@ sysview_index_bsize(struct index *index)
 	return 0;
 }
 
+static bool
+sysview_index_def_change_requires_rebuild(struct index *index,
+					  const struct index_def *new_def)
+{
+	(void)index;
+	(void)new_def;
+	return true;
+}
+
 static struct iterator *
 sysview_index_create_iterator(struct index *base, enum iterator_type type,
 			      const char *key, uint32_t part_count)
@@ -166,6 +175,8 @@ static const struct index_vtab sysview_index_vtab = {
 	/* .commit_drop = */ generic_index_commit_drop,
 	/* .update_def = */ generic_index_update_def,
 	/* .depends_on_pk = */ generic_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		sysview_index_def_change_requires_rebuild,
 	/* .size = */ generic_index_size,
 	/* .bsize = */ sysview_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 47804ecc..c99b518e 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -966,6 +966,49 @@ vinyl_index_depends_on_pk(struct index *index)
 	return true;
 }
 
+static bool
+vinyl_index_def_change_requires_rebuild(struct index *index,
+					const struct index_def *new_def)
+{
+	struct index_def *old_def = index->def;
+
+	assert(old_def->iid == new_def->iid);
+	assert(old_def->space_id == new_def->space_id);
+	assert(old_def->type == TREE && new_def->type == TREE);
+
+	if (!old_def->opts.is_unique && new_def->opts.is_unique)
+		return true;
+
+	assert(index_depends_on_pk(index));
+	const struct key_def *old_cmp_def = old_def->cmp_def;
+	const struct key_def *new_cmp_def = new_def->cmp_def;
+
+	/*
+	 * It is not enough to check only fieldno in case of Vinyl,
+	 * because the index may store some overwritten or deleted
+	 * statements conforming to the old format. CheckSpaceFormat
+	 * won't reveal such statements, but we may still need to
+	 * compare them to statements inserted after ALTER hence
+	 * we can't narrow field types without index rebuild.
+	 */
+	if (old_cmp_def->part_count != new_cmp_def->part_count)
+		return true;
+
+	for (uint32_t i = 0; i < new_cmp_def->part_count; i++) {
+		const struct key_part *old_part = &old_cmp_def->parts[i];
+		const struct key_part *new_part = &new_cmp_def->parts[i];
+		if (old_part->fieldno != new_part->fieldno)
+			return true;
+		if (old_part->coll != new_part->coll)
+			return true;
+		if (old_part->is_nullable && !new_part->is_nullable)
+			return true;
+		if (!field_type1_contains_type2(new_part->type, old_part->type))
+			return true;
+	}
+	return false;
+}
+
 static void
 vinyl_init_system_space(struct space *space)
 {
@@ -3906,6 +3949,8 @@ static const struct index_vtab vinyl_index_vtab = {
 	/* .commit_drop = */ vinyl_index_commit_drop,
 	/* .update_def = */ generic_index_update_def,
 	/* .depends_on_pk = */ vinyl_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		vinyl_index_def_change_requires_rebuild,
 	/* .size = */ vinyl_index_size,
 	/* .bsize = */ vinyl_index_bsize,
 	/* .min = */ generic_index_min,
diff --git a/test/vinyl/ddl.result b/test/vinyl/ddl.result
index 4ea94d36..5142f0f2 100644
--- a/test/vinyl/ddl.result
+++ b/test/vinyl/ddl.result
@@ -850,3 +850,31 @@ s.index.secondary:select(10)
 s:drop()
 ---
 ...
+-- Narrowing indexed field type entails index rebuild.
+s = box.schema.space.create('test', {engine = 'vinyl'})
+---
+...
+_ = s:create_index('i1')
+---
+...
+_ = s:create_index('i2', {parts = {2, 'integer'}})
+---
+...
+_ = s:create_index('i3', {parts = {{3, 'string', is_nullable = true}}})
+---
+...
+_ = s:replace{1, 1, 'test'}
+---
+...
+-- Should fail with 'Vinyl does not support building an index for a non-empty space'.
+s.index.i2:alter{parts = {2, 'unsigned'}}
+---
+- error: Vinyl does not support building an index for a non-empty space
+...
+s.index.i3:alter{parts = {{3, 'string', is_nullable = false}}}
+---
+- error: Vinyl does not support building an index for a non-empty space
+...
+s:drop()
+---
+...
diff --git a/test/vinyl/ddl.test.lua b/test/vinyl/ddl.test.lua
index 8ce8b920..c4bd36bb 100644
--- a/test/vinyl/ddl.test.lua
+++ b/test/vinyl/ddl.test.lua
@@ -304,3 +304,14 @@ s.index.secondary.unique
 s:insert{2, 10}
 s.index.secondary:select(10)
 s:drop()
+
+-- Narrowing indexed field type entails index rebuild.
+s = box.schema.space.create('test', {engine = 'vinyl'})
+_ = s:create_index('i1')
+_ = s:create_index('i2', {parts = {2, 'integer'}})
+_ = s:create_index('i3', {parts = {{3, 'string', is_nullable = true}}})
+_ = s:replace{1, 1, 'test'}
+-- Should fail with 'Vinyl does not support building an index for a non-empty space'.
+s.index.i2:alter{parts = {2, 'unsigned'}}
+s.index.i3:alter{parts = {{3, 'string', is_nullable = false}}}
+s:drop()
-- 
2.11.0