Thread: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

balasubramanian c r

Date:

02 September 2021, 14:09:09

Hi Team

We have encountered a problem in our testing environment.
I have a scenario where I am running a similarity match for an address
I have created a table with following number of records
1603423

We are using pg_similarity extension in postgresql version is 13.

And I have created GIN index (since i am using pg_similarity) library jaccard similarity method
when I run the Explain analyze
EXPLAIN ANALYZE select complete_address, jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017') as qsim from address where complete_address~??'raj nagar ext near ajnara integrity up ghaziabad 201017' order by qsim DESC;
QUERY PLAN

Sort (cost=5856.13..5860.14 rows=1603 width=93) (actual time=12101.194..12101.197 rows=6 loops=1)

Sort Key: (jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)) DESC
Sort Method: quicksort Memory: 25kB
-> Bitmap Heap Scan on address (cost=172.43..5770.80 rows=1603 width=93) (actual time=3516.233..12101.172 rows=6 loops=1)
Recheck Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Rows Removed by Index Recheck: 1039186
Heap Blocks: exact=58018
-> Bitmap Index Scan on address_complete_address_idx1 (cost=0.00..172.02 rows=1603 width=0) (actual time=256.037..256.037 rows=1039192 loops=1)
Index Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Planning Time: 0.141 ms
Execution Time: 12101.245 ms
(11 rows)
it took 12 seconds
following are my pgconf file settings
shared buffer as 4GB
work_mem 256 MB
maintenence_work_mem 512MB
autovacuum_work_mem 20MB
My index definition is this "address_complete_address_idx1" gin (complete_address gin_similarity_ops)

It is taking the index correctly. But why it took 12 seconds to process I really don't understand.

Please help.

Thanks
C.R.Bala

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

Ninad Shah

Date:

02 September 2021, 17:47:17

Hi Bala,

Are your statistics updated? Also, have you used the gin operator(gin_similarity_ops) correctly?

It is fetching just 6 records out of a million, hence, it should not go for bitmap index scan. As bitmap index scan loads a complete index, and access relevant pages from the table later by bitmap heap scan.

Regards,

Ninad Shah

On Thu, 2 Sept 2021 at 16:39, balasubramanian c r <crbs.siebel@gmail.com> wrote:

Hi Team
We have encountered a problem in our testing environment.
I have a scenario where I am running a similarity match for an address
I have created a table with following number of records
1603423
We are using pg_similarity extension in postgresql version is 13.
And I have created GIN index (since i am using pg_similarity) library jaccard similarity method
when I run the Explain analyze
EXPLAIN ANALYZE select complete_address, jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017') as qsim from address where complete_address~??'raj nagar ext near ajnara integrity up ghaziabad 201017' order by qsim DESC;
QUERY PLAN
Sort (cost=5856.13..5860.14 rows=1603 width=93) (actual time=12101.194..12101.197 rows=6 loops=1)
Sort Key: (jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)) DESC
Sort Method: quicksort Memory: 25kB
-> Bitmap Heap Scan on address (cost=172.43..5770.80 rows=1603 width=93) (actual time=3516.233..12101.172 rows=6 loops=1)
Recheck Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Rows Removed by Index Recheck: 1039186
Heap Blocks: exact=58018
-> Bitmap Index Scan on address_complete_address_idx1 (cost=0.00..172.02 rows=1603 width=0) (actual time=256.037..256.037 rows=1039192 loops=1)
Index Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Planning Time: 0.141 ms
Execution Time: 12101.245 ms
(11 rows)
it took 12 seconds
following are my pgconf file settings
shared buffer as 4GB
work_mem 256 MB
maintenence_work_mem 512MB
autovacuum_work_mem 20MB
My index definition is this "address_complete_address_idx1" gin (complete_address gin_similarity_ops)
It is taking the index correctly. But why it took 12 seconds to process I really don't understand.
Please help.
Thanks
C.R.Bala

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

Michael Lewis

Date:

02 September 2021, 18:27:28

This is showing many false positives from the index scan that get removed when the actual values are examined. With such a long search parameter, that does not seem surprising. I would expect a search on "raj nagar ghaziabad 201017" or something like that to yield far fewer results from the index scan. I don't know GIN indexes super well, but I would guess that including words that are very common will yield false positives that get filtered out later.

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

balasubramanian c r

Date:

02 September 2021, 21:09:40

HI Ninad

Thanks for your reply.

If bitmap index should not be used. Do i need to disable it for the time being and carry out the test.

The documentation in pg_similarity shows that index can be created on text column using gin with gin_similarity_ops.

