2

Introduction

Imagine a (fairly advanced) ToDo app in which items are catogorized into lists (which can be temporarily deactivated), have custom additional attributes, can be assigned to a user and can be shared between users by explicitly listing them as "subscribed" to the item. This can be represented with the following tables (natural foreign keys in parentheses:

  1. todo_list
  2. todo_item (list_id)
  3. todo_attribute (item_id)
  4. todo_subscription (item_id + user_id)

We now want to show a list of all items a user is subscribed to, and allow them to filter in various ways as well as sort by different fields of the items. Finally, since our users are quite busy and accumulate many items, we need to paginate this.


Database Layout

Now, let's get more specific and explain the layout of the different tables. There are two columns that all tables contain and which always form the primary key:

 Column |     Type      |  Indexed 
--------+---------------+---------
team_id | varchar(1024) |
id      | varchar(1024) |

Note that "Indexed" here refers to this column having a dedicated single-column index (currently).

todo_list:

name   | varchar(1024) |
active | boolean       | yes

todo_item:

list_id       | varchar(1024) | yes
name          | varchar(1024) | yes
assignee_id   | varchar(1024) |
status        | varchar(1024) | yes
creation_date | timestamp     | yes
change_date   | timestamp     | yes

todo_attribute:

item_id | varchar(1024) | yes
name    | varchar(1024) | yes
value   | varchar(1024) | yes

todo_subscription:

item_id             | varchar(1024) | yes
user_id             | varchar(1024) |
subscription_date   | timestamp     |
unsubscription_date | timestamp     | yes

On the last table, there's also a unique multi-column index on (user_id, item_id, team_id).


The Problem

We now want to retrieve a list of todo_items with the following restrictions:

  1. The result must be paginated
  2. The result (before pagination) must be ordered by either name, creation date, change date or status of the item, or ordered by the value of a specific attribute which has been chosen by its name.
  3. The results can be (optionally) searched in either the name of the item or the value of all attributes belonging to it.
  4. The results can be (optionally) filtered by status, assignee or name¹.

Due to the framework we use, there are some restrictions in place. Namely, queries cannot be built dynamically from the application (we can only pass parameters to a pre-defined query).

¹ There's technically even more, but for brevity I'll leave those out.


The Query

All of this lead to the following, current query. It does the job, but it behaves pretty poor whenever there's a large number of items involved (several thousands), taking upwards of 10s (we also have to make other queries, for example to calculate the number of pages).

SELECT * FROM (
    SELECT DISTINCT ON (item.id)
        item.*,
        sortattr.value AS sortattr_value
    FROM todo_item item
    LEFT OUTER JOIN todo_attribute attr ON 1 = 1
        AND attr.team_id = item.team_id
        AND attr.item_id = item.id
    LEFT OUTER JOIN todo_attribute sortattr ON 1 = 1
        AND sortattr.team_id = item.team_id
        AND sortattr.item_id = item.id
        AND sortattr.name = :sortByAttribute
    JOIN todo_subscription sub ON 1 = 1
        AND sub.item_id = item.id
        AND sub.team_id = item.team_id
    JOIN todo_list list ON 1 = 1
        AND list.team_id = item.team_id
        AND list.id = item.list_id
    WHERE 1 = 1
        AND item.team_id = :teamId
        AND sub.user_id = :userId
        AND sub.unsubscription_date IS NULL
        AND list.active

        AND (CAST(:searchText AS TEXT) IS NULL
            OR LOWER(item.name) LIKE '%' || LOWER(:searchText) || '%'
            OR (:searchAttributes IS TRUE AND LOWER(attr.value) LIKE '%' || LOWER(:searchText) || '%')
        )
        AND item.status IN (:status)
        AND (:numberOfAssigneeIds = 0 OR COALESCE(item.assignee_id, 'unassigned') IN (:assigneeIds))
        AND (:numberOfNames = 0 OR item.name IN (:names))
) t
ORDER BY
    CASE WHEN (:sortDirection = 'ASC'  AND CAST(:sortByAttribute AS TEXT) IS NOT NULL)                     THEN sortattr_value END ASC,
    CASE WHEN (:sortDirection = 'DESC' AND CAST(:sortByAttribute AS TEXT) IS NOT NULL)                     THEN sortattr_value END DESC,
    CASE WHEN (:sortDirection = 'ASC'  AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'NAME')    THEN name           END ASC,
    CASE WHEN (:sortDirection = 'DESC' AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'NAME')    THEN name           END DESC,
    CASE WHEN (:sortDirection = 'ASC'  AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'CREATED') THEN creation_date  END ASC,
    CASE WHEN (:sortDirection = 'DESC' AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'CREATED') THEN creation_date  END DESC,
    CASE WHEN (:sortDirection = 'ASC'  AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'UPDATED') THEN change_date    END ASC,
    CASE WHEN (:sortDirection = 'DESC' AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'UPDATED') THEN change_date    END DESC,
    CASE WHEN (:sortDirection = 'ASC'  AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'STATUS')  THEN status         END ASC,
    CASE WHEN (:sortDirection = 'DESC' AND CAST(:sortByAttribute AS TEXT) IS NULL AND :sortBy = 'STATUS')  THEN status         END DESC,

    -- Always fall back to sorting by ID to have a stable order
    id ASC
LIMIT :limit OFFSET :offset;

This has the following parameters:

  1. teamId (obvious)
  2. userId (of the user for which we generated the list of items)
  3. sortByAttribute (name of attribute to sort by, else NULL)
  4. sortBy (name of column to sort by, else NULL)
  5. sortDirection (obvious)
  6. limit (obvious)
  7. offset (obvious)
  8. searchText (otherwise NULL)
  9. status (always a non-empty list of the possible statuses)
  10. numberOfAssigneeIds (can be 0)
  11. assigneeIds (list of IDs, never empty)
  12. numberOfNames (can be 0)
  13. names (never empty)

For the last four, the split into list + size of the list is simply because the framework generates WHERE IN () for an empty list, which is a syntax error, so we add a dummy value to the list in this case and instead avoid the condition by checking the list size (which doesn't count the dummy value).


The Question

Running our query through EXPLAIN ANALYZE yields the following plan; unfortunately, this plan is anonymized and thus the names don't match the example above. I'm not sure if there's a good way to "fix" this as a query run on a toy dataset won't have the same statistics. :-(

Limit  (cost=55889.350..55889.370 rows=9 width=1176) (actual time=12403.523..12403.544 rows=50 loops=1)
  ->  Sort  (cost=55889.350..55889.370 rows=9 width=1176) (actual time=12403.522..12403.537 rows=50 loops=1)
          Sort Key: romeo.charlie, romeo.lima_three
          Sort Method: top-N heapsort  Memory: 50kB
        ->  Subquery Scan on romeo  (cost=55889.070..55889.210 rows=9 width=1176) (actual time=11808.772..12397.097 rows=9151 loops=1)
              ->  Unique  (cost=55889.070..55889.120 rows=9 width=1016) (actual time=11808.768..12392.807 rows=9151 loops=1)
                    ->  Sort  (cost=55889.070..55889.100 rows=9 width=1016) (actual time=11808.767..12341.675 rows=204315 loops=1)
                            Sort Key: golf_two.lima_three
                            Sort Method: external merge  Disk: 61008kB
                          ->  Nested Loop Left Join  (cost=6045.260..55888.930 rows=9 width=1016) (actual time=528.546..8161.845 rows=204315 loops=1)
                                  Join Filter: false
                                ->  Nested Loop Left Join  (cost=6045.260..55888.840 rows=9 width=1002) (actual time=528.544..7785.811 rows=204315 loops=1)
                                      ->  Nested Loop  (cost=6044.710..55836.950 rows=2 width=1002) (actual time=528.512..6338.285 rows=9151 loops=1)
                                              Join Filter: ((golf_two.papa)::text = (golf_sierra.lima_three)::text)
                                              Rows Removed by Join Filter: 347738
                                            ->  Nested Loop  (cost=6011.250..54875.320 rows=249 width=1002) (actual time=528.238..5904.009 rows=9151 loops=1)
                                                  ->  Bitmap Heap Scan on juliet lima_whiskey  (cost=6010.700..21824.470 rows=4077 width=74) (actual time=528.087..884.885 rows=47082 loops=1)
                                                          Recheck Cond: (((india)::text = 'tango_papa'::text) AND ((hotel)::text = 'xray'::text))
                                                          Filter: (mike five_romeo NULL)
                                                          Heap Blocks: exact=28203
                                                        ->  Bitmap Index Scan on yankee  (cost=0.000..6009.690 rows=4320 width=0) (actual time=487.676..487.676 rows=47489 loops=1)
                                                                Index Cond: (((india)::text = 'tango_papa'::text) AND ((hotel)::text = 'xray'::text))
                                                  ->  Index Scan using delta on victor_romeo golf_two  (cost=0.550..8.100 rows=1 width=1002) (actual time=0.104..0.104 rows=0 loops=47082)
                                                          Index Cond: (((hotel)::text = 'xray'::text) AND ((lima_three)::text = (lima_whiskey.sierra_november)::text))
                                                          Filter: ((november)::text = ANY ('victor_foxtrot'::text[]))
                                                          Rows Removed by Filter: 1
                                            ->  Materialize  (cost=33.450..551.050 rows=110 width=74) (actual time=0.000..0.012 rows=39 loops=9151)
                                                  ->  Bitmap Heap Scan on five_lima golf_sierra  (cost=33.450..550.500 rows=110 width=74) (actual time=0.212..0.311 rows=39 loops=1)
                                                          Recheck Cond: ((hotel)::text = 'xray'::text)
                                                          Filter: foxtrot
                                                          Rows Removed by Filter: 29
                                                          Heap Blocks: exact=49
                                                        ->  Bitmap Index Scan on oscar  (cost=0.000..33.430 rows=135 width=0) (actual time=0.051..0.051 rows=68 loops=1)
                                                                Index Cond: ((hotel)::text = 'xray'::text)
                                      ->  Index Scan using tango_quebec on sierra_echo seven  (cost=0.560..25.530 rows=42 width=74) (actual time=0.068..0.124 rows=22 loops=9151)
                                              Index Cond: ((sierra_november)::text = (golf_two.lima_three)::text)
                                              Filter: (((hotel)::text = 'xray'::text) AND ((hotel)::text = (golf_two.hotel)::text))
                                ->  Result  (cost=0.000..0.000 rows=0 width=14) (actual time=0.000..0.000 rows=0 loops=204315)
                                        One-Time Filter: false
  Planning time: 4.141 ms
  Execution time: 12610.113 ms

To what I can ready, the main problem is this scan:

->  Index Scan using delta on victor_romeo golf_two  (cost=0.550..8.100 rows=1 width=1002) (actual time=0.104..0.104 rows=0 loops=47082)
        Index Cond: (((hotel)::text = 'xray'::text) AND ((lima_three)::text = (lima_whiskey.sierra_november)::text))
        Filter: ((november)::text = ANY ('victor_foxtrot'::text[]))
        Rows Removed by Filter: 1

This translates to an index scan over todo_item's primary key, and the filter is the condition on the status column.

Plain and simple, the question is: can anything be done to improve this, and if so, what? Can it be written in a much smarter way (probably, yes)? Are there indices to watch out for? Anything to try?


Additional details:

One thing I noticed now after posting (talk about rubberducking) is that LOWER probably kills the index usage. I'll turn the indices on item names and attribute values into expression indices on LOWER(…). I think there's a bigger issues here nonetheless.

Your Answer

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

Browse other questions tagged or ask your own question.