Date: Mon, 6 Jan 2020 16:21:55 +0100
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Nikita Glukhov <n.gluhov@postgrespro.ru>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>,
	PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
	Tom Lane <tgl@sss.pgh.pa.us>, Julien Rouhaud <rjuju123@gmail.com>,
	Thomas Munro <thomas.munro@gmail.com>,
	Marc Cousin <cousinmarc@gmail.com>
Subject: Re: Avoid full GIN index scan when possible
Message-ID: <20200106152155.uuungi2p776p5lbk@development>
References: 
 <CAOBaU_b3u1xpoESb2JD6dQ4V7fhwmbfOFW5PiadZHJX6bNdnfw@mail.gmail.com>
 <17590.1564685940@sss.pgh.pa.us>
 <CAPpHfdvfK+Zk=MjjC1M_66+ALD+vdR6BG3quoFAZzjL6hNv-NQ@mail.gmail.com>
 <19189.1564687723@sss.pgh.pa.us>
 <a6e1564e-98c8-e420-cfaf-0309316c4910@postgrespro.ru>
 <19438.1565209940@sss.pgh.pa.us>
 <f2889144-db1d-e3b2-db97-cfc8794cda43@postgrespro.ru>
 <CAPpHfdsXN5iq3rUwjuwtp_GRFmhq+1QAtgiywGM_6YM9PdGdMg@mail.gmail.com>
 <CAPpHfdvT_t6ShG2pvptEWceDxEnyNRsm2MxmCWWvxBzQ-pbMuw@mail.gmail.com>
 <b53614eb-6f9f-8c5c-9df8-f703b0b102b6@postgrespro.ru>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <b53614eb-6f9f-8c5c-9df8-f703b0b102b6@postgrespro.ru>
Precedence: bulk

On Fri, Dec 27, 2019 at 04:36:14AM +0300, Nikita Glukhov wrote:
>On 26.12.2019 4:59, Alexander Korotkov wrote:
>>
>>狢've tried to add patch #4 to comparison, but I've catch assertion 
>>failure.
>>
>>TRAP: FailedAssertion("key->includeNonMatching", File: "ginget.c", 
>>Line: 1340)
>There simply should be inverted condition in the assertion:
>Assert(!key->includeNonMatching);
>
>I have looked at v9 patch, and here is my review:
>
>1. I agree with NULL-flag handling simplifications in ginNewScanKey(),
>ginScanKeyAddHiddenEntry() extraction.
>
>2. I also agree that usage of nrequired/nadditional in keyGetItem() is a more
>natural solution to implement exclusion keys than my previous attempt of doing
>that in scanGetKey().
>
>But there are some questions:
>
>Can we avoid referencing excludeOnly flag keyGetItem() by replacing these
>references with !nrequired?
>
>Maybe it would be better to move the whole block of keyGetItem() code
>starting from the first loop over required keys and ending before the loop over
>additional keys inside 'if (key->nrequired) { ... }'?
>
>Can we avoid introducing excludeOnly flag by reusing searchMode and/or by
>moving the initialization of nrequired/nadditional into ginNewScanKey()?
>
>
>3. The following two times repeated NULL-filtering check looks too complicated
>and needs to be refactored somehow:
>
>-	res = key->triConsistentFn(key);
>+	if (key->excludeOnly &&
>+		key->nuserentries < key->nentries &&
>+		key->scanEntry[key->nuserentries]->queryCategory == GIN_CAT_NULL_KEY &&
>+		key->entryRes[key->nuserentries] == GIN_TRUE)
>+		res = GIN_FALSE;
>+	else
>+		res = key->triConsistentFn(key);
>
>For example, a special consistentFn() can be introduced for such NOT_NULL
>scankeys.  Or even a hidden separate one-entry scankey with a trivial
>consistentFn() can be added instead of adding hidden entry.
>
>
>4. forcedRecheck flag that was previously used for discarded empty ALL scankeys
>is removed now.  0-entry exclusion keys can appear instead, and their
>consistentFn() simply returns constant value.  Could this lead to tangible
>overhead in some cases (in comparison to forcedRecheck flag)?
>
>
>5. A hidden GIN_CAT_EMPTY_QUERY is added only for the first empty ALL-scankey,
>NULLs in other columns are filtered out with GIN_CAT_NULL_KEY.  This looks like
>asymmetric, and it leads to accelerations is some cases and slowdowns in others
>(depending on NULL fractions and their correlations in columns).
>
>The following test shows a significant performance regression of v9:
>
>insert into t select array[i], NULL, NULL from generate_series(1, 1000000) i;
>
>                                       |        Query time, ms
>            WHERE condition            | master |   v8   |    v9
>---------------------------------------+--------+--------+---------
> a @> '{}'                             |    224 |    213 |    212
> a @> '{}' and b @> '{}'               |     52 |     57 |    255
> a @> '{}' and b @> '{}' and c @> '{}' |     51 |     58 |    290
>
>
>In the older version of the patch I tried to do the similar things (initialize
>only one NOT_NULL entry for the first column), but refused to do this in v8.
>
>So, to avoid slowdowns relative to master, I can offer simply to add
>GIN_CAT_EMPTY_QUERY entry for each column with empty ALL-keys if there are
>no normal keys.
>

Yeah, I can confirm those results, although on my system the timings are
a bit different (I haven't tested v8):

                                        |        Query time, ms
             WHERE condition            | master |    v9
---------------------------------------+--------+---------
  a @> '{}'                             |    610 |    589
  a @> '{}' and b @> '{}'               |    185 |    665
  a @> '{}' and b @> '{}' and c @> '{}' |    185 |    741

So that's something we probably need to address, perhaps by using the
GIN_CAT_EMPTY_QUERY entries as proposed.

I've also tested this on a database storing mailing lists archives with
a trigram index, and in that case the performance with short values gets
much better. The "messages" table has two text fields with a GIN trigram
index - subject and body, and querying them with short/long values works
like this:

                    WHERE                    |  master  |    v9
  --------------------------------------------------------------
  subject LIKE '%aa%' AND body LIKE '%xx%'   |    4943  |  4052
  subject LIKE '%aaa%' AND body LIKE '%xx%'  |      10  |    10
  subject LIKE '%aa%' AND body LIKE '%xxx%'  |     380  |    13
  subject LIKE '%aaa%' AND BODY LIKE '%xxx%' |       2  |     2

which seems fairly nice. I've done tests with individual columns, and
that seems to be working fine too.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services