The same way the index is created like

CREATE INDEX on address using GIN(complete_address gin_similarity_ops);

AFAIK I have not seen any other operators other than gin in the pg_smilarity extension.

Thanks

C.R.Bala

On Thu, Sep 2, 2021 at 8:17 PM Ninad Shah <nshah.postgres@gmail.com> wrote:

Hi Bala,

Are your statistics updated? Also, have you used the gin operator(gin_similarity_ops) correctly?

It is fetching just 6 records out of a million, hence, it should not go for bitmap index scan. As bitmap index scan loads a complete index, and access relevant pages from the table later by bitmap heap scan.

Regards,
Ninad Shah

On Thu, 2 Sept 2021 at 16:39, balasubramanian c r <crbs.siebel@gmail.com> wrote:
Hi Team
We have encountered a problem in our testing environment.
I have a scenario where I am running a similarity match for an address
I have created a table with following number of records
1603423
We are using pg_similarity extension in postgresql version is 13.
And I have created GIN index (since i am using pg_similarity) library jaccard similarity method
when I run the Explain analyze
EXPLAIN ANALYZE select complete_address, jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017') as qsim from address where complete_address~??'raj nagar ext near ajnara integrity up ghaziabad 201017' order by qsim DESC;
QUERY PLAN
Sort (cost=5856.13..5860.14 rows=1603 width=93) (actual time=12101.194..12101.197 rows=6 loops=1)
Sort Key: (jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)) DESC
Sort Method: quicksort Memory: 25kB
-> Bitmap Heap Scan on address (cost=172.43..5770.80 rows=1603 width=93) (actual time=3516.233..12101.172 rows=6 loops=1)
Recheck Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Rows Removed by Index Recheck: 1039186
Heap Blocks: exact=58018
-> Bitmap Index Scan on address_complete_address_idx1 (cost=0.00..172.02 rows=1603 width=0) (actual time=256.037..256.037 rows=1039192 loops=1)
Index Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Planning Time: 0.141 ms
Execution Time: 12101.245 ms
(11 rows)
it took 12 seconds
following are my pgconf file settings
shared buffer as 4GB
work_mem 256 MB
maintenence_work_mem 512MB
autovacuum_work_mem 20MB
My index definition is this "address_complete_address_idx1" gin (complete_address gin_similarity_ops)
It is taking the index correctly. But why it took 12 seconds to process I really don't understand.
Please help.
Thanks
C.R.Bala

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

Ninad Shah

Date:

02 September 2021, 22:42:16

Try the pg_tgrm extension. It is a rich set of operators.

Regards,

Ninad Shah

On Thu, 2 Sept 2021 at 23:39, balasubramanian c r <crbs.siebel@gmail.com> wrote:

HI Ninad

Thanks for your reply.
If bitmap index should not be used. Do i need to disable it for the time being and carry out the test.

The documentation in pg_similarity shows that index can be created on text column using gin with gin_similarity_ops.
The same way the index is created like
CREATE INDEX on address using GIN(complete_address gin_similarity_ops);

AFAIK I have not seen any other operators other than gin in the pg_smilarity extension.

Thanks
C.R.Bala

On Thu, Sep 2, 2021 at 8:17 PM Ninad Shah <nshah.postgres@gmail.com> wrote:
Hi Bala,

Are your statistics updated? Also, have you used the gin operator(gin_similarity_ops) correctly?

It is fetching just 6 records out of a million, hence, it should not go for bitmap index scan. As bitmap index scan loads a complete index, and access relevant pages from the table later by bitmap heap scan.

Regards,
Ninad Shah

On Thu, 2 Sept 2021 at 16:39, balasubramanian c r <crbs.siebel@gmail.com> wrote:
Hi Team
We have encountered a problem in our testing environment.
I have a scenario where I am running a similarity match for an address
I have created a table with following number of records
1603423
We are using pg_similarity extension in postgresql version is 13.
And I have created GIN index (since i am using pg_similarity) library jaccard similarity method
when I run the Explain analyze
EXPLAIN ANALYZE select complete_address, jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017') as qsim from address where complete_address~??'raj nagar ext near ajnara integrity up ghaziabad 201017' order by qsim DESC;
QUERY PLAN
Sort (cost=5856.13..5860.14 rows=1603 width=93) (actual time=12101.194..12101.197 rows=6 loops=1)
Sort Key: (jaccard(complete_address, 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)) DESC
Sort Method: quicksort Memory: 25kB
-> Bitmap Heap Scan on address (cost=172.43..5770.80 rows=1603 width=93) (actual time=3516.233..12101.172 rows=6 loops=1)
Recheck Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Rows Removed by Index Recheck: 1039186
Heap Blocks: exact=58018
-> Bitmap Index Scan on address_complete_address_idx1 (cost=0.00..172.02 rows=1603 width=0) (actual time=256.037..256.037 rows=1039192 loops=1)
Index Cond: (complete_address ~?? 'raj nagar ext near ajnara integrity up ghaziabad 201017'::text)
Planning Time: 0.141 ms
Execution Time: 12101.245 ms
(11 rows)
it took 12 seconds
following are my pgconf file settings
shared buffer as 4GB
work_mem 256 MB
maintenence_work_mem 512MB
autovacuum_work_mem 20MB
My index definition is this "address_complete_address_idx1" gin (complete_address gin_similarity_ops)
It is taking the index correctly. But why it took 12 seconds to process I really don't understand.
Please help.
Thanks
C.R.Bala

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

