MDEV-20301 InnoDB's MVCC has O(N^2) behaviors

If there're multiple row versions in InnoDB, reading one row from PK
may have O(N) complexity and reading from secondary keys may have
O(N^2) complexity.

The problem occurs when there are many pending versions of the same
row, meaning that the primary key is the same, but a secondary key is
different.  The slowdown occurs when the secondary index is
traversed. This patch creates a helper class for the function
row_sel_get_clust_rec_for_mysql() which can remember and re-use
cached_clust_rec & cached_old_vers so that rec_get_offsets() does not
need to be called over and over for the clustered record.

Corrections by Kevin Lewis <kevin.lewis@oracle.com>

MDEV-20341 Unstable innodb.innodb_bug14704286

Removed test that tested the ability of interrupting long query which
is not long anymore.

1 files changed, 46 insertions, 9 deletions

diff --git a/storage/innobase/row/row0sel.cc b/storage/innobase/row/row0sel.cc
index 877d9c3ef78..d5b1a596f01 100644
--- a/storage/innobase/row/row0sel.cc
+++ b/storage/innobase/row/row0sel.cc
@@ -3309,14 +3309,29 @@ row_sel_build_prev_vers_for_mysql(
 	return(err);
 }
 
+/** Helper class to cache clust_rec and old_ver */
+class Row_sel_get_clust_rec_for_mysql
+{
+	const rec_t *cached_clust_rec;
+	rec_t *cached_old_vers;
+
+public:
+	Row_sel_get_clust_rec_for_mysql() :
+	cached_clust_rec(NULL), cached_old_vers(NULL) {}
+
+	dberr_t operator()(row_prebuilt_t *prebuilt, dict_index_t *sec_index,
+			const rec_t *rec, que_thr_t *thr, const rec_t **out_rec,
+			ulint **offsets, mem_heap_t **offset_heap,
+			dtuple_t **vrow, mtr_t *mtr);
+};
+
 /*********************************************************************//**
 Retrieves the clustered index record corresponding to a record in a
 non-clustered index. Does the necessary locking. Used in the MySQL
 interface.
 @return DB_SUCCESS, DB_SUCCESS_LOCKED_REC, or error code */
-static MY_ATTRIBUTE((warn_unused_result))
 dberr_t
-row_sel_get_clust_rec_for_mysql(
+Row_sel_get_clust_rec_for_mysql::operator()(
 /*============================*/
 	row_prebuilt_t*	prebuilt,/*!< in: prebuilt struct in the handle */
 	dict_index_t*	sec_index,/*!< in: secondary index where rec resides */
@@ -3508,15 +3523,36 @@ row_sel_get_clust_rec_for_mysql(
 			    clust_rec, clust_index, *offsets,
 			    trx_get_read_view(trx))) {
 
-			/* The following call returns 'offsets' associated with
-			'old_vers' */
-			err = row_sel_build_prev_vers_for_mysql(
-				trx->read_view, clust_index, prebuilt,
-				clust_rec, offsets, offset_heap, &old_vers,
-				vrow, mtr);
+			if (clust_rec != cached_clust_rec) {
+				/* The following call returns 'offsets' associated with
+				'old_vers' */
+				err = row_sel_build_prev_vers_for_mysql(
+					trx->read_view, clust_index, prebuilt,
+					clust_rec, offsets, offset_heap, &old_vers,
+					vrow, mtr);
+
+				if (err != DB_SUCCESS) {
+
+					goto err_exit;
+				}
+				cached_clust_rec = clust_rec;
+				cached_old_vers = old_vers;
+			} else {
+				err = DB_SUCCESS;
+				old_vers = cached_old_vers;
+
+				/* The offsets need not be same for the latest
+				version of clust_rec and its old version
+				old_vers. Re-calculate the offsets for old_vers. */
 
-			if (err != DB_SUCCESS || old_vers == NULL) {
+				if (old_vers != NULL) {
+					*offsets = rec_get_offsets(
+						old_vers, clust_index, *offsets,
+						true, ULINT_UNDEFINED, offset_heap);
+				}
+			}
 
+			if (old_vers == NULL) {
 				goto err_exit;
 			}
 
@@ -4233,6 +4269,7 @@ row_search_mvcc(
 	dtuple_t*	vrow = NULL;
 	const rec_t*	result_rec = NULL;
 	const rec_t*	clust_rec;
+	Row_sel_get_clust_rec_for_mysql row_sel_get_clust_rec_for_mysql;
 	dberr_t		err				= DB_SUCCESS;
 	ibool		unique_search			= FALSE;
 	ibool		mtr_has_extra_clust_latch	= FALSE;