Обсуждение: Slow "not in array" operation

What's the plan for the slow one? What's the time to just count all rows?

It is very interesting to me that the optimizer chose a parallel sequential scan rather than an index scan on either of your indexes that start with project_id that also reference trashed_at.

1) Are you running on SSD type storage? Has random_page_cost been lowered to 1-1.5 or so (close to 1 assumes good cache hits)?

2) It seems you have increased parallel workers. Have you also changed the startup or other cost configs related to how inclined the system is to use sequential scans?

3) If you disable sequential scan, what does the plan look like for this query? (SET ENABLE_SEQSCAN TO OFF;)

Marco Colli <collimarco91@gmail.com> writes:
> 3) Here's the query plan that I get after disabling the seq scan:

>  Finalize Aggregate  (cost=2183938.89..2183938.90 rows=1 width=8) (actual
> time=94972.253..94972.254 rows=1 loops=1)

So, this is slower than the seqscan, which means the planner made the
right choice.

You seem to be imagining that there's some way the index could be used
with the NOT clause, but there isn't.  Indexable clauses are of the form
        indexed_column indexable_operator constant
and there's no provision for a NOT in that.  If we had a "not contained
in" array operator, the NOT could be folded to be of this syntactic form,
but it's highly unlikely that any index operator class would consider such
an operator to be a supported indexable operator.  It doesn't lend itself
to searching an index.

So the planner is doing the best it can, which in this case is a
full-table scan.

A conceivable solution, if the tags array is a lot smaller than
the table as a whole and the table is fairly static, is that you could
make a btree index on the tags array and let the planner fall back
to an index-only scan that is just using the index as a cheaper
source of the array data.  (This doesn't work for your existing GIST
index because GIST can't reconstruct the original arrays on-demand.)
I suspect though that this wouldn't win much, even if you disregard
the maintenance costs for the extra index.  The really fundamental
problem here is that a large fraction of the table satisfies the
NOT-in condition, and no index is going to beat a seqscan by all that
much when that's true.  Indexes are good at retrieving small portions
of tables.

                        regards, tom lane

3) Here's the query plan that I get after disabling the seq scan:

                                                                                        QUERY PLAN                                                                                         

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 Finalize Aggregate  (cost=2183938.89..2183938.90 rows=1 width=8) (actual time=94972.253..94972.254 rows=1 loops=1)

   ->  Gather  (cost=2183938.16..2183938.87 rows=7 width=8) (actual time=94952.895..95132.626 rows=8 loops=1)

         Workers Planned: 7

         Workers Launched: 7

         ->  Partial Aggregate  (cost=2182938.16..2182938.17 rows=1 width=8) (actual time=94950.958..94950.958 rows=1 loops=8)

               ->  Parallel Bitmap Heap Scan on subscriptions  (cost=50294.50..2180801.47 rows=854677 width=0) (actual time=1831.342..94895.208 rows=611828 loops=8)

                     Recheck Cond: ((project_id = 123) AND (trashed_at IS NULL))

                     Rows Removed by Index Recheck: 2217924

                     Filter: (NOT (tags @> '{en}'::character varying[]))

                     Rows Removed by Filter: 288545

                     Heap Blocks: exact=120301 lossy=134269

                     ->  Bitmap Index Scan on index_subscriptions_on_project_id_and_tags  (cost=0.00..48798.81 rows=6518094 width=0) (actual time=1493.823..1493.823 rows=7203173 loops=1)

                           Index Cond: (project_id = 123)

 Planning Time: 1.273 ms

 Execution Time: 95132.766 ms

(15 rows)

What was the plan for the one that took 500ms?  I don't see how it is possible that this one is 180 times slower than that one.  Maybe a hot cache versus cold cache?  Also, it seems weird to me that "trashed_at IS NULL" shows up in the recheck but not in the original  Index Cond.  Increasing work_mem can also help, but since the  Bitmap Index Scan itself took half the time there is only so much it can do.

Cheers,

Jeff

On Wed, Nov 13, 2019 at 4:20 AM Marco Colli <collimarco91@gmail.com> wrote:

Replying to the previous questions:

- work_mem = 64MB (there are hundreds of connections)

- the project 123 has more than 7M records, and those that don't have the tag 'en' are 4.8M

 

What was the plan for the one that took 500ms?

This is the query / plan without the filter on tags:

SELECT COUNT(*) FROM "subscriptions" WHERE "subscriptions"."project_id" = 123 AND "subscriptions"."trashed_at" IS NULL;

                 QUERY PLAN                                                                                                 

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 Finalize Aggregate  (cost=291342.67..291342.68 rows=1 width=8) (actual time=354.556..354.556 rows=1 loops=1)

   ->  Gather  (cost=291342.05..291342.66 rows=6 width=8) (actual time=354.495..374.305 rows=7 loops=1)

         Workers Planned: 6

         Workers Launched: 6

         ->  Partial Aggregate  (cost=290342.05..290342.06 rows=1 width=8) (actual time=349.799..349.799 rows=1 loops=7)

               ->  Parallel Index Only Scan using index_subscriptions_on_project_id_and_uid on subscriptions  (cost=0.56..287610.27 rows=1092713 width=0) (actual time=0.083..273.018 rows=1030593 loops=7)

                     Index Cond: (project_id = 123)

                     Heap Fetches: 280849

 Planning Time: 0.753 ms

 Execution Time: 374.483 ms

(10 rows)

My previous comment about the bitmap index scan taking half the time was a slip of the eye, I was comparing *cost* of the bitmap index scan to the *time* of the overall plan.  But then the question is, why isn't it doing an index-only scan on  "index_subscriptions_on_project_id_and_tags"?  And the answer is that is because it is a GIN index.  Make the same index only as btree, and you should get good performance as it can filter the tags within a given project without visiting the table.

Cheers,

Jeff

On Wed, Nov 13, 2019 at 6:56 AM Marco Colli <collimarco91@gmail.com> wrote:

> the answer is that is because it is a GIN index. Make the same index only as btree, and you should get good performance as it can filter the tags within a given project without visiting the table.

Currently I have this GIN index:

    "index_subscriptions_on_project_id_and_tags" gin (project_id, tags) WHERE trashed_at IS NULL

Multicolumn GIN indexes are nearly worthless IMO when one column is a scalar.  You can use this index, but it won't be better than one just on "GIN (tags)  trashed_at IS NULL".  An N-column GIN index is mostly the same thing as N single column GIN indexes.

 

It uses the btree_gin extension and works perfectly for tag search, except for the "NOT" operator. I don't understand why it doesn't use the GIN index also for the "NOT" operator.

Because it can't.  Tom already did a good job of describing that. Can you describe what steps you think an index should take to jump to the specific rows which fail to exist in an inverted index?

The problem is that I cannot create the same index with BTree, because PG doesn't support BTree on array :( 

Sure it does.  It can't jump to specific parts of the index based on the array containment operators, but it can use them for in-index filtering (but only if you can do an index-only scan).  And really, that is probably all you need to get > 100x improvement.

Are you getting an error when you try to build it?  If so, what is the error?

Cheers,

Jeff