From: "n.pettik" <korablev@tarantool.org> To: tarantool-patches@freelists.org Cc: Vladislav Shpilevoy <v.shpilevoy@tarantool.org> Subject: [tarantool-patches] Re: [PATCH 3/6] sql: refactor arithmetic operations to support unsigned ints Date: Wed, 17 Jul 2019 15:24:44 +0300 [thread overview] Message-ID: <E9D846F0-333F-4A8C-A907-DC45F45BD74A@tarantool.org> (raw) In-Reply-To: <ba4b1598-867f-40f2-63c6-f16235043c55@tarantool.org> > I did this: > > @@ -4943,7 +4943,7 @@ case OP_OffsetLimit: { /* in1, out2, in3 */ > uint64_t x = pIn1->u.u; > uint64_t rhs = pIn3->u.u; > bool unused; > - if (x == 0 || sql_add_int(x, false, rhs, false, (int64_t *) &x, > + if (x == 0 || sql_add_int(x, true, rhs, false, (int64_t *) &x, > &unused) != 0) { > /* If the LIMIT is less than or equal to zero, loop forever. This > * is documented. But also, if the LIMIT+OFFSET exceeds 2^63 then > > And the tests passed. Looks like a test was not added. Ok, I’ve dived a bit into this code and added auxiliary commit: commit b954fac26809286f764e4509335c0ee7b63d42c2 (HEAD) Author: Nikita Pettik <korablev@tarantool.org> Date: Tue Jul 16 19:25:05 2019 +0300 sql: refactor VDBE opcode OP_OffsetLimit OP_OffsetLimit instruction calculates sum of OFFSET and LIMIT values when they are present. This sum serves as a counter of entries to be inserted to temporary space during VDBE execution. Consider query like: SELECT * FROM t ORDER BY x LIMIT 5 OFFSET 2; To perform ordering alongside with applying limit and offset restrictions, first 7 (5 + 2) entries are inserted into temporary space. They are sorted and then first two tuples are skipped according to offset clause. The rest tuples from temporary space get to result set. When sum of LIMIT and OFFSET values is big enough to cause integer overflow, we can't apply this approach. Previously, counter was simply set to -1 which means that all entries from base table will be transferred to ephemeral space. As a result, LIMIT clause was ignored and the result of query would be incorrect. Motivation for this obviously wrong step was that to perform query with such huge limit and offset values too many time is required (like years). What is more, ephemeral spaces support auto-generated IDs in the range up to 2^32, so there's even no opportunity to process such queries in theory. Nevertheless, to make code cleaner let's fix this tricky place and just raise an overflow error if result of addition exceeds integer range. This patch fixes obsolete comments saying that in case of overflow execution won't stop; now limit and offset counter are always >= 0, so removed redundant branching. diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c index 181f71deb..e349af68f 100644 --- a/src/box/sql/vdbe.c +++ b/src/box/sql/vdbe.c @@ -4861,7 +4861,7 @@ case OP_IfPos: { /* jump, in1 */ } /* Opcode: OffsetLimit P1 P2 P3 * * - * Synopsis: if r[P1]>0 then r[P2]=r[P1]+max(0,r[P3]) else r[P2]=(-1) + * Synopsis: r[P2]=r[P1]+r[P3] * * This opcode performs a commonly used computation associated with * LIMIT and OFFSET process. r[P1] holds the limit counter. r[P3] @@ -4870,35 +4870,23 @@ case OP_IfPos: { /* jump, in1 */ * value computed is the total number of rows that will need to be * visited in order to complete the query. * - * If r[P3] is zero or negative, that means there is no OFFSET - * and r[P2] is set to be the value of the LIMIT, r[P1]. - * - * if r[P1] is zero or negative, that means there is no LIMIT - * and r[P2] is set to -1. - * - * Otherwise, r[P2] is set to the sum of r[P1] and r[P3]. + * Otherwise, r[P2] is set to the sum of r[P1] and r[P3]. If the + * sum is larger than 2^63-1 (i.e. overflow takes place) then + * error is raised. */ case OP_OffsetLimit: { /* in1, out2, in3 */ - i64 x; pIn1 = &aMem[pOp->p1]; pIn3 = &aMem[pOp->p3]; pOut = out2Prerelease(p, pOp); assert(pIn1->flags & MEM_Int); assert(pIn3->flags & MEM_Int); - x = pIn1->u.i; - if (x<=0 || sqlAddInt64(&x, pIn3->u.i>0?pIn3->u.i:0)) { - /* If the LIMIT is less than or equal to zero, loop forever. This - * is documented. But also, if the LIMIT+OFFSET exceeds 2^63 then - * also loop forever. This is undocumented. In fact, one could argue - * that the loop should terminate. But assuming 1 billion iterations - * per second (far exceeding the capabilities of any current hardware) - * it would take nearly 300 years to actually reach the limit. So - * looping forever is a reasonable approximation. - */ - pOut->u.i = -1; - } else { - pOut->u.i = x; + i64 x = pIn1->u.i; + if (sqlAddInt64(&x, pIn3->u.i) != 0) { + diag_set(ClientError, ER_SQL_EXECUTE, "sum of LIMIT and OFFSET " + "values should not result in integer overflow"); + goto abort_due_to_error; } + pOut->u.i = x; break; } diff --git a/test/sql-tap/limit.test.lua b/test/sql-tap/limit.test.lua index 40b787b52..84d0798db 100755 --- a/test/sql-tap/limit.test.lua +++ b/test/sql-tap/limit.test.lua @@ -1,6 +1,6 @@ #!/usr/bin/env tarantool test = require("sqltester") -test:plan(111) +test:plan(113) --!./tcltestrunner.lua -- 2001 November 6 @@ -1354,4 +1354,18 @@ test:do_execsql_test( -- </limit-14.7.2> }) +-- Sum of LIMIT and OFFSET values should not cause integer overflow. +-- +test:do_catchsql_test( + "limit-15.1", + [[ + SELECT 1 LIMIT 9223372036854775807 OFFSET 1; + ]], { 1, "Failed to execute SQL statement: sum of LIMIT and OFFSET values should not result in integer overflow" } ) + +test:do_catchsql_test( + "limit-15.2", + [[ + SELECT 1 LIMIT 1 OFFSET 9223372036854775807; + ]], { 1, "Failed to execute SQL statement: sum of LIMIT and OFFSET values should not result in integer overflow "} ) + test:finish_test()
next prev parent reply other threads:[~2019-07-17 12:24 UTC|newest] Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-06-07 15:37 [tarantool-patches] [PATCH 0/6] Introduce UNSIGNED type in SQL Nikita Pettik 2019-06-07 15:37 ` [tarantool-patches] [PATCH 1/6] sql: refactor sql_atoi64() Nikita Pettik 2019-06-11 21:11 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-01 14:20 ` n.pettik 2019-07-01 21:53 ` Vladislav Shpilevoy 2019-07-05 16:32 ` n.pettik 2019-06-07 15:37 ` [tarantool-patches] [PATCH 2/6] sql: separate VDBE memory holding positive and negative ints Nikita Pettik 2019-06-11 21:11 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-01 14:21 ` n.pettik 2019-07-01 21:53 ` Vladislav Shpilevoy 2019-07-05 16:33 ` n.pettik 2019-06-07 15:37 ` [tarantool-patches] [PATCH 3/6] sql: refactor arithmetic operations to support unsigned ints Nikita Pettik 2019-06-11 21:11 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-01 14:21 ` n.pettik 2019-07-01 21:53 ` Vladislav Shpilevoy 2019-07-05 16:36 ` n.pettik 2019-07-10 22:49 ` Vladislav Shpilevoy 2019-07-17 12:24 ` n.pettik [this message] 2019-06-07 15:37 ` [tarantool-patches] [PATCH 4/6] sql: make built-in functions operate on unsigned values Nikita Pettik 2019-06-11 21:11 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-01 14:21 ` n.pettik 2019-07-01 21:53 ` Vladislav Shpilevoy 2019-07-05 16:36 ` n.pettik 2019-07-10 22:49 ` Vladislav Shpilevoy 2019-07-17 0:53 ` n.pettik 2019-06-07 15:37 ` [tarantool-patches] [PATCH 5/6] sql: introduce extended range for INTEGER type Nikita Pettik 2019-06-11 21:11 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-01 14:21 ` n.pettik 2019-07-01 21:53 ` Vladislav Shpilevoy 2019-07-24 15:59 ` Konstantin Osipov 2019-07-24 16:54 ` n.pettik 2019-07-24 17:09 ` Konstantin Osipov 2019-06-07 15:37 ` [tarantool-patches] [PATCH 6/6] sql: allow to specify UNSIGNED column type Nikita Pettik 2019-07-01 21:53 ` [tarantool-patches] " Vladislav Shpilevoy 2019-07-05 16:36 ` n.pettik 2019-07-10 22:49 ` Vladislav Shpilevoy 2019-07-11 21:25 ` Vladislav Shpilevoy 2019-07-17 0:53 ` n.pettik 2019-07-18 20:18 ` Vladislav Shpilevoy 2019-07-18 20:56 ` n.pettik 2019-07-18 21:08 ` Vladislav Shpilevoy 2019-07-18 21:13 ` Vladislav Shpilevoy 2019-07-22 10:20 ` n.pettik 2019-07-22 19:17 ` Vladislav Shpilevoy 2019-07-22 10:20 ` n.pettik 2019-07-17 0:54 ` n.pettik 2019-07-18 20:18 ` Vladislav Shpilevoy 2019-08-06 19:36 ` n.pettik 2019-07-24 13:01 ` [tarantool-patches] Re: [PATCH 0/6] Introduce UNSIGNED type in SQL Kirill Yukhin
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=E9D846F0-333F-4A8C-A907-DC45F45BD74A@tarantool.org \ --to=korablev@tarantool.org \ --cc=tarantool-patches@freelists.org \ --cc=v.shpilevoy@tarantool.org \ --subject='[tarantool-patches] Re: [PATCH 3/6] sql: refactor arithmetic operations to support unsigned ints' \ /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