Ninad Shah

Date:

02 September 2021, 22:43:05

I see an issue with the operator. GIN index is capable of performing index scan and index-only scan.

Regards,

Ninad Shah

On Thu, 2 Sept 2021 at 20:57, Michael Lewis <mlewis@entrata.com> wrote:

This is showing many false positives from the index scan that get removed when the actual values are examined. With such a long search parameter, that does not seem surprising. I would expect a search on "raj nagar ghaziabad 201017" or something like that to yield far fewer results from the index scan. I don't know GIN indexes super well, but I would guess that including words that are very common will yield false positives that get filtered out later.

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

Tom Lane

Date:

02 September 2021, 22:44:09

Michael Lewis <mlewis@entrata.com> writes:
> This is showing many false positives from the index scan that get removed
> when the actual values are examined. With such a long search parameter,
> that does not seem surprising. I would expect a search on "raj nagar
> ghaziabad 201017" or something like that to yield far fewer results from
> the index scan. I don't know GIN indexes super well, but I would guess that
> including words that are very common will yield false positives that get
> filtered out later.

Yeah, the huge "Rows Removed" number shows that this index is very
poorly adapted to the query.  I don't think the problem is with GIN
per se, but with a poor choice of how to use it.  The given example
looks like what the OP really wants to do is full text search.
If so, a GIN index should be fine as long as you put tsvector/tsquery
filtering in front of it.  If that's not a good characterization of
the goal, it'd help to tell us what the goal is.  (Just saying "I
want to use jaccard similarity" sounds a lot like a man whose only
tool is a hammer, therefore his problem must be a nail, despite
evidence to the contrary.)

            regards, tom lane

Re: Querying a table with jaccard similarity with 1.6 million records take 12 seconds

From

balasubramanian c r

Date:

03 September 2021, 01:12:26

HI Tom/Ninad

My bad I didn't explain my use case properly.

The use case is to find the best string similarity for a given address against the list of addresses in the table.

Initially I tried a similarity function provided by the pg_trgm extension.

But the similarity scores were not satisfactory.

Later I explored the pg_similarity extension which had an exhaustive list of functions which supported indexes primarily on GIN.

After trying multiple functions like levenshtein, cosine, qgram, jaro, jaro winkler and jaccard similarity functions

jaccard similarity functions were providing better accurate results.

Hence we decided to use that for our analysis.

Now with a small amount of data the query response time is better. But with such 1.6 million it is taking a long time.

Even the documentation owner of pg_similarity provided an example on how to create an index using GIN. We followed exactly the same process.

But still when the data is huge we don't know why it is taking time to scan through the records.

Thanks

C.R.Bala

On Fri, Sep 3, 2021 at 1:14 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Michael Lewis <mlewis@entrata.com> writes:
> This is showing many false positives from the index scan that get removed
> when the actual values are examined. With such a long search parameter,
> that does not seem surprising. I would expect a search on "raj nagar
> ghaziabad 201017" or something like that to yield far fewer results from
> the index scan. I don't know GIN indexes super well, but I would guess that
> including words that are very common will yield false positives that get
> filtered out later.

Yeah, the huge "Rows Removed" number shows that this index is very
poorly adapted to the query. I don't think the problem is with GIN
per se, but with a poor choice of how to use it. The given example
looks like what the OP really wants to do is full text search.
If so, a GIN index should be fine as long as you put tsvector/tsquery
filtering in front of it. If that's not a good characterization of
the goal, it'd help to tell us what the goal is. (Just saying "I
want to use jaccard similarity" sounds a lot like a man whose only
tool is a hammer, therefore his problem must be a nail, despite
evidence to the contrary.)

regards, tom lane