Re: [Tarantool-patches] [PATCH v3 1/1] sql: enable autoindex optimization

[Nikita Pettik <korablev@tarantool.org>]

On 14 Oct 12:30, Mergen Imeev wrote:
> Привет! Спасибо за ревью. Мои ответы и изменения ниже.
> 
> On Tue, Oct 13, 2020 at 02:08:34PM +0000, Nikita Pettik wrote:
> > On 11 Oct 13:48, imeevma@tarantool.org wrote:
> > > From: Kirill Yukhin <kyukhin@tarantool.org>
> > > 
> > > This patch enables "autoindex" optimization. This optimization uses an
> > > ephemeral space that contains all the fields used in the query. This
> > 
> > Не очень понимаю, что значит "все поля в запросе"..? Это как?:)
> > Ты имеешь ввиду все поля result-set'a? Или объединение всех полей
> > всех таблиц используемых в запросе?
> > 
> Я думаю лучше будет показать на примере:
> CREATE TABLE t1 (i INT PRIMARY KEY, a INT, b INT, c INT);
> CREATE TABLE t2 (i INT PRIMARY KEY, a INT, b INT, c INT);
> ...
> SELECT t1.a, t2.b FROM t1, t2 WHERE t1.b = t2.c
> 
> В данном случае планировщик выберет один из спейсов, для которого он сделает
> автоиндекс. В случае, если он выберет t1, то автоиндекс будет состоять из
> трех полей: rowid, b, a (в таком порядке). Если он выберет t2, то автоиндекс
> будет так же состоять из трех полей: rowid, c, b. Т.е. в любом случае автоиндекс
> будет содержать не только поля спейса которые участвуют в WHERE, но и поля
> который участвуют в возвращаемом значении, даже если они не участвуют в WHERE.
> Это сделано для того, чтобы не обращаться к оригинальному спейсу в случае
> использования автоиндекс и пользоваться самим автоиндексом вместо оригинального
> спейса.

Ок, вот это было бы здорово сразу в коммит месседже описать.
 
> > > ephemeral space is called "autoindex". Autoindex may have fewer fields
> > > than the original space, and the order of these fields in autoindex may
> > 
> > Опять: original space - это какой спейс? В запросе может участвовать
> > много таблиц..
> > 
> Один из спейсов участвующих в запросе. Какой именно выбирает планировщик.

ditto

> > Еще имхо какая-то путаница выходит: называем эфемерные спейсы автоиндексами.
> > Я бы обозвал это как-нибудь по-другому. Это же просто еще одно использование
> > эфемерных таблиц, не более.
> > 
> Мне кажется это не совсем верно. Обычно использование эфемерных спейсов является
> необходимостью а не оптимизацией. 

Так, и?

> Насчет того что это спейс а не индекс я
> согласен, но в некотором смысле он ведет себя как индекс.

Это как?

> Т.е. SQL считает, что
> мы создали индекс. Один из случаев когда это важно упомянут ниже.

Короче, предлагаю называть это хотя бы ephemeral index opt,
autoindex space opt или что-нибудь в это духе (чтобы не путать со
скулайтовской терминологией).
 
> > > be different from their order in the original space. In addition to the
> > > mentioned fields, autoindex contains a rowid.
> > > 
> > > The primary key of autoindex is a covering index, i.e. it contains all
> > > of its fields.
> > 
> > В мемтиксе все индексы покрывающие. И 'covering' - свойство для каждого
> > запроса отдельно взятого, а не индекса как такового.
> > 
> В данном случае 'covering' означает что определение содержит все поля спейса.
> В предыдущем ревью я предложил разобраться с этим вопросом чуть позже, т.к.
> считаю, что здесь это не очень важно.

У этого термина есть общепринятое определение. Не понимаю в чем тут разбираться,
если он используется не по назначению..
 
> > > 
> > > Currently this optimization mainly used in cases when values SELECTED
> > > from more than one space and WHERE specified.
> > > 
> > > At the moment, this optimization does not take into account the number
> > > of tuples in spaces. This should be fixed.
> > > 
> > > Closes #4933
> > > 
> > > Co-authored-by: Mergen Imeev <imeevma@gmail.com>
> > > Co-authored-by: Timur Safin <tsafin@tarantool.org>
> > > ---
> > > https://github.com/tarantool/tarantool/issues/4933
> > > https://github.com/tarantool/tarantool/tree/imeevma/gh-4933-autoindex
> > > 
> > > @ChangeLog
> > >  - "autoindex" optimization is now enabled (gh-4933).
> > 
> > МНе кажется, можно чуть больше написать про такую важную штуку
> >  
> Мне кажется это не настолько важная оптимизация

Ну-ну

