From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp46.i.mail.ru (smtp46.i.mail.ru [94.100.177.106]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 3CEC1469719 for ; Thu, 15 Oct 2020 04:40:58 +0300 (MSK) Date: Thu, 15 Oct 2020 01:40:56 +0000 From: Nikita Pettik Message-ID: <20201015014056.GB25221@tarantool.org> References: <5c615731b1bd3e6d279dfb0cbc92823dea993a03.1602413265.git.imeevma@gmail.com> <20201013140833.GA18852@tarantool.org> <20201014093019.GA360354@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20201014093019.GA360354@tarantool.org> Subject: Re: [Tarantool-patches] [PATCH v3 1/1] sql: enable autoindex optimization List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Mergen Imeev Cc: Mergen Imeev , tarantool-patches@dev.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 > > > > > > 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 > > > Co-authored-by: Timur Safin > > > --- > > > 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);