Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1aISyC-0001T1-D2 for pgsql-hackers@arkaria.postgresql.org; Mon, 11 Jan 2016 03:16:36 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.84) (envelope-from ) id 1aISyB-0000RS-Rd for pgsql-hackers@arkaria.postgresql.org; Mon, 11 Jan 2016 03:16:35 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84) (envelope-from ) id 1aISyB-0000RM-7Z for pgsql-hackers@postgresql.org; Mon, 11 Jan 2016 03:16:35 +0000 Received: from mail-wm0-x235.google.com ([2a00:1450:400c:c09::235]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.84) (envelope-from ) id 1aISy1-0004ph-F0 for pgsql-hackers@postgresql.org; Mon, 11 Jan 2016 03:16:33 +0000 Received: by mail-wm0-x235.google.com with SMTP id b14so248016877wmb.1 for ; Sun, 10 Jan 2016 19:16:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=2ndquadrant-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=wa+7BIzwAjUTKIDZ51QNIeHRreEwMCP2AFCS2EFIxeo=; b=WyRUlV6BhH30OKw4+1c6X8Hr+QO8in9aGH3C3Qws6+yG/dN5rJEm19kOX5oWNqEsJA r0KOS7FNgvkhJrNzCFlf06Wr+HNPny9927LcKFuz0kJWbqPtvbPBolBbbRmFcUioXh7O MRvhj8uzM1MQ4/MIvOhZFFQvekIROQfkpj8osPB2NfsPK/PT3MLVmViugaMFbitVNpIV TqbcHNpkmzKsACjbn9Cmfd55Nd4X62GC8NESsQbhjTFCdlJ16ZsABZ9pVSoWFlyShsJ2 OA7tnfoJ2UnloX7eqLsWPDju45LwH0aEoymKp1thVhqP1hyhMFPThn3GExDsn4LFYbeH aN0Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=wa+7BIzwAjUTKIDZ51QNIeHRreEwMCP2AFCS2EFIxeo=; b=gYQLYzC0l4CmcujTgaC7s5N+0REJrb1EhpOd72JJNIKmlYeMMoo0W/CmFbxTRFMPDy ETKL+XAHKUzslaRJQNYr0FN+LMLLRbllDlm8MNz8AQqArd8B/codJSdprpsddAK0gb3c rcFx0756H75fNiVMiQtkoqh4SVFUOsb9BNhRuJTu5N53lewalbVzciF/bCby9PsiXR0J Lex5+U0FkUSa4yCPoMsF56Ic7a93mMMpYBdd4qGujtbDJREJvnLngzmoQh8JToNUm1xy 16JdNmLpFle76JooRfR0E4HIJWZn02il8nTFzLGHeqNTSWXr1imWpxNv/8/6V1NWhJAk R51Q== X-Gm-Message-State: ALoCoQk/7q71B8Hj0saVPDo02ny0nN3O1G/2nDHpxdn+mNpYI68zqWcrTPFbM+r2zNATbDIGVvyWbfkF3EbVDDGFCIelFMqFuV/5Yhmw94GR1NMLW5n8EJk= MIME-Version: 1.0 X-Received: by 10.194.117.163 with SMTP id kf3mr132243217wjb.139.1452482184023; Sun, 10 Jan 2016 19:16:24 -0800 (PST) Received: by 10.27.46.21 with HTTP; Sun, 10 Jan 2016 19:16:23 -0800 (PST) In-Reply-To: <567ED6CA.2040504@sigaev.ru> References: <567ED6CA.2040504@sigaev.ru> Date: Mon, 11 Jan 2016 16:16:23 +1300 Message-ID: Subject: Re: POC, WIP: OR-clause support for indexes From: David Rowley To: Teodor Sigaev Cc: Pgsql Hackers Content-Type: multipart/alternative; boundary=001a1130c84a9f2aac0529065cf1 X-Pg-Spam-Score: -2.6 (--) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org --001a1130c84a9f2aac0529065cf1 Content-Type: text/plain; charset=UTF-8 On 27 December 2015 at 07:04, Teodor Sigaev wrote: > I'd like to present OR-clause support for indexes. Although OR-clauses > could be supported by bitmapOR index scan it isn't very effective and such > scan lost any order existing in index. We (with Alexander Korotkov) > presented results on Vienna's conference this year. In short, it provides > performance improvement: > > EXPLAIN ANALYZE > SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000; > me=0.080..0.267 rows=173 loops=1) > Recheck Cond: ((id = 5) OR (id = 500) OR (id = 5000)) > Heap Blocks: exact=172 > -> Bitmap Index Scan on idx_gin (cost=0.00..57.50 rows=15000 > width=0) (actual time=0.059..0.059 rows=147 loops=1) > Index Cond: ((id = 5) OR (id = 500) OR (id = 5000)) > Planning time: 0.077 ms > Execution time: 0.308 ms <------- > QUERY PLAN > > ----------------------------------------------------------------------------------------------------------------------------------- > Aggregate (cost=51180.53..51180.54 rows=1 width=0) (actual > time=796.766..796.766 rows=1 loops=1) > -> Index Only Scan using idx_btree on tst (cost=0.42..51180.40 > rows=55 width=0) (actual time=0.444..796.736 rows=173 loops=1) > Filter: ((id = 5) OR (id = 500) OR (id = 5000)) > Rows Removed by Filter: 999829 > Heap Fetches: 1000002 > Planning time: 0.087 ms > Execution time: 796.798 ms <------ > QUERY PLAN > > ------------------------------------------------------------------------------------------------------------- > Aggregate (cost=21925.63..21925.64 rows=1 width=0) (actual > time=160.412..160.412 rows=1 loops=1) > -> Seq Scan on tst (cost=0.00..21925.03 rows=237 width=0) (actual > time=0.535..160.362 rows=175 loops=1) > Filter: ((id = 5) OR (id = 500) OR (id = 5000)) > Rows Removed by Filter: 999827 > Planning time: 0.459 ms > Execution time: 160.451 ms > > > It also could work together with KNN feature of GiST and in this case > performance improvement could be up to several orders of magnitude, in > artificial example it was 37000 times faster. > > Not all indexes can support oR-clause, patch adds support to GIN, GiST > and BRIN indexes. pg_am table is extended for adding amcanorclause column > which indicates possibility of executing of OR-clause by index. > > indexqual and indexqualorig doesn't contain implicitly-ANDed list of > index qual expressions, now that lists could contain OR RestrictionInfo. > Actually, the patch just tries to convert BitmapOr node to IndexScan or > IndexOnlyScan. Thats significantly simplifies logic to find possible > clause's list for index. > Index always gets a array of ScanKey but for indexes which support > OR-clauses > array of ScanKey is actually exection tree in reversed polish notation > form. Transformation is done in ExecInitIndexScan(). > > The problems on the way which I see for now: > 1 Calculating cost. Right now it's just a simple transformation of costs > computed for BitmapOr path. I'd like to hope that's possible and so index's > estimation function could be non-touched. So, they could believe that all > clauses are implicitly-ANDed > 2 I'd like to add such support to btree but it seems that it should be a > separated patch. Btree search algorithm doesn't use any kind of stack of > pages and algorithm to walk over btree doesn't clear for me for now. > 3 I could miss some places which still assumes implicitly-ANDed list of > clauses although regression tests passes fine. > > Hope, hackers will not have an strong objections to do that. But obviously > patch > requires further work and I'd like to see comments, suggestions and > recommendations. Thank you. Hi, I'd like to see comments too! but more so in the code. :) I've had a look over this, and it seems like a great area in which we could improve on, and your reported performance improvements are certainly very interesting too. However I'm finding the code rather hard to follow, which might be a combination of my lack of familiarity with the index code, but more likely it's the lack of comments to explain what's going on. Let's just take 1 function as an example: Here there's not a single comment, so I'm just going to try to work out what's going on based on the code. +static void +compileScanKeys(IndexScanDesc scan) +{ + GISTScanOpaque so = (GISTScanOpaque) scan->opaque; + int *stack, + stackPos = -1, + i; + + if (scan->numberOfKeys <= 1 || so->useExec == false) + return; + + Assert(scan->numberOfKeys >=3); Why can numberOfKeys never be 2? I looked at what calls this and I can't really work it out. I'm really also not sure what useExec means as there's no comment in that struct member, and what if numberOfKeys == 1 and useExec == false, won't this Assert() fail? If that's not a possible situation then why not? + + if (so->leftArgs != NULL) + return; + + so->leftArgs = MemoryContextAlloc(so->giststate->scanCxt, + sizeof(*so->leftArgs) * scan->numberOfKeys); + so->rightArgs = MemoryContextAlloc(so->giststate->scanCxt, + sizeof(*so->rightArgs) * scan->numberOfKeys); + + stack = palloc(sizeof(*stack) * scan->numberOfKeys); + + for(i=0; inumberOfKeys; i++) + { + ScanKey key = scan->keyData + i; Is there a reason not to use keyData[i]; ? + + if (stackPos >= 0 && (key->sk_flags & (SK_OR | SK_AND))) + { + Assert(stackPos >= 1 && stackPos < scan->numberOfKeys); stackPos >= 1? This seems unnecessary and confusing as the if test surely makes that impossible. + + so->leftArgs[i] = stack[stackPos - 1]; Something is broken here as stackPos can be 0 (going by the if() not the Assert()), therefore that's stack[-1]. + so->rightArgs[i] = stack[stackPos]; + stackPos--; + } + else + { + stackPos++; + } + stackPos is initialised to -1, so this appears to always skip the first element of the keyData array. If that's really the intention, then wouldn't it be better to just make the initial condition of the for() look i = 1 ? + stack[stackPos] = i; + } + + Assert(stackPos == 0); + pfree(stack); +} I'd like to review more, but it feels like a job that's more difficult than it needs to be due to lack of comments. Would it be possible to update the patch to try and explain things a little better? Many thanks David -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services --001a1130c84a9f2aac0529065cf1 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On 2= 7 December 2015 at 07:04, Teodor Sigaev <teodor@sigaev.ru> wr= ote:
I'd like to present OR-clause support for inde= xes. Although OR-clauses could be supported by bitmapOR index scan it isn&#= 39;t very effective and such scan lost any order existing in index. We (wit= h Alexander Korotkov) presented results on Vienna's conference this yea= r. In short, it provides performance improvement:

EXPLAIN ANALYZE
SELECT count(*) FROM tst WHERE id =3D 5 OR id =3D 500 OR id =3D 5000;
me=3D0.080..0.267 rows=3D173 loops=3D1)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Recheck Cond: ((id =3D 5) OR (id =3D 500)= OR (id =3D 5000))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Heap Blocks: exact=3D172
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0->=C2=A0 Bitmap Index Scan on idx_gin= =C2=A0 (cost=3D0.00..57.50 rows=3D15000 width=3D0) (actual time=3D0.059..0.= 059 rows=3D147 loops=3D1)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Index Cond: ((id =3D= 5) OR (id =3D 500) OR (id =3D 5000))
=C2=A0Planning time: 0.077 ms
=C2=A0Execution time: 0.308 ms=C2=A0 =C2=A0<-------
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 QUERY PLAN <= br> ---------------------------------------------------------------------------= --------------------------------------------------------
=C2=A0Aggregate=C2=A0 (cost=3D51180.53..51180.54 rows=3D1 width=3D0) (actua= l time=3D796.766..796.766 rows=3D1 loops=3D1)
=C2=A0 =C2=A0->=C2=A0 Index Only Scan using idx_btree on tst=C2=A0 (cost= =3D0.42..51180.40 rows=3D55 width=3D0) (actual time=3D0.444..796.736 rows= =3D173 loops=3D1)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Filter: ((id =3D 5) OR (id =3D 500) OR (i= d =3D 5000))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Rows Removed by Filter: 999829
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Heap Fetches: 1000002
=C2=A0Planning time: 0.087 ms
=C2=A0Execution time: 796.798 ms=C2=A0 <------
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 QUERY PLAN
---------------------------------------------------------------------------= ----------------------------------
=C2=A0Aggregate=C2=A0 (cost=3D21925.63..21925.64 rows=3D1 width=3D0) (actua= l time=3D160.412..160.412 rows=3D1 loops=3D1)
=C2=A0 =C2=A0->=C2=A0 Seq Scan on tst=C2=A0 (cost=3D0.00..21925.03 rows= =3D237 width=3D0) (actual time=3D0.535..160.362 rows=3D175 loops=3D1)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Filter: ((id =3D 5) OR (id =3D 500) OR (i= d =3D 5000))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Rows Removed by Filter: 999827
=C2=A0Planning time: 0.459 ms
=C2=A0Execution time: 160.451 ms


