Subject: Re: Avoid full GIN index scan when possible
References: 
 <CAOBaU_YGP5-BEt5Cc0=zMve92vocPzD+XiZgiZs1kjY0cj=XBg@mail.gmail.com>
 <CAOBaU_ZCg4955_HGcQZdn44wtTQRpiHkLgkVsxqQ5cfymDL-XQ@mail.gmail.com>
 <20190628161051.szk2kxmue6yjdmra@development>
 <CAOBaU_ZCJBm3mGvJpMN4VX4Q2oQvgPEwMA1jJyrb7-P0HJbnQA@mail.gmail.com>
 <4547.1561748599@sss.pgh.pa.us> <20190628195401.frwhcga76rrytbc4@development>
 <7773.1561752983@sss.pgh.pa.us>
 <CAOBaU_bDF-7E5x0WVPmmtoc+0z7S3hmcXnnV+1ggy8CMGyZxgg@mail.gmail.com>
From: Marc Cousin <cousinmarc@gmail.com>
Openpgp: preference=signencrypt
Autocrypt: addr=cousinmarc@gmail.com; keydata=
 mQENBFlwwSIBCACtPV+Ciu0/ZrcUzC+KScvsGgfg5pYz2pKoZr8o3UIko2kRPiycsw2or98k
 6YnfLmGm/l46712vWclyJhlZhO/LTHQlMOqK51JfxQDcJPqaZHFDuXz+5IRn/Jq4GLRU+vbM
 ZMmii3Nvh2FgHU65smSSWnmlG261U4uDUklEjyq9c7KIayyfV6mo8Yx1JplDql8dYGVqFy2x
 MHIVrXGz+4HSl+ttXWIp4hfb+SFBjhVsWjP6Gkb4tWQp5AmP5zn/U002AxbK7d4aEUDIYh/M
 hioYzI9AyoEqVFRuQoqLUgZC2tmAoyemtG2xznHRoNfRLkWUP1w4LxdIF6RHVm/LCg+VABEB
 AAG0Ik1hcmMgQ291c2luIDxjb3VzaW5tYXJjQGdtYWlsLmNvbT6JAU4EEwEIADgWIQStEkWi
 pDVaYcLm2jT298ZWi8CQnwUCWXDBIgIbAwULCQgHAgYVCAkKCwIEFgIDAQIeAQIXgAAKCRD2
 98ZWi8CQn54gB/91jBW7cwU+yaZ64z32PlyKZMn/3JFV1A1R6hehlTaiI/w0/szKpre9n5BR
 pQSzOUUGlquZ1flMozyR9vud/wuNXU3FE9YI8cmHOJgAYUEtQaiSNLEMfdl55SADYkLKNJot
 0jDf8NFiSfu3Qaw5pRlwi5+LFfm48PpQtCyLsxjntrYcuRB0PBLaMbCwbMfhyfBFTI3/nN4b
 K9hIHmK9Vecg7l55NAz99dIyzcHLk5sSE/MPXd8wlV4kACWH1+CuItioO3sUcAlLvCB0QzcE
 zdpc9wJl1rE7cTYG+/4EGKJ0AZyIPWN9ApUWrRAsY8YByHRv7JGgj8U8IC65pCkCQG1quQEN
 BFlwwSIBCADBVrMqQ+BHb6YVuTiSigcleaMH1A2Sb7aF5UZXdsrUI0EmFEWeUABD6g+MC0Pg
 78Xg0L3SdmW7nAz+l1AoX6HYP0jgxVlRCOXcTfDdVBg8wsgYyjv8Ar4JkOvOWwDwhtcwHQfc
 xeCAUghtI1tvgaw297gx9KFu6czwBjwLIBMpHUPcYze4HryMct1z/NMUwduRyoT1hlZq8dNe
 sG8AON+9It1lXHm3CI55iEIeTDlkPJBhl4ngxPeWSNoe1XnW1qtyrQJ9ICuddP4Ty9JEuTQ8
 LA6ljiqDF//5/05gw38IelGMevuNOA2I6l228qtWmgYaB7tfoLKJdUCGPAr4u3etABEBAAGJ
 ATYEGAEIACAWIQStEkWipDVaYcLm2jT298ZWi8CQnwUCWXDBIgIbDAAKCRD298ZWi8CQn7Fv
 B/9t4EuKxWEzjdLciVtoL+Pm4KcwRQbqiUg30J1REZnuEXHvdfAqxDcC5QWiNzu9occnbcxa
 cFoUtA83dseDlAT1uL1eUdv8njY8GE12IO9KLdH8JfzR4sQGimEJ3YC+yY18aHi7v9M2EY3f
 uArH0LNik82kjF+8U5ndsSlkJ/WD8fR82SQkZuNYoeCIfa+p/VKn7f8Ommz27WtMa6IfCFj1
 O8PNaDkr3YUVSpWimSJPmNXm+xbsyDWSbP6M6M6IVt9sOcdl+ohQDrK+5mfYjRACPrTGOe1z
 5CB21gJ8KsVxvolvJIgsIm8qytOdEyOdY6wDW2rb4ZZuHWk7bstcN08F
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Message-ID: <eca8612b-e289-e2fc-c5df-84be46f75ec1@gmail.com>
Date: Mon, 1 Jul 2019 17:56:17 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.7.2
MIME-Version: 1.0
In-Reply-To: 
 <CAOBaU_bDF-7E5x0WVPmmtoc+0z7S3hmcXnnV+1ggy8CMGyZxgg@mail.gmail.com>