> что ее стоит отдельно много
> описывать. Круг ее применения довольно ограничен -- в основном джойны и 
> сабселекты с подходящим WHERE.

> > > diff --git a/src/box/sql/where.c b/src/box/sql/where.c
> > > index e9e936856..6ab2be3ba 100644
> > > --- a/src/box/sql/where.c
> > > +++ b/src/box/sql/where.c
> > > @@ -683,7 +683,6 @@ translateColumnToCopy(Vdbe * v,		/* The VDBE containing code to translate */
> > >  	}
> > > +/**
> > > + * Generate a code that will create a tuple, which will be inserted in the
> > > + * autoindex. The created tuple consists of rowid and fields described in the
> > > + * index key description.
> > > + *
> > > + * @param parse Parsing context.
> > > + * @param key_def The index key description.
> > > + * @param cursor Cursor of space where we will get values for tuple.
> > > + * @param reg_out Register to which the created tuple will be placed.
> > > + * @param reg_eph Register holding pointer to autoindex.
> > > + *
> > > + * @return Return a register number which is the first in a block of registers
> > > + * that holds the elements of the created tuple. The block of registers has
> > > + * already been deallocated by the time this routine returns.
> > 
> > Не очень понял, зачем возвращать уже деаллоцированные регистры..
> > 
> Это значение используется в ветке if, которую я воспроизвести не смог. Насколько
> я понимаю это нужно для подсчета количества используемых регистров в случае
> использованию корутины. Если это так, это может быть необходимо для
> предварительного вычисления количества используемых в корутине регистров. Но это
> только мои предположения.

Может стоит все-таки разобраться, покрыть тестами там, или удалить мертвый код.
 
> > > + */
> > > +static int
> > > +vdbe_emit_create_autoindex_tuple(struct Parse *parse,
> > > +				 const struct key_def *key_def,
> > > +				 int cursor, int reg_out, int reg_eph)
> > > +{
> > > +	assert(reg_out != 0);
> > > +	struct Vdbe *v = parse->pVdbe;
> > > +	int col_cnt = key_def->part_count;
> > > +	int reg_base = sqlGetTempRange(parse, col_cnt + 1);
> > > +	for (int j = 0; j < col_cnt; j++) {
> > > +		uint32_t tabl_col = key_def->parts[j].fieldno;
> > > +		sqlVdbeAddOp3(v, OP_Column, cursor, tabl_col, reg_base + j);
> > > +	}
> > > +	sqlVdbeAddOp2(v, OP_NextIdEphemeral, reg_eph, reg_base + col_cnt);
> > > +	sqlVdbeAddOp3(v, OP_MakeRecord, reg_base, col_cnt + 1, reg_out);
> > > +	sqlReleaseTempRange(parse, reg_base, col_cnt + 1);
> > > +	return reg_base;
> > > +}
> > > +
> > >  /*
> > > - * Generate code to construct the Index object for an automatic index
> > > - * and to set up the WhereLevel object pLevel so that the code generator
> > > - * makes use of the automatic index.
> > > + * Generate code to construct the ephemeral space that contains all used in
> > > + * query fields of one of the tables. This ephemeral space will be known as an
> > 
> > Опять: какой таблицы..Очень запутывающий коммент имхо
> > 
> Будет лучше если я напишу "selected by planner table"?

Как минимум да
 
> > > + * "autoindex". PK of this ephemeral space is a covering index. Also, this
> > > + * functions set up the WhereLevel object pLevel so that the code generator
> > > + * makes use of the auto-index.
> > >   */
> > >  static void
> > >  constructAutomaticIndex(Parse * pParse,			/* The parsing context */
> > >  		}
> > >   * Estimate the location of a particular key among all keys in an
> > > -#ifndef SQL_OMIT_AUTOMATIC_INDEX
> > >  	/* Automatic indexes */
> > > -	LogEst rSize = pTab->nRowLogEst;
> > > +	rSize = DEFAULT_TUPLE_LOG_COUNT;
> > > +	/* Increase cost of autoindex if number of tuples in space < ~10000. */
> > 
> > 10k как-то маловато. В скулайте, если я правильно помню, какие-то подвижки
> > начинаются со 100к affected rows.
> > 
> Это значение было подобрано эксперементально. На подбор более точных эвристик
> есть отдельная задачу у @tsafin на следующий квартал.

На каких "экспериментальных данных"? Сейчас это выглядит оочень агрессивно

> > > +	if (!space->def->opts.is_view && sql_space_tuple_log_count(space) < 133)
> > > +		rSize += DEFAULT_TUPLE_LOG_COUNT;
> > 
> > Почему для представления это не работает?
> > 
> Скорее наоборот - у представлений стоимость автоиндекса не увеличивается, так
> что он используется чаще. Связано с тем, что посчитать количества таплов в
> представлении не в ран-тайме довольно проблематично. 