It also could work together with KNN feature of GiST and in this case perfo= rmance improvement could be up to several orders of magnitude, in artificia= l example it was 37000 times faster.

Not all=C2=A0 indexes can support oR-clause, patch adds support to GIN, GiS= T and BRIN indexes. pg_am table is extended for adding amcanorclause column= which indicates possibility of executing of OR-clause by index.

=C2=A0indexqual and indexqualorig doesn't contain implicitly-ANDed list= of index qual expressions, now that lists could contain OR RestrictionInfo= . Actually, the patch just tries to convert BitmapOr node to IndexScan or I= ndexOnlyScan. Thats significantly simplifies logic to find possible clause&= #39;s list for index.
Index always gets a array of ScanKey but for indexes which support OR-claus= es
array=C2=A0 of ScanKey is actually exection tree in reversed polish notatio= n form. Transformation is done in ExecInitIndexScan().

The problems on the way which I see for now:
1 Calculating cost. Right now it's just a simple transformation of cost= s computed for BitmapOr path. I'd like to hope that's possible and = so index's estimation function could be non-touched. So, they could bel= ieve that all clauses are implicitly-ANDed
2 I'd like to add such support to btree but it seems that it should be = a separated patch. Btree search algorithm doesn't use any kind of stack= of pages and algorithm to walk over btree doesn't clear for me for now= .
3 I could miss some places which still assumes=C2=A0 implicitly-ANDed list = of clauses although regression tests passes fine.

