Tarantool development patches archive
 help / color / mirror / Atom feed
From: Kirill Yukhin <kyukhin@tarantool.org>
To: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>
Cc: tarantool-patches@freelists.org
Subject: [tarantool-patches] Re: [PATCH 2/2] sql: replace KeyInfo with key_def
Date: Fri, 11 May 2018 15:56:23 +0300	[thread overview]
Message-ID: <20180511125623.ulx2xolqwyx2azit@tarantool.org> (raw)
In-Reply-To: <af19ae87-e7af-c57d-8f3b-17c730325cad@tarantool.org>

Hi Vlad,
On 11 мая 14:22, Vladislav Shpilevoy wrote:
> 
> Hello. Thanks for fixes. See travis: https://travis-ci.org/tarantool/tarantool/jobs/377267310.
> 
> See 10 comments below.
Thanks, I've updated the patch (in the bottom). Answers inlined.

> > diff --git a/src/box/sql/build.c b/src/box/sql/build.c
> > index 029c71e..bfaf3af 100644
> > --- a/src/box/sql/build.c
> > +++ b/src/box/sql/build.c
> > @@ -1119,10 +1131,9 @@ sql_index_collation(Index *idx, uint32_t column)
> >   		return idx->coll_array[column];
> >   	}
> > -	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
> > -	struct index *index = space_index(space, index_id);
> > -	assert(index != NULL && index->def->key_def->part_count >= column);
> > -	return index->def->key_def->parts[column].coll;
> > +	struct key_def *key_def = sql_index_key_def(idx);
> 
> 1. Sql_index_key_def makes dup, that is not needed to get the collation.
> 
> 2. It leaks.
I've added a flag which signals if duplication is needed to sql_index_key_def.

> > +	assert(key_def != NULL && key_def->part_count >= column);
> 
> 3. Assertion can fail on OOM.
No more mallocs, see p 1, 2.

> > @@ -1143,10 +1154,9 @@ sql_index_column_sort_order(Index *idx, uint32_t column)
> >   		return idx->sort_order[column];
> >   	}
> > -	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
> > -	struct index *index = space_index(space, index_id);
> > -	assert(index != NULL && index->def->key_def->part_count >= column);
> > -	return index->def->key_def->parts[column].sort_order;
> > +	struct key_def *key_def = sql_index_key_def(idx);
> > +	assert(key_def != NULL && key_def->part_count >= column);
> > +	return key_def->parts[column].sort_order;
> 
> 4. All the same. Maybe it is better to do not dup key_def in sql_index_key_def
> and just return it as is. And do dup() in caller code.
Ditto.

> > @@ -2643,14 +2650,13 @@ sqlite3RefillIndex(Parse * pParse, Index * pIndex, int memRootPage)
> >   	} else {
> >   		tnum = pIndex->tnum;
> >   	}
> > -	pKey = sqlite3KeyInfoOfIndex(pParse, db, pIndex);
> > -	assert(pKey != 0 || db->mallocFailed || pParse->nErr);
> > +	struct key_def *def = sql_index_key_def(pIndex);
> > +	assert(def != NULL || db->mallocFailed || pParse->nErr);
> 
> 5. Assertion can fail - when sql_index_key_def fails to do dup(),
> it does not set mallocFailed and nErr.
Ditto.

> > diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
> > index 3f74b93..b6fc135 100644
> > --- a/src/box/sql/delete.c
> > +++ b/src/box/sql/delete.c
> > @@ -386,10 +386,10 @@ sqlite3DeleteFrom(Parse * pParse,	/* The parser context */
> >   			iPk = pParse->nMem + 1;
> >   			pParse->nMem += nPk;
> >   			iEphCur = pParse->nTab++;
> > -			KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nPk, 0);
> > +			struct key_def *def = key_def_new(nPk);
> 
> 6. Nobody sets pParse->rc. Maybe it is better to declare a function like
> parser_key_def_new, that takes all the same as key_def + struct Parse, and sets
> rc = SQL_TARANTOOL_ERROR to get OOM from diag.
I think we should refactor all error reporting, so no need to do that right now.
I've added check for OOM.

> > diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
> > index cc969ca..635357b 100644
> > --- a/src/box/sql/expr.c
> > +++ b/src/box/sql/expr.c
> > @@ -1766,10 +1766,13 @@ sqlite3ExprListSetSortOrder(ExprList * p, int iSortOrder)
> >   		return;
> >   	assert(p->nExpr > 0);
> >   	if (iSortOrder == SORT_ORDER_UNDEF) {
> > -		assert(p->a[p->nExpr - 1].sortOrder == SORT_ORDER_ASC);
> > +		assert(p->a[p->nExpr - 1].sort_order == SORT_ORDER_ASC);
> >   		return;
> >   	}
> > -	p->a[p->nExpr - 1].sortOrder = (u8) iSortOrder;
> > +	if (iSortOrder == 0)
> > +		p->a[p->nExpr - 1].sort_order = SORT_ORDER_ASC;
> > +	else
> > +		p->a[p->nExpr - 1].sort_order = SORT_ORDER_DESC;
> 
> 7. Lets make iSortOrder be enum sort_order and remove this 'if's.
Done. Refactored sqlite3CreateIndex() as well

> > @@ -2761,7 +2763,7 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
> >   			pExpr->is_ephemeral = 1;
> >   			addr = sqlite3VdbeAddOp2(v, OP_OpenTEphemeral,
> >   						 pExpr->iTable, nVal);
> > -			pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nVal, 1);
> > +			struct key_def *key_def = key_def_new(nVal);
> 
> 8. pParse->rc is not set to error.
Fixed.

> > @@ -2787,29 +2789,34 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
> >   					pSelect->iLimit = 0;
> >   					testcase(pSelect->
> >   						 selFlags & SF_Distinct);
> > -					testcase(pKeyInfo == 0);	/* Caused by OOM in sqlite3KeyInfoAlloc() */
> >   					if (sqlite3Select
> >   					    (pParse, pSelect, &dest)) {
> >   						sqlite3DbFree(pParse->db,
> >   							      dest.zAffSdst);
> > -						sqlite3KeyInfoUnref(pKeyInfo);
> > +						if (key_def != NULL)
> > +							free(key_def);
> >   						return 0;
> >   					}
> >   					sqlite3DbFree(pParse->db,
> >   						      dest.zAffSdst);
> > -					assert(pKeyInfo != 0);	/* OOM will cause exit after sqlite3Select() */
> > +					assert(key_def != NULL);
> 
> 9. Assertion fails, if key_def == NULL. Maybe it is better to check key_def == NULL once right
> after key_def_new, return on error, and remove this 'if (key_def != NULL)' everywhere.
Done.

> > diff --git a/src/box/sql/insert.c b/src/box/sql/insert.c
> > index 1a34f71..95a2610 100644
> > --- a/src/box/sql/insert.c
> > +++ b/src/box/sql/insert.c
> > @@ -565,9 +565,9 @@ sqlite3Insert(Parse * pParse,	/* Parser context */
> >   			regRec = sqlite3GetTempReg(pParse);
> >   			regCopy = sqlite3GetTempRange(pParse, nColumn);
> >   			regTempId = sqlite3GetTempReg(pParse);
> > -			KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, 1+nColumn, 0);
> > +			struct key_def *def = key_def_new(nColumn + 1);
> 
> 10. No error code is set. I will not repeat this comment below, but the error code is not
> set in more places.
Fixed.

--
Regards, Kirill Yukhin

commit db01ff515830b422ee7a874f5c0d34e6814222c5
Author: Kirill Yukhin <kyukhin@tarantool.org>
Date:   Fri May 4 16:11:02 2018 +0300

    sql: replace KeyInfo with key_def
    
    KeyInfo is a legacy struct which was heavily used in SQL
    front-end. This patch replaces all its usages w/ Tarantool's
    natural key description structure called key_def.
    
    This change is a part of data dictionary integration effort:
    Tarantool indexes don't aware of KeyInfo, that is why it was
    evicted.
    
    Legacy KeyInfo memory handling was ref-counting based and now
    is replaced w/ memory duplication. This state of affairs should
    be improved in future.
    
    Part of #3235

diff --git a/src/box/sql.c b/src/box/sql.c
index e312d03..79da550 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -357,7 +357,7 @@ int tarantoolSqlite3Count(BtCursor *pCur, i64 *pnEntry)
 	return SQLITE_OK;
 }
 
-/*
+/**
  * Create ephemeral space and set cursor to the first entry. Features of
  * ephemeral spaces: id == 0, name == "ephemeral", memtx engine (in future it
  * can be changed, but now only memtx engine is supported), primary index
@@ -366,12 +366,12 @@ int tarantoolSqlite3Count(BtCursor *pCur, i64 *pnEntry)
  *
  * @param pCur Cursor which will point to the new ephemeral space.
  * @param field_count Number of fields in ephemeral space.
- * @param aColl Collation sequence of ephemeral space.
+ * @param def Keys description for new ephemeral space.
  *
  * @retval SQLITE_OK on success, SQLITE_TARANTOOL_ERROR otherwise.
  */
 int tarantoolSqlite3EphemeralCreate(BtCursor *pCur, uint32_t field_count,
-				    struct coll *aColl)
+				    struct key_def *def)
 {
 	assert(pCur);
 	assert(pCur->curFlags & BTCF_TEphemCursor);
@@ -380,12 +380,13 @@ int tarantoolSqlite3EphemeralCreate(BtCursor *pCur, uint32_t field_count,
 	if (ephemer_key_def == NULL)
 		return SQL_TARANTOOL_ERROR;
 	for (uint32_t part = 0; part < field_count; ++part) {
-		key_def_set_part(ephemer_key_def, part /* part no */,
-				 part /* filed no */,
-				 FIELD_TYPE_SCALAR,
-				 ON_CONFLICT_ACTION_NONE /* nullable_action */,
-				 aColl /* coll */,
-				 SORT_ORDER_ASC);
+		struct coll *coll;
+		if (part < def->part_count)
+			coll = def->parts[part].coll;
+		else
+			coll = NULL;
+		key_def_set_part(ephemer_key_def, part, part, FIELD_TYPE_SCALAR,
+				 ON_CONFLICT_ACTION_NONE, coll, SORT_ORDER_ASC);
 	}
 
 	struct index_def *ephemer_index_def =
@@ -929,16 +930,13 @@ rename_fail:
 	return SQL_TARANTOOL_ERROR;
 }
 
-/*
- * Performs exactly as extract_key + sqlite3VdbeCompareMsgpack,
- * only faster.
- */
-int tarantoolSqlite3IdxKeyCompare(BtCursor *pCur, UnpackedRecord *pUnpacked,
-				  int *res)
+int
+tarantoolSqlite3IdxKeyCompare(struct BtCursor *cursor,
+			      struct UnpackedRecord *unpacked, int *res)
 {
-	assert(pCur->curFlags & BTCF_TaCursor);
-	assert(pCur->iter != NULL);
-	assert(pCur->last_tuple != NULL);
+	assert(cursor->curFlags & BTCF_TaCursor);
+	assert(cursor->iter != NULL);
+	assert(cursor->last_tuple != NULL);
 
 	const box_key_def_t *key_def;
 	const struct tuple *tuple;
@@ -955,9 +953,9 @@ int tarantoolSqlite3IdxKeyCompare(BtCursor *pCur, UnpackedRecord *pUnpacked,
 	uint32_t key_size;
 #endif
 
-	key_def = box_iterator_key_def(pCur->iter);
-	n = MIN(pUnpacked->nField, key_def->part_count);
-	tuple = pCur->last_tuple;
+	key_def = box_iterator_key_def(cursor->iter);
+	n = MIN(unpacked->nField, key_def->part_count);
+	tuple = cursor->last_tuple;
 	base = tuple_data(tuple);
 	format = tuple_format(tuple);
 	field_map = tuple_field_map(tuple);
@@ -991,28 +989,28 @@ int tarantoolSqlite3IdxKeyCompare(BtCursor *pCur, UnpackedRecord *pUnpacked,
 			} else {
 				p = base + field_map[
 					format->fields[fieldno].offset_slot
-];
+					];
 			}
 		}
 		next_fieldno = fieldno + 1;
-		rc = sqlite3VdbeCompareMsgpack(&p, pUnpacked, i);
+		rc = sqlite3VdbeCompareMsgpack(&p, unpacked, i);
 		if (rc != 0) {
-			if (pUnpacked->pKeyInfo->aSortOrder[i]) {
+			if (unpacked->key_def->parts[i].sort_order !=
+			    SORT_ORDER_ASC) {
 				rc = -rc;
 			}
 			*res = rc;
 			goto out;
 		}
 	}
-	*res = pUnpacked->default_rc;
+	*res = unpacked->default_rc;
 out:
 #ifndef NDEBUG
 	/* Sanity check. */
 	original_size = region_used(&fiber()->gc);
 	key = tuple_extract_key(tuple, key_def, &key_size);
 	if (key != NULL) {
-		rc = sqlite3VdbeRecordCompareMsgpack((int)key_size, key,
-						     pUnpacked);
+		rc = sqlite3VdbeRecordCompareMsgpack(key, unpacked);
 		region_truncate(&fiber()->gc, original_size);
 		assert(rc == *res);
 	}
diff --git a/src/box/sql/analyze.c b/src/box/sql/analyze.c
index f0054c5..ec23481 100644
--- a/src/box/sql/analyze.c
+++ b/src/box/sql/analyze.c
@@ -176,8 +176,8 @@ openStatTable(Parse * pParse,	/* Parsing context */
 	/* Open the sql_stat[134] tables for writing. */
 	for (i = 0; aTable[i]; i++) {
 		int addr = emit_open_cursor(pParse, iStatCur + i, aRoot[i]);
-		v->aOp[addr].p4.pKeyInfo = 0;
-		v->aOp[addr].p4type = P4_KEYINFO;
+		v->aOp[addr].p4.key_def = NULL;
+		v->aOp[addr].p4type = P4_KEYDEF;
 		sqlite3VdbeChangeP5(v, aCreateTbl[i]);
 		VdbeComment((v, aTable[i]));
 	}
@@ -914,7 +914,7 @@ analyzeOneTable(Parse * pParse,	/* Parser context */
 				     (void *) space);
 		sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pIdx->tnum,
 				  space_ptr_reg);
-		sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
+		sql_vdbe_set_p4_key_def(pParse, pIdx);
 		VdbeComment((v, "%s", pIdx->zName));
 
 		/* Invoke the stat_init() function. The arguments are:
diff --git a/src/box/sql/build.c b/src/box/sql/build.c
index 49ac1fa..be40982 100644
--- a/src/box/sql/build.c
+++ b/src/box/sql/build.c
@@ -985,13 +985,13 @@ sqlite3AddPrimaryKey(Parse * pParse,	/* Parsing context */
 			pTab->tabFlags |= TF_Autoincrement;
 		}
 		if (pList)
-			pParse->iPkSortOrder = pList->a[0].sortOrder;
+			pParse->iPkSortOrder = pList->a[0].sort_order;
 	} else if (autoInc) {
 		sqlite3ErrorMsg(pParse, "AUTOINCREMENT is only allowed on an "
 				"INTEGER PRIMARY KEY or INT PRIMARY KEY");
 	} else {
-		sqlite3CreateIndex(pParse, 0, 0, pList, onError, 0,
-				   0, sortOrder, 0, SQLITE_IDXTYPE_PRIMARYKEY);
+		sql_create_index(pParse, 0, 0, pList, onError, 0,
+				 0, sortOrder, false, SQLITE_IDXTYPE_PRIMARYKEY);
 		pList = 0;
 	}
 
@@ -1094,6 +1094,21 @@ sql_column_collation(Table *table, uint32_t column)
 	return space->format->fields[column].coll;
 }
 
+struct key_def*
+sql_index_key_def(struct Index *idx, bool is_dup)
+{
+	uint32_t space_id = SQLITE_PAGENO_TO_SPACEID(idx->pTable->tnum);
+	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
+	struct space *space = space_by_id(space_id);
+	assert(space != NULL);
+	struct index *index = space_index(space, index_id);
+	assert(index != NULL && index->def != NULL);
+	if (is_dup)
+		return key_def_dup(index->def->key_def);
+	else
+		return index->def->key_def;
+}
+
 /**
  * Return name of given column collation from index.
  *
@@ -1119,10 +1134,9 @@ sql_index_collation(Index *idx, uint32_t column)
 		return idx->coll_array[column];
 	}
 
-	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
-	struct index *index = space_index(space, index_id);
-	assert(index != NULL && index->def->key_def->part_count >= column);
-	return index->def->key_def->parts[column].coll;
+	struct key_def *key_def = sql_index_key_def(idx, false);
+	assert(key_def != NULL && key_def->part_count >= column);
+	return key_def->parts[column].coll;
 }
 
 enum sort_order
@@ -1143,10 +1157,9 @@ sql_index_column_sort_order(Index *idx, uint32_t column)
 		return idx->sort_order[column];
 	}
 
-	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
-	struct index *index = space_index(space, index_id);
-	assert(index != NULL && index->def->key_def->part_count >= column);
-	return index->def->key_def->parts[column].sort_order;
+	struct key_def *key_def = sql_index_key_def(idx, false);
+	assert(key_def != NULL && key_def->part_count >= column);
+	return key_def->parts[column].sort_order;
 }
 
 /**
@@ -1443,9 +1456,7 @@ hasColumn(const i16 * aiCol, int nCol, int x)
  *     (2)  Set the Index.tnum of the PRIMARY KEY Index object in the
  *          schema to the rootpage from the main table.
  *     (3)  Add all table columns to the PRIMARY KEY Index object
- *          so that the PRIMARY KEY is a covering index.  The surplus
- *          columns are part of KeyInfo.nXField and are not used for
- *          sorting or lookup or uniqueness checks.
+ *          so that the PRIMARY KEY is a covering index.
  */
 static void
 convertToWithoutRowidTable(Parse * pParse, Table * pTab)
@@ -1476,10 +1487,11 @@ convertToWithoutRowidTable(Parse * pParse, Table * pTab)
 							       &ipkToken, 0));
 		if (pList == 0)
 			return;
-		pList->a[0].sortOrder = pParse->iPkSortOrder;
+		pList->a[0].sort_order = pParse->iPkSortOrder;
 		assert(pParse->pNewTable == pTab);
-		sqlite3CreateIndex(pParse, 0, 0, pList, pTab->keyConf, 0, 0, 0,
-				   0, SQLITE_IDXTYPE_PRIMARYKEY);
+		sql_create_index(pParse, 0, 0, pList, pTab->keyConf, 0, 0,
+				 SORT_ORDER_ASC, false,
+				 SQLITE_IDXTYPE_PRIMARYKEY);
 		if (db->mallocFailed)
 			return;
 		pPk = sqlite3PrimaryKeyIndex(pTab);
@@ -2632,7 +2644,6 @@ sqlite3RefillIndex(Parse * pParse, Index * pIndex, int memRootPage)
 	int tnum;		/* Root page of index */
 	int iPartIdxLabel;	/* Jump to this label to skip a row */
 	Vdbe *v;		/* Generate code into this virtual machine */
-	KeyInfo *pKey;		/* KeyInfo for index */
 	int regRecord;		/* Register holding assembled index record */
 	sqlite3 *db = pParse->db;	/* The database connection */
 	v = sqlite3GetVdbe(pParse);
@@ -2643,14 +2654,13 @@ sqlite3RefillIndex(Parse * pParse, Index * pIndex, int memRootPage)
 	} else {
 		tnum = pIndex->tnum;
 	}
-	pKey = sqlite3KeyInfoOfIndex(pParse, db, pIndex);
-	assert(pKey != 0 || db->mallocFailed || pParse->nErr);
+	struct key_def *def = sql_index_key_def(pIndex, false);
+	assert(def != NULL || db->mallocFailed || pParse->nErr);
 
 	/* Open the sorter cursor if we are to use one. */
 	iSorter = pParse->nTab++;
 	sqlite3VdbeAddOp4(v, OP_SorterOpen, iSorter, 0, pIndex->nColumn,
-			  (char *)
-			  sqlite3KeyInfoRef(pKey), P4_KEYINFO);
+			  (char *)def, P4_KEYDEF);
 
 	/* Open the table. Loop through all rows of the table, inserting index
 	 * records into the sorter.
@@ -2836,34 +2846,11 @@ index_is_unique(Index *idx)
 	return tnt_index->def->opts.is_unique;
 }
 
-/*
- * Create a new index for an SQL table.  pName1.pName2 is the name of the index
- * and pTblList is the name of the table that is to be indexed.  Both will
- * be NULL for a primary key or an index that is created to satisfy a
- * UNIQUE constraint.  If pTable and pIndex are NULL, use pParse->pNewTable
- * as the table to be indexed.  pParse->pNewTable is a table that is
- * currently being constructed by a CREATE TABLE statement.
- *
- * pList is a list of columns to be indexed.  pList will be NULL if this
- * is a primary key or unique-constraint on the most recent column added
- * to the table currently under construction.
- */
 void
-sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
-		   Token * pName,	/* Index name. May be NULL */
-		   SrcList * pTblName,	/* Table to index. Use pParse->pNewTable if 0 */
-		   ExprList * pList,	/* A list of columns to be indexed */
-		   int onError,	        /* ON_CONFLICT_ACTION_ABORT, _IGNORE,
-					 * _REPLACE, or _NONE.
-					 */
-		   Token MAYBE_UNUSED * pStart,	/* The CREATE token that begins
-						 * this statement
-						 */
-		   Expr * pPIWhere,	/* WHERE clause for partial indices */
-		   int sortOrder,	/* Sort order of primary key when pList==NULL */
-		   int ifNotExist,	/* Omit error if index already exists */
-		   u8 idxType	/* The index type */
-    )
+sql_create_index(struct Parse *parse, struct Token *token,
+		 struct SrcList *tbl_name, struct ExprList *col_list,
+		 int on_error, struct Token *start, struct Expr *pi_where,
+		 enum sort_order sort_order, bool if_not_exist, u8 idx_type)
 {
 	Table *pTab = 0;	/* Table to be indexed */
 	Index *pIndex = 0;	/* The index to be created */
@@ -2871,13 +2858,13 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	int nName;		/* Number of characters in zName */
 	int i, j;
 	DbFixer sFix;		/* For assigning database names to pTable */
-	sqlite3 *db = pParse->db;
-	struct ExprList_item *pListItem;	/* For looping over pList */
+	sqlite3 *db = parse->db;
+	struct ExprList_item *col_listItem;	/* For looping over col_list */
 	int nExtra = 0;		/* Space allocated for zExtra[] */
 	char *zExtra = 0;	/* Extra space after the Index object */
 	struct session *user_session = current_session();
 
-	if (db->mallocFailed || pParse->nErr > 0) {
+	if (db->mallocFailed || parse->nErr > 0) {
 		goto exit_create_index;
 	}
 	/* Do not account nested operations: the count of such
@@ -2886,8 +2873,8 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * PRIMARY KEY and UNIQUE constraint - they had been accounted
 	 * in CREATE TABLE already.
 	 */
-	if (!pParse->nested && idxType == SQLITE_IDXTYPE_APPDEF) {
-		Vdbe *v = sqlite3GetVdbe(pParse);
+	if (!parse->nested && idx_type == SQLITE_IDXTYPE_APPDEF) {
+		Vdbe *v = sqlite3GetVdbe(parse);
 		if (v == NULL)
 			goto exit_create_index;
 		sqlite3VdbeCountChanges(v);
@@ -2897,39 +2884,39 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	/*
 	 * Find the table that is to be indexed.  Return early if not found.
 	 */
-	if (pTblName != 0) {
+	if (tbl_name != 0) {
 
 		/* Use the two-part index name to determine the database
 		 * to search for the table. 'Fix' the table name to this db
 		 * before looking up the table.
 		 */
-		assert(pName && pName->z);
+		assert(token && token->z);
 
-		sqlite3FixInit(&sFix, pParse, "index", pName);
-		if (sqlite3FixSrcList(&sFix, pTblName)) {
-			/* Because the parser constructs pTblName from a single identifier,
+		sqlite3FixInit(&sFix, parse, "index", token);
+		if (sqlite3FixSrcList(&sFix, tbl_name)) {
+			/* Because the parser constructs tbl_name from a single identifier,
 			 * sqlite3FixSrcList can never fail.
 			 */
 			assert(0);
 		}
-		pTab = sqlite3LocateTable(pParse, 0, pTblName->a[0].zName);
+		pTab = sqlite3LocateTable(parse, 0, tbl_name->a[0].zName);
 		assert(db->mallocFailed == 0 || pTab == 0);
 		if (pTab == 0)
 			goto exit_create_index;
 		sqlite3PrimaryKeyIndex(pTab);
 	} else {
-		assert(pName == 0);
-		assert(pStart == 0);
-		pTab = pParse->pNewTable;
+		assert(token == 0);
+		assert(start == 0);
+		pTab = parse->pNewTable;
 		if (!pTab)
 			goto exit_create_index;
 	}
 
 	assert(pTab != 0);
-	assert(pParse->nErr == 0);
+	assert(parse->nErr == 0);
 #ifndef SQLITE_OMIT_VIEW
 	if (pTab->pSelect) {
-		sqlite3ErrorMsg(pParse, "views may not be indexed");
+		sqlite3ErrorMsg(parse, "views may not be indexed");
 		goto exit_create_index;
 	}
 #endif
@@ -2942,27 +2929,27 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * one of the index names collides with the name of a temporary table or
 	 * index, then we will continue to process this index.
 	 *
-	 * If pName==0 it means that we are
+	 * If token==0 it means that we are
 	 * dealing with a primary key or UNIQUE constraint.  We have to invent our
 	 * own name.
 	 */
-	if (pName) {
-		zName = sqlite3NameFromToken(db, pName);
+	if (token) {
+		zName = sqlite3NameFromToken(db, token);
 		if (zName == 0)
 			goto exit_create_index;
-		assert(pName->z != 0);
+		assert(token->z != 0);
 		if (!db->init.busy) {
 			if (sqlite3HashFind(&db->pSchema->tblHash, zName) !=
 			    NULL) {
-				sqlite3ErrorMsg(pParse,
+				sqlite3ErrorMsg(parse,
 						"there is already a table named %s",
 						zName);
 				goto exit_create_index;
 			}
 		}
 		if (sqlite3HashFind(&pTab->idxHash, zName) != NULL) {
-			if (!ifNotExist) {
-				sqlite3ErrorMsg(pParse,
+			if (!if_not_exist) {
+				sqlite3ErrorMsg(parse,
 						"index %s.%s already exists",
 						pTab->zName, zName);
 			} else {
@@ -2984,29 +2971,29 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 		}
 	}
 
-	/* If pList==0, it means this routine was called to make a primary
+	/* If col_list==0, it means this routine was called to make a primary
 	 * key out of the last column added to the table under construction.
 	 * So create a fake list to simulate this.
 	 */
-	if (pList == 0) {
+	if (col_list == 0) {
 		Token prevCol;
 		sqlite3TokenInit(&prevCol, pTab->aCol[pTab->nCol - 1].zName);
-		pList = sqlite3ExprListAppend(pParse, 0,
+		col_list = sqlite3ExprListAppend(parse, 0,
 					      sqlite3ExprAlloc(db, TK_ID,
 							       &prevCol, 0));
-		if (pList == 0)
+		if (col_list == 0)
 			goto exit_create_index;
-		assert(pList->nExpr == 1);
-		sqlite3ExprListSetSortOrder(pList, sortOrder);
+		assert(col_list->nExpr == 1);
+		sqlite3ExprListSetSortOrder(col_list, sort_order);
 	} else {
-		sqlite3ExprListCheckLength(pParse, pList, "index");
+		sqlite3ExprListCheckLength(parse, col_list, "index");
 	}
 
 	/* Figure out how many bytes of space are required to store explicitly
 	 * specified collation sequence names.
 	 */
-	for (i = 0; i < pList->nExpr; i++) {
-		Expr *pExpr = pList->a[i].pExpr;
+	for (i = 0; i < col_list->nExpr; i++) {
+		Expr *pExpr = col_list->a[i].pExpr;
 		assert(pExpr != 0);
 		if (pExpr->op == TK_COLLATE) {
 			nExtra += (1 + sqlite3Strlen30(pExpr->u.zToken));
@@ -3017,7 +3004,7 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * Allocate the index structure.
 	 */
 	nName = sqlite3Strlen30(zName);
-	pIndex = sqlite3AllocateIndexObject(db, pList->nExpr,
+	pIndex = sqlite3AllocateIndexObject(db, col_list->nExpr,
 					    nName + nExtra + 1, &zExtra);
 	if (db->mallocFailed) {
 		goto exit_create_index;
@@ -3028,26 +3015,26 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	zExtra += nName + 1;
 	memcpy(pIndex->zName, zName, nName + 1);
 	pIndex->pTable = pTab;
-	pIndex->onError = (u8) onError;
+	pIndex->onError = (u8) on_error;
 	/*
 	 * Don't make difference between UNIQUE indexes made by user
 	 * using CREATE INDEX statement and those created during
 	 * CREATE TABLE processing.
 	 */
-	if (idxType == SQLITE_IDXTYPE_APPDEF &&
-	    onError != ON_CONFLICT_ACTION_NONE) {
+	if (idx_type == SQLITE_IDXTYPE_APPDEF &&
+	    on_error != ON_CONFLICT_ACTION_NONE) {
 		pIndex->idxType = SQLITE_IDXTYPE_UNIQUE;
 	} else {
-		pIndex->idxType = idxType;
+		pIndex->idxType = idx_type;
 	}
 	pIndex->pSchema = db->pSchema;
-	pIndex->nColumn = pList->nExpr;
+	pIndex->nColumn = col_list->nExpr;
 	/* Tarantool have access to each column by any index */
-	if (pPIWhere) {
-		sqlite3ResolveSelfReference(pParse, pTab, NC_PartIdx, pPIWhere,
+	if (pi_where) {
+		sqlite3ResolveSelfReference(parse, pTab, NC_PartIdx, pi_where,
 					    0);
-		pIndex->pPartIdxWhere = pPIWhere;
-		pPIWhere = 0;
+		pIndex->pPartIdxWhere = pi_where;
+		pi_where = 0;
 	}
 
 	/* Analyze the list of expressions that form the terms of the index and
@@ -3059,16 +3046,16 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * TODO: Issue a warning if the table primary key is used as part of the
 	 * index key.
 	 */
-	for (i = 0, pListItem = pList->a; i < pList->nExpr; i++, pListItem++) {
+	for (i = 0, col_listItem = col_list->a; i < col_list->nExpr; i++, col_listItem++) {
 		Expr *pCExpr;	/* The i-th index expression */
 		enum sort_order requested_so;	/* ASC or DESC on the i-th expression */
-		sqlite3ResolveSelfReference(pParse, pTab, NC_IdxExpr,
-					    pListItem->pExpr, 0);
-		if (pParse->nErr)
+		sqlite3ResolveSelfReference(parse, pTab, NC_IdxExpr,
+					    col_listItem->pExpr, 0);
+		if (parse->nErr)
 			goto exit_create_index;
-		pCExpr = sqlite3ExprSkipCollate(pListItem->pExpr);
+		pCExpr = sqlite3ExprSkipCollate(col_listItem->pExpr);
 		if (pCExpr->op != TK_COLUMN) {
-			sqlite3ErrorMsg(pParse,
+			sqlite3ErrorMsg(parse,
 					"functional indexes aren't supported "
 					"in the current version");
 			goto exit_create_index;
@@ -3081,9 +3068,9 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 			pIndex->aiColumn[i] = (i16) j;
 		}
 		struct coll *coll;
-		if (pListItem->pExpr->op == TK_COLLATE) {
-			const char *coll_name = pListItem->pExpr->u.zToken;
-			coll = sqlite3GetCollSeq(pParse, 0, coll_name);
+		if (col_listItem->pExpr->op == TK_COLLATE) {
+			const char *coll_name = col_listItem->pExpr->u.zToken;
+			coll = sqlite3GetCollSeq(parse, 0, coll_name);
 
 			if (coll == NULL &&
 			    sqlite3StrICmp(coll_name, "binary") != 0) {
@@ -3099,15 +3086,15 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 		/* Tarantool: DESC indexes are not supported so far.
 		 * See gh-3016.
 		 */
-		requested_so = pListItem->sortOrder & 0;
+		requested_so = col_listItem->sort_order & 0;
 		pIndex->sort_order[i] = requested_so;
 	}
 
 	sqlite3DefaultRowEst(pIndex);
-	if (pParse->pNewTable == 0)
+	if (parse->pNewTable == 0)
 		estimateIndexWidth(pIndex);
 
-	if (pTab == pParse->pNewTable) {
+	if (pTab == parse->pNewTable) {
 		/* This routine has been called to create an automatic index as a
 		 * result of a PRIMARY KEY or UNIQUE clause on a column definition, or
 		 * a PRIMARY KEY or UNIQUE clause following the column definitions.
@@ -3161,7 +3148,7 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 					    (pIdx->onError == ON_CONFLICT_ACTION_DEFAULT
 					     || pIndex->onError ==
 					     ON_CONFLICT_ACTION_DEFAULT)) {
-						sqlite3ErrorMsg(pParse,
+						sqlite3ErrorMsg(parse,
 								"conflicting ON CONFLICT clauses specified",
 								0);
 					}
@@ -3169,8 +3156,8 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 						pIdx->onError = pIndex->onError;
 					}
 				}
-				if (idxType == SQLITE_IDXTYPE_PRIMARYKEY)
-					pIdx->idxType = idxType;
+				if (idx_type == SQLITE_IDXTYPE_PRIMARYKEY)
+					pIdx->idxType = idx_type;
 				goto exit_create_index;
 			}
 		}
@@ -3179,7 +3166,7 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	/* Link the new Index structure to its table and to the other
 	 * in-memory database structures.
 	 */
-	assert(pParse->nErr == 0);
+	assert(parse->nErr == 0);
 	if (db->init.busy) {
 		Index *p;
 		p = sqlite3HashInsert(&pTab->idxHash, pIndex->zName, pIndex);
@@ -3198,23 +3185,23 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * But, do not do this if we are simply parsing the schema, or if this
 	 * index is the PRIMARY KEY index.
 	 *
-	 * If pTblName==0 it means this index is generated as an implied PRIMARY KEY
+	 * If tbl_name==0 it means this index is generated as an implied PRIMARY KEY
 	 * or UNIQUE index in a CREATE TABLE statement.  Since the table
 	 * has just been created, it contains no data and the index initialization
 	 * step can be skipped.
 	 */
-	else if (pTblName) {
+	else if (tbl_name) {
 		Vdbe *v;
 		char *zStmt;
-		int iCursor = pParse->nTab++;
-		int index_space_ptr_reg = pParse->nTab++;
+		int iCursor = parse->nTab++;
+		int index_space_ptr_reg = parse->nTab++;
 		int iSpaceId, iIndexId, iFirstSchemaCol;
 
-		v = sqlite3GetVdbe(pParse);
+		v = sqlite3GetVdbe(parse);
 		if (v == 0)
 			goto exit_create_index;
 
-		sql_set_multi_write(pParse, true);
+		sql_set_multi_write(parse, true);
 
 
 		sqlite3VdbeAddOp2(v, OP_SIDtoPtr, BOX_INDEX_ID,
@@ -3226,34 +3213,34 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 		/* Gather the complete text of the CREATE INDEX statement into
 		 * the zStmt variable
 		 */
-		assert(pStart); {
+		assert(start); {
 			int n =
-			    (int)(pParse->sLastToken.z - pName->z) +
-			    pParse->sLastToken.n;
-			if (pName->z[n - 1] == ';')
+			    (int)(parse->sLastToken.z - token->z) +
+			    parse->sLastToken.n;
+			if (token->z[n - 1] == ';')
 				n--;
 			/* A named index with an explicit CREATE INDEX statement */
 			zStmt = sqlite3MPrintf(db, "CREATE%s INDEX %.*s",
-					       onError ==
+					       on_error ==
 					       ON_CONFLICT_ACTION_NONE
 					       ? "" : " UNIQUE", n,
-					       pName->z);
+					       token->z);
 		}
 
 		iSpaceId = SQLITE_PAGENO_TO_SPACEID(pTab->tnum);
-		iIndexId = getNewIid(pParse, iSpaceId, iCursor);
+		iIndexId = getNewIid(parse, iSpaceId, iCursor);
 		sqlite3VdbeAddOp1(v, OP_Close, iCursor);
-		createIndex(pParse, pIndex, iSpaceId, iIndexId, zStmt);
+		createIndex(parse, pIndex, iSpaceId, iIndexId, zStmt);
 
 		/* consumes zStmt */
 		iFirstSchemaCol =
-		    makeIndexSchemaRecord(pParse, pIndex, iSpaceId, iIndexId,
+		    makeIndexSchemaRecord(parse, pIndex, iSpaceId, iIndexId,
 					  zStmt);
 
 		/* Reparse the schema. Code an OP_Expire
 		 * to invalidate all pre-compiled statements.
 		 */
-		sqlite3ChangeCookie(pParse);
+		sqlite3ChangeCookie(parse);
 		sqlite3VdbeAddParseSchema2Op(v, iFirstSchemaCol, 4);
 		sqlite3VdbeAddOp0(v, OP_Expire);
 	}
@@ -3268,7 +3255,7 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
 	 * UPDATE and INSERT statements.
 	 */
 
-	if (!(db->init.busy || pTblName == 0))
+	if (!(db->init.busy || tbl_name == 0))
 		goto exit_create_index;
 	addIndexToTable(pIndex, pTab);
 	pIndex = 0;
@@ -3277,9 +3264,9 @@ sqlite3CreateIndex(Parse * pParse,	/* All information about this parse */
  exit_create_index:
 	if (pIndex)
 		freeIndex(db, pIndex);
-	sql_expr_free(db, pPIWhere, false);
-	sqlite3ExprListDelete(db, pList);
-	sqlite3SrcListDelete(db, pTblName);
+	sql_expr_free(db, pi_where, false);
+	sqlite3ExprListDelete(db, col_list);
+	sqlite3SrcListDelete(db, tbl_name);
 	sqlite3DbFree(db, zName);
 }
 
@@ -3374,15 +3361,6 @@ index_is_unique_not_null(const Index *idx)
 		!index->def->key_def->is_nullable);
 }
 
-/**
- * This routine will drop an existing named index.  This routine
- * implements the DROP INDEX statement.
- *
- * @param parse_context Current parsing context.
- * @param index_name_list List containing index name.
- * @param table_token Token representing table name.
- * @param if_exists True, if statement contains 'IF EXISTS' clause.
- */
 void
 sql_drop_index(struct Parse *parse_context, struct SrcList *index_name_list,
 	       struct Token *table_token, bool if_exists)
@@ -4171,46 +4149,6 @@ sqlite3Reindex(Parse * pParse, Token * pName1, Token * pName2)
 }
 #endif
 
-/*
- * Return a KeyInfo structure that is appropriate for the given Index.
- *
- * The caller should invoke sqlite3KeyInfoUnref() on the returned object
- * when it has finished using it.
- */
-KeyInfo *
-sqlite3KeyInfoOfIndex(Parse * pParse, sqlite3 * db, Index * pIdx)
-{
-	int i;
-	int nCol = pIdx->nColumn;
-	int nTableCol = pIdx->pTable->nCol;
-	KeyInfo *pKey;
-
-	if (pParse && pParse->nErr)
-		return 0;
-
-	/*
-	 * KeyInfo describes the index (i.e. the number of key columns,
-	 * comparator options, and the number of columns beyond the key).
-	 * Since Tarantool iterator yields the full tuple, we need a KeyInfo
-	 * as wide as the table itself.  Otherwize, not enough slots
-	 * for row parser cache are allocated in VdbeCursor object.
-	 */
-	pKey = sqlite3KeyInfoAlloc(db, nCol, nTableCol - nCol);
-	if (pKey) {
-		assert(sqlite3KeyInfoIsWriteable(pKey));
-		for (i = 0; i < nCol; i++) {
-			pKey->aColl[i] = sql_index_collation(pIdx, i);
-			pKey->aSortOrder[i] = sql_index_column_sort_order(pIdx,
-									  i);
-		}
-		if (pParse && pParse->nErr) {
-			sqlite3KeyInfoUnref(pKey);
-			pKey = 0;
-		}
-	}
-	return pKey;
-}
-
 #ifndef SQLITE_OMIT_CTE
 /*
  * This routine is invoked once per CTE by the parser while parsing a
diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
index 3f74b93..e229d45 100644
--- a/src/box/sql/delete.c
+++ b/src/box/sql/delete.c
@@ -386,10 +386,14 @@ sqlite3DeleteFrom(Parse * pParse,	/* The parser context */
 			iPk = pParse->nMem + 1;
 			pParse->nMem += nPk;
 			iEphCur = pParse->nTab++;
-			KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nPk, 0);
+			struct key_def *def = key_def_new(nPk);
+			if (def == NULL) {
+				pParse->rc = SQL_TARANTOOL_ERROR;
+				goto delete_from_cleanup;
+			}
 			addrEphOpen =
 				sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, iEphCur,
-						  nPk, 0, (char*) pKeyInfo, P4_KEYINFO);
+						  nPk, 0, (char*)def, P4_KEYDEF);
 		} else {
 			pPk = sqlite3PrimaryKeyIndex(pTab);
 			assert(pPk != 0);
@@ -400,7 +404,7 @@ sqlite3DeleteFrom(Parse * pParse,	/* The parser context */
 			addrEphOpen =
 			    sqlite3VdbeAddOp2(v, OP_OpenTEphemeral, iEphCur,
 					      nPk);
-			sqlite3VdbeSetP4KeyInfo(pParse, pPk);
+			sql_vdbe_set_p4_key_def(pParse, pPk);
 		}
 
 		/* Construct a query to find the primary key for every row
diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index cc969ca..83cbe60 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -1505,7 +1505,7 @@ sqlite3ExprListDup(sqlite3 * db, ExprList * p, int flags)
 		}
 		pItem->zName = sqlite3DbStrDup(db, pOldItem->zName);
 		pItem->zSpan = sqlite3DbStrDup(db, pOldItem->zSpan);
-		pItem->sortOrder = pOldItem->sortOrder;
+		pItem->sort_order = pOldItem->sort_order;
 		pItem->done = 0;
 		pItem->bSpanIsTab = pOldItem->bSpanIsTab;
 		pItem->u = pOldItem->u;
@@ -1756,20 +1756,17 @@ sqlite3ExprListAppendVector(Parse * pParse,	/* Parsing context */
 	return pList;
 }
 
-/*
- * Set the sort order for the last element on the given ExprList.
- */
 void
-sqlite3ExprListSetSortOrder(ExprList * p, int iSortOrder)
+sqlite3ExprListSetSortOrder(struct ExprList *p, enum sort_order sort_order)
 {
 	if (p == 0)
 		return;
 	assert(p->nExpr > 0);
-	if (iSortOrder == SORT_ORDER_UNDEF) {
-		assert(p->a[p->nExpr - 1].sortOrder == SORT_ORDER_ASC);
+	if (sort_order == SORT_ORDER_UNDEF) {
+		assert(p->a[p->nExpr - 1].sort_order == SORT_ORDER_ASC);
 		return;
 	}
-	p->a[p->nExpr - 1].sortOrder = (u8) iSortOrder;
+	p->a[p->nExpr - 1].sort_order = sort_order;
 }
 
 /*
@@ -2522,7 +2519,7 @@ sqlite3FindInIndex(Parse * pParse,	/* Parsing context */
 							  P4_DYNAMIC);
 					emit_open_cursor(pParse, iTab,
 							 pIdx->tnum);
-					sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
+					sql_vdbe_set_p4_key_def(pParse, pIdx);
 					VdbeComment((v, "%s", pIdx->zName));
 					assert(IN_INDEX_INDEX_DESC ==
 					       IN_INDEX_INDEX_ASC + 1);
@@ -2739,7 +2736,6 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
 	case TK_IN:{
 			int addr;	/* Address of OP_OpenEphemeral instruction */
 			Expr *pLeft = pExpr->pLeft;	/* the LHS of the IN operator */
-			KeyInfo *pKeyInfo = 0;	/* Key information */
 			int nVal;	/* Size of vector pLeft */
 
 			nVal = sqlite3ExprVectorSize(pLeft);
@@ -2761,7 +2757,11 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
 			pExpr->is_ephemeral = 1;
 			addr = sqlite3VdbeAddOp2(v, OP_OpenTEphemeral,
 						 pExpr->iTable, nVal);
-			pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nVal, 1);
+			struct key_def *key_def = key_def_new(nVal);
+			if (key_def == NULL) {
+				pParse->rc = SQL_TARANTOOL_ERROR;
+				return 0;
+			}
 
 			if (ExprHasProperty(pExpr, EP_xIsSelect)) {
 				/* Case 1:     expr IN (SELECT ...)
@@ -2787,29 +2787,33 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
 					pSelect->iLimit = 0;
 					testcase(pSelect->
 						 selFlags & SF_Distinct);
-					testcase(pKeyInfo == 0);	/* Caused by OOM in sqlite3KeyInfoAlloc() */
 					if (sqlite3Select
 					    (pParse, pSelect, &dest)) {
 						sqlite3DbFree(pParse->db,
 							      dest.zAffSdst);
-						sqlite3KeyInfoUnref(pKeyInfo);
+						if (key_def != NULL)
+							key_def_delete(key_def);
 						return 0;
 					}
 					sqlite3DbFree(pParse->db,
 						      dest.zAffSdst);
-					assert(pKeyInfo != 0);	/* OOM will cause exit after sqlite3Select() */
 					assert(pEList != 0);
 					assert(pEList->nExpr > 0);
-					assert(sqlite3KeyInfoIsWriteable
-					       (pKeyInfo));
 					for (i = 0; i < nVal; i++) {
 						Expr *p =
 						    sqlite3VectorFieldSubexpr
 						    (pLeft, i);
-						pKeyInfo->aColl[i] =
-						    sqlite3BinaryCompareCollSeq
-						    (pParse, p,
-						     pEList->a[i].pExpr);
+
+						struct coll *coll;
+						coll = sqlite3BinaryCompareCollSeq
+							(pParse, p,
+							 pEList->a[i].pExpr);
+
+						key_def_set_part(key_def, i, i,
+								 FIELD_TYPE_SCALAR,
+								 ON_CONFLICT_ACTION_ABORT,
+								 coll,
+								 SORT_ORDER_ASC);
 					}
 				}
 			} else if (ALWAYS(pExpr->x.pList != 0)) {
@@ -2830,14 +2834,18 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
 				if (!affinity) {
 					affinity = SQLITE_AFF_BLOB;
 				}
-				if (pKeyInfo) {
+				if (key_def != NULL) {
 					bool unused;
-					assert(sqlite3KeyInfoIsWriteable
-					       (pKeyInfo));
-					pKeyInfo->aColl[0] =
-						sql_expr_coll(pParse,
-							      pExpr->pLeft,
-							      &unused);
+					struct coll *coll;
+					coll = sql_expr_coll(pParse,
+							     pExpr->pLeft,
+							     &unused);
+
+					key_def_set_part(key_def, 0, 0,
+							 FIELD_TYPE_SCALAR,
+							 ON_CONFLICT_ACTION_ABORT,
+							 coll,
+							 SORT_ORDER_ASC);
 				}
 
 				/* Loop through each expression in <exprlist>. */
@@ -2868,9 +2876,9 @@ sqlite3CodeSubselect(Parse * pParse,	/* Parsing context */
 				sqlite3ReleaseTempReg(pParse, r1);
 				sqlite3ReleaseTempReg(pParse, r2);
 			}
-			if (pKeyInfo) {
-				sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo,
-						    P4_KEYINFO);
+			if (key_def != NULL) {
+				sqlite3VdbeChangeP4(v, addr, (void *)key_def,
+						    P4_KEYDEF);
 			}
 			break;
 		}
@@ -5183,7 +5191,7 @@ sqlite3ExprListCompare(ExprList * pA, ExprList * pB, int iTab)
 	for (i = 0; i < pA->nExpr; i++) {
 		Expr *pExprA = pA->a[i].pExpr;
 		Expr *pExprB = pB->a[i].pExpr;
-		if (pA->a[i].sortOrder != pB->a[i].sortOrder)
+		if (pA->a[i].sort_order != pB->a[i].sort_order)
 			return 1;
 		if (sqlite3ExprCompare(pExprA, pExprB, iTab))
 			return 1;
diff --git a/src/box/sql/fkey.c b/src/box/sql/fkey.c
index 55edf6b..60b4786 100644
--- a/src/box/sql/fkey.c
+++ b/src/box/sql/fkey.c
@@ -437,7 +437,7 @@ fkLookupParent(Parse * pParse,	/* Parse context */
 			int regRec = sqlite3GetTempReg(pParse);
 
 			emit_open_cursor(pParse, iCur, pIdx->tnum);
-			sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
+			sql_vdbe_set_p4_key_def(pParse, pIdx);
 			for (i = 0; i < nCol; i++) {
 				sqlite3VdbeAddOp2(v, OP_Copy,
 						  aiCol[i] + 1 + regData,
diff --git a/src/box/sql/insert.c b/src/box/sql/insert.c
index 3ad3fc7..f6a93ce 100644
--- a/src/box/sql/insert.c
+++ b/src/box/sql/insert.c
@@ -55,7 +55,7 @@ sqlite3OpenTable(Parse * pParse,	/* Generate code into this VDBE */
 	assert(pPk != 0);
 	assert(pPk->tnum == pTab->tnum);
 	emit_open_cursor(pParse, iCur, pPk->tnum);
-	sqlite3VdbeSetP4KeyInfo(pParse, pPk);
+	sql_vdbe_set_p4_key_def(pParse, pPk);
 	VdbeComment((v, "%s", pTab->zName));
 }
 
@@ -566,9 +566,13 @@ sqlite3Insert(Parse * pParse,	/* Parser context */
 			regRec = sqlite3GetTempReg(pParse);
 			regCopy = sqlite3GetTempRange(pParse, nColumn);
 			regTempId = sqlite3GetTempReg(pParse);
-			KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, 1+nColumn, 0);
+			struct key_def *def = key_def_new(nColumn + 1);
+			if (def == NULL) {
+				pParse->rc = SQL_TARANTOOL_ERROR;
+				goto insert_cleanup;
+			}
 			sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, srcTab, nColumn+1,
-					  0, (char*)pKeyInfo, P4_KEYINFO);
+					  0, (char*)def, P4_KEYDEF);
 			/* Create counter for rowid */
 			sqlite3VdbeAddOp4Dup8(v, OP_Int64,
 					      0 /* unused */,
@@ -1602,7 +1606,7 @@ sqlite3OpenTableAndIndices(Parse * pParse,	/* Parsing context */
 			if (aToOpen == 0 || aToOpen[i + 1]) {
 				sqlite3VdbeAddOp3(v, op, iIdxCur, pIdx->tnum,
 						  space_ptr_reg);
-				sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
+				sql_vdbe_set_p4_key_def(pParse, pIdx);
 				sqlite3VdbeChangeP5(v, p5);
 				VdbeComment((v, "%s", pIdx->zName));
 			}
@@ -1916,10 +1920,10 @@ xferOptimization(Parse * pParse,	/* Parser context */
 		}
 		assert(pSrcIdx);
 		emit_open_cursor(pParse, iSrc, pSrcIdx->tnum);
-		sqlite3VdbeSetP4KeyInfo(pParse, pSrcIdx);
+		sql_vdbe_set_p4_key_def(pParse, pSrcIdx);
 		VdbeComment((v, "%s", pSrcIdx->zName));
 		emit_open_cursor(pParse, iDest, pDestIdx->tnum);
-		sqlite3VdbeSetP4KeyInfo(pParse, pDestIdx);
+		sql_vdbe_set_p4_key_def(pParse, pDestIdx);
 		sqlite3VdbeChangeP5(v, OPFLAG_BULKCSR);
 		VdbeComment((v, "%s", pDestIdx->zName));
 		addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iSrc, 0);
diff --git a/src/box/sql/parse.y b/src/box/sql/parse.y
index f548b4d..a40009d 100644
--- a/src/box/sql/parse.y
+++ b/src/box/sql/parse.y
@@ -281,8 +281,9 @@ ccons ::= NULL onconf.
 ccons ::= NOT NULL onconf(R).    {sqlite3AddNotNull(pParse, R);}
 ccons ::= PRIMARY KEY sortorder(Z) onconf(R) autoinc(I).
                                  {sqlite3AddPrimaryKey(pParse,0,R,I,Z);}
-ccons ::= UNIQUE onconf(R).      {sqlite3CreateIndex(pParse,0,0,0,R,0,0,0,0,
-                                   SQLITE_IDXTYPE_UNIQUE);}
+ccons ::= UNIQUE onconf(R).      {sql_create_index(pParse,0,0,0,R,0,0,
+						   SORT_ORDER_ASC, false,
+						   SQLITE_IDXTYPE_UNIQUE);}
 ccons ::= CHECK LP expr(X) RP.   {sqlite3AddCheckConstraint(pParse,X.pExpr);}
 ccons ::= REFERENCES nm(T) eidlist_opt(TA) refargs(R).
                                  {sqlite3CreateForeignKey(pParse,0,&T,TA,R);}
@@ -331,8 +332,9 @@ tcons ::= CONSTRAINT nm(X).      {pParse->constraintName = X;}
 tcons ::= PRIMARY KEY LP sortlist(X) autoinc(I) RP onconf(R).
                                  {sqlite3AddPrimaryKey(pParse,X,R,I,0);}
 tcons ::= UNIQUE LP sortlist(X) RP onconf(R).
-                                 {sqlite3CreateIndex(pParse,0,0,X,R,0,0,0,0,
-                                       SQLITE_IDXTYPE_UNIQUE);}
+                                 {sql_create_index(pParse,0,0,X,R,0,0,
+						   SORT_ORDER_ASC,false,
+						   SQLITE_IDXTYPE_UNIQUE);}
 tcons ::= CHECK LP expr(E) RP onconf.
                                  {sqlite3AddCheckConstraint(pParse,E.pExpr);}
 tcons ::= FOREIGN KEY LP eidlist(FA) RP
@@ -1239,9 +1241,9 @@ paren_exprlist(A) ::= LP exprlist(X) RP.  {A = X;}
 //
 cmd ::= createkw(S) uniqueflag(U) INDEX ifnotexists(NE) nm(X)
         ON nm(Y) LP sortlist(Z) RP where_opt(W). {
-  sqlite3CreateIndex(pParse, &X, 
-                     sqlite3SrcListAppend(pParse->db,0,&Y), Z, U,
-                      &S, W, SORT_ORDER_ASC, NE, SQLITE_IDXTYPE_APPDEF);
+  sql_create_index(pParse, &X, 
+		   sqlite3SrcListAppend(pParse->db,0,&Y), Z, U,
+		   &S, W, SORT_ORDER_ASC, NE, SQLITE_IDXTYPE_APPDEF);
 }
 
 %type uniqueflag {int}
diff --git a/src/box/sql/pragma.c b/src/box/sql/pragma.c
index 20a1587..1e4ae81 100644
--- a/src/box/sql/pragma.c
+++ b/src/box/sql/pragma.c
@@ -643,8 +643,8 @@ sqlite3Pragma(Parse * pParse, Token * pId,	/* First part of [schema.]id field */
 									  pIdx->
 									  tnum,
 									  0);
-							sqlite3VdbeSetP4KeyInfo
-							    (pParse, pIdx);
+							sql_vdbe_set_p4_key_def(pParse,
+										pIdx);
 						}
 					} else {
 						k = 0;
diff --git a/src/box/sql/select.c b/src/box/sql/select.c
index a5e6563..e49b90b 100644
--- a/src/box/sql/select.c
+++ b/src/box/sql/select.c
@@ -562,12 +562,31 @@ sqliteProcessJoin(Parse * pParse, Select * p)
 	return 0;
 }
 
-/* Forward reference */
-static KeyInfo *
-keyInfoFromExprList(Parse * pParse,	/* Parsing context */
-		    ExprList * pList,	/* Form the KeyInfo object from this ExprList */
-		    int iStart,		/* Begin with this column of pList */
-		    int nExtra);	/* Add this many extra columns to the end */
+/**
+ * Given an expression list, generate a key_def structure that
+ * records the collating sequence for each expression in that
+ * expression list.
+ *
+ * If the ExprList is an ORDER BY or GROUP BY clause then the
+ * resulting key_def structure is appropriate for initializing
+ * a virtual index to implement that clause.  If the ExprList is
+ * the result set of a SELECT then the key_info structure is
+ * appropriate for initializing a virtual index to implement a
+ * DISTINCT test.
+ *
+ * Space to hold the key_info structure is obtained from malloc.
+ * The calling function is responsible for seeing that this
+ * structure is eventually freed.
+ *
+ * @param parse Parsing context.
+ * @param list Expression list.
+ * @param start No of leading parts to skip.
+ *
+ * @retval Allocated key_def, NULL in case of OOM.
+ */
+static struct key_def *
+sql_expr_list_to_key_def(struct Parse *parse, struct ExprList *list, int start);
+
 
 /*
  * Generate code that will push the record in registers regData
@@ -623,7 +642,6 @@ pushOntoSorter(Parse * pParse,		/* Parser context */
 		int addrJmp;	/* Address of the OP_Jump opcode */
 		VdbeOp *pOp;	/* Opcode that opens the sorter */
 		int nKey;	/* Number of sorting key columns, including OP_Sequence */
-		KeyInfo *pKI;	/* Original KeyInfo on the sorter table */
 
 		regPrevKey = pParse->nMem + 1;
 		pParse->nMem += pSort->nOBSat;
@@ -643,13 +661,17 @@ pushOntoSorter(Parse * pParse,		/* Parser context */
 		if (pParse->db->mallocFailed)
 			return;
 		pOp->p2 = nKey + nData;
-		pKI = pOp->p4.pKeyInfo;
-		memset(pKI->aSortOrder, 0, pKI->nField);	/* Makes OP_Jump below testable */
-		sqlite3VdbeChangeP4(v, -1, (char *)pKI, P4_KEYINFO);
-		testcase(pKI->nXField > 2);
-		pOp->p4.pKeyInfo =
-		    keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat,
-					pKI->nXField - 1);
+		struct key_def *def = key_def_dup(pOp->p4.key_def);
+		if (def == NULL) {
+			pParse->rc = SQL_TARANTOOL_ERROR;
+			return;
+		}
+		for (uint32_t i = 0; i < def->part_count; ++i)
+			pOp->p4.key_def->parts[i].sort_order = SORT_ORDER_ASC;
+		sqlite3VdbeChangeP4(v, -1, (char *)def, P4_KEYDEF);
+		pOp->p4.key_def = sql_expr_list_to_key_def(pParse,
+							   pSort->pOrderBy,
+							   nOBSat);
 		addrJmp = sqlite3VdbeCurrentAddr(v);
 		sqlite3VdbeAddOp3(v, OP_Jump, addrJmp + 1, 0, addrJmp + 1);
 		VdbeCoverage(v);
@@ -1193,109 +1215,24 @@ selectInnerLoop(Parse * pParse,		/* The parser context */
 	}
 }
 
-/*
- * Allocate a KeyInfo object sufficient for an index of N key columns and
- * X extra columns.
- */
-KeyInfo *
-sqlite3KeyInfoAlloc(sqlite3 * db, int N, int X)
+static struct key_def *
+sql_expr_list_to_key_def(struct Parse *parse, struct ExprList *list, int start)
 {
-	int nExtra = (N + X) * (sizeof(struct coll *) + 1);
-	KeyInfo *p = sqlite3DbMallocRawNN(db, sizeof(KeyInfo) + nExtra);
-	if (p) {
-		p->aSortOrder = (u8 *) & p->aColl[N + X];
-		p->nField = (u16) N;
-		p->nXField = (u16) X;
-		p->db = db;
-		p->nRef = 1;
-		p->aColl[0] = NULL;
-		memset(&p[1], 0, nExtra);
-	} else {
-		sqlite3OomFault(db);
-	}
-	return p;
-}
-
-/*
- * Deallocate a KeyInfo object
- */
-void
-sqlite3KeyInfoUnref(KeyInfo * p)
-{
-	if (p) {
-		assert(p->nRef > 0);
-		p->nRef--;
-		if (p->nRef == 0)
-			sqlite3DbFree(p->db, p);
-	}
-}
-
-/*
- * Make a new pointer to a KeyInfo object
- */
-KeyInfo *
-sqlite3KeyInfoRef(KeyInfo * p)
-{
-	if (p) {
-		assert(p->nRef > 0);
-		p->nRef++;
+	int expr_count = list->nExpr;
+	struct key_def *def = key_def_new(expr_count);
+	if (def == NULL) {
+		parse->rc = SQL_TARANTOOL_ERROR;
+		return NULL;
 	}
-	return p;
-}
-
-#ifdef SQLITE_DEBUG
-/*
- * Return TRUE if a KeyInfo object can be change.  The KeyInfo object
- * can only be changed if this is just a single reference to the object.
- *
- * This routine is used only inside of assert() statements.
- */
-int
-sqlite3KeyInfoIsWriteable(KeyInfo * p)
-{
-	return p->nRef == 1;
-}
-#endif				/* SQLITE_DEBUG */
-
-/*
- * Given an expression list, generate a KeyInfo structure that records
- * the collating sequence for each expression in that expression list.
- *
- * If the ExprList is an ORDER BY or GROUP BY clause then the resulting
- * KeyInfo structure is appropriate for initializing a virtual index to
- * implement that clause.  If the ExprList is the result set of a SELECT
- * then the KeyInfo structure is appropriate for initializing a virtual
- * index to implement a DISTINCT test.
- *
- * Space to hold the KeyInfo structure is obtained from malloc.  The calling
- * function is responsible for seeing that this structure is eventually
- * freed.
- */
-static KeyInfo *
-keyInfoFromExprList(Parse * pParse,	/* Parsing context */
-		    ExprList * pList,	/* Form the KeyInfo object from this ExprList */
-		    int iStart,		/* Begin with this column of pList */
-		    int nExtra)		/* Add this many extra columns to the end */
-{
-	int nExpr;
-	KeyInfo *pInfo;
-	struct ExprList_item *pItem;
-	sqlite3 *db = pParse->db;
-	int i;
-
-	nExpr = pList->nExpr;
-	pInfo = sqlite3KeyInfoAlloc(db, nExpr - iStart, nExtra + 1);
-	if (pInfo) {
-		assert(sqlite3KeyInfoIsWriteable(pInfo));
-		for (i = iStart, pItem = pList->a + iStart; i < nExpr;
-		     i++, pItem++) {
-			bool unused;
-			pInfo->aColl[i - iStart] =
-				sql_expr_coll(pParse, pItem->pExpr, &unused);
-			pInfo->aSortOrder[i - iStart] = pItem->sortOrder;
-		}
+	struct ExprList_item *item = list->a + start;
+	for (int i = start; i < expr_count; ++i, ++item) {
+		bool unused;
+		struct coll *coll = sql_expr_coll(parse, item->pExpr, &unused);
+		key_def_set_part(def, i-start, i-start, FIELD_TYPE_SCALAR,
+				 ON_CONFLICT_ACTION_ABORT, coll,
+				 item->sort_order);
 	}
-	return pInfo;
+	return def;
 }
 
 /*
@@ -2123,54 +2060,62 @@ multiSelectCollSeq(Parse * pParse, Select * p, int iCol, bool *is_found)
 	return coll;
 }
 
-/*
- * The select statement passed as the second parameter is a compound SELECT
- * with an ORDER BY clause. This function allocates and returns a KeyInfo
- * structure suitable for implementing the ORDER BY.
+/**
+ * The select statement passed as the second parameter is a
+ * compound SELECT with an ORDER BY clause. This function
+ * allocates and returns a key_def structure suitable for
+ * implementing the ORDER BY.
+ *
+ * Space to hold the key_def structure is obtained from malloc.
+ * The calling function is responsible for ensuring that this
+ * structure is eventually freed.
  *
- * Space to hold the KeyInfo structure is obtained from malloc. The calling
- * function is responsible for ensuring that this structure is eventually
- * freed.
+ * @param parse Parsing context.
+ * @param s Select struct to analyze.
+ * @param extra No of extra slots to allocate.
+ *
+ * @retval Allocated key_def, NULL in case of OOM.
  */
-static KeyInfo *
-multiSelectOrderByKeyInfo(Parse * pParse, Select * p, int nExtra)
+static struct key_def *
+sql_multiselect_orderby_to_key_def(struct Parse *parse, struct Select *s,
+				   int extra)
 {
-	ExprList *pOrderBy = p->pOrderBy;
-	int nOrderBy = p->pOrderBy->nExpr;
-	sqlite3 *db = pParse->db;
-	KeyInfo *pRet = sqlite3KeyInfoAlloc(db, nOrderBy + nExtra, 1);
-	if (pRet) {
-		int i;
-		for (i = 0; i < nOrderBy; i++) {
-			struct ExprList_item *pItem = &pOrderBy->a[i];
-			Expr *pTerm = pItem->pExpr;
-			struct coll *coll;
-			bool is_found = false;
+	int ob_count = s->pOrderBy->nExpr;
+	struct key_def *key_def = key_def_new(ob_count + extra);
+	if (key_def == NULL) {
+		parse->rc = SQL_TARANTOOL_ERROR;
+		return NULL;
+	}
 
-			if (pTerm->flags & EP_Collate) {
-				coll = sql_expr_coll(pParse, pTerm, &is_found);
+	ExprList *order_by = s->pOrderBy;
+	for (int i = 0; i < ob_count; i++) {
+		struct ExprList_item *item = &order_by->a[i];
+		struct Expr *term = item->pExpr;
+		struct coll *coll;
+		bool is_found = false;
+
+		if (term->flags & EP_Collate) {
+			coll = sql_expr_coll(parse, term, &is_found);
+		} else {
+			coll = multiSelectCollSeq(parse, s,
+						  item->u.x.iOrderByCol - 1,
+						  &is_found);
+			if (coll != NULL) {
+				order_by->a[i].pExpr =
+					sqlite3ExprAddCollateString(parse, term,
+								    coll->name);
 			} else {
-				coll =
-				    multiSelectCollSeq(pParse, p,
-						       pItem->u.x.iOrderByCol - 1,
-						       &is_found);
-				if (coll != NULL) {
-					pOrderBy->a[i].pExpr =
-						sqlite3ExprAddCollateString(pParse, pTerm,
-									    coll->name);
-				} else {
-					pOrderBy->a[i].pExpr =
-						sqlite3ExprAddCollateString(pParse, pTerm,
-									    "BINARY");
-				}
+				order_by->a[i].pExpr =
+					sqlite3ExprAddCollateString(parse, term,
+								    "BINARY");
 			}
-			assert(sqlite3KeyInfoIsWriteable(pRet));
-			pRet->aColl[i] = coll;
-			pRet->aSortOrder[i] = pOrderBy->a[i].sortOrder;
 		}
+		key_def_set_part(key_def, i, i, FIELD_TYPE_SCALAR,
+				 ON_CONFLICT_ACTION_ABORT, coll,
+				 order_by->a[i].sort_order);
 	}
 
-	return pRet;
+	return key_def;
 }
 
 #ifndef SQLITE_OMIT_CTE
@@ -2270,16 +2215,17 @@ generateWithRecursiveQuery(Parse * pParse,	/* Parsing context */
 	regCurrent = ++pParse->nMem;
 	sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);
 	if (pOrderBy) {
-		KeyInfo *pKeyInfo = multiSelectOrderByKeyInfo(pParse, p, 1);
+		struct key_def *def = sql_multiselect_orderby_to_key_def(pParse,
+									 p, 1);
 		sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, iQueue,
-				  pOrderBy->nExpr + 2, 0, (char *)pKeyInfo,
-				  P4_KEYINFO);
+				  pOrderBy->nExpr + 2, 0, (char *)def,
+				  P4_KEYDEF);
 		VdbeComment((v, "Orderby table"));
 		destQueue.pOrderBy = pOrderBy;
 	} else {
-		KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nCol + 1, 0);
+		struct key_def *def = key_def_new(nCol + 1);
 		sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, iQueue, nCol + 1, 0,
-				  (char*)pKeyInfo, P4_KEYINFO);
+				  (char*)def, P4_KEYDEF);
 		VdbeComment((v, "Queue table"));
 	}
 	if (iDistinct) {
@@ -2480,9 +2426,9 @@ multiSelect(Parse * pParse,	/* Parsing context */
 	if (dest.eDest == SRT_EphemTab) {
 		assert(p->pEList);
 		int nCols = p->pEList->nExpr;
-		KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nCols + 1, 0);
+		struct key_def *def = key_def_new(nCols + 1);
 		sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, dest.iSDParm, nCols + 1,
-				  0, (char*)pKeyInfo, P4_KEYINFO);
+				  0, (char*)def, P4_KEYDEF);
 		VdbeComment((v, "Destination temp"));
 		dest.eDest = SRT_Table;
 	}
@@ -2790,7 +2736,7 @@ multiSelect(Parse * pParse,	/* Parsing context */
 
 	/* Compute collating sequences used by
 	 * temporary tables needed to implement the compound select.
-	 * Attach the KeyInfo structure to all temporary tables.
+	 * Attach the key_def structure to all temporary tables.
 	 *
 	 * This section is run by the right-most SELECT statement only.
 	 * SELECT statements to the left always skip this part.  The right-most
@@ -2798,26 +2744,25 @@ multiSelect(Parse * pParse,	/* Parsing context */
 	 * no temp tables are required.
 	 */
 	if (p->selFlags & SF_UsesEphemeral) {
-		int i;		/* Loop counter */
-		KeyInfo *pKeyInfo;	/* Collating sequence for the result set */
-		Select *pLoop;	/* For looping through SELECT statements */
-		struct coll **apColl;	/* For looping through pKeyInfo->aColl[] */
-		int nCol;	/* Number of columns in result set */
-
-		assert(p->pNext == 0);
-		nCol = p->pEList->nExpr;
-		pKeyInfo = sqlite3KeyInfoAlloc(db, nCol, 1);
-		if (!pKeyInfo) {
+		assert(p->pNext == NULL);
+		int nCol = p->pEList->nExpr;
+		struct key_def *key_def = key_def_new(nCol);
+		if (key_def == NULL) {
 			rc = SQLITE_NOMEM_BKPT;
 			goto multi_select_end;
 		}
-		for (i = 0, apColl = pKeyInfo->aColl; i < nCol; i++, apColl++) {
-			bool is_found = false;
-			*apColl = multiSelectCollSeq(pParse, p, i, &is_found);
+		for (int i = 0; i < nCol; i++) {
+			bool unused;
+			key_def_set_part(key_def, i, i,
+					 FIELD_TYPE_SCALAR,
+					 ON_CONFLICT_ACTION_ABORT,
+					 multiSelectCollSeq(pParse, p, i,
+							    &unused),
+					 SORT_ORDER_ASC);
 		}
 
-		for (pLoop = p; pLoop; pLoop = pLoop->pPrior) {
-			for (i = 0; i < 2; i++) {
+		for (struct Select *pLoop = p; pLoop; pLoop = pLoop->pPrior) {
+			for (int i = 0; i < 2; i++) {
 				int addr = pLoop->addrOpenEphm[i];
 				if (addr < 0) {
 					/* If [0] is unused then [1] is also unused.  So we can
@@ -2827,14 +2772,19 @@ multiSelect(Parse * pParse,	/* Parsing context */
 					break;
 				}
 				sqlite3VdbeChangeP2(v, addr, nCol);
+				struct key_def *dup_def = key_def_dup(key_def);
+				if (dup_def == NULL) {
+					rc = SQLITE_NOMEM_BKPT;
+					goto multi_select_end;
+				}
+				
 				sqlite3VdbeChangeP4(v, addr,
-						    (char *)
-						    sqlite3KeyInfoRef(pKeyInfo),
-						    P4_KEYINFO);
+						    (char *)dup_def,
+						    P4_KEYDEF);
 				pLoop->addrOpenEphm[i] = -1;
 			}
 		}
-		sqlite3KeyInfoUnref(pKeyInfo);
+		free(key_def);
 	}
 
  multi_select_end:
@@ -2845,54 +2795,57 @@ multiSelect(Parse * pParse,	/* Parsing context */
 }
 #endif				/* SQLITE_OMIT_COMPOUND_SELECT */
 
-/*
- * Error message for when two or more terms of a compound select have different
- * size result sets.
- */
 void
-sqlite3SelectWrongNumTermsError(Parse * pParse, Select * p)
+sqlite3SelectWrongNumTermsError(struct Parse *parse, struct Select * p)
 {
 	if (p->selFlags & SF_Values) {
-		sqlite3ErrorMsg(pParse,
+		sqlite3ErrorMsg(parse,
 				"all VALUES must have the same number of terms");
 	} else {
-		sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
+		sqlite3ErrorMsg(parse, "SELECTs to the left and right of %s"
 				" do not have the same number of result columns",
 				selectOpName(p->op));
 	}
 }
 
-/*
+/**
  * Code an output subroutine for a coroutine implementation of a
  * SELECT statment.
  *
  * The data to be output is contained in pIn->iSdst.  There are
- * pIn->nSdst columns to be output.  pDest is where the output should
- * be sent.
+ * pIn->nSdst columns to be output.  pDest is where the output
+ * should be sent.
  *
  * regReturn is the number of the register holding the subroutine
  * return address.
  *
  * If regPrev>0 then it is the first register in a vector that
- * records the previous output.  mem[regPrev] is a flag that is false
- * if there has been no previous output.  If regPrev>0 then code is
- * generated to suppress duplicates.  pKeyInfo is used for comparing
- * keys.
+ * records the previous output.  mem[regPrev] is a flag that is
+ * false if there has been no previous output.  If regPrev>0 then
+ * code is generated to suppress duplicates.  def is used for
+ * comparing keys.
  *
  * If the LIMIT found in p->iLimit is reached, jump immediately to
  * iBreak.
+ *
+ * @param parse Parsing context.
+ * @param p The SELECT statement.
+ * @param in Coroutine supplying data.
+ * @param dest Where to send the data.
+ * @param reg_ret The return address register.
+ * @param reg_prev Previous result register.  No uniqueness if 0.
+ * @param def For comparing with previous entry.
+ * @param break_addr Jump here if we hit the LIMIT.
+ *
+ * @retval Address of generated routine.
  */
 static int
-generateOutputSubroutine(Parse * pParse,	/* Parsing context */
-			 Select * p,		/* The SELECT statement */
-			 SelectDest * pIn,	/* Coroutine supplying data */
-			 SelectDest * pDest,	/* Where to send the data */
-			 int regReturn,		/* The return address register */
-			 int regPrev,		/* Previous result register.  No uniqueness if 0 */
-			 KeyInfo * pKeyInfo,	/* For comparing with previous entry */
-			 int iBreak)		/* Jump here if we hit the LIMIT */
+generateOutputSubroutine(struct Parse *parse, struct Select *p,
+			 struct SelectDest *in, struct SelectDest *dest,
+			 int reg_ret, int reg_prev, const struct key_def *def,
+			 int break_addr)
 {
-	Vdbe *v = pParse->pVdbe;
+	Vdbe *v = parse->pVdbe;
 	int iContinue;
 	int addr;
 
@@ -2901,63 +2854,68 @@ generateOutputSubroutine(Parse * pParse,	/* Parsing context */
 
 	/* Suppress duplicates for UNION, EXCEPT, and INTERSECT
 	 */
-	if (regPrev) {
+	if (reg_prev) {
 		int addr1, addr2;
-		addr1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev);
+		addr1 = sqlite3VdbeAddOp1(v, OP_IfNot, reg_prev);
 		VdbeCoverage(v);
+		struct key_def *dup_def = key_def_dup(def);
+		if (dup_def == NULL) {
+			parse->db->mallocFailed = 1;
+			return 0;
+		}
 		addr2 =
-		    sqlite3VdbeAddOp4(v, OP_Compare, pIn->iSdst, regPrev + 1,
-				      pIn->nSdst,
-				      (char *)sqlite3KeyInfoRef(pKeyInfo),
-				      P4_KEYINFO);
+		    sqlite3VdbeAddOp4(v, OP_Compare, in->iSdst, reg_prev + 1,
+				      in->nSdst,
+				      (char *)dup_def,
+				      P4_KEYDEF);
 		sqlite3VdbeAddOp3(v, OP_Jump, addr2 + 2, iContinue, addr2 + 2);
 		VdbeCoverage(v);
 		sqlite3VdbeJumpHere(v, addr1);
-		sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev + 1,
-				  pIn->nSdst - 1);
-		sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);
+		sqlite3VdbeAddOp3(v, OP_Copy, in->iSdst, reg_prev + 1,
+				  in->nSdst - 1);
+		sqlite3VdbeAddOp2(v, OP_Integer, 1, reg_prev);
 	}
-	if (pParse->db->mallocFailed)
+	if (parse->db->mallocFailed)
 		return 0;
 
 	/* Suppress the first OFFSET entries if there is an OFFSET clause
 	 */
 	codeOffset(v, p->iOffset, iContinue);
 
-	assert(pDest->eDest != SRT_Exists);
-	assert(pDest->eDest != SRT_Table);
-	switch (pDest->eDest) {
+	assert(dest->eDest != SRT_Exists);
+	assert(dest->eDest != SRT_Table);
+	switch (dest->eDest) {
 		/* Store the result as data using a unique key.
 		 */
 	case SRT_EphemTab:{
-			int regRec = sqlite3GetTempReg(pParse);
-			int regCopy = sqlite3GetTempRange(pParse, pIn->nSdst + 1);
-			sqlite3VdbeAddOp3(v, OP_NextIdEphemeral, pDest->iSDParm,
-					  pIn->nSdst, regCopy + pIn->nSdst);
-			sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regCopy,
-					  pIn->nSdst - 1);
+			int regRec = sqlite3GetTempReg(parse);
+			int regCopy = sqlite3GetTempRange(parse, in->nSdst + 1);
+			sqlite3VdbeAddOp3(v, OP_NextIdEphemeral, dest->iSDParm,
+					  in->nSdst, regCopy + in->nSdst);
+			sqlite3VdbeAddOp3(v, OP_Copy, in->iSdst, regCopy,
+					  in->nSdst - 1);
 			sqlite3VdbeAddOp3(v, OP_MakeRecord, regCopy,
-					  pIn->nSdst + 1, regRec);
+					  in->nSdst + 1, regRec);
 			/* Set flag to save memory allocating one by malloc. */
 			sqlite3VdbeChangeP5(v, 1);
-			sqlite3VdbeAddOp2(v, OP_IdxInsert, pDest->iSDParm, regRec);
-			sqlite3ReleaseTempRange(pParse, regCopy, pIn->nSdst + 1);
-			sqlite3ReleaseTempReg(pParse, regRec);
+			sqlite3VdbeAddOp2(v, OP_IdxInsert, dest->iSDParm, regRec);
+			sqlite3ReleaseTempRange(parse, regCopy, in->nSdst + 1);
+			sqlite3ReleaseTempReg(parse, regRec);
 			break;
 		}
 		/* If we are creating a set for an "expr IN (SELECT ...)".
 		 */
 	case SRT_Set:{
 			int r1;
-			testcase(pIn->nSdst > 1);
-			r1 = sqlite3GetTempReg(pParse);
-			sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst,
-					  pIn->nSdst, r1, pDest->zAffSdst,
-					  pIn->nSdst);
-			sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst,
-						       pIn->nSdst);
-			sqlite3VdbeAddOp2(v, OP_IdxInsert, pDest->iSDParm, r1);
-			sqlite3ReleaseTempReg(pParse, r1);
+			testcase(in->nSdst > 1);
+			r1 = sqlite3GetTempReg(parse);
+			sqlite3VdbeAddOp4(v, OP_MakeRecord, in->iSdst,
+					  in->nSdst, r1, dest->zAffSdst,
+					  in->nSdst);
+			sqlite3ExprCacheAffinityChange(parse, in->iSdst,
+						       in->nSdst);
+			sqlite3VdbeAddOp2(v, OP_IdxInsert, dest->iSDParm, r1);
+			sqlite3ReleaseTempReg(parse, r1);
 			break;
 		}
 
@@ -2966,25 +2924,25 @@ generateOutputSubroutine(Parse * pParse,	/* Parsing context */
 		 * of the scan loop.
 		 */
 	case SRT_Mem:{
-			assert(pIn->nSdst == 1 || pParse->nErr > 0);
-			testcase(pIn->nSdst != 1);
-			sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSDParm,
+			assert(in->nSdst == 1 || parse->nErr > 0);
+			testcase(in->nSdst != 1);
+			sqlite3ExprCodeMove(parse, in->iSdst, dest->iSDParm,
 					    1);
 			/* The LIMIT clause will jump out of the loop for us */
 			break;
 		}
 		/* The results are stored in a sequence of registers
-		 * starting at pDest->iSdst.  Then the co-routine yields.
+		 * starting at dest->iSdst.  Then the co-routine yields.
 		 */
 	case SRT_Coroutine:{
-			if (pDest->iSdst == 0) {
-				pDest->iSdst =
-				    sqlite3GetTempRange(pParse, pIn->nSdst);
-				pDest->nSdst = pIn->nSdst;
+			if (dest->iSdst == 0) {
+				dest->iSdst =
+				    sqlite3GetTempRange(parse, in->nSdst);
+				dest->nSdst = in->nSdst;
 			}
-			sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSdst,
-					    pIn->nSdst);
-			sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
+			sqlite3ExprCodeMove(parse, in->iSdst, dest->iSdst,
+					    in->nSdst);
+			sqlite3VdbeAddOp1(v, OP_Yield, dest->iSDParm);
 			break;
 		}
 
@@ -2997,11 +2955,11 @@ generateOutputSubroutine(Parse * pParse,	/* Parsing context */
 		 * return the next row of result.
 		 */
 	default:{
-			assert(pDest->eDest == SRT_Output);
-			sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iSdst,
-					  pIn->nSdst);
-			sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst,
-						       pIn->nSdst);
+			assert(dest->eDest == SRT_Output);
+			sqlite3VdbeAddOp2(v, OP_ResultRow, in->iSdst,
+					  in->nSdst);
+			sqlite3ExprCacheAffinityChange(parse, in->iSdst,
+						       in->nSdst);
 			break;
 		}
 	}
@@ -3009,14 +2967,14 @@ generateOutputSubroutine(Parse * pParse,	/* Parsing context */
 	/* Jump to the end of the loop if the LIMIT is reached.
 	 */
 	if (p->iLimit) {
-		sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak);
+		sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, break_addr);
 		VdbeCoverage(v);
 	}
 
 	/* Generate the subroutine return
 	 */
 	sqlite3VdbeResolveLabel(v, iContinue);
-	sqlite3VdbeAddOp1(v, OP_Return, regReturn);
+	sqlite3VdbeAddOp1(v, OP_Return, reg_ret);
 
 	return addr;
 }
@@ -3140,8 +3098,10 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 	int labelEnd;		/* Label for the end of the overall SELECT stmt */
 	int addr1;		/* Jump instructions that get retargetted */
 	int op;			/* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
-	KeyInfo *pKeyDup = 0;	/* Comparison information for duplicate removal */
-	KeyInfo *pKeyMerge;	/* Comparison information for merging rows */
+	/* Comparison information for duplicate removal */
+	struct key_def *def_dup = NULL;
+	/* Comparison information for merging rows */
+	struct key_def *def_merge;
 	sqlite3 *db;		/* Database connection */
 	ExprList *pOrderBy;	/* The ORDER BY clause */
 	int nOrderBy;		/* Number of terms in the ORDER BY clause */
@@ -3150,7 +3110,6 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 	int iSub2;		/* EQP id of right-hand query */
 
 	assert(p->pOrderBy != 0);
-	assert(pKeyDup == 0);	/* "Managed" code needs this.  Ticket #3382. */
 	db = pParse->db;
 	v = pParse->pVdbe;
 	assert(v != 0);		/* Already thrown the error if VDBE alloc failed */
@@ -3195,7 +3154,7 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 		}
 	}
 
-	/* Compute the comparison permutation and keyinfo that is used with
+	/* Compute the comparison permutation and key_def that is used with
 	 * the permutation used to determine if the next
 	 * row of results comes from selectA or selectB.  Also add explicit
 	 * collations to the ORDER BY clause terms so that when the subqueries
@@ -3211,9 +3170,9 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 			assert(pItem->u.x.iOrderByCol <= p->pEList->nExpr);
 			aPermute[i] = pItem->u.x.iOrderByCol - 1;
 		}
-		pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);
+		def_merge = sql_multiselect_orderby_to_key_def(pParse, p, 1);
 	} else {
-		pKeyMerge = 0;
+		def_merge = NULL;
 	}
 
 	/* Reattach the ORDER BY clause to the query.
@@ -3221,27 +3180,30 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 	p->pOrderBy = pOrderBy;
 	pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy, 0);
 
-	/* Allocate a range of temporary registers and the KeyInfo needed
+	/* Allocate a range of temporary registers and the key_def needed
 	 * for the logic that removes duplicate result rows when the
 	 * operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
 	 */
 	if (op == TK_ALL) {
 		regPrev = 0;
 	} else {
-		int nExpr = p->pEList->nExpr;
-		assert(nOrderBy >= nExpr || db->mallocFailed);
+		int expr_count = p->pEList->nExpr;
+		assert(nOrderBy >= expr_count || db->mallocFailed);
 		regPrev = pParse->nMem + 1;
-		pParse->nMem += nExpr + 1;
+		pParse->nMem += expr_count + 1;
 		sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
-		pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);
-		if (pKeyDup) {
-			assert(sqlite3KeyInfoIsWriteable(pKeyDup));
-			for (i = 0; i < nExpr; i++) {
+		def_dup = key_def_new(expr_count);
+		if (def_dup != NULL) {
+			for (int i = 0; i < expr_count; i++) {
 				bool is_found = false;
-				pKeyDup->aColl[i] =
-					multiSelectCollSeq(pParse, p, i,
-							   &is_found);
-				pKeyDup->aSortOrder[i] = 0;
+				struct coll *coll;
+				coll = multiSelectCollSeq(pParse, p, i,
+							  &is_found);
+				key_def_set_part(def_dup, i, i,
+						 FIELD_TYPE_SCALAR,
+						 ON_CONFLICT_ACTION_ABORT,
+						 coll,
+						 SORT_ORDER_ASC);
 			}
 		}
 	}
@@ -3316,7 +3278,7 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 	VdbeNoopComment((v, "Output routine for A"));
 	addrOutA = generateOutputSubroutine(pParse,
 					    p, &destA, pDest, regOutA,
-					    regPrev, pKeyDup, labelEnd);
+					    regPrev, def_dup, labelEnd);
 
 	/* Generate a subroutine that outputs the current row of the B
 	 * select as the next output row of the compound select.
@@ -3325,9 +3287,10 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 		VdbeNoopComment((v, "Output routine for B"));
 		addrOutB = generateOutputSubroutine(pParse,
 						    p, &destB, pDest, regOutB,
-						    regPrev, pKeyDup, labelEnd);
+						    regPrev, def_dup, labelEnd);
 	}
-	sqlite3KeyInfoUnref(pKeyDup);
+
+	key_def_delete(def_dup);
 
 	/* Generate a subroutine to run when the results from select A
 	 * are exhausted and only data in select B remains.
@@ -3407,7 +3370,7 @@ multiSelectOrderBy(Parse * pParse,	/* Parsing context */
 	sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char *)aPermute,
 			  P4_INTARRAY);
 	sqlite3VdbeAddOp4(v, OP_Compare, destA.iSdst, destB.iSdst, nOrderBy,
-			  (char *)pKeyMerge, P4_KEYINFO);
+			  (char *)def_merge, P4_KEYDEF);
 	sqlite3VdbeChangeP5(v, OPFLAG_PERMUTE);
 	sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB);
 	VdbeCoverage(v);
@@ -5140,12 +5103,13 @@ resetAccumulator(Parse * pParse, AggInfo * pAggInfo)
 						"argument");
 				pFunc->iDistinct = -1;
 			} else {
-				KeyInfo *pKeyInfo =
-				    keyInfoFromExprList(pParse, pE->x.pList, 0,
-							0);
+				struct key_def *def;
+				def = sql_expr_list_to_key_def(pParse,
+							       pE->x.pList,
+							       0);
 				sqlite3VdbeAddOp4(v, OP_OpenTEphemeral,
 						  pFunc->iDistinct, 1, 0,
-						  (char *)pKeyInfo, P4_KEYINFO);
+						  (char *)def, P4_KEYDEF);
 			}
 		}
 	}
@@ -5616,23 +5580,22 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 	 * that change.
 	 */
 	if (sSort.pOrderBy) {
-		KeyInfo *pKeyInfo;
-		pKeyInfo =
-		    keyInfoFromExprList(pParse, sSort.pOrderBy, 0, pEList->nExpr);
+		struct key_def *def;
+		def = sql_expr_list_to_key_def(pParse, sSort.pOrderBy, 0);
 		sSort.iECursor = pParse->nTab++;
 		/* Number of columns in transient table equals to number of columns in
 		 * SELECT statement plus number of columns in ORDER BY statement
 		 * and plus one column for ID.
 		 */
 		int nCols = pEList->nExpr + sSort.pOrderBy->nExpr + 1;
-		if (pKeyInfo->aSortOrder[0] == SORT_ORDER_DESC) {
+		if (def->parts[0].sort_order == SORT_ORDER_DESC) {
 			sSort.sortFlags |= SORTFLAG_DESC;
 		}
 		sSort.addrSortIndex =
 		    sqlite3VdbeAddOp4(v, OP_OpenTEphemeral,
 				      sSort.iECursor,
 				      nCols,
-				      0, (char *)pKeyInfo, P4_KEYINFO);
+				      0, (char *)def, P4_KEYDEF);
 		VdbeComment((v, "Sort table"));
 	} else {
 		sSort.addrSortIndex = -1;
@@ -5641,10 +5604,10 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 	/* If the output is destined for a temporary table, open that table.
 	 */
 	if (pDest->eDest == SRT_EphemTab) {
-		KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db,
-							pEList->nExpr + 1, 0);
+		struct key_def *def;
+		def = key_def_new(pEList->nExpr + 1);
 		sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, pDest->iSDParm,
-				  pEList->nExpr + 1, 0, (char*)pKeyInfo, P4_KEYINFO);
+				  pEList->nExpr + 1, 0, (char*)def, P4_KEYDEF);
 
 		VdbeComment((v, "Output table"));
 	}
@@ -5665,12 +5628,12 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 	 */
 	if (p->selFlags & SF_Distinct) {
 		sDistinct.tabTnct = pParse->nTab++;
-		KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, p->pEList, 0, 0);
+		struct key_def *def = sql_expr_list_to_key_def(pParse, p->pEList, 0);
 		sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenTEphemeral,
 						       sDistinct.tabTnct,
-						       pKeyInfo->nField,
-						       0, (char *)pKeyInfo,
-						       P4_KEYINFO);
+						       def->part_count,
+						       0, (char *)def,
+						       P4_KEYDEF);
 		VdbeComment((v, "Distinct table"));
 		sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
 	} else {
@@ -5811,7 +5774,6 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 		 * much more complex than aggregates without a GROUP BY.
 		 */
 		if (pGroupBy) {
-			KeyInfo *pKeyInfo;	/* Keying information for the group by clause */
 			int addr1;	/* A-vs-B comparision jump */
 			int addrOutputRow;	/* Start of subroutine that outputs a result row */
 			int regOutputRow;	/* Return address register for output subroutine */
@@ -5827,14 +5789,12 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 			 * will be converted into a Noop.
 			 */
 			sAggInfo.sortingIdx = pParse->nTab++;
-			pKeyInfo =
-			    keyInfoFromExprList(pParse, pGroupBy, 0,
-						sAggInfo.nColumn);
+			struct key_def *def = sql_expr_list_to_key_def(pParse, pGroupBy, 0);
 			addrSortingIdx =
 			    sqlite3VdbeAddOp4(v, OP_SorterOpen,
 					      sAggInfo.sortingIdx,
 					      sAggInfo.nSortingColumn, 0,
-					      (char *)pKeyInfo, P4_KEYINFO);
+					      (char *)def, P4_KEYDEF);
 
 			/* Initialize memory locations used by GROUP BY aggregate processing
 			 */
@@ -5872,7 +5832,7 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 			if (sqlite3WhereIsOrdered(pWInfo) == pGroupBy->nExpr) {
 				/* The optimizer is able to deliver rows in group by order so
 				 * we do not have to sort.  The OP_OpenEphemeral table will be
-				 * cancelled later because we still need to use the pKeyInfo
+				 * cancelled later because we still need to use the key_def
 				 */
 				groupBySort = 0;
 			} else {
@@ -5982,10 +5942,15 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 							iBMem + j);
 				}
 			}
+			struct key_def *dup_def = key_def_dup(def);
+			if (dup_def == NULL) {
+				db->mallocFailed = 1;
+				goto select_end;
+			}
 			sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem,
 					  pGroupBy->nExpr,
-					  (char *)sqlite3KeyInfoRef(pKeyInfo),
-					  P4_KEYINFO);
+					  (char*)dup_def,
+					  P4_KEYDEF);
 			addr1 = sqlite3VdbeCurrentAddr(v);
 			sqlite3VdbeAddOp3(v, OP_Jump, addr1 + 1, 0, addr1 + 1);
 			VdbeCoverage(v);
@@ -6095,7 +6060,7 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 				 */
 				const int iCsr = pParse->nTab++;	/* Cursor to scan b-tree */
 				Index *pIdx;	/* Iterator variable */
-				KeyInfo *pKeyInfo = 0;	/* Keyinfo for scanned index */
+				struct key_def *def = NULL;
 				Index *pBest;	/* Best index found so far */
 				int iRoot = pTab->tnum;	/* Root page of scanned b-tree */
 
@@ -6105,7 +6070,7 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 				 *
 				 * (2013-10-03) Do not count the entries in a partial index.
 				 *
-				 * In practice the KeyInfo structure will not be used. It is only
+				 * In practice the key_def structure will not be used. It is only
 				 * passed to keep OP_OpenRead happy.
 				 */
 				pBest = sqlite3PrimaryKeyIndex(pTab);
@@ -6121,19 +6086,17 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 						pBest = pIdx;
 					}
 				}
-				if (pBest) {
+				if (pBest != NULL) {
 					iRoot = pBest->tnum;
-					pKeyInfo =
-					    sqlite3KeyInfoOfIndex(pParse, db,
-								  pBest);
+					def = sql_index_key_def(pBest, true);
 				}
 
 				/* Open a read-only cursor, execute the OP_Count, close the cursor. */
 				emit_open_cursor(pParse, iCsr, iRoot);
-				if (pKeyInfo) {
+				if (def != NULL) {
 					sqlite3VdbeChangeP4(v, -1,
-							    (char *)pKeyInfo,
-							    P4_KEYINFO);
+							    (char *)def,
+							    P4_KEYDEF);
 				}
 				sqlite3VdbeAddOp2(v, OP_Count, iCsr,
 						  sAggInfo.aFunc[0].iMem);
@@ -6186,7 +6149,7 @@ sqlite3Select(Parse * pParse,		/* The parser context */
 					assert(db->mallocFailed
 					       || pMinMax != 0);
 					if (!db->mallocFailed) {
-						pMinMax->a[0].sortOrder =
+						pMinMax->a[0].sort_order =
 						    flag !=
 						    WHERE_ORDERBY_MIN ? 1 : 0;
 						pMinMax->a[0].pExpr->op =
diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h
index 2a801a4..7fa8d6f 100644
--- a/src/box/sql/sqliteInt.h
+++ b/src/box/sql/sqliteInt.h
@@ -1462,7 +1462,6 @@ typedef struct IdList IdList;
 typedef struct Index Index;
 typedef struct IndexSample IndexSample;
 typedef struct KeyClass KeyClass;
-typedef struct KeyInfo KeyInfo;
 typedef struct Lookaside Lookaside;
 typedef struct LookasideSlot LookasideSlot;
 typedef struct NameContext NameContext;
@@ -2025,24 +2024,6 @@ struct FKey {
 #define OE_SetDflt  8		/* Set the foreign key value to its default */
 #define OE_Cascade  9		/* Cascade the changes */
 
-/*
- * An instance of the following structure is passed as the first
- * argument to sqlite3VdbeKeyCompare and is used to control the
- * comparison of the two index keys.
- *
- * Note that aSortOrder[] and aColl[] have nField+1 slots.  There
- * are nField slots for the columns of an index.
- */
-struct KeyInfo {
-	u32 nRef;		/* Number of references to this KeyInfo object */
-	u8 enc;			/* Text encoding - one of the SQLITE_UTF* values */
-	u16 nField;		/* Number of key columns in the index */
-	u16 nXField;		/* Number of columns beyond the key columns */
-	sqlite3 *db;		/* The database connection */
-	u8 *aSortOrder;		/* Sort order for each column. */
-	struct coll *aColl[1];	/* Collating sequence for each term of the key */
-};
-
 /*
  * This object holds a record which has been parsed out into individual
  * fields, for the purposes of doing a comparison.
@@ -2057,7 +2038,7 @@ struct KeyInfo {
  * an index b+tree. The goal of the search is to find the entry that
  * is closed to the key described by this object.  This object might hold
  * just a prefix of the key.  The number of fields is given by
- * pKeyInfo->nField.
+ * key_def->part_count.
  *
  * The r1 and r2 fields are the values to return if this key is less than
  * or greater than a key in the btree, respectively.  These are normally
@@ -2067,7 +2048,7 @@ struct KeyInfo {
  * The key comparison functions actually return default_rc when they find
  * an equals comparison.  default_rc can be -1, 0, or +1.  If there are
  * multiple entries in the b-tree with the same key (when only looking
- * at the first pKeyInfo->nFields,) then default_rc can be set to -1 to
+ * at the first key_def->part_count) then default_rc can be set to -1 to
  * cause the search to find the last match, or +1 to cause the search to
  * find the first match.
  *
@@ -2079,7 +2060,8 @@ struct KeyInfo {
  * b-tree.
  */
 struct UnpackedRecord {
-	KeyInfo *pKeyInfo;	/* Collation and sort-order information */
+	/** Collation and sort-order information. */
+	struct key_def* key_def;
 	Mem *aMem;		/* Values */
 	u16 nField;		/* Number of entries in apMem[] */
 	i8 default_rc;		/* Comparison result if keys are equal */
@@ -2456,7 +2438,7 @@ struct ExprList {
 		Expr *pExpr;	/* The list of expressions */
 		char *zName;	/* Token associated with this expression */
 		char *zSpan;	/* Original text of the expression */
-		u8 sortOrder;	/* 1 for DESC or 0 for ASC */
+		enum sort_order sort_order;
 		unsigned done:1;	/* A flag to indicate when processing is finished */
 		unsigned bSpanIsTab:1;	/* zSpan holds DB.TABLE.COLUMN */
 		unsigned reusable:1;	/* Constant expression is reusable */
@@ -2688,12 +2670,12 @@ struct NameContext {
  *
  * addrOpenEphm[] entries contain the address of OP_OpenEphemeral opcodes.
  * These addresses must be stored so that we can go back and fill in
- * the P4_KEYINFO and P2 parameters later.  Neither the KeyInfo nor
+ * the P4_KEYDEF and P2 parameters later.  Neither the key_def nor
  * the number of columns in P2 can be computed at the same time
  * as the OP_OpenEphm instruction is coded because not
  * enough information about the compound query is known at that point.
- * The KeyInfo for addrOpenTran[0] and [1] contains collating sequences
- * for the result set.  The KeyInfo for addrOpenEphm[2] contains collating
+ * The key_def for addrOpenTran[0] and [1] contains collating sequences
+ * for the result set.  The key_def for addrOpenEphm[2] contains collating
  * sequences for the ORDER BY clause.
  */
 struct Select {
@@ -3495,7 +3477,15 @@ Expr *sqlite3ExprFunction(Parse *, ExprList *, Token *);
 void sqlite3ExprAssignVarNumber(Parse *, Expr *, u32);
 ExprList *sqlite3ExprListAppend(Parse *, ExprList *, Expr *);
 ExprList *sqlite3ExprListAppendVector(Parse *, ExprList *, IdList *, Expr *);
-void sqlite3ExprListSetSortOrder(ExprList *, int);
+
+/**
+ * Set the sort order for the last element on the given ExprList.
+ *
+ * @param p Expression list.
+ * @param sort_order Sort order to set.
+ */
+void sqlite3ExprListSetSortOrder(ExprList *, enum sort_order sort_order);
+
 void sqlite3ExprListSetName(Parse *, ExprList *, Token *, int);
 void sqlite3ExprListSetSpan(Parse *, ExprList *, ExprSpan *);
 void sqlite3ExprListDelete(sqlite3 *, ExprList *);
@@ -3527,11 +3517,22 @@ const char *
 index_collation_name(Index *, uint32_t);
 struct coll *
 sql_index_collation(Index *idx, uint32_t column);
-struct coll *
-sql_default_coll();
 bool
 space_is_view(Table *);
 
+/**
+ * Return key_def of provided struct Index. This routine
+ * actually performs key duplication.
+ *
+ * @param idx Pointer to `struct Index` object.
+ * @param is_dup Flag which is set if key_def should be
+ * duplicated.
+ *
+ * @retval Pointer to `struct key_def`.
+ */
+struct key_def*
+sql_index_key_def(struct Index *idx, bool is_dup);
+
 /**
  * Return sort order of given column from index.
  *
@@ -3586,10 +3587,50 @@ void sqlite3SrcListDelete(sqlite3 *, SrcList *);
 Index *sqlite3AllocateIndexObject(sqlite3 *, i16, int, char **);
 bool
 index_is_unique(Index *);
-void sqlite3CreateIndex(Parse *, Token *, SrcList *, ExprList *, int, Token *,
-			Expr *, int, int, u8);
+
+/**
+ * Create a new index for an SQL table.  name is the name of the
+ * index and tbl_name is the name of the table that is to be
+ * indexed.  Both will be NULL for a primary key or an index that
+ * is created to satisfy a UNIQUE constraint.  If tbl_name and
+ * name are NULL, use parse->pNewTable as the table to be indexed.
+ * parse->pNewTable is a table that is currently being
+ * constructed by a CREATE TABLE statement.
+ *
+ * col_list is a list of columns to be indexed.  col_list will be
+ * NULL if this is a primary key or unique-constraint on the most
+ * recent column added to the table currently under construction.
+ *
+ * @param parse All information about this parse.
+ * @param name Index name. May be NULL.
+ * @param tbl_name Table to index. Use pParse->pNewTable ifNULL.
+ * @param col_list A list of columns to be indexed.
+ * @param on_error One of ON_CONFLICT_ACTION_ABORT, _IGNORE,
+ *        _REPLACE, or _NONE.
+ * @param start The CREATE token that begins this statement.
+ * @param pi_where WHERE clause for partial indices.
+ * @param sort_order Sort order of primary key when pList==NULL.
+ * @param if_not_exist Omit error if index already exists.
+ * @param idx_type The index type.
+ */
+void
+sql_create_index(struct Parse *parse, struct Token *token,
+		 struct SrcList *tbl_name, struct ExprList *col_list,
+		 int on_error, struct Token *start, struct Expr *pi_where,
+		 enum sort_order sort_order, bool if_not_exist, u8 idx_type);
+
+/**
+ * This routine will drop an existing named index.  This routine
+ * implements the DROP INDEX statement.
+ *
+ * @param parse_context Current parsing context.
+ * @param index_name_list List containing index name.
+ * @param table_token Token representing table name.
+ * @param if_exists True, if statement contains 'IF EXISTS' clause.
+ */
 void
 sql_drop_index(struct Parse *, struct SrcList *, struct Token *, bool);
+
 int sqlite3Select(Parse *, Select *, SelectDest *);
 Select *sqlite3SelectNew(Parse *, ExprList *, SrcList *, Expr *, ExprList *,
 			 Expr *, ExprList *, u32, Expr *, Expr *);
@@ -3920,7 +3961,17 @@ void sqlite3NestedParse(Parse *, const char *, ...);
 void sqlite3ExpirePreparedStatements(sqlite3 *);
 int sqlite3CodeSubselect(Parse *, Expr *, int);
 void sqlite3SelectPrep(Parse *, Select *, NameContext *);
-void sqlite3SelectWrongNumTermsError(Parse * pParse, Select * p);
+
+/**
+ * Error message for when two or more terms of a compound select
+ * have different size result sets.
+ *
+ * @param parse Parsing context.
+ * @param p Select struct to analyze.
+ */
+void
+sqlite3SelectWrongNumTermsError(struct Parse *parse, struct Select *p);
+
 int sqlite3MatchSpanName(const char *, const char *, const char *);
 int sqlite3ResolveExprNames(NameContext *, Expr *);
 int sqlite3ResolveExprListNames(NameContext *, ExprList *);
@@ -3949,13 +4000,6 @@ void sqlite3RegisterLikeFunctions(sqlite3 *, int);
 int sqlite3IsLikeFunction(sqlite3 *, Expr *, int *, char *);
 void sqlite3SchemaClear(sqlite3 *);
 Schema *sqlite3SchemaCreate(sqlite3 *);
-KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *, int, int);
-void sqlite3KeyInfoUnref(KeyInfo *);
-KeyInfo *sqlite3KeyInfoRef(KeyInfo *);
-KeyInfo *sqlite3KeyInfoOfIndex(Parse *, sqlite3 *, Index *);
-#ifdef SQLITE_DEBUG
-int sqlite3KeyInfoIsWriteable(KeyInfo *);
-#endif
 int sqlite3CreateFunc(sqlite3 *, const char *, int, int, void *,
 		      void (*)(sqlite3_context *, int, sqlite3_value **),
 		      void (*)(sqlite3_context *, int, sqlite3_value **),
diff --git a/src/box/sql/tarantoolInt.h b/src/box/sql/tarantoolInt.h
index 57fc4a1..8fc9dd6 100644
--- a/src/box/sql/tarantoolInt.h
+++ b/src/box/sql/tarantoolInt.h
@@ -98,7 +98,7 @@ int tarantoolSqlite3RenameParentTable(int iTab, const char *zOldParentName,
 
 /* Interface for ephemeral tables. */
 int tarantoolSqlite3EphemeralCreate(BtCursor * pCur, uint32_t filed_count,
-				    struct coll *aColl);
+				    struct key_def *def);
 /**
  * Insert tuple into ephemeral space.
  * In contrast to ordinary spaces, there is no need to create and
@@ -119,12 +119,19 @@ int tarantoolSqlite3EphemeralClearTable(BtCursor * pCur);
 int tarantoolSqlite3EphemeralGetMaxId(BtCursor * pCur, uint32_t fieldno,
 				       uint64_t * max_id);
 
-/* Compare against the index key under a cursor -
- * the key may span non-adjacent fields in a random order,
- * ex: [4]-[1]-[2]
+/**
+ * Performs exactly as extract_key + sqlite3VdbeCompareMsgpack,
+ * only faster.
+ *
+ * @param pCur cursor which point to tuple to compare.
+ * @param pUnpacked Unpacked record to compare with.
+ * @param[out] res Comparison result.
+ *
+ * @retval Error code.
  */
-int tarantoolSqlite3IdxKeyCompare(BtCursor * pCur, UnpackedRecord * pUnpacked,
-				  int *res);
+int
+tarantoolSqlite3IdxKeyCompare(struct BtCursor *cursor,
+			      struct UnpackedRecord *unpacked, int *res);
 
 /**
  * The function assumes the cursor is open on _schema.
diff --git a/src/box/sql/update.c b/src/box/sql/update.c
index f3bd0b7..31d07d5 100644
--- a/src/box/sql/update.c
+++ b/src/box/sql/update.c
@@ -358,12 +358,16 @@ sqlite3Update(Parse * pParse,		/* The parser context */
 	sqlite3VdbeAddOp2(v, OP_Null, 0, iPk);
 
 	if (isView) {
-		KeyInfo *pKeyInfo = sqlite3KeyInfoAlloc(pParse->db, nKey, 0);
+		struct key_def *def = key_def_new(nKey);
+		if (def == NULL) {
+			pParse->db->mallocFailed = 1;
+			goto update_cleanup;
+		}
 		addrOpen = sqlite3VdbeAddOp4(v, OP_OpenTEphemeral, iEph,
-					     nKey, 0, (char*)pKeyInfo, P4_KEYINFO);
+					     nKey, 0, (char*)def, P4_KEYDEF);
 	} else {
 		addrOpen = sqlite3VdbeAddOp2(v, OP_OpenTEphemeral, iEph, nPk);
-		sqlite3VdbeSetP4KeyInfo(pParse, pPk);
+		sql_vdbe_set_p4_key_def(pParse, pPk);
 	}
 
 	pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0,
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index f405ac0..127f320 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -2242,35 +2242,36 @@ case OP_Permutation: {
  * OPFLAG_PERMUTE bit is clear, then register are compared in sequential
  * order.
  *
- * P4 is a KeyInfo structure that defines collating sequences and sort
+ * P4 is a key_def structure that defines collating sequences and sort
  * orders for the comparison.  The permutation applies to registers
- * only.  The KeyInfo elements are used sequentially.
+ * only.  The key_def elements are used sequentially.
  *
  * The comparison is a sort comparison, so NULLs compare equal,
  * NULLs are less than numbers, numbers are less than strings,
  * and strings are less than blobs.
  */
 case OP_Compare: {
-	int n;
-	int i;
 	int p1;
 	int p2;
-	const KeyInfo *pKeyInfo;
 	int idx;
-	struct coll *pColl;    /* Collating sequence to use on this term */
-	int bRev;          /* True for DESCENDING sort order */
 
-	if ((pOp->p5 & OPFLAG_PERMUTE)==0) aPermute = 0;
-	n = pOp->p3;
-	pKeyInfo = pOp->p4.pKeyInfo;
+	if ((pOp->p5 & OPFLAG_PERMUTE) == 0)
+		aPermute = 0;
+
+	int n = pOp->p3;
+
+	assert(pOp->p4type == P4_KEYDEF);
 	assert(n>0);
-	assert(pKeyInfo!=0);
 	p1 = pOp->p1;
 	p2 = pOp->p2;
+
+	struct key_def *def = pOp->p4.key_def;
 #if SQLITE_DEBUG
 	if (aPermute) {
-		int k, mx = 0;
-		for(k=0; k<n; k++) if (aPermute[k]>mx) mx = aPermute[k];
+		int mx = 0;
+		for(uint32_t k = 0; k < (uint32_t)n; k++)
+			if (aPermute[k] > mx)
+				mx = aPermute[k];
 		assert(p1>0 && p1+mx<=(p->nMem+1 - p->nCursor)+1);
 		assert(p2>0 && p2+mx<=(p->nMem+1 - p->nCursor)+1);
 	} else {
@@ -2278,18 +2279,19 @@ case OP_Compare: {
 		assert(p2>0 && p2+n<=(p->nMem+1 - p->nCursor)+1);
 	}
 #endif /* SQLITE_DEBUG */
-	for(i=0; i<n; i++) {
+	for(int i = 0; i < n; i++) {
 		idx = aPermute ? aPermute[i] : i;
 		assert(memIsValid(&aMem[p1+idx]));
 		assert(memIsValid(&aMem[p2+idx]));
 		REGISTER_TRACE(p1+idx, &aMem[p1+idx]);
 		REGISTER_TRACE(p2+idx, &aMem[p2+idx]);
-		assert(i<pKeyInfo->nField);
-		pColl = pKeyInfo->aColl[i];
-		bRev = pKeyInfo->aSortOrder[i];
-		iCompare = sqlite3MemCompare(&aMem[p1+idx], &aMem[p2+idx], pColl);
+		assert(i < (int)def->part_count);
+		struct coll *coll = def->parts[i].coll;
+		bool is_rev = def->parts[i].sort_order == SORT_ORDER_DESC;
+		iCompare = sqlite3MemCompare(&aMem[p1+idx], &aMem[p2+idx], coll);
 		if (iCompare) {
-			if (bRev) iCompare = -iCompare;
+			if (is_rev)
+				iCompare = -iCompare;
 			break;
 		}
 	}
@@ -3118,8 +3120,8 @@ case OP_SetCookie: {
  * values need not be contiguous but all P1 values should be
  * small integers. It is an error for P1 to be negative.
  *
- * The P4 value may be a pointer to a KeyInfo structure.
- * If it is a pointer to a KeyInfo structure, then said structure
+ * The P4 value may be a pointer to a key_def structure.
+ * If it is a pointer to a key_def structure, then said structure
  * defines the content and collatining sequence of the index
  * being opened. Otherwise, P4 is NULL.
  *
@@ -3207,7 +3209,7 @@ case OP_OpenWrite:
 	pBtCur->index = index;
 	pBtCur->eState = CURSOR_INVALID;
 	/* Key info still contains sorter order and collation. */
-	pCur->pKeyInfo = pOp->p4.pKeyInfo;
+	pCur->key_def = index->def->key_def;
 
 open_cursor_set_hints:
 	assert(OPFLAG_BULKCSR==BTREE_BULKLOAD);
@@ -3222,8 +3224,12 @@ open_cursor_set_hints:
 	break;
 }
 
-/* Opcode: OpenTEphemeral P1 P2 * * *
- * Synopsis: nColumn = P2
+/**
+ * Opcode: OpenTEphemeral P1 P2 * P4 *
+ * Synopsis:
+ * @param P1 index of new cursor to be created
+ * @param P2 number of columns in a new table
+ * @param P4 key def for new table
  *
  * This opcode creates Tarantool's ephemeral table and sets cursor P1 to it.
  */
@@ -3232,21 +3238,21 @@ case OP_OpenTEphemeral: {
 	BtCursor *pBtCur;
 	assert(pOp->p1 >= 0);
 	assert(pOp->p2 > 0);
-	assert(pOp->p4.pKeyInfo != 0);
-	assert(pOp->p4type == P4_KEYINFO);
+	assert(pOp->p4.key_def != NULL);
+	assert(pOp->p4type == P4_KEYDEF);
 
 	pCx = allocateCursor(p, pOp->p1, pOp->p2, CURTYPE_TARANTOOL);
 	if (pCx == 0) goto no_mem;
 	pCx->nullRow = 1;
 
-	pCx->pKeyInfo  = pOp->p4.pKeyInfo;
+	pCx->key_def  = pOp->p4.key_def;
 	pBtCur = pCx->uc.pCursor;
 	/* Ephemeral spaces don't have space_id */
 	pBtCur->eState = CURSOR_INVALID;
 	pBtCur->curFlags = BTCF_TEphemCursor;
 
 	rc = tarantoolSqlite3EphemeralCreate(pCx->uc.pCursor, pOp->p2,
-					     pOp->p4.pKeyInfo->aColl[0]);
+					     pCx->key_def);
 	if (rc) goto abort_due_to_error;
 	break;
 }
@@ -3268,9 +3274,8 @@ case OP_SorterOpen: {
 	assert(pOp->p2>=0);
 	pCx = allocateCursor(p, pOp->p1, pOp->p2, CURTYPE_SORTER);
 	if (pCx==0) goto no_mem;
-	pCx->pKeyInfo = pOp->p4.pKeyInfo;
-	assert(pCx->pKeyInfo->db==db);
-	rc = sqlite3VdbeSorterInit(db, pOp->p3, pCx);
+	pCx->key_def = pOp->p4.key_def;
+	rc = sqlite3VdbeSorterInit(db, pCx);
 	if (rc) goto abort_due_to_error;
 	break;
 }
@@ -3546,7 +3551,7 @@ case OP_SeekGT: {       /* jump, in3 */
 	nField = pOp->p4.i;
 	assert(pOp->p4type==P4_INT32);
 	assert(nField>0);
-	r.pKeyInfo = pC->pKeyInfo;
+	r.key_def = pC->key_def;
 	r.nField = (u16)nField;
 
 	if (reg_ipk > 0) {
@@ -3698,7 +3703,7 @@ case OP_Found: {        /* jump, in3 */
 	assert(pC->eCurType==CURTYPE_TARANTOOL);
 	assert(pC->uc.pCursor!=0);
 	if (pOp->p4.i>0) {
-		r.pKeyInfo = pC->pKeyInfo;
+		r.key_def = pC->key_def;
 		r.nField = (u16)pOp->p4.i;
 		r.aMem = pIn3;
 #ifdef SQLITE_DEBUG
@@ -3711,11 +3716,12 @@ case OP_Found: {        /* jump, in3 */
 		pIdxKey = &r;
 		pFree = 0;
 	} else {
-		pFree = pIdxKey = sqlite3VdbeAllocUnpackedRecord(pC->pKeyInfo);
+		pFree = pIdxKey = sqlite3VdbeAllocUnpackedRecord(db, pC->key_def);
 		if (pIdxKey==0) goto no_mem;
 		assert(pIn3->flags & MEM_Blob );
 		(void)ExpandBlob(pIn3);
-		sqlite3VdbeRecordUnpackMsgpack(pC->pKeyInfo, pIn3->n, pIn3->z, pIdxKey);
+		sqlite3VdbeRecordUnpackMsgpack(pC->key_def,
+					       pIn3->z, pIdxKey);
 	}
 	pIdxKey->default_rc = 0;
 	pIdxKey->opcode = pOp->opcode;
@@ -4491,7 +4497,7 @@ case OP_IdxDelete: {
 	pCrsr = pC->uc.pCursor;
 	assert(pCrsr!=0);
 	assert(pOp->p5==0);
-	r.pKeyInfo = pC->pKeyInfo;
+	r.key_def = pC->key_def;
 	r.nField = (u16)pOp->p3;
 	r.default_rc = 0;
 	r.aMem = &aMem[pOp->p2];
@@ -4575,7 +4581,7 @@ case OP_IdxGE:  {       /* jump */
 	assert(pC->deferredMoveto==0);
 	assert(pOp->p5==0 || pOp->p5==1);
 	assert(pOp->p4type==P4_INT32);
-	r.pKeyInfo = pC->pKeyInfo;
+	r.key_def = pC->key_def;
 	r.nField = (u16)pOp->p4.i;
 	if (pOp->opcode<OP_IdxLT) {
 		assert(pOp->opcode==OP_IdxLE || pOp->opcode==OP_IdxGT);
@@ -4589,7 +4595,7 @@ case OP_IdxGE:  {       /* jump */
 	{ int i; for(i=0; i<r.nField; i++) assert(memIsValid(&r.aMem[i])); }
 #endif
 	res = 0;  /* Not needed.  Only used to silence a warning. */
-	rc = sqlite3VdbeIdxKeyCompare(db, pC, &r, &res);
+	rc = sqlite3VdbeIdxKeyCompare(pC, &r, &res);
 	assert((OP_IdxLE&1)==(OP_IdxLT&1) && (OP_IdxGE&1)==(OP_IdxGT&1));
 	if ((pOp->opcode&1)==(OP_IdxLT&1)) {
 		assert(pOp->opcode==OP_IdxLE || pOp->opcode==OP_IdxLT);
diff --git a/src/box/sql/vdbe.h b/src/box/sql/vdbe.h
index d1f416b..e9ef693 100644
--- a/src/box/sql/vdbe.h
+++ b/src/box/sql/vdbe.h
@@ -77,7 +77,6 @@ struct VdbeOp {
 		struct coll *pColl;	/* Used when p4type is P4_COLLSEQ */
 		Mem *pMem;	/* Used when p4type is P4_MEM */
 		bool b;         /* Used when p4type is P4_BOOL */
-		KeyInfo *pKeyInfo;	/* Used when p4type is P4_KEYINFO */
 		int *ai;	/* Used when p4type is P4_INTARRAY */
 		SubProgram *pProgram;	/* Used when p4type is P4_SUBPROGRAM */
 		Index *pIndex;	/* Used when p4type is P4_INDEX */
@@ -85,6 +84,8 @@ struct VdbeOp {
 		Expr *pExpr;	/* Used when p4type is P4_EXPR */
 #endif
 		int (*xAdvance) (BtCursor *, int *);
+		/* Used when p4type is P4_KEYDEF. */
+		struct key_def *key_def;
 	} p4;
 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
 	char *zComment;		/* Comment to improve readability */
@@ -131,7 +132,6 @@ typedef struct VdbeOpList VdbeOpList;
 #define P4_STATIC   (-2)	/* Pointer to a static string */
 #define P4_COLLSEQ  (-3)	/* P4 is a pointer to a CollSeq structure */
 #define P4_FUNCDEF  (-4)	/* P4 is a pointer to a FuncDef structure */
-#define P4_KEYINFO  (-5)	/* P4 is a pointer to a KeyInfo structure */
 #define P4_EXPR     (-6)	/* P4 is a pointer to an Expr tree */
 #define P4_MEM      (-7)	/* P4 is a pointer to a Mem*    structure */
 #define P4_TRANSIENT  0		/* P4 is a pointer to a transient string */
@@ -147,7 +147,6 @@ typedef struct VdbeOpList VdbeOpList;
 #define P4_PTR      (-18)	/* P4 is a generic pointer */
 #define P4_KEYDEF   (-19)       /* P4 is a pointer to key_def structure. */
 
-
 /* Error message codes for OP_Halt */
 #define P5_ConstraintNotNull 1
 #define P5_ConstraintUnique  2
@@ -249,7 +248,16 @@ int sqlite3VdbeChangeToNoop(Vdbe *, int addr);
 int sqlite3VdbeDeletePriorOpcode(Vdbe *, u8 op);
 void sqlite3VdbeChangeP4(Vdbe *, int addr, const char *zP4, int N);
 void sqlite3VdbeAppendP4(Vdbe *, void *pP4, int p4type);
-void sqlite3VdbeSetP4KeyInfo(Parse *, Index *);
+
+/**
+ * Set the P4 on the most recently added opcode to the key_def for the
+ * index given.
+ * @param Parse context, for error reporting.
+ * @param Index to get key_def from.
+ */
+void
+sql_vdbe_set_p4_key_def(struct Parse *parse, struct Index *index);
+
 VdbeOp *sqlite3VdbeGetOp(Vdbe *, int);
 int sqlite3VdbeMakeLabel(Vdbe *);
 void sqlite3VdbeRunOnlyOnce(Vdbe *);
@@ -280,14 +288,27 @@ char *sqlite3VdbeExpandSql(Vdbe *, const char *);
 #endif
 int sqlite3MemCompare(const Mem *, const Mem *, const struct coll *);
 
-void sqlite3VdbeRecordUnpackMsgpack(KeyInfo *, int, const void *,
-				    UnpackedRecord *);
-int sqlite3VdbeRecordCompare(int, const void *, UnpackedRecord *);
-int sqlite3VdbeRecordCompareWithSkip(int, const void *, UnpackedRecord *, int);
-UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *);
+/**
+ * Perform unpacking of provided message pack.
+ *
+ * @param key_def Information about the record format
+ * @param key The binary record
+ * @param dest Populate this structure before returning.
+ */
+void sqlite3VdbeRecordUnpackMsgpack(struct key_def *key_def,
+				    const void *msgpack,
+				    struct UnpackedRecord *dest);
+
+int sqlite3VdbeRecordCompare(struct sqlite3 *db, int key_count,
+			     const void *key1, UnpackedRecord *key2);
+int sqlite3VdbeRecordCompareWithSkip(struct sqlite3 *db,
+				     int key_count, const void *key1,
+				     struct UnpackedRecord *key2, bool is_skip);
+UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(struct sqlite3 *,
+					       struct key_def *);
 int sql_vdbe_mem_alloc_region(Mem *, uint32_t);
 
-typedef int (*RecordCompare) (int, const void *, UnpackedRecord *);
+typedef int (*RecordCompare) (const void *, UnpackedRecord *);
 RecordCompare sqlite3VdbeFindCompare(UnpackedRecord *);
 
 #ifndef SQLITE_OMIT_TRIGGER
diff --git a/src/box/sql/vdbeInt.h b/src/box/sql/vdbeInt.h
index 3a907cd..9779654 100644
--- a/src/box/sql/vdbeInt.h
+++ b/src/box/sql/vdbeInt.h
@@ -110,7 +110,8 @@ struct VdbeCursor {
 		int pseudoTableReg;	/* CURTYPE_PSEUDO. Reg holding content. */
 		VdbeSorter *pSorter;	/* CURTYPE_SORTER. Sorter object */
 	} uc;
-	KeyInfo *pKeyInfo;	/* Info about index keys needed by index cursors */
+	/* Info about keys needed by index cursors. */
+	struct key_def *key_def;
 	i16 nField;		/* Number of fields in the header */
 	u16 nHdrParsed;		/* Number of header fields parsed so far */
 	const u8 *aRow;		/* Data for the current row, if all on one page */
@@ -430,7 +431,6 @@ struct PreUpdate {
 	VdbeCursor *pCsr;	/* Cursor to read old values from */
 	int op;			/* One of SQLITE_INSERT, UPDATE, DELETE */
 	u8 *aRecord;		/* old.* database record */
-	KeyInfo keyinfo;
 	UnpackedRecord *pUnpacked;	/* Unpacked version of aRecord[] */
 	UnpackedRecord *pNewUnpacked;	/* Unpacked version of new.* record */
 	int iNewReg;		/* Register for new.* values */
@@ -458,7 +458,24 @@ u32 sqlite3VdbeSerialPut(unsigned char *, Mem *, u32);
 u32 sqlite3VdbeSerialGet(const unsigned char *, u32, Mem *);
 void sqlite3VdbeDeleteAuxData(sqlite3 *, AuxData **, int, int);
 
-int sqlite3VdbeIdxKeyCompare(sqlite3 *, VdbeCursor *, UnpackedRecord *, int *);
+/**
+ * Compare the key of the index entry that cursor vdbe_cursor is
+ * pointing to against the key string in unpacked.  Write into
+ * *res a number that is negative, zero, or positive if
+ * vdbe_cursor is less than, equal to, or greater than unpacked.
+ * Return SQLITE_OK on success.
+ *
+ * @param vdbe_cursor Cursor, which points to tuple to compare.
+ * @param unpacked Unpacked version of key.
+ * @param[out] Write the comparison result here.
+ *
+ * @retval Error status code.
+ */
+int
+sqlite3VdbeIdxKeyCompare(struct VdbeCursor *vdbe_cursor,
+			 struct UnpackedRecord *unpacked,
+			 int * res);
+
 int sqlite3VdbeExec(Vdbe *);
 int sqlite3VdbeList(Vdbe *);
 int
@@ -500,13 +517,9 @@ int sqlite3VdbeMemClearAndResize(Mem * pMem, int n);
 int sqlite3VdbeCloseStatement(Vdbe *, int);
 void sqlite3VdbeFrameDelete(VdbeFrame *);
 int sqlite3VdbeFrameRestore(VdbeFrame *);
-#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
-void sqlite3VdbePreUpdateHook(Vdbe *, VdbeCursor *, int, const char *, Table *,
-			      i64, int);
-#endif
 int sqlite3VdbeTransferError(Vdbe * p);
 
-int sqlite3VdbeSorterInit(sqlite3 *, int, VdbeCursor *);
+int sqlite3VdbeSorterInit(struct sqlite3 *db, struct VdbeCursor *cursor);
 void sqlite3VdbeSorterReset(sqlite3 *, VdbeSorter *);
 void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);
 int sqlite3VdbeSorterRowkey(const VdbeCursor *, Mem *);
@@ -543,10 +556,28 @@ int sqlite3VdbeMemExpandBlob(Mem *);
 
 i64 sqlite3VdbeMsgpackRecordLen(Mem * pMem, u32 n);
 u32 sqlite3VdbeMsgpackRecordPut(u8 * pBuf, Mem * pMem, u32 n);
-int sqlite3VdbeCompareMsgpack(const char **pKey1,
-			      UnpackedRecord * pUnpacked, int iKey2);
-int sqlite3VdbeRecordCompareMsgpack(int nKey1, const void *pKey1,
-				    UnpackedRecord * pPKey2);
+/**
+ * Perform comparison of two keys: one is packed and one is not.
+ *
+ * @param key1 Pointer to pointer to first key.
+ * @param unpacked Pointer to unpacked tuple.
+ * @param key2_idx index of key in umpacked record to compare.
+ *
+ * @retval +1 if key1 > pUnpacked[iKey2], -1 ptherwise.
+ */
+int sqlite3VdbeCompareMsgpack(const char **key1,
+			      struct UnpackedRecord *unpacked, int key2_idx);
+
+/**
+ * Perform comparison of two tuples: unpacked (key1) and packed (key2)
+ *
+ * @param key1 Packed key.
+ * @param unpacked Unpacked key.
+ *
+ * @retval +1 if key1 > unpacked, -1 otherwise.
+ */
+int sqlite3VdbeRecordCompareMsgpack(const void *key1,
+				    struct UnpackedRecord *key2);
 u32 sqlite3VdbeMsgpackGet(const unsigned char *buf, Mem * pMem);
 
 #endif				/* !defined(SQLITE_VDBEINT_H) */
diff --git a/src/box/sql/vdbeapi.c b/src/box/sql/vdbeapi.c
index 32af463..d35338a 100644
--- a/src/box/sql/vdbeapi.c
+++ b/src/box/sql/vdbeapi.c
@@ -1577,103 +1577,6 @@ sqlite3_expanded_sql(sqlite3_stmt * pStmt)
 #endif
 }
 
-#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
-/*
- * Allocate and populate an UnpackedRecord structure based on the serialized
- * record in nKey/pKey. Return a pointer to the new UnpackedRecord structure
- * if successful, or a NULL pointer if an OOM error is encountered.
- */
-static UnpackedRecord *
-vdbeUnpackRecord(KeyInfo * pKeyInfo, int nKey, const void *pKey)
-{
-	UnpackedRecord *pRet;	/* Return value */
-
-	pRet = sqlite3VdbeAllocUnpackedRecord(pKeyInfo);
-	if (pRet) {
-		memset(pRet->aMem, 0, sizeof(Mem) * (pKeyInfo->nField + 1));
-		sqlite3VdbeRecordUnpack(pKeyInfo, nKey, pKey, pRet);
-	}
-	return pRet;
-}
-
-/*
- * This function is called from within a pre-update callback to retrieve
- * a field of the row currently being updated or deleted.
- */
-int
-sqlite3_preupdate_old(sqlite3 * db, int iIdx, sqlite3_value ** ppValue)
-{
-	PreUpdate *p = db->pPreUpdate;
-	int rc = SQLITE_OK;
-
-	/* Test that this call is being made from within an SQLITE_DELETE or
-	 * SQLITE_UPDATE pre-update callback, and that iIdx is within range.
-	 */
-	if (!p || p->op == SQLITE_INSERT) {
-		rc = SQLITE_MISUSE_BKPT;
-		goto preupdate_old_out;
-	}
-	if (iIdx >= p->pCsr->nField || iIdx < 0) {
-		rc = SQLITE_RANGE;
-		goto preupdate_old_out;
-	}
-
-	/* If the old.* record has not yet been loaded into memory, do so now. */
-	if (p->pUnpacked == 0) {
-		u32 nRec;
-		u8 *aRec;
-
-		nRec = sqlite3BtreePayloadSize(p->pCsr->uc.pCursor);
-		aRec = sqlite3DbMallocRaw(db, nRec);
-		if (!aRec)
-			goto preupdate_old_out;
-		rc = sqlite3BtreePayload(p->pCsr->uc.pCursor, 0, nRec, aRec);
-		if (rc == SQLITE_OK) {
-			p->pUnpacked =
-			    vdbeUnpackRecord(&p->keyinfo, nRec, aRec);
-			if (!p->pUnpacked)
-				rc = SQLITE_NOMEM;
-		}
-		if (rc != SQLITE_OK) {
-			sqlite3DbFree(db, aRec);
-			goto preupdate_old_out;
-		}
-		p->aRecord = aRec;
-	}
-
-	if (iIdx >= p->pUnpacked->nField) {
-		*ppValue = (sqlite3_value *) columnNullValue();
-	} else {
-		Mem *pMem = *ppValue = &p->pUnpacked->aMem[iIdx];
-		*ppValue = &p->pUnpacked->aMem[iIdx];
-		if (iIdx == p->pTab->iPKey) {
-			sqlite3VdbeMemSetInt64(pMem, p->iKey1);
-		} else if (p->pTab->aCol[iIdx].affinity == SQLITE_AFF_REAL) {
-			if (pMem->flags & MEM_Int) {
-				sqlite3VdbeMemRealify(pMem);
-			}
-		}
-	}
-
- preupdate_old_out:
-	sqlite3Error(db, rc);
-	return sqlite3ApiExit(db, rc);
-}
-#endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
-
-#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
-/*
- * This function is called from within a pre-update callback to retrieve
- * the number of columns in the row being updated, deleted or inserted.
- */
-int
-sqlite3_preupdate_count(sqlite3 * db)
-{
-	PreUpdate *p = db->pPreUpdate;
-	return (p ? p->keyinfo.nField : 0);
-}
-#endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
-
 #ifdef SQLITE_ENABLE_PREUPDATE_HOOK
 /*
  * This function is designed to be called from within a pre-update callback
@@ -1694,92 +1597,6 @@ sqlite3_preupdate_depth(sqlite3 * db)
 }
 #endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
 
-#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
-/*
- * This function is called from within a pre-update callback to retrieve
- * a field of the row currently being updated or inserted.
- */
-int
-sqlite3_preupdate_new(sqlite3 * db, int iIdx, sqlite3_value ** ppValue)
-{
-	PreUpdate *p = db->pPreUpdate;
-	int rc = SQLITE_OK;
-	Mem *pMem;
-
-	if (!p || p->op == SQLITE_DELETE) {
-		rc = SQLITE_MISUSE_BKPT;
-		goto preupdate_new_out;
-	}
-	if (iIdx >= p->pCsr->nField || iIdx < 0) {
-		rc = SQLITE_RANGE;
-		goto preupdate_new_out;
-	}
-
-	if (p->op == SQLITE_INSERT) {
-		/* For an INSERT, memory cell p->iNewReg contains the serialized record
-		 * that is being inserted. Deserialize it.
-		 */
-		UnpackedRecord *pUnpack = p->pNewUnpacked;
-		if (!pUnpack) {
-			Mem *pData = &p->v->aMem[p->iNewReg];
-			rc = ExpandBlob(pData);
-			if (rc != SQLITE_OK)
-				goto preupdate_new_out;
-			pUnpack =
-			    vdbeUnpackRecord(&p->keyinfo, pData->n, pData->z);
-			if (!pUnpack) {
-				rc = SQLITE_NOMEM;
-				goto preupdate_new_out;
-			}
-			p->pNewUnpacked = pUnpack;
-		}
-		if (iIdx >= pUnpack->nField) {
-			pMem = (sqlite3_value *) columnNullValue();
-		} else {
-			pMem = &pUnpack->aMem[iIdx];
-			if (iIdx == p->pTab->iPKey) {
-				sqlite3VdbeMemSetInt64(pMem, p->iKey2);
-			}
-		}
-	} else {
-		/* For an UPDATE, memory cell (p->iNewReg+1+iIdx) contains the required
-		 * value. Make a copy of the cell contents and return a pointer to it.
-		 * It is not safe to return a pointer to the memory cell itself as the
-		 * caller may modify the value text encoding.
-		 */
-		assert(p->op == SQLITE_UPDATE);
-		if (!p->aNew) {
-			p->aNew =
-			    (Mem *) sqlite3DbMallocZero(db,
-							sizeof(Mem) *
-							p->pCsr->nField);
-			if (!p->aNew) {
-				rc = SQLITE_NOMEM;
-				goto preupdate_new_out;
-			}
-		}
-		assert(iIdx >= 0 && iIdx < p->pCsr->nField);
-		pMem = &p->aNew[iIdx];
-		if (pMem->flags == 0) {
-			if (iIdx == p->pTab->iPKey) {
-				sqlite3VdbeMemSetInt64(pMem, p->iKey2);
-			} else {
-				rc = sqlite3VdbeMemCopy(pMem,
-							&p->v->aMem[p->iNewReg +
-								    1 + iIdx]);
-				if (rc != SQLITE_OK)
-					goto preupdate_new_out;
-			}
-		}
-	}
-	*ppValue = pMem;
-
- preupdate_new_out:
-	sqlite3Error(db, rc);
-	return sqlite3ApiExit(db, rc);
-}
-#endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
-
 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
 /*
  * Return status data for a single loop within query pStmt.
diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c
index ead9659..1fb609b 100644
--- a/src/box/sql/vdbeaux.c
+++ b/src/box/sql/vdbeaux.c
@@ -978,11 +978,9 @@ freeP4(sqlite3 * db, int p4type, void *p4)
 			sqlite3DbFree(db, p4);
 			break;
 		}
-	case P4_KEYINFO:{
-			if (db->pnBytesFreed == 0)
-				sqlite3KeyInfoUnref((KeyInfo *) p4);
-			break;
-		}
+	case P4_KEYDEF:
+		key_def_delete(p4);
+		break;
 #ifdef SQLITE_ENABLE_CURSOR_HINTS
 	case P4_EXPR:{
 			sqlite3ExprDelete(db, (Expr *) p4);
@@ -1170,20 +1168,19 @@ sqlite3VdbeAppendP4(Vdbe * p, void *pP4, int n)
 	}
 }
 
-/*
- * Set the P4 on the most recently added opcode to the KeyInfo for the
- * index given.
- */
 void
-sqlite3VdbeSetP4KeyInfo(Parse * pParse, Index * pIdx)
-{
-	Vdbe *v = pParse->pVdbe;
-	KeyInfo *pKeyInfo;
-	assert(v != 0);
-	assert(pIdx != 0);
-	pKeyInfo = sqlite3KeyInfoOfIndex(pParse, pParse->db, pIdx);
-	if (pKeyInfo)
-		sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
+sql_vdbe_set_p4_key_def(struct Parse *parse, struct Index *idx)
+{
+	struct Vdbe *v = parse->pVdbe;
+	assert(v != NULL);
+	assert(idx != NULL);
+	uint32_t space_id = SQLITE_PAGENO_TO_SPACEID(idx->tnum);
+	uint32_t index_id = SQLITE_PAGENO_TO_INDEXID(idx->tnum);
+	struct space *space = space_by_id(space_id);
+	assert(space != NULL);
+	struct index *index = index_find(space, index_id);
+	assert(index != NULL);
+	sqlite3VdbeAppendP4(v, key_def_dup(index->def->key_def), P4_KEYDEF);
 }
 
 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
@@ -1542,26 +1539,28 @@ displayP4(Op * pOp, char *zTemp, int nTemp)
 	assert(nTemp >= 20);
 	sqlite3StrAccumInit(&x, 0, zTemp, nTemp, 0);
 	switch (pOp->p4type) {
-	case P4_KEYINFO:{
-			int j;
-			KeyInfo *pKeyInfo;
+	case P4_KEYDEF:{
+			struct key_def *def;
 
-			if (pOp->p4.pKeyInfo == NULL) {
+			if (pOp->p4.key_def == NULL) {
 				sqlite3XPrintf(&x, "k[NULL]");
 			} else {
-				pKeyInfo = pOp->p4.pKeyInfo;
-				assert(pKeyInfo->aSortOrder != 0);
-				sqlite3XPrintf(&x, "k(%d", pKeyInfo->nField);
-				for (j = 0; j < pKeyInfo->nField; j++) {
-					struct coll *pColl = pKeyInfo->aColl[j];
-					const char *zColl =
-					    pColl ? pColl->name : "";
-					if (strcmp(zColl, "BINARY") == 0)
-						zColl = "B";
+				def = pOp->p4.key_def;
+				sqlite3XPrintf(&x, "k(%d", def->part_count);
+				for (int j = 0; j < (int)def->part_count; j++) {
+					struct coll *coll = def->parts[j].coll;
+					const char *coll_str =
+					    coll != NULL ? coll->name : "";
+					if (strcmp(coll_str, "BINARY") == 0)
+						coll_str = "B";
+					const char *sort_order = "";
+					if (def->parts[j].sort_order ==
+					    SORT_ORDER_DESC) {
+						sort_order = "-";
+					}
 					sqlite3XPrintf(&x, ",%s%s",
-						       pKeyInfo->
-						       aSortOrder[j] ? "-" : "",
-						       zColl);
+						       sort_order,
+						       coll_str);
 				}
 				sqlite3StrAccumAppend(&x, ")", 1);
 			}
@@ -3506,7 +3505,7 @@ sqlite3VdbeSerialGet(const unsigned char *buf,	/* Buffer to deserialize from */
 /*
  * This routine is used to allocate sufficient space for an UnpackedRecord
  * structure large enough to be used with sqlite3VdbeRecordUnpack() if
- * the first argument is a pointer to KeyInfo structure pKeyInfo.
+ * the first argument is a pointer to key_def structure.
  *
  * The space is either allocated using sqlite3DbMallocRaw() or from within
  * the unaligned buffer passed via the second and third arguments (presumably
@@ -3518,20 +3517,19 @@ sqlite3VdbeSerialGet(const unsigned char *buf,	/* Buffer to deserialize from */
  * If an OOM error occurs, NULL is returned.
  */
 UnpackedRecord *
-sqlite3VdbeAllocUnpackedRecord(KeyInfo * pKeyInfo)
+sqlite3VdbeAllocUnpackedRecord(struct sqlite3 *db, struct key_def *key_def)
 {
 	UnpackedRecord *p;	/* Unpacked record to return */
 	int nByte;		/* Number of bytes required for *p */
 	nByte =
-	    ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem) * (pKeyInfo->nField +
+	    ROUND8(sizeof(UnpackedRecord)) + sizeof(Mem) * (key_def->part_count +
 							    1);
-	p = (UnpackedRecord *) sqlite3DbMallocRaw(pKeyInfo->db, nByte);
+	p = (UnpackedRecord *) sqlite3DbMallocRaw(db, nByte);
 	if (!p)
 		return 0;
 	p->aMem = (Mem *) & ((char *)p)[ROUND8(sizeof(UnpackedRecord))];
-	assert(pKeyInfo->aSortOrder != 0);
-	p->pKeyInfo = pKeyInfo;
-	p->nField = pKeyInfo->nField + 1;
+	p->key_def = key_def;
+	p->nField = key_def->part_count + 1;
 	return p;
 }
 
@@ -3560,7 +3558,8 @@ sql_vdbe_mem_alloc_region(Mem *vdbe_mem, uint32_t size)
  * Return false if there is a disagreement.
  */
 static int
-vdbeRecordCompareDebug(int nKey1, const void *pKey1,	/* Left key */
+vdbeRecordCompareDebug(struct sqlite3 *db,
+		       int nKey1, const void *pKey1,	/* Left key */
 		       const UnpackedRecord * pPKey2,	/* Right key */
 		       int desiredResult)		/* Correct answer */
 {
@@ -3570,13 +3569,11 @@ vdbeRecordCompareDebug(int nKey1, const void *pKey1,	/* Left key */
 	int i = 0;
 	int rc = 0;
 	const unsigned char *aKey1 = (const unsigned char *)pKey1;
-	KeyInfo *pKeyInfo;
+	struct key_def *key_def;
 	Mem mem1;
 
-	pKeyInfo = pPKey2->pKeyInfo;
-	if (pKeyInfo->db == 0)
-		return 1;
-	mem1.db = pKeyInfo->db;
+	key_def = pPKey2->key_def;
+	mem1.db = db;
 	/* mem1.flags = 0;  // Will be initialized by sqlite3VdbeSerialGet() */
 	VVA_ONLY(mem1.szMalloc = 0;
 	    )
@@ -3594,10 +3591,7 @@ vdbeRecordCompareDebug(int nKey1, const void *pKey1,	/* Left key */
 	if (szHdr1 > 98307)
 		return SQLITE_CORRUPT;
 	d1 = szHdr1;
-	assert(pKeyInfo->nField + pKeyInfo->nXField >= pPKey2->nField
-	       || CORRUPT_DB);
-	assert(pKeyInfo->aSortOrder != 0);
-	assert(pKeyInfo->nField > 0);
+	assert(key_def->part_count > 0);
 	assert(idx1 <= szHdr1 || CORRUPT_DB);
 	do {
 		u32 serial_type1;
@@ -3624,10 +3618,10 @@ vdbeRecordCompareDebug(int nKey1, const void *pKey1,	/* Left key */
 		/* Do the comparison
 		 */
 		rc = sqlite3MemCompare(&mem1, &pPKey2->aMem[i],
-				       pKeyInfo->aColl[i]);
+				       key_def->parts[i].coll);
 		if (rc != 0) {
 			assert(mem1.szMalloc == 0);	/* See comment below */
-			if (pKeyInfo->aSortOrder[i]) {
+			if (key_def->parts[i].sort_order != SORT_ORDER_ASC) {
 				rc = -rc;	/* Invert the result for DESC sort order. */
 			}
 			goto debugCompareEnd;
@@ -3656,7 +3650,7 @@ vdbeRecordCompareDebug(int nKey1, const void *pKey1,	/* Left key */
 		return 1;
 	if (CORRUPT_DB)
 		return 1;
-	if (pKeyInfo->db->mallocFailed)
+	if (db->mallocFailed)
 		return 1;
 	return 0;
 }
@@ -3932,12 +3926,13 @@ vdbeRecordDecodeInt(u32 serial_type, const u8 * aKey)
  * If database corruption is discovered, set pPKey2->errCode to
  * SQLITE_CORRUPT and return 0. If an OOM error is encountered,
  * pPKey2->errCode is set to SQLITE_NOMEM and, if it is not NULL, the
- * malloc-failed flag set on database handle (pPKey2->pKeyInfo->db).
+ * malloc-failed flag set on database handle.
  */
 int
-sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
+sqlite3VdbeRecordCompareWithSkip(struct sqlite3 *db,
+				 int nKey1, const void *pKey1,	/* Left key */
 				 UnpackedRecord * pPKey2,	/* Right key */
-				 int bSkip)			/* If true, skip the first field */
+				 bool bSkip)			/* If true, skip the first field */
 {
 	u32 d1;			/* Offset into aKey[] of next data element */
 	int i;			/* Index of next field to compare */
@@ -3945,7 +3940,7 @@ sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
 	u32 idx1;		/* Offset of first type in header */
 	int rc = 0;		/* Return value */
 	Mem *pRhs = pPKey2->aMem;	/* Next field of pPKey2 to compare */
-	KeyInfo *pKeyInfo = pPKey2->pKeyInfo;
+	struct key_def *key_def = pPKey2->key_def;
 	const unsigned char *aKey1 = (const unsigned char *)pKey1;
 	Mem mem1;
 
@@ -3972,10 +3967,7 @@ sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
 
 	VVA_ONLY(mem1.szMalloc = 0;
 	    )			/* Only needed by assert() statements */
-	    assert(pPKey2->pKeyInfo->nField + pPKey2->pKeyInfo->nXField >=
-		   pPKey2->nField || CORRUPT_DB);
-	assert(pPKey2->pKeyInfo->aSortOrder != 0);
-	assert(pPKey2->pKeyInfo->nField > 0);
+	assert(pPKey2->key_def->part_count > 0);
 	assert(idx1 <= szHdr1 || CORRUPT_DB);
 	do {
 		u32 serial_type;
@@ -4050,13 +4042,14 @@ sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
 					pPKey2->errCode =
 					    (u8) SQLITE_CORRUPT_BKPT;
 					return 0;	/* Corruption */
-				} else if (pKeyInfo->aColl[i]) {
-					mem1.db = pKeyInfo->db;
+				} else if (key_def->parts[i].coll !=NULL) {
+					mem1.db = db;
 					mem1.flags = MEM_Str;
 					mem1.z = (char *)&aKey1[d1];
+					struct coll* coll;
+					coll = key_def->parts[i].coll;
 					rc = vdbeCompareMemString(&mem1, pRhs,
-								  pKeyInfo->
-								  aColl[i],
+								  coll,
 								  &pPKey2->
 								  errCode);
 				} else {
@@ -4106,11 +4099,10 @@ sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
 		}
 
 		if (rc != 0) {
-			if (pKeyInfo->aSortOrder[i]) {
+			if (key_def->parts[i].sort_order != SORT_ORDER_ASC)
 				rc = -rc;
-			}
 			assert(vdbeRecordCompareDebug
-			       (nKey1, pKey1, pPKey2, rc));
+			       (db, nKey1, pKey1, pPKey2, rc));
 			assert(mem1.szMalloc == 0);	/* See comment below */
 			return rc;
 		}
@@ -4133,18 +4125,19 @@ sqlite3VdbeRecordCompareWithSkip(int nKey1, const void *pKey1,	/* Left key */
 	 * value.
 	 */
 	assert(CORRUPT_DB
-	       || vdbeRecordCompareDebug(nKey1, pKey1, pPKey2,
+	       || vdbeRecordCompareDebug(db, nKey1, pKey1, pPKey2,
 					 pPKey2->default_rc)
-	       || pKeyInfo->db->mallocFailed);
+	       || db->mallocFailed);
 	pPKey2->eqSeen = 1;
 	return pPKey2->default_rc;
 }
 
 int
-sqlite3VdbeRecordCompare(int nKey1, const void *pKey1,	/* Left key */
-			 UnpackedRecord * pPKey2)	/* Right key */
+sqlite3VdbeRecordCompare(struct sqlite3 *db,
+			 int key_count, const void *key1,	/* Left key */
+			 UnpackedRecord *key2)	/* Right key */
 {
-	return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 0);
+	return sqlite3VdbeRecordCompareWithSkip(db, key_count, key1, key2, false);
 }
 
 /*
@@ -4159,27 +4152,19 @@ sqlite3VdbeFindCompare(UnpackedRecord * p)
 	return sqlite3VdbeRecordCompareMsgpack;
 }
 
-/*
- * Compare the key of the index entry that cursor pC is pointing to against
- * the key string in pUnpacked.  Write into *pRes a number
- * that is negative, zero, or positive if pC is less than, equal to,
- * or greater than pUnpacked.  Return SQLITE_OK on success.
- */
 int
-sqlite3VdbeIdxKeyCompare(sqlite3 * db,			/* Database connection */
-			 VdbeCursor * pC,		/* The cursor to compare against */
-			 UnpackedRecord * pUnpacked,	/* Unpacked version of key */
-			 int *res)			/* Write the comparison result here */
-{
-	(void)db;
-	BtCursor *pCur;
-
-	assert(pC->eCurType == CURTYPE_TARANTOOL);
-	pCur = pC->uc.pCursor;
-	assert(sqlite3CursorIsValid(pCur));
-	if (pCur->curFlags & BTCF_TaCursor ||
-	    pCur->curFlags & BTCF_TEphemCursor) {
-		return tarantoolSqlite3IdxKeyCompare(pCur, pUnpacked, res);
+sqlite3VdbeIdxKeyCompare(struct VdbeCursor *vdbe_cursor,
+			 struct UnpackedRecord *unpacked,
+			 int *res)
+{
+	struct BtCursor *cursor;
+
+	assert(vdbe_cursor->eCurType == CURTYPE_TARANTOOL);
+	cursor = vdbe_cursor->uc.pCursor;
+	assert(sqlite3CursorIsValid(cursor));
+	if (cursor->curFlags & BTCF_TaCursor ||
+	    cursor->curFlags & BTCF_TEphemCursor) {
+		return tarantoolSqlite3IdxKeyCompare(cursor, unpacked, res);
 	}
 	unreachable();
 	return SQLITE_OK;
@@ -4301,68 +4286,6 @@ vdbeFreeUnpacked(sqlite3 * db, UnpackedRecord * p)
 }
 #endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
 
-#ifdef SQLITE_ENABLE_PREUPDATE_HOOK
-/*
- * Invoke the pre-update hook. If this is an UPDATE or DELETE pre-update call,
- * then cursor passed as the second argument should point to the row about
- * to be update or deleted. If the application calls sqlite3_preupdate_old(),
- * the required value will be read from the row the cursor points to.
- */
-void
-sqlite3VdbePreUpdateHook(Vdbe * v,		/* Vdbe pre-update hook is invoked by */
-			 VdbeCursor * pCsr,	/* Cursor to grab old.* values from */
-			 int op,		/* SQLITE_INSERT, UPDATE or DELETE */
-			 Table * pTab,		/* Modified table */
-			 i64 iKey1,		/* Initial key value */
-			 int iReg)		/* Register for new.* record */
-{
-	sqlite3 *db = v->db;
-	i64 iKey2;
-	PreUpdate preupdate;
-	const char *zTbl = pTab->zName;
-	static const u8 fakeSortOrder = 0;
-
-	assert(db->pPreUpdate == 0);
-	memset(&preupdate, 0, sizeof(PreUpdate));
-	if (op == SQLITE_UPDATE) {
-		iKey2 = v->aMem[iReg].u.i;
-	} else {
-		iKey2 = iKey1;
-	}
-
-	assert(pCsr->nField == pTab->nCol
-	       || (pCsr->nField == pTab->nCol + 1 && op == SQLITE_DELETE
-		   && iReg == -1)
-	    );
-
-	preupdate.v = v;
-	preupdate.pCsr = pCsr;
-	preupdate.op = op;
-	preupdate.iNewReg = iReg;
-	preupdate.keyinfo.db = db;
-	preupdate.keyinfo.nField = pTab->nCol;
-	preupdate.keyinfo.aSortOrder = (u8 *) & fakeSortOrder;
-	preupdate.iKey1 = iKey1;
-	preupdate.iKey2 = iKey2;
-	preupdate.pTab = pTab;
-
-	db->pPreUpdate = &preupdate;
-	db->xPreUpdateCallback(db->pPreUpdateArg, db, op, zTbl, iKey1,
-			       iKey2);
-	db->pPreUpdate = 0;
-	sqlite3DbFree(db, preupdate.aRecord);
-	vdbeFreeUnpacked(db, preupdate.pUnpacked);
-	vdbeFreeUnpacked(db, preupdate.pNewUnpacked);
-	if (preupdate.aNew) {
-		int i;
-		for (i = 0; i < pCsr->nField; i++) {
-			sqlite3VdbeMemRelease(&preupdate.aNew[i]);
-		}
-		sqlite3DbFree(db, preupdate.aNew);
-	}
-}
-#endif				/* SQLITE_ENABLE_PREUPDATE_HOOK */
-
 i64
 sqlite3VdbeMsgpackRecordLen(Mem * pRec, u32 n)
 {
@@ -4435,11 +4358,11 @@ sqlite3VdbeMsgpackRecordPut(u8 * pBuf, Mem * pRec, u32 n)
 }
 
 int
-sqlite3VdbeCompareMsgpack(const char **pKey1,
-			  UnpackedRecord * pUnpacked, int iKey2)
+sqlite3VdbeCompareMsgpack(const char **key1,
+			  struct UnpackedRecord *unpacked, int key2_idx)
 {
-	const char *aKey1 = *pKey1;
-	Mem *pKey2 = pUnpacked->aMem + iKey2;
+	const char *aKey1 = *key1;
+	Mem *pKey2 = unpacked->aMem + key2_idx;
 	Mem mem1;
 	int rc = 0;
 	switch (mp_typeof(*aKey1)) {
@@ -4508,17 +4431,17 @@ sqlite3VdbeCompareMsgpack(const char **pKey1,
 		}
 	case MP_STR:{
 			if (pKey2->flags & MEM_Str) {
-				KeyInfo *pKeyInfo = pUnpacked->pKeyInfo;
+				struct key_def *key_def = unpacked->key_def;
 				mem1.n = mp_decode_strl(&aKey1);
 				mem1.z = (char *)aKey1;
 				aKey1 += mem1.n;
-				if (pKeyInfo->aColl[iKey2]) {
-					mem1.db = pKeyInfo->db;
+				struct coll *coll;
+				coll = key_def->parts[key2_idx].coll;
+				if (coll != NULL) {
 					mem1.flags = MEM_Str;
 					rc = vdbeCompareMemString(&mem1, pKey2,
-								  pKeyInfo->
-								  aColl[iKey2],
-								  &pUnpacked->
+								  coll,
+								  &unpacked->
 								  errCode);
 				} else {
 					goto do_bin_cmp;
@@ -4563,34 +4486,32 @@ sqlite3VdbeCompareMsgpack(const char **pKey1,
 			goto do_blob;
 		}
 	}
-	*pKey1 = aKey1;
+	*key1 = aKey1;
 	return rc;
 }
 
 int
-sqlite3VdbeRecordCompareMsgpack(int nKey1, const void *pKey1,	/* Left key */
-				UnpackedRecord * pPKey2)	/* Right key */
+sqlite3VdbeRecordCompareMsgpack(const void *key1,
+				struct UnpackedRecord *key2)
 {
-	(void)nKey1;		/* assume valid data */
-
-	int rc = 0;		/* Return value */
-	const char *aKey1 = (const char *)pKey1;
-	u32 i, n = mp_decode_array(&aKey1);
+	int rc = 0;
+	u32 i, n = mp_decode_array((const char**)&key1);
 
-	n = MIN(n, pPKey2->nField);
+	n = MIN(n, key2->nField);
 
 	for (i = 0; i != n; i++) {
-		rc = sqlite3VdbeCompareMsgpack(&aKey1, pPKey2, i);
+		rc = sqlite3VdbeCompareMsgpack((const char**)&key1, key2, i);
 		if (rc != 0) {
-			if (pPKey2->pKeyInfo->aSortOrder[i]) {
+			if (key2->key_def->parts[i].sort_order !=
+			    SORT_ORDER_ASC) {
 				rc = -rc;
 			}
 			return rc;
 		}
 	}
 
-	pPKey2->eqSeen = 1;
-	return pPKey2->default_rc;
+	key2->eqSeen = 1;
+	return key2->default_rc;
 }
 
 u32
@@ -4669,21 +4590,18 @@ sqlite3VdbeMsgpackGet(const unsigned char *buf,	/* Buffer to deserialize from */
 }
 
 void
-sqlite3VdbeRecordUnpackMsgpack(KeyInfo * pKeyInfo,	/* Information about the record format */
-			       int nKey,		/* Size of the binary record */
+sqlite3VdbeRecordUnpackMsgpack(struct key_def *key_def,	/* Information about the record format */
 			       const void *pKey,	/* The binary record */
 			       UnpackedRecord * p)	/* Populate this structure before returning. */
 {
 	uint32_t n;
 	const char *zParse = pKey;
-	(void)nKey;
 	Mem *pMem = p->aMem;
 	n = mp_decode_array(&zParse);
-	n = p->nField = MIN(n, pKeyInfo->nField);
+	n = p->nField = MIN(n, key_def->part_count);
 	p->default_rc = 0;
+	p->key_def = key_def;
 	while (n--) {
-		pMem->db = pKeyInfo->db;
-		/* pMem->flags = 0; // sqlite3VdbeSerialGet() will set this for us */
 		pMem->szMalloc = 0;
 		pMem->z = 0;
 		u32 sz = sqlite3VdbeMsgpackGet((u8 *) zParse, pMem);
diff --git a/src/box/sql/vdbemem.c b/src/box/sql/vdbemem.c
index 9dd254f..3c23991 100644
--- a/src/box/sql/vdbemem.c
+++ b/src/box/sql/vdbemem.c
@@ -1089,14 +1089,13 @@ valueNew(sqlite3 * db, struct ValueNewStat4Ctx *p)
 			int i;	/* Counter variable */
 			int nCol = index_column_count(pIdx);
 
-			nByte =
-			    sizeof(Mem) * nCol + ROUND8(sizeof(UnpackedRecord));
+			nByte = sizeof(Mem) * nCol +
+				ROUND8(sizeof(UnpackedRecord));
 			pRec =
 			    (UnpackedRecord *) sqlite3DbMallocZero(db, nByte);
-			if (pRec) {
-				pRec->pKeyInfo =
-				    sqlite3KeyInfoOfIndex(p->pParse, db, pIdx);
-				if (pRec->pKeyInfo) {
+			if (pRec != NULL) {
+				pRec->key_def = sql_index_key_def(pIdx, true);
+				if (pRec->key_def != NULL) {
 					pRec->aMem =
 					    (Mem *) ((u8 *) pRec +
 						     ROUND8(sizeof
@@ -1655,13 +1654,12 @@ sqlite3Stat4ProbeFree(UnpackedRecord * pRec)
 {
 	if (pRec) {
 		int i;
-		int nCol = pRec->pKeyInfo->nField;
+		int nCol = pRec->key_def->part_count;
 		Mem *aMem = pRec->aMem;
 		sqlite3 *db = aMem[0].db;
 		for (i = 0; i < nCol; i++) {
 			sqlite3VdbeMemRelease(&aMem[i]);
 		}
-		sqlite3KeyInfoUnref(pRec->pKeyInfo);
 		sqlite3DbFree(db, pRec);
 	}
 }
diff --git a/src/box/sql/vdbesort.c b/src/box/sql/vdbesort.c
index be3cc4c..7c45553 100644
--- a/src/box/sql/vdbesort.c
+++ b/src/box/sql/vdbesort.c
@@ -312,8 +312,8 @@ struct MergeEngine {
  * after the thread has finished are not dire. So we don't worry about
  * memory barriers and such here.
  */
-typedef int (*SorterCompare) (SortSubtask *, int *, const void *, int,
-			      const void *, int);
+typedef int (*SorterCompare) (SortSubtask *, bool *, const void *,
+			      const void *);
 struct SortSubtask {
 	SQLiteThread *pThread;	/* Background thread, if any */
 	int bDone;		/* Set if thread is finished but not joined */
@@ -343,7 +343,7 @@ struct VdbeSorter {
 	PmaReader *pReader;	/* Readr data from here after Rewind() */
 	MergeEngine *pMerger;	/* Or here, if bUseThreads==0 */
 	sqlite3 *db;		/* Database connection */
-	KeyInfo *pKeyInfo;	/* How to compare records */
+	struct key_def *key_def;
 	UnpackedRecord *pUnpacked;	/* Used by VdbeSorterCompare() */
 	SorterList list;	/* List of in-memory records */
 	int iMemory;		/* Offset of free space in list.aMemory */
@@ -794,10 +794,10 @@ vdbePmaReaderInit(SortSubtask * pTask,	/* Task context */
 	return rc;
 }
 
-/*
- * Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2,
- * size nKey2 bytes). Use (pTask->pKeyInfo) for the collation sequences
- * used by the comparison. Return the result of the comparison.
+/**
+ * Compare key1 with key2. Use (pTask->key_def) for the collation
+ * sequences used by the comparison. Return the result of the
+ * comparison.
  *
  * If IN/OUT parameter *pbKey2Cached is true when this function is called,
  * it is assumed that (pTask->pUnpacked) contains the unpacked version
@@ -806,27 +806,31 @@ vdbePmaReaderInit(SortSubtask * pTask,	/* Task context */
  *
  * If an OOM error is encountered, (pTask->pUnpacked->error_rc) is set
  * to SQLITE_NOMEM.
+ *
+ * @param task Subtask context (for key_def).
+ * @param key2_cached True if pTask->pUnpacked is key2.
+ * @param key1 Left side of comparison.
+ * @param key2 Right side of comparison.
+ *
+ * @retval +1 if key1 > key2, -1 otherwise.
  */
 static int
-vdbeSorterCompare(SortSubtask * pTask,	/* Subtask context (for pKeyInfo) */
-		  int *pbKey2Cached,	/* True if pTask->pUnpacked is pKey2 */
-		  const void *pKey1, int nKey1,	/* Left side of comparison */
-		  const void *pKey2, int nKey2	/* Right side of comparison */
-    )
+vdbeSorterCompare(struct SortSubtask *task, bool *key2_cached,
+		  const void *key1, const void *key2)
 {
-	UnpackedRecord *r2 = pTask->pUnpacked;
-	if (!*pbKey2Cached) {
-		sqlite3VdbeRecordUnpackMsgpack(pTask->pSorter->pKeyInfo, nKey2,
-					       pKey2, r2);
-		*pbKey2Cached = 1;
+	struct UnpackedRecord *r2 = task->pUnpacked;
+	if (!*key2_cached) {
+		sqlite3VdbeRecordUnpackMsgpack(task->pSorter->key_def,
+					       key2, r2);
+		*key2_cached = 1;
 	}
-	return sqlite3VdbeRecordCompareMsgpack(nKey1, pKey1, r2);
+	return sqlite3VdbeRecordCompareMsgpack(key1, r2);
 }
 
 /*
  * Initialize the temporary index cursor just opened as a sorter cursor.
  *
- * Usually, the sorter module uses the value of (pCsr->pKeyInfo->nField)
+ * Usually, the sorter module uses the value of (pCsr->key_def->part_count)
  * to determine the number of fields that should be compared from the
  * records being sorted. However, if the value passed as argument nField
  * is non-zero and the sorter is able to guarantee a stable sort, nField
@@ -844,16 +848,12 @@ vdbeSorterCompare(SortSubtask * pTask,	/* Subtask context (for pKeyInfo) */
  */
 int
 sqlite3VdbeSorterInit(sqlite3 * db,	/* Database connection (for malloc()) */
-		      int nField,	/* Number of key fields in each record */
 		      VdbeCursor * pCsr	/* Cursor that holds the new sorter */
     )
 {
 	int pgsz;		/* Page size of main database */
 	int i;			/* Used to iterate through aTask[] */
 	VdbeSorter *pSorter;	/* The new sorter */
-	KeyInfo *pKeyInfo;	/* Copy of pCsr->pKeyInfo with db==0 */
-	int szKeyInfo;		/* Size of pCsr->pKeyInfo in bytes */
-	int sz;			/* Size of pSorter in bytes */
 	int rc = SQLITE_OK;
 #if SQLITE_MAX_WORKER_THREADS==0
 #define nWorker 0
@@ -875,25 +875,15 @@ sqlite3VdbeSorterInit(sqlite3 * db,	/* Database connection (for malloc()) */
 	}
 #endif
 
-	assert(pCsr->pKeyInfo);
+	assert(pCsr->key_def != NULL);
 	assert(pCsr->eCurType == CURTYPE_SORTER);
-	szKeyInfo =
-	    sizeof(KeyInfo) + (pCsr->pKeyInfo->nField - 1) * sizeof(struct coll *);
-	sz = sizeof(VdbeSorter) + nWorker * sizeof(SortSubtask);
 
-	pSorter = (VdbeSorter *) sqlite3DbMallocZero(db, sz + szKeyInfo);
+	pSorter = (VdbeSorter *) sqlite3DbMallocZero(db, sizeof(VdbeSorter));
 	pCsr->uc.pSorter = pSorter;
 	if (pSorter == 0) {
 		rc = SQLITE_NOMEM_BKPT;
 	} else {
-		pSorter->pKeyInfo = pKeyInfo =
-		    (KeyInfo *) ((u8 *) pSorter + sz);
-		memcpy(pKeyInfo, pCsr->pKeyInfo, szKeyInfo);
-		pKeyInfo->db = 0;
-		if (nField && nWorker == 0) {
-			pKeyInfo->nXField += (pKeyInfo->nField - nField);
-			pKeyInfo->nField = nField;
-		}
+		pSorter->key_def = pCsr->key_def;
 		pSorter->pgsz = pgsz = 1024;
 		pSorter->nTask = nWorker + 1;
 		pSorter->iPrev = (u8) (nWorker - 1);
@@ -929,8 +919,8 @@ sqlite3VdbeSorterInit(sqlite3 * db,	/* Database connection (for malloc()) */
 			}
 		}
 
-		if ((pKeyInfo->nField + pKeyInfo->nXField) < 13
-		    && (pKeyInfo->aColl[0] == NULL)) {
+		if (pCsr->key_def->part_count < 13
+		    && (pCsr->key_def->parts[0].coll == NULL)) {
 			pSorter->typeMask =
 			    SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT;
 		}
@@ -1280,10 +1270,11 @@ vdbeSortAllocUnpacked(SortSubtask * pTask)
 {
 	if (pTask->pUnpacked == 0) {
 		pTask->pUnpacked =
-		    sqlite3VdbeAllocUnpackedRecord(pTask->pSorter->pKeyInfo);
+			sqlite3VdbeAllocUnpackedRecord(pTask->pSorter->db,
+						       pTask->pSorter->key_def);
 		if (pTask->pUnpacked == 0)
 			return SQLITE_NOMEM_BKPT;
-		pTask->pUnpacked->nField = pTask->pSorter->pKeyInfo->nField;
+		pTask->pUnpacked->nField = pTask->pSorter->key_def->part_count;
 		pTask->pUnpacked->errCode = 0;
 	}
 	return SQLITE_OK;
@@ -1300,14 +1291,14 @@ vdbeSorterMerge(SortSubtask * pTask,	/* Calling thread context */
 {
 	SorterRecord *pFinal = 0;
 	SorterRecord **pp = &pFinal;
-	int bCached = 0;
+	bool bCached = false;
 
 	assert(p1 != 0 && p2 != 0);
 	for (;;) {
 		int res;
 		res =
-		    pTask->xCompare(pTask, &bCached, SRVAL(p1), p1->nVal,
-				    SRVAL(p2), p2->nVal);
+		    pTask->xCompare(pTask, &bCached, SRVAL(p1),
+				    SRVAL(p2));
 
 		if (res <= 0) {
 			*pp = p1;
@@ -1599,7 +1590,7 @@ vdbeMergeEngineStep(MergeEngine * pMerger,	/* The merge engine to advance to the
 		int i;		/* Index of aTree[] to recalculate */
 		PmaReader *pReadr1;	/* First PmaReader to compare */
 		PmaReader *pReadr2;	/* Second PmaReader to compare */
-		int bCached = 0;
+		bool bCached = false;
 
 		/* Find the first two PmaReaders to compare. The one that was just
 		 * advanced (iPrev) and the one next to it in the array.
@@ -1617,9 +1608,7 @@ vdbeMergeEngineStep(MergeEngine * pMerger,	/* The merge engine to advance to the
 			} else {
 				iRes = pTask->xCompare(pTask, &bCached,
 						       pReadr1->aKey,
-						       pReadr1->nKey,
-						       pReadr2->aKey,
-						       pReadr2->nKey);
+						       pReadr2->aKey);
 			}
 
 			/* If pReadr1 contained the smaller value, set aTree[i] to its index.
@@ -2075,12 +2064,11 @@ vdbeMergeEngineCompare(MergeEngine * pMerger,	/* Merge engine containing PmaRead
 		iRes = i1;
 	} else {
 		SortSubtask *pTask = pMerger->pTask;
-		int bCached = 0;
+		bool cached = false;
 		int res;
 		assert(pTask->pUnpacked != 0);	/* from vdbeSortSubtaskMain() */
 		res =
-		    pTask->xCompare(pTask, &bCached, p1->aKey, p1->nKey,
-				    p2->aKey, p2->nKey);
+		    pTask->xCompare(pTask, &cached, p1->aKey, p2->aKey);
 		if (res <= 0) {
 			iRes = i1;
 		} else {
@@ -2824,7 +2812,6 @@ sqlite3VdbeSorterCompare(const VdbeCursor * pCsr,	/* Sorter cursor */
 {
 	VdbeSorter *pSorter;
 	UnpackedRecord *r2;
-	KeyInfo *pKeyInfo;
 	int i;
 	void *pKey;
 	int nKey;		/* Sorter key to compare pVal with */
@@ -2832,10 +2819,9 @@ sqlite3VdbeSorterCompare(const VdbeCursor * pCsr,	/* Sorter cursor */
 	assert(pCsr->eCurType == CURTYPE_SORTER);
 	pSorter = pCsr->uc.pSorter;
 	r2 = pSorter->pUnpacked;
-	pKeyInfo = pCsr->pKeyInfo;
 	if (r2 == 0) {
 		r2 = pSorter->pUnpacked =
-		    sqlite3VdbeAllocUnpackedRecord(pKeyInfo);
+			sqlite3VdbeAllocUnpackedRecord(pSorter->db,  pCsr->key_def);
 		if (r2 == 0)
 			return SQLITE_NOMEM_BKPT;
 		r2->nField = nKeyCol;
@@ -2843,7 +2829,7 @@ sqlite3VdbeSorterCompare(const VdbeCursor * pCsr,	/* Sorter cursor */
 	assert(r2->nField == nKeyCol);
 
 	pKey = vdbeSorterRowkey(pSorter, &nKey);
-	sqlite3VdbeRecordUnpackMsgpack(pKeyInfo, nKey, pKey, r2);
+	sqlite3VdbeRecordUnpackMsgpack(pCsr->key_def, pKey, r2);
 	for (i = 0; i < nKeyCol; i++) {
 		if (r2->aMem[i].flags & MEM_Null) {
 			*pRes = -1;
@@ -2851,6 +2837,6 @@ sqlite3VdbeSorterCompare(const VdbeCursor * pCsr,	/* Sorter cursor */
 		}
 	}
 
-	*pRes = sqlite3VdbeRecordCompareMsgpack(pVal->n, pVal->z, r2);
+	*pRes = sqlite3VdbeRecordCompareMsgpack(pVal->z, r2);
 	return SQLITE_OK;
 }
diff --git a/src/box/sql/where.c b/src/box/sql/where.c
index bad964a..cde3815 100644
--- a/src/box/sql/where.c
+++ b/src/box/sql/where.c
@@ -812,7 +812,7 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	assert(pLevel->iIdxCur >= 0);
 	pLevel->iIdxCur = pParse->nTab++;
 	sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol + 1);
-	sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
+	sql_vdbe_set_p4_key_def(pParse, pIdx);
 	VdbeComment((v, "for %s", pTable->zName));
 
 	/* Fill the automatic index with content */
@@ -971,9 +971,7 @@ whereKeyStats(Parse * pParse,	/* Database connection */
 		}
 
 		pRec->nField = n;
-		res =
-		    sqlite3VdbeRecordCompareMsgpack(aSample[iSamp].n,
-						    aSample[iSamp].p, pRec);
+		res = sqlite3VdbeRecordCompareMsgpack(aSample[iSamp].p, pRec);
 		if (res < 0) {
 			iLower =
 			    aSample[iSamp].anLt[n - 1] + aSample[iSamp].anEq[n -
@@ -1002,8 +1000,7 @@ whereKeyStats(Parse * pParse,	/* Database connection */
 			assert(iCol == nField - 1);
 			pRec->nField = nField;
 			assert(0 ==
-			       sqlite3VdbeRecordCompareMsgpack(aSample[i].n,
-							       aSample[i].p,
+			       sqlite3VdbeRecordCompareMsgpack(aSample[i].p,
 							       pRec)
 			       || pParse->db->mallocFailed);
 		} else {
@@ -1014,8 +1011,7 @@ whereKeyStats(Parse * pParse,	/* Database connection */
 			assert(i <= pIdx->nSample && i >= 0);
 			pRec->nField = iCol + 1;
 			assert(i == pIdx->nSample
-			       || sqlite3VdbeRecordCompareMsgpack(aSample[i].n,
-								  aSample[i].p,
+			       || sqlite3VdbeRecordCompareMsgpack(aSample[i].p,
 								  pRec) > 0
 			       || pParse->db->mallocFailed);
 
@@ -1027,14 +1023,14 @@ whereKeyStats(Parse * pParse,	/* Database connection */
 			if (iCol > 0) {
 				pRec->nField = iCol;
 				assert(sqlite3VdbeRecordCompareMsgpack
-				       (aSample[i].n, aSample[i].p, pRec) <= 0
+				       (aSample[i].p, pRec) <= 0
 				       || pParse->db->mallocFailed);
 			}
 			if (i > 0) {
 				pRec->nField = nField;
 				assert(sqlite3VdbeRecordCompareMsgpack
-				       (aSample[i - 1].n, aSample[i - 1].p,
-					pRec) < 0 || pParse->db->mallocFailed);
+				       (aSample[i - 1].p, pRec) < 0 ||
+				       pParse->db->mallocFailed);
 			}
 		}
 	}
@@ -3385,12 +3381,12 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 					 */
 					if (revSet) {
 						if ((rev ^ revIdx) !=
-						    pOrderBy->a[i].sortOrder)
+						    pOrderBy->a[i].sort_order)
 							isMatch = 0;
 					} else {
 						rev =
 						    revIdx ^ pOrderBy->a[i].
-						    sortOrder;
+						    sort_order;
 						if (rev)
 							*pRevMask |=
 							    MASKBIT(iLoop);
@@ -4571,7 +4567,7 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 			assert(iIndexCur >= 0);
 			if (op) {
 				emit_open_cursor(pParse, iIndexCur, pIx->tnum);
-				sqlite3VdbeSetP4KeyInfo(pParse, pIx);
+				sql_vdbe_set_p4_key_def(pParse, pIx);
 				if ((pLoop->wsFlags & WHERE_CONSTRAINT) != 0
 				    && (pLoop->
 					wsFlags & (WHERE_COLUMN_RANGE |
diff --git a/src/box/sql/wherecode.c b/src/box/sql/wherecode.c
index b467bbe..878425c 100644
--- a/src/box/sql/wherecode.c
+++ b/src/box/sql/wherecode.c
@@ -1618,7 +1618,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo,	/* Complete information about t
 			regRowset = pParse->nTab++;
 			sqlite3VdbeAddOp2(v, OP_OpenTEphemeral,
 					  regRowset, nPkCol);
-			sqlite3VdbeSetP4KeyInfo(pParse, pPk);
+			sql_vdbe_set_p4_key_def(pParse, pPk);
 			regPk = ++pParse->nMem;
 		}
 		iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
diff --git a/src/box/tuple.c b/src/box/tuple.c
index df2686e..7bcd9f8 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -474,3 +474,12 @@ tuple_str(const struct tuple *tuple)
 		return "<failed to format tuple>";
 	return buf;
 }
+
+const char *
+mp_str(const char *data)
+{
+	char *buf = tt_static_buf();
+	if (mp_snprint(buf, TT_STATIC_BUF_LEN, data) < 0)
+		return "<failed to format message pack>";
+	return buf;
+}
diff --git a/src/box/tuple.h b/src/box/tuple.h
index 97b81cf..9a459d9 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -395,6 +395,15 @@ tuple_snprint(char *buf, int size, const struct tuple *tuple);
 const char *
 tuple_str(const struct tuple *tuple);
 
+/**
+ * Format msgpack into string using a static buffer.
+ * Useful for debugger. Example: [1, 2, "string"]
+ * @param msgpack to format
+ * @return formatted null-terminated string
+ */
+const char *
+mp_str(const char *data);
+
 /**
  * Get the format of the tuple.
  * @param tuple Tuple.

  reply	other threads:[~2018-05-11 12:56 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-08  7:56 [tarantool-patches] [PATCH 0/2] sql: replace KeyInfo w/ key_def in SQL front-end Kirill Yukhin
2018-05-08  7:56 ` [tarantool-patches] [PATCH 1/2] sql: introduce sort order to key_part/key_part_def Kirill Yukhin
2018-05-08 16:02   ` [tarantool-patches] " Vladislav Shpilevoy
2018-05-10 13:01     ` Kirill Yukhin
2018-05-08  7:56 ` [tarantool-patches] [PATCH] sql: use collation pointers instead of names Kirill Yukhin
2018-04-17 18:06   ` [tarantool-patches] " Vladislav Shpilevoy
2018-04-18  5:42     ` Kirill Yukhin
2018-05-08  7:59   ` Kirill Yukhin
2018-05-08  7:56 ` [tarantool-patches] [PATCH 2/2] sql: replace KeyInfo with key_def Kirill Yukhin
2018-05-08 16:02   ` [tarantool-patches] " Vladislav Shpilevoy
2018-05-10 12:59     ` Kirill Yukhin
2018-05-11 11:22       ` Vladislav Shpilevoy
2018-05-11 12:56         ` Kirill Yukhin [this message]
2018-05-11 19:05           ` Vladislav Shpilevoy
2018-05-14 11:40             ` Kirill Yukhin
  -- strict thread matches above, loose matches on Subject: below --
2018-04-13  8:05 [tarantool-patches] [PATCH] sql: use collation pointers instead of names Kirill Yukhin
2018-04-16 13:43 ` [tarantool-patches] " Vladislav Shpilevoy

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180511125623.ulx2xolqwyx2azit@tarantool.org \
    --to=kyukhin@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --cc=v.shpilevoy@tarantool.org \
    --subject='[tarantool-patches] Re: [PATCH 2/2] sql: replace KeyInfo with key_def' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox