5

I have a Rails application with a legacy query that I'd like to refurbish. The current implementation performs two SQL queries: one to get a large number of IDs and a second query that uses those IDs and applies some additional joins and filters to get the desired result.

I am trying to replace this with a single query that avoids the round trip, but doing so has incurred a large performance degradation in my local testing environment (which is a copy of the full production dataset). It appears that an index is not being used in the new query, leading to a full table scan. I had hoped the single query would keep the same performance as the original code, ideally improving on it due to not needing to send all the IDs around.

This is a fairly minimized version of my actual problem. A slightly larger version is discussed at Why does a list of 10,000 IDs perform better in a complicated query with multiple CTEs compared to the equivalent SQL to select them?.

Current Query

There's a query that takes ~6.5 seconds to calculate a list of 10000+ IDs. You can see that as the CTE visible_projects in the "proposed query" section below. Those IDs are then fed into this query:

EXPLAIN (ANALYZE, BUFFERS)
WITH visible_projects AS NOT MATERIALIZED (
    SELECT
        id
    FROM
        "projects"
    WHERE
        "projects"."id" IN (
            -- 10000+ IDs removed
)),
visible_tasks AS MATERIALIZED (
    SELECT
        tasks.id
    FROM
        tasks
    WHERE
        tasks.project_id IN (
            SELECT
                id
            FROM
                visible_projects))
SELECT
    COUNT(1)
FROM
    visible_tasks;

Query plan (depesz)

Aggregate  (cost=1309912.31..1309912.32 rows=1 width=8) (actual time=148.661..153.739 rows=1 loops=1)
   Buffers: shared hit=73107 read=22301
   CTE visible_tasks
     ->  Gather  (cost=43024.54..1308639.80 rows=56556 width=4) (actual time=46.337..137.260 rows=48557 loops=1)
           Workers Planned: 2
           Workers Launched: 2
           Buffers: shared hit=73107 read=22301
           ->  Nested Loop  (cost=42024.54..1301984.20 rows=23565 width=4) (actual time=28.871..120.682 rows=16186 loops=3)
                 Buffers: shared hit=73107 read=22301
                 ->  Parallel Bitmap Heap Scan on projects  (cost=42023.97..138877.16 rows=4378 width=4) (actual time=28.621..52.627 rows=3502 loops=3)
                       Recheck Cond: (id = ANY ('{ REMOVED_IDS }'::integer[]))
                       Heap Blocks: exact=3536
                       Buffers: shared hit=30410 read=9833
                       ->  Bitmap Index Scan on projects_pkey  (cost=0.00..42021.35 rows=10507 width=0) (actual time=35.642..35.642 rows=10507 loops=1)
                             Index Cond: (id = ANY ('{ REMOVED_IDS }'::integer[]))
                             Buffers: shared hit=30410 read=1111
                 ->  Index Scan using test_tasks_on_project on tasks  (cost=0.57..263.85 rows=182 width=8) (actual time=0.012..0.018 rows=5 loops=10507)
                       Index Cond: (project_id = projects.id)
                       Buffers: shared hit=42697 read=12468
   ->  CTE Scan on visible_tasks  (cost=0.00..1131.12 rows=56556 width=0) (actual time=46.339..144.641 rows=48557 loops=1)
         Buffers: shared hit=73107 read=22301
 Planning:
   Buffers: shared hit=10 read=10
 Planning Time: 8.857 ms
 Execution Time: 156.102 ms

Proposed Query

This is the same query structure, but instead of inserting the 10000+ IDs directly into the visible_projects CTE, I've embedded the SQL that finds those IDs.

EXPLAIN (ANALYZE, BUFFERS)
WITH visible_projects AS NOT MATERIALIZED (
    SELECT
        id
    FROM
        "projects"
    WHERE
        "projects"."company_id" = 11171
        AND "projects"."state" < 6
        AND "projects"."is_template" = FALSE),
visible_tasks AS MATERIALIZED (
    SELECT
        tasks.id
    FROM
        tasks
    WHERE
        tasks.project_id IN (
            SELECT
                id
            FROM
                visible_projects))
SELECT
    COUNT(1)
FROM
    visible_tasks;

Query plan (depesz):

 Aggregate  (cost=2212223.53..2212223.54 rows=1 width=8) (actual time=40675.984..40686.708 rows=1 loops=1)
   Buffers: shared hit=118145 read=1567727
   CTE visible_tasks
     ->  Gather  (cost=279353.08..2208430.12 rows=168596 width=4) (actual time=7050.894..40666.025 rows=48557 loops=1)
           Workers Planned: 2
           Workers Launched: 2
           Buffers: shared hit=118145 read=1567727
           ->  Hash Join  (cost=278353.08..2190570.52 rows=70248 width=4) (actual time=7038.932..40650.430 rows=16186 loops=3)
                 Hash Cond: (tasks.project_id = projects.id)
                 Buffers: shared hit=118145 read=1567727
                 ->  Parallel Seq Scan on tasks  (cost=0.00..1828314.43 rows=31963043 width=8) (actual time=0.397..29372.029 rows=25572144 loops=3)
                       Buffers: shared read=1508684
                 ->  Hash  (cost=277961.56..277961.56 rows=31322 width=4) (actual time=6977.480..6977.481 rows=10507 loops=3)
                       Buckets: 32768  Batches: 1  Memory Usage: 626kB
                       Buffers: shared hit=118061 read=59031
                       ->  Index Scan using index_projects_on_company_id on projects  (cost=0.43..277961.56 rows=31322 width=4) (actual time=0.591..6970.696 rows=10507 loops=3)
                             Index Cond: (company_id = 11171)
                             Filter: ((NOT is_template) AND (state < 6))
                             Rows Removed by Filter: 63512
                             Buffers: shared hit=118061 read=59031
   ->  CTE Scan on visible_tasks  (cost=0.00..3371.92 rows=168596 width=0) (actual time=7050.896..40671.054 rows=48557 loops=1)
         Buffers: shared hit=118145 read=1567727
 Planning:
   Buffers: shared hit=2 read=18
 Planning Time: 9.528 ms
 Execution Time: 40687.524 ms

Even accounting for the two previous queries combined, this takes 6x the time as the current implementation.

I see that this has chosen to use Parallel Seq Scan on tasks which is the main contributing time factor. What I don't understand is why this was chosen and what I should do to return to using the index.

Through research, I've learned that Postgres doesn't offer query hints to force the use of an index, so I assume that a good solution will involve demonstrating to the query planner that using the index would be beneficial.

Meta

I'm using COUNT(1) combined with the AS MATERIALIZED / AS NOT MATERIALIZED controls in this question to produce a smaller example.

The larger query in the application does not use these, but it also performs some filtering on the tasks table before producing a number of other CTEs and some aggregate metrics as the final result.

Schema

                                                 Table "public.projects"
           Column           |             Type              | Collation | Nullable |               Default
----------------------------+-------------------------------+-----------+----------+--------------------------------------
 id                         | integer                       |           | not null | nextval('projects_id_seq'::regclass)
 name                       | character varying(255)        |           |          |
 description                | text                          |           |          |
 due                        | timestamp without time zone   |           |          |
 created_at                 | timestamp without time zone   |           | not null |
 updated_at                 | timestamp without time zone   |           | not null |
 client_id                  | integer                       |           |          |
 company_id                 | integer                       |           |          |
 repeat                     | boolean                       |           | not null | true
 end_date                   | timestamp without time zone   |           |          |
 prev_id                    | integer                       |           |          |
 next_id                    | integer                       |           |          |
 completed_tasks_count      | integer                       |           | not null | 0
 tasks_count                | integer                       |           | not null | 0
 done_at                    | timestamp without time zone   |           |          |
 state                      | integer                       |           |          |
 schedule                   | text                          |           |          |
 start_date                 | timestamp without time zone   |           |          |
 manager_id                 | integer                       |           |          |
 partner_id                 | integer                       |           |          |
 exschedule                 | text                          |           |          |
 extdue                     | timestamp without time zone   |           |          |
 is_template                | boolean                       |           | not null | false
 predicted_duration         | integer                       |           |          | 0
 budget                     | integer                       |           |          | 0
 cached_effective_due_date  | timestamp without time zone   |           |          |
 cached_manager_fullname    | character varying(255)        |           |          | ''::character varying
 cached_partner_fullname    | character varying(255)        |           |          | ''::character varying
 cached_staffs_fullnames    | text                          |           |          | ''::text
 cached_staffs_ids          | text                          |           |          | ''::text
 cached_label_ids           | character varying(255)        |           |          | ''::character varying
 date_in                    | timestamp without time zone   |           |          |
 cached_label_sum           | integer                       |           |          | 0
 date_out                   | timestamp without time zone   |           |          |
 turn_around_time           | integer                       |           |          | 0
 dues_calculated_at         | timestamp without time zone   |           |          |
 dues                       | timestamp without time zone[] |           |          |
 dues_rewind                | integer[]                     |           |          |
 quickbooks_item_id         | integer                       |           |          |
 perform_final_review       | boolean                       |           | not null | false
 quickbooks_desktop_item_id | integer                       |           |          |
 billing_model_type         | character varying             |           | not null | 'staff'::character varying
 series_id                  | integer                       |           |          |
 shared                     | boolean                       |           |          | false
Indexes:
    "projects_pkey" PRIMARY KEY, btree (id)
    "index_projects_on_cached_effective_due_date" btree (cached_effective_due_date)
    "index_projects_on_client_id" btree (client_id)
    "index_projects_on_company_id" btree (company_id)
    "index_projects_on_manager_id" btree (manager_id)
    "index_projects_on_next_id" btree (next_id)
    "index_projects_on_partner_id" btree (partner_id)
    "index_projects_on_series_id" btree (series_id)
    "index_projects_on_shared_and_is_template" btree (shared, is_template) WHERE shared = true AND is_template = true
Foreign-key constraints:
    "fk_rails_243d23cb48" FOREIGN KEY (quickbooks_desktop_item_id) REFERENCES quickbooks_desktop_items(id)
    "fk_rails_33ba8711de" FOREIGN KEY (quickbooks_item_id) REFERENCES quickbooks_items(id)
    "fk_rails_fcf0ca7614" FOREIGN KEY (series_id) REFERENCES series(id) NOT VALID
Referenced by:
    TABLE "tasks" CONSTRAINT "tasks_project_id_fkey" FOREIGN KEY (project_id) REFERENCES projects(id)

The projects table has 14,273,833 rows.

  • 124,005 are is_template = true
                                               Table "public.tasks"
         Column          |            Type             | Collation | Nullable |              Default
-------------------------+-----------------------------+-----------+----------+-----------------------------------
 id                      | integer                     |           | not null | nextval('tasks_id_seq'::regclass)
 name                    | character varying(255)      |           |          |
 description             | text                        |           |          |
 duedate                 | timestamp without time zone |           |          |
 created_at              | timestamp without time zone |           | not null |
 updated_at              | timestamp without time zone |           | not null |
 project_id              | integer                     |           | not null |
 done                    | boolean                     |           | not null | false
 position                | integer                     |           |          |
 done_at                 | timestamp without time zone |           |          |
 dueafter                | integer                     |           |          |
 done_by_user_id         | integer                     |           |          |
 predicted_duration      | integer                     |           |          |
 auto_predicted_duration | integer                     |           |          | 0
 assignable_id           | integer                     |           |          |
 assignable_type         | character varying           |           |          |
 will_assign_to_client   | boolean                     |           | not null | false
Indexes:
    "tasks_pkey" PRIMARY KEY, btree (id)
    "index_tasks_on_assignable_type_and_assignable_id" btree (assignable_type, assignable_id)
    "index_tasks_on_done_by_user_id" btree (done_by_user_id)
    "index_tasks_on_duedate" btree (duedate)
    "test_tasks_on_project" btree (project_id)
Foreign-key constraints:
    "tasks_project_id_fkey" FOREIGN KEY (project_id) REFERENCES projects(id)

The tasks table has 76,716,433 rows.

System specifications

  • PostgreSQL 13.1
  • 2.9 GHz 6-Core Intel Core i9
  • 32 GB RAM
  • macOS 10.15.7
3

The main reason for the different query plan is probably the increased number of rows that Postgres estimates to get back from projects:

(cost=0.00..42021.35 rows=10507 width=0) (actual time=35.642..35.642 rows=10507 loops=1)

vs.

(cost=0.43..277961.56 rows=31322 width=4) (actual time=0.591..6970.696 rows=10507 loops=3)

Over-estimated by factor 3, which is not dramatic, but obviously enough to favor a different (inferior) query plan. Related:

Assuming projects.is_template is mostly false, I suggest these multicolumn indices:

CREATE INDEX ON projects(company_id, state);

Equality first, range later. See:

You might also try to increase the statistics target on company_id, state, and ANALYZE the table, to get better estimates.

And:

CREATE INDEX ON tasks (project_id, id);

Plus increase statistics target on tasks.project_id and ANALYZE.

In both cases, the multicolumn index can replace the one on just project.company_id / task.project_id. Since all columns are integer, the size of the index will would be the same - except for the effect of index de-duplication (added with Postgres 13), which shows strongly in your test for the highly duplicative tasks.project_id. See:

And this query:

SELECT t.id
FROM   projects p
JOIN   tasks t ON t.project_id = p.id
WHERE  p.company_id = 11171
AND    p.state < 6
AND    p.is_template = FALSE;

The direct join should be faster.

8
  • The direct join should be faster — unfortunately, this would be less than ideal in our case because it would force inlining the permissions / visibility logic into this query, duplicating it. The form that I've shown here is the "easy" one where permissions are wide open (such as to the administrator of the company), but more restricted permissions are much subtler (to my chagrin). – Shepmaster Dec 9 '20 at 3:34
  • Can you share a bit (or link, I love them links, keep em coming) about what signals you used to determine that those fields were the appropriate ones to add to the composite index? I'm guessing that the cardinality of is_template came into play, based on your listed assumption. – Shepmaster Dec 9 '20 at 3:54
  • 523.250 ms is quite a bit better already. But the estimates of the planner are still off. Assuming that most of the rows are not templates (correct me if I'm wrong), I assume that WHERE p.is_template = FALSE is hardly selective, so it won't pay to add this column to the index or base a partial index on it. – Erwin Brandstetter Dec 9 '20 at 4:00
  • I've been trying to apply your suggestions to the broader example in my code, but that version is still slow. I've trimmed the complete thing down again a bit, and it falls back to a sequential scan that discards ~67M rows before joining to the CTE that has ~10K rows (depesz). What would a good way to do this iteration? Shall I ask a new question, edit this one, leave it in comments? – Shepmaster Dec 9 '20 at 19:32
  • 1
    Your question is (now) examplary in providing everything of relevance. That's what made me have a closer look. One thing: actual CREATE TABLE and CREATE INDEX statements are superior to the psql output, as one can run quick tests with it. And it's the canonical form of a table definition. (But psql output is not too bad either.) – Erwin Brandstetter Dec 9 '20 at 22:00
1

I applied the two indices suggested from Erwin Brandstetter's answer:

CREATE INDEX erwin_1 ON projects (company_id, state);
CREATE INDEX erwin_2 ON tasks (project_id, id);

The query performance greatly increased (depesz):

 Aggregate  (cost=255694.30..255694.31 rows=1 width=8) (actual time=517.535..521.112 rows=1 loops=1)
   Buffers: shared hit=44812 read=9896
   CTE visible_tasks
     ->  Gather  (cost=1437.11..251900.65 rows=168607 width=4) (actual time=7.935..508.539 rows=48557 loops=1)
           Workers Planned: 2
           Workers Launched: 2
           Buffers: shared hit=44812 read=9896
           ->  Nested Loop  (cost=437.11..234039.95 rows=70253 width=4) (actual time=3.341..501.705 rows=16186 loops=3)
                 Buffers: shared hit=44812 read=9896
                 ->  Parallel Bitmap Heap Scan on projects  (cost=436.54..112544.40 rows=13071 width=4) (actual time=2.436..304.805 rows=3502 loops=3)
                       Recheck Cond: ((company_id = 11171) AND (state < 6))
                       Filter: (NOT is_template)
                       Rows Removed by Filter: 13
                       Heap Blocks: exact=2864
                       Buffers: shared hit=2460 read=6312
                       ->  Bitmap Index Scan on erwin_1  (cost=0.00..428.69 rows=31626 width=0) (actual time=4.958..4.959 rows=10545 loops=1)
                             Index Cond: ((company_id = 11171) AND (state < 6))
                             Buffers: shared read=12
                 ->  Index Only Scan using erwin_2 on tasks  (cost=0.57..7.48 rows=182 width=8) (actual time=0.054..0.055 rows=5 loops=10507)
                       Index Cond: (project_id = projects.id)
                       Heap Fetches: 0
                       Buffers: shared hit=42352 read=3584
   ->  CTE Scan on visible_tasks  (cost=0.00..3372.14 rows=168607 width=0) (actual time=7.937..513.890 rows=48557 loops=1)
         Buffers: shared hit=44812 read=9896
 Planning:
   Buffers: shared hit=47 read=21 dirtied=2
 Planning Time: 11.682 ms
 Execution Time: 523.250 ms

0.5 seconds is much better than the original 6.5 seconds or my terrible 40s.

This isn't a free lunch, of course:

  1. The first composite index is 97 MB, replacing an existing index of 96 MB, which seems like a clear win.
  2. The second composite is 1643 MB, replacing an existing index of 779 MB. It adds 864 MB of index data, which is non-negligible.

Erwin Brandstetter explains further:

This is the effect of index de-duplication - new in Postgres 13. project_id is probably hugely duplicative, so an index on just (project_id) can be compressed a lot. Adding the unique id disables the effect almost completely. Without the new de-deduplication feature (such as in Postgres 12), an index on (project_id, id) (2x integer) would have the exact same size as the one on (project_id) (except for possible volatile bloat). The minimum size is bit above (4+8+8) x (number of rows) bytes. SELECT pg_size_pretty(76716433 * 20.0); --> 1463 MB.

5
  • 1
    Ah, the effect of index de-duplication - new in pg 13. project_id is probably hugely duplicative, so an index on just (project_id) can be compressed a lot. Adding the unique id disables the effect almost completely. Without the new feature, an index on (project_id, id) (2x integer) would have the exact same size as the one on (project_id). – Erwin Brandstetter Dec 9 '20 at 21:29
  • @ErwinBrandstetter and without the new feature, both indices would be large, correct? That could actually work in my favor here, as our production DB is running 12.5 (I accidentally upgraded to 13 locally and have been rolling with it). – Shepmaster Dec 9 '20 at 21:36
  • On Postgres 12, both indexes should have exactly the same size (except for possible volatile bloat). – Erwin Brandstetter Dec 9 '20 at 21:40
  • @ErwinBrandstetter yes, I got that. My question is: would both indices in Postgres 12 be 1643MB or something else? – Shepmaster Dec 9 '20 at 21:41
  • 1
    Yes, the bigger size (uncompressed). The minimum size is bit above (4+8+8) x (number or rows) bytes. SELECT pg_size_pretty(76716433 * 20.0); --> 1463 MB. Some overhead for initial idx page, bloat, and most importantly fill factor, which is 90% by default for btree indexes. So add around 15% to arrive at the actual minimum size. – Erwin Brandstetter Dec 9 '20 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.