Hope, hackers will not have an strong objections to do that. But obviously = patch
requires further work and I'd like to see comments, suggestions and rec= ommendations. Thank you.

Hi,

=
I'd like to see comments too! but more so in the code. :) I&= #39;ve had a look over this, and it seems like a great area in which we cou= ld improve on, and your reported performance improvements are certainly ver= y interesting too. However I'm finding the code rather hard to follow, = which might be a combination of my lack of familiarity with the index code,= but more likely it's the lack of comments to explain what's going = on. Let's just take 1 function as an example:

= Here there's not a single comment, so I'm just going to try to work= out what's going on based on the code.

+= static void
+compileScanKeys(IndexScanDesc scan)
+{
+ GISTScanOpaque so =3D (GISTScanOpaque) sc= an->opaque;
+ int *stack,
+ stackPos =3D -1,<= /div>
+ i;
<= div>+
+ if (sca= n->numberOfKeys <=3D 1 || so->useExec =3D=3D false)
+ return;
+
<= div>+ Assert(scan->num= berOfKeys >=3D3);

Why can numberOfKeys never be= 2? I looked at what calls this and I can't really work it out. I'm= really also not sure what useExec means as there's no comment in that = struct member, and what if numberOfKeys =3D=3D 1 and useExec =3D=3D false, = won't this Assert() fail? If that's not a possible situation then w= hy not?=C2=A0

+
+ if (so->leftArgs !=3D NULL)
+ return;
+
+ so->leftArgs =3D = MemoryContextAlloc(so->giststate->scanCxt,
+ =C2=A0sizeof(*so->leftArgs)= * scan->numberOfKeys);
+ so->rightArgs =3D MemoryContextAlloc(so->giststate->= scanCxt,
+ =C2=A0 sizeof(*so->rightArgs) * scan->numberOfKeys);
+=
+ stack =3D pa= lloc(sizeof(*stack) * scan->numberOfKeys);
+
+ for(i=3D0; i<scan->numbe= rOfKeys; i++)
+ {
+ ScanKey = =C2=A0 =C2=A0 key =3D scan->keyData + i;

Is the= re a reason not to use keyData[i]; ?

+
+= if (stackPos >=3D 0 = && (key->sk_flags & (SK_OR | SK_AND)))
+ {
+ Assert(stackPos >=3D 1 && stack= Pos < scan->numberOfKeys);

stackPos >=3D = 1? This seems unnecessary and confusing as the if test surely makes that im= possible.=C2=A0
+
+ so->leftArgs[i] =3D stack[stackPos - 1];

=
Something is broken here as stackPos can be 0 (going by the if()= not the Assert()), therefore that's stack[-1].

+ so->rightArgs[i]= =3D stack[stackPos];
+ stackPos--;
+ }
+ else
+ {
+ stackPos++;
+ }
+
=C2=A0
stackPos is initialised to -1, so this appears to= always skip the first element of the keyData array. If that's really t= he intention, then wouldn't it be better to just make the initial condi= tion of the for() look i =3D 1 ?=C2=A0

+ stack[stackPos] =3D i;
= + }
+
+ Assert(stackPos =3D=3D= 0);
+ pfree(st= ack);
+}

I'd like to review m= ore, but it feels like a job that's more difficult than it needs to be = due to lack of comments.

Would it be possible to update the patch to try and expl= ain things a little better?

Many thanks

David

--
=C2=A0David Rowley =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0http://www.2ndQuadrant.com/
=C2=A0Postgre= SQL Development, 24x7 Support, Training & Services
--001a1130c84a9f2aac0529065cf1--