Content-Type: multipart/signed; micalg=pgp-sha256;
 protocol="application/pgp-signature";
 boundary="euD5Kz8gxmDHiXXO3IlMb2YiPeAnVv1KO"
Precedence: bulk

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--euD5Kz8gxmDHiXXO3IlMb2YiPeAnVv1KO
Content-Type: multipart/mixed; boundary="5IGAZF2HZhDTbPaIP0cgnElDMW8XIG88f";
 protected-headers="v1"
From: Marc Cousin <cousinmarc@gmail.com>
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Message-ID: <eca8612b-e289-e2fc-c5df-84be46f75ec1@gmail.com>
Subject: Re: Avoid full GIN index scan when possible
References: <CAOBaU_YGP5-BEt5Cc0=zMve92vocPzD+XiZgiZs1kjY0cj=XBg@mail.gmail.com>
 <CAOBaU_ZCg4955_HGcQZdn44wtTQRpiHkLgkVsxqQ5cfymDL-XQ@mail.gmail.com>
 <20190628161051.szk2kxmue6yjdmra@development>
 <CAOBaU_ZCJBm3mGvJpMN4VX4Q2oQvgPEwMA1jJyrb7-P0HJbnQA@mail.gmail.com>
 <4547.1561748599@sss.pgh.pa.us> <20190628195401.frwhcga76rrytbc4@development>
 <7773.1561752983@sss.pgh.pa.us>
 <CAOBaU_bDF-7E5x0WVPmmtoc+0z7S3hmcXnnV+1ggy8CMGyZxgg@mail.gmail.com>
In-Reply-To: <CAOBaU_bDF-7E5x0WVPmmtoc+0z7S3hmcXnnV+1ggy8CMGyZxgg@mail.gmail.com>

--5IGAZF2HZhDTbPaIP0cgnElDMW8XIG88f
Content-Type: text/plain; charset=utf-8
Content-Language: en-US-large
Content-Transfer-Encoding: quoted-printable

On 29/06/2019 00:23, Julien Rouhaud wrote:
> On Fri, Jun 28, 2019 at 10:16 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>
>> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>>> On Fri, Jun 28, 2019 at 03:03:19PM -0400, Tom Lane wrote:
>>>> I not only don't want that function in indxpath.c, I don't even want=

>>>> it to be known/called from there.  If we need the ability for the in=
dex
>>>> AM to editorialize on the list of indexable quals (which I'm not ver=
y
>>>> convinced of yet), let's make an AM interface function to do it.
>>
>>> Wouldn't it be better to have a function that inspects a single qual =
and
>>> says whether it's "optimizable" or not? That could be part of the AM
>>> implementation, and we'd call it and it'd be us messing with the list=
=2E
>>
>> Uh ... we already determined that the qual is indexable (ie is a membe=
r
>> of the index's opclass), or allowed the index AM to derive an indexabl=
e
>> clause from it, so I'm not sure what you envision would happen
>> additionally there.  If I understand what Julien is concerned about
>> --- and I may not --- it's that the set of indexable clauses *as a who=
le*
>> may have or lack properties of interest.  So I'm thinking the answer
>> involves some callback that can do something to the whole list, not
>> qual-at-a-time.  We've already got facilities for the latter case.
>=20
> Yes, the root issue here is that with gin it's entirely possible that
> "WHERE sometable.col op value1" is way more efficient than "WHERE
> sometable.col op value AND sometable.col op value2", where both qual
> are determined indexable by the opclass.  The only way to avoid that
> is indeed to inspect the whole list, as done in this poor POC.
>=20
> This is a problem actually hit in production, and as far as I know
> there's no easy way from the application POV to prevent unexpected
> slowdown.  Maybe Marc will have more details about the actual problem
> and how expensive such a case was compared to the normal ones.

Sorry for the delay...

Yes, quite easily, here is what we had (it's just a bit simplified, we ha=
ve other criterions but I think it shows the problem):

rh2=3D> explain analyze select * from account_employee where typeahead li=
ke '%albert%';
                                                                       QU=
ERY PLAN                                                                 =
     =20
-------------------------------------------------------------------------=
-------------------------------------------------------------------------=
------
 Bitmap Heap Scan on account_employee  (cost=3D53.69..136.27 rows=3D734 w=
idth=3D666) (actual time=3D15.562..35.044 rows=3D8957 loops=3D1)
   Recheck Cond: (typeahead ~~ '%albert%'::text)
   Rows Removed by Index Recheck: 46
   Heap Blocks: exact=3D8919
   ->  Bitmap Index Scan on account_employee_site_typeahead_gin_idx  (cos=
t=3D0.00..53.51 rows=3D734 width=3D0) (actual time=3D14.135..14.135 rows=3D=
9011 loops=3D1)
         Index Cond: (typeahead ~~ '%albert%'::text)
 Planning time: 0.224 ms
 Execution time: 35.389 ms
(8 rows)

rh2=3D> explain analyze select * from account_employee where typeahead li=
ke '%albert%' and typeahead like '%lo%';
                                                                         =
  QUERY PLAN                                                             =
             =20
-------------------------------------------------------------------------=
-------------------------------------------------------------------------=
--------------
 Bitmap Heap Scan on account_employee  (cost=3D28358.38..28366.09 rows=3D=
67 width=3D666) (actual time=3D18210.109..18227.134 rows=3D1172 loops=3D1=
)
   Recheck Cond: ((typeahead ~~ '%albert%'::text) AND (typeahead ~~ '%lo%=
'::text))
   Rows Removed by Index Recheck: 7831
   Heap Blocks: exact=3D8919
   ->  Bitmap Index Scan on account_employee_site_typeahead_gin_idx  (cos=
t=3D0.00..28358.37 rows=3D67 width=3D0) (actual time=3D18204.756..18204.7=
56 rows=3D9011 loops=3D1)
         Index Cond: ((typeahead ~~ '%albert%'::text) AND (typeahead ~~ '=
%lo%'::text))
 Planning time: 0.288 ms
 Execution time: 18230.182 ms
(8 rows)


We noticed this because the application timed out for users searching som=
eone whose name was 2 characters ( it happens :) ).

We reject such filters when it's the only criterion, as we know it's goin=
g to be slow, but ignoring it as a supplementary filter would be a bit we=
ird.

Of course there is the possibility of filtering with two stages with a CT=
E, but that's not as great as having PostgreSQL doing it itself.


By the way, while preparing this, I noticed that it seems that during thi=
s kind of index scan, the interrupt signal is masked
for a very long time. Control-C takes a very long while to cancel the que=
ry. But it's an entirely different problem :)

Regards


--5IGAZF2HZhDTbPaIP0cgnElDMW8XIG88f--

--euD5Kz8gxmDHiXXO3IlMb2YiPeAnVv1KO
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEErRJFoqQ1WmHC5to09vfGVovAkJ8FAl0aLSEACgkQ9vfGVovA
kJ/XQwf/Qpf3GY+1Bt3qgL1gb5okqico3f/folLxFWr6lgb1lF9y4Kdt+ohg1TRN
l+9fsd5xVwdG2Ikw92GsPqnQhoEUgVd/TBFgHi6F7nF9iI6VhLGuOdx1z12AmAQO
xIsK6XXIfUODSiCwhmBiaioGJP3WRb0InpEUIKUaSnjJbFw7VS0wLK2qx0mJzrW9
FTH7sbRErs4iIGsUEqDg7ndYlWCfdXxn6sBnpce0UMXNMd8Y6C2iwdq9UMgEOrDV
4Ht/YVNvlygNlBLsHD/4rl9xdqaazpLEKGPkifNPffbEGVWVj0YAtaCTMbD6VxYj
LhoG15MvGEyVK+4O0UpYaRernc7+zQ==
=abIm
-----END PGP SIGNATURE-----

--euD5Kz8gxmDHiXXO3IlMb2YiPeAnVv1KO--