Так там сейчас все равно константа добавляется. С аналайзом можно и для
вью посчитать кол-во таплов.
 
> > >  	LogEst rLogSize = estLog(rSize);
> > >  	if (!pBuilder->pOrSet && /* Not pqart of an OR optimization */
> > >  	    (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) == 0 &&
> > >  	    (pWInfo->pParse->sql_flags & SQL_AutoIndex) != 0 &&
> > >  	    pSrc->pIBIndex == 0	/* Has no INDEXED BY clause */
> > >  	    && !pSrc->fg.notIndexed	/* Has no NOT INDEXED clause */
> > >  	    &&!pSrc->fg.isCorrelated	/* Not a correlated subquery */
> > >  	    && !pSrc->fg.isRecursive	/* Not a recursive common table expression. */
> > >  	    ) {
> > > @@ -2829,24 +2910,10 @@ tnt_error:
> > >  			if (termCanDriveIndex(pTerm, pSrc, 0)) {
> > >  				pNew->nEq = 1;
> > >  				pNew->nSkip = 0;
> > > -				pNew->pIndex = 0;
> > > +				pNew->index_def = NULL;
> > >  				pNew->nLTerm = 1;
> > >  				pNew->aLTerm[0] = pTerm;
> > > -				/* TUNING: One-time cost for computing the automatic index is
> > > -				 * estimated to be X*N*log2(N) where N is the number of rows in
> > > -				 * the table being indexed and where X is 7 (LogEst=28) for normal
> > > -				 * tables or 1.375 (LogEst=4) for views and subqueries.  The value
> > > -				 * of X is smaller for views and subqueries so that the query planner
> > > -				 * will be more aggressive about generating automatic indexes for
> > > -				 * those objects, since there is no opportunity to add schema
> > > -				 * indexes on subqueries and views.
> > > -				 */
> > > -				pNew->rSetup = rLogSize + rSize + 4;
> > > -				if (!pTab->def->opts.is_view &&
> > > -				    pTab->def->id == 0)
> > > -					pNew->rSetup += 24;
> > > -				if (pNew->rSetup < 0)
> > > -					pNew->rSetup = 0;
> > > +				pNew->rSetup = rLogSize + rSize;
> > 
> > Можешь объяснить, почему тут произошли изменения? То есть почему оптимизация
> > стала более агрессивной?
> > 
> Эти значение получены эксперементальным путем. Это так же будет уточняться в
> ходе подбора эвристик.

Ну не удаляй тогда код хотя бы, оставь там еще свой коммент какой-то.
Тот же кто потом с этим будет возиться в этом болоте утонет..

> > > diff --git a/test/sql-tap/autoindex1.test.lua b/test/sql-tap/autoindex1.test.lua
> > > new file mode 100755
> > > index 000000000..42b995dd3
> > > --- /dev/null
> > > +++ b/test/sql-tap/autoindex1.test.lua
> > > +---------------------------------------------------------------------------
> > > +--  This file implements regression tests for sql library.  The focus of this
> > > +-- script is testing automatic index creation logic.
> > > +
> > > +test:execsql([[
> > > +    CREATE TABLE t1(a INT, b INT PRIMARY KEY);
> > > +    INSERT INTO t1 VALUES(1, 11);
> > > +    INSERT INTO t1 VALUES(2, 22);
> > > +    INSERT INTO t1 SELECT a + 2, b + 22 FROM t1;
> > > +    INSERT INTO t1 SELECT a + 4, b + 44 FROM t1;
> > > +    CREATE TABLE t2(c INT, d INT PRIMARY KEY);
> > > +]])
> > > +
> > > +for i = 1, 11000 do test:execsql("INSERT INTO t2 VALUES ("..i..", "..i..");") end
> > 
> > Это быстро работает? Может сделать тест long-run?
> > Было бы еще неплохо к каждой группе тестов коммент, поясняющий почему
> > с эфмереной табличкой будет быстрее.
> > 
> На моем ноутбуке это работает быстро, быстрее чем некоторые другие стандартные
> SQL тесты. До появления сообщения о '10 second...' ни разу не дошло.
> Добавил коммент о том, что из-за автоиндекса тест работает быстрее, чем в случае
> если автоиндекс не используется.
> 
> 
> Diff:
> 
> +-- Make sure that autoindex is used in all cases below.

Я имел ввиду добавить объяснение, почему автоиндекс будет быстрее,
чем тыркание туда-сюда по таблицам. Можешь посмотреть примеры в тестах
на аналайз

>  test:execsql([[
>      CREATE TABLE t1(a INT, b INT PRIMARY KEY);
>      INSERT INTO t1 VALUES(1, 11);