Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1q29dp-00040x-7M for pgsql-general@arkaria.postgresql.org; Thu, 25 May 2023 12:00:25 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1q29dn-0000n6-0q for pgsql-general@arkaria.postgresql.org; Thu, 25 May 2023 12:00:23 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1q29dm-0000mp-K4 for pgsql-general@lists.postgresql.org; Thu, 25 May 2023 12:00:22 +0000 Received: from mail-ej1-x62f.google.com ([2a00:1450:4864:20::62f]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1q29dd-00248B-BF for pgsql-general@lists.postgresql.org; Thu, 25 May 2023 12:00:20 +0000 Received: by mail-ej1-x62f.google.com with SMTP id a640c23a62f3a-96fffe11714so96245766b.0 for ; Thu, 25 May 2023 05:00:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=enterprisedb.com; s=google; t=1685016011; x=1687608011; h=content-transfer-encoding:in-reply-to:from:content-language :references:to:subject:user-agent:mime-version:date:message-id:from :to:cc:subject:date:message-id:reply-to; bh=4fLeOfMTsZ5/QFCkKBrD1tNeWLInqE5X4qFXLKvCn54=; b=UgF2H3/85ERT2jXyrwkbuM4Y5hgcuLhx2LEPck8enG9HvvwRQ19cy8xTtxNZiH+A/P y5qVx+j+9MsJjBSajSnGuUIMBvXOvt2UhQOuev9lwwxfuyn6XXJAkp8aKshMI3RkfpEh VMK1Bql71+baOASqycNNz0cJKQMidOsMeFoBv5Fp6u321Z529nxZbWuwkAGcLBE/tBl6 Fgu1FNQua91iBl1tQuvv/BSHZGpGRvtpZQmovhnZkJsLdiNlHCAE4fUaCCME/TL6wS0a FG6X37H4UiYSQ8+AD8RR/RnXP79qnZbpdz/wkjD4qoimlCljbXMwwp8/sjAHeUiS/z0G 4/AQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685016011; x=1687608011; h=content-transfer-encoding:in-reply-to:from:content-language :references:to:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=4fLeOfMTsZ5/QFCkKBrD1tNeWLInqE5X4qFXLKvCn54=; b=d0nm7wrwUO6jJXK1Wm6ZEQM/UgXHmHVLNhMpKu16V/K1y/Zejuwlh0Q4G/j/xzh20o Ipiesmlnk1D1l+60RPQsIHDWMZFSFgINbzd15wtq1ghBOHw8CmDIIKSTdIZQIWwb8YXB XuizvbcntQDToeLBZQ/YdKhDdgL2rkyA3205IvRpnUhrT8BpQUlPDO7XffEsHxdZXH6C 40htlPJBD/iIpwnvLTt5MHLXXVWDC1jmw110RbY3FXxOSkKa2H9Jn5U8wtjsnOhM0dtB 6XN5Xb4DzY3gury29/1aytXsYxCcWl24wvK9BprUj+SlEleQVooDJETc1fRH6pnJytwu 5efQ== X-Gm-Message-State: AC+VfDyA41fi3wTy2x5r7V4W1v8AMG5mj66i5PHSDhn1RA2A9fEvEKQD yzrQi1p1EPueCRvkf41DNvEmxteyWInSv/q6NIZgZHABl+O03nZRcndM2ImEWwF5U1WiH0DPFSa odf0npD+HuYi14wCKjzIZuzTEa6fScnL+E47JCOTyRG3WK1EUON44a7YPQzAirFTQgisI4FzXZo J+CCocZDZLfZcOInrBHEis/RyPDyQUy7crtkwGOdkSu28ExzBkH2OcGuvRgI7688vwLg== X-Google-Smtp-Source: ACHHUZ7G50LaOjmbuaE9jEKBbf8965MsgEgWaTuRTUwpCr49yzSoAvpWH2SUl0WZmime9gqvlJnEvA== X-Received: by 2002:a17:907:944c:b0:94a:58a5:2300 with SMTP id dl12-20020a170907944c00b0094a58a52300mr1385279ejc.27.1685016010786; Thu, 25 May 2023 05:00:10 -0700 (PDT) Received: from [10.137.0.17] (static-84-42-175-93.bb.vodafone.cz. [84.42.175.93]) by smtp.gmail.com with ESMTPSA id r20-20020a170906365400b0094e7d196aa4sm733663ejb.160.2023.05.25.05.00.09 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 25 May 2023 05:00:10 -0700 (PDT) Message-ID: <89c58efe-4892-5f2b-5a9c-4d876955a6f1@enterprisedb.com> Date: Thu, 25 May 2023 14:00:09 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: Question regarding specifics of GIN and pg_trgm performance and potential use of show_trgm to improve it To: Pavel Horal , pgsql-general@lists.postgresql.org References: Content-Language: en-US From: Tomas Vondra In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-CLOUD-SEC-AV-Info: enterprisedb,google_mail,monitor X-CLOUD-SEC-AV-Sent: true X-Gm-Spam: 0 X-Gm-Phishy: 0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk On 5/24/23 22:28, Pavel Horal wrote: > Hello PostgreSQL community, > > I am trying to improve performance of using similarity based queries on > a large datasets and I would like to confirm my understanding of how GIN > indexes work and how pg_trgm uses them. > > If I understand it correctly, using GIN index is always a two step > process: first, potential matches are searched in the index; then as a > second step tuples are actually fetched and rechecked if they really > match the query. This two step process can lead to degraded performance > when the index scan matches too many elements that then are read from > disk only to be dropped as non-matching during the recheck phase. *Is > that understanding correct?* > Correct. GIN gives you "candidate" rows, but the recheck may still eliminate those. > Now to the issue... pg_trgm's similarity search can use similarity > operator % to search for "similar" documents. Concept of "similarity" is > based on a similarity of trigram array extracted from the query string > and trigram arrays of searched values. This concept is quite tricky in a > sense that just by matching trigrams in GIN index PostgreSQL can not > tell if the final value will match or not as it does not know how many > trigrams overall are there in that value...  > > Consider following example: > > CREATE TABLE test (id SERIAL, value TEXT); > CREATE INDEX test_idx ON test USING GIN (value gin_trgm_ops); > INSERT INTO test (value) SELECT 'lorem ipsum ' || id || repeat('foo > bar', CAST(random() * 100 AS INT)) FROM generate_series(1, 100000) > source(id); > > SET pg_trgm.similarity_threshold TO 0.5; > EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM test WHERE value % 'lorem'; >                                                          QUERY PLAN > ---------------------------------------------------------------------------------------------------------------------------- >  Bitmap Heap Scan on test  (cost=2024.08..2062.86 rows=10 width=374) > (actual time=2261.727..2261.728 rows=0 loops=1) >    Recheck Cond: (value % 'lorem'::text) >    Rows Removed by Index Recheck: 100000 >    Heap Blocks: exact=5025 >    Buffers: shared hit=5636 >    ->  Bitmap Index Scan on test_idx  (cost=0.00..2024.08 rows=10 > width=0) (actual time=19.242..19.242 rows=100000 loops=1) >          Index Cond: (value % 'lorem'::text) >          Buffers: shared hit=611 >  Planning: >    Buffers: shared hit=1 >  Planning Time: 2.417 ms >  Execution Time: 2261.765 ms > (12 rows) > > > If I understand this correctly the *index scan really matches all 100000 > items that are then read from disk* only *to be discarded during the > recheck*. So 2 seconds of doing all that work to return zero results > (and I was lucky in my example to only have shared buffer hits, so no > real disk I/O). > > *Is my understanding correct that this happens only because pg_trgm is > not able to actually determine if the matched item from the index search > is actually much much longer than the query?* Yes, I think that's mostly correct understanding. The trouble here is that the posting list for "lorem" is very long - it contains TID for pretty much every row in the table. We can't calculate similarity at that point from trigrams alone, so we have to fetch the rows. > Is there any way how the > performance can be improved in this case? I thought that I can store > number of trigrams in the index, but that is not being used by the query > planner: > > CREATE INDEX test_idx2 ON test USING GIN (value gin_trgm_ops, > array_length(show_trgm(value), 1)); > > EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM test WHERE value % 'lorem' AND > array_length(show_trgm(value), 1) < array_length(show_trgm('lorem'), 1) > / 0.5; >                                                         QUERY PLAN > --------------------------------------------------------------------------------------------------------------------------- >  Bitmap Heap Scan on test  (cost=56.08..94.96 rows=3 width=376) (actual > time=2273.225..2273.226 rows=0 loops=1) >    Recheck Cond: (value % 'lorem'::text) >    Rows Removed by Index Recheck: 100000 >    Filter: ((array_length(show_trgm(value), 1))::numeric < > 12.0000000000000000) >    Heap Blocks: exact=5025 >    Buffers: shared hit=5134 >    ->  Bitmap Index Scan on test_idx3  (cost=0.00..56.08 rows=10 > width=0) (actual time=15.945..15.946 rows=100000 loops=1) >          Index Cond: (value % 'lorem'::text) >          Buffers: shared hit=109 >  Planning: >    Buffers: shared hit=3 >  Planning Time: 2.394 ms >  Execution Time: 2273.256 ms > (13 rows) > > > Thank you for any sort of insight into this. I don't think indexing the number of trigrams like this can help, and I'm not sure how to improve this (at least for the built-in GIN). It seem similarity searches are bound to be proportional to the most frequent trigram in the query. I wonder if the "newer" GIN variants like RUM [1] could improve this, but I don't think it has trgm opclasses. regards [1] https://github.com/postgrespro/rum -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company