[Tarantool-patches] [PATCH v3 1/1] sql: enable autoindex optimization
Nikita Pettik
korablev at tarantool.org
Thu Oct 15 04:40:56 MSK 2020
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 at tarantool.org wrote:
> > > From: Kirill Yukhin <kyukhin at 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 at gmail.com>
> > > Co-authored-by: Timur Safin <tsafin at 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);
More information about the Tarantool-patches
mailing list