title: Indexing columns across multiple tables in PostgreSQL
body: <p>I'm trying to optimize the following join query:</p>
  
  <p>A notification is a record that says whether a user has read some activity. One notification points to one activity but many users can be notified about an activity. The activity record has some columns such as the workspace the activity is in and the type of activity.</p>
  
  <p>This query gets the user non-comment notifications that have been read in a specific workspace ordered by time.</p>
  
  <pre><code>explain analyze
  select activity.id from activity, notification
  where notification.user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'
  and notification.read = true
  
  and notification.activity_id = activity.id
  
  and activity.space_id = '6d702c09-8795-4185-abb3-dc6b3e8907dc'
  and activity.type != 'commented'
  order by activity.end_time desc
  limit 20;
  </code></pre>
  
  <p>The problem is that this query has to run through every notification the user has every gotten.</p>
  
  <pre><code>Limit  (cost=4912.35..4912.36 rows=1 width=24) (actual time=138.767..138.779 rows=20 loops=1)
    -&gt;  Sort  (cost=4912.35..4912.36 rows=1 width=24) (actual time=138.766..138.770 rows=20 loops=1)
          Sort Key: activity.end_time DESC
          Sort Method: top-N heapsort  Memory: 27kB
          -&gt;  Nested Loop  (cost=32.57..4912.34 rows=1 width=24) (actual time=1.354..138.606 rows=447 loops=1)
                -&gt;  Bitmap Heap Scan on notification  (cost=32.01..3847.48 rows=124 width=16) (actual time=1.341..6.639 rows=1218 loops=1)
                      Recheck Cond: (user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'::uuid)
                      Filter: read
                      Rows Removed by Filter: 4101
                      Heap Blocks: exact=4774
                      -&gt;  Bitmap Index Scan on notification_user_id_idx  (cost=0.00..31.98 rows=988 width=0) (actual time=0.719..0.719 rows=5355 loops=1)
                            Index Cond: (user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'::uuid)
                -&gt;  Index Scan using activity_pkey on activity  (cost=0.56..8.59 rows=1 width=24) (actual time=0.108..0.108 rows=0 loops=1218)
                      Index Cond: (id = notification.activity_id)
                      Filter: ((type &lt;&gt; 'commented'::activity_type) AND (space_id = '6d702c09-8795-4185-abb3-dc6b3e8907dc'::uuid))
                      Rows Removed by Filter: 1
  Planning time: 0.428 ms
  Execution time: 138.825 ms
  </code></pre>
  
  <p><strong>Edit:</strong> Here is the performance after the cache has been warmed.</p>
  
  <pre><code>Limit  (cost=4912.35..4912.36 rows=1 width=24) (actual time=13.618..13.629 rows=20 loops=1)
    -&gt;  Sort  (cost=4912.35..4912.36 rows=1 width=24) (actual time=13.617..13.621 rows=20 loops=1)
          Sort Key: activity.end_time DESC
          Sort Method: top-N heapsort  Memory: 27kB
          -&gt;  Nested Loop  (cost=32.57..4912.34 rows=1 width=24) (actual time=1.365..13.447 rows=447 loops=1)
                -&gt;  Bitmap Heap Scan on notification  (cost=32.01..3847.48 rows=124 width=16) (actual time=1.352..6.606 rows=1218 loops=1)
                      Recheck Cond: (user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'::uuid)
                      Filter: read
                      Rows Removed by Filter: 4101
                      Heap Blocks: exact=4774
                      -&gt;  Bitmap Index Scan on notification_user_id_idx  (cost=0.00..31.98 rows=988 width=0) (actual time=0.729..0.729 rows=5355 loops=1)
                            Index Cond: (user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'::uuid)
                -&gt;  Index Scan using activity_pkey on activity  (cost=0.56..8.59 rows=1 width=24) (actual time=0.005..0.005 rows=0 loops=1218)
                      Index Cond: (id = notification.activity_id)
                      Filter: ((type &lt;&gt; 'commented'::activity_type) AND (space_id = '6d702c09-8795-4185-abb3-dc6b3e8907dc'::uuid))
                      Rows Removed by Filter: 1
  Planning time: 0.438 ms
  Execution time: 13.673 ms
  </code></pre>
  
  <p>I could create a multi-column index on user_id and read, but that doesn't solve the issue I'm trying to solve.</p>
  
  <p>I could solve this problem myself by manually denormalizing the data, adding the space_id, type, and end_time columns in the notification record, but that seems like it should be unnecessary.</p>
  
  <p>I would expect Postgres to be able create an index across the two tables, but everything I read so far says this isn't possible.</p>
  
  <p>So my question: what is the best way to optimize this query?</p>
  
  <hr>
  
  <p><strong>Edit:</strong> After creating the suggested indexes:</p>
  
  <pre><code>create index tmp_index_1 on activity using btree (
      space_id, 
      id, 
      end_time
  ) where (
      type != 'commented'
  );
  
  create index tmp_index_2 on notification using btree (
      user_id,
      activity_id
  ) where (
      read = true
  );
  </code></pre>
  
  <p>The query performance improved 3x.</p>
  
  <pre><code>explain analyse
  select activity.id from activity
  INNER JOIN notification  ON  notification.user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'
      and notification.read = true
      and notification.activity_id = activity.id
      and activity.space_id = '6d702c09-8795-4185-abb3-dc6b3e8907dc'
      and activity.type != 'commented'
  order by activity.end_time desc
  limit 20;
  
  Limit  (cost=955.26..955.27 rows=1 width=24) (actual time=4.386..4.397 rows=20 loops=1)
    -&gt;  Sort  (cost=955.26..955.27 rows=1 width=24) (actual time=4.385..4.389 rows=20 loops=1)
          Sort Key: activity.end_time DESC
          Sort Method: top-N heapsort  Memory: 27kB
          -&gt;  Nested Loop  (cost=1.12..955.25 rows=1 width=24) (actual time=0.035..4.244 rows=447 loops=1)
                -&gt;  Index Only Scan using tmp_index_2 on notification  (cost=0.56..326.71 rows=124 width=16) (actual time=0.017..1.039 rows=1218 loops=1)
                      Index Cond: (user_id = '9a51f675-e1e2-46e5-8bcd-6bc535c7e7cb'::uuid)
                      Heap Fetches: 689
                -&gt;  Index Only Scan using tmp_index_1 on activity  (cost=0.56..5.07 rows=1 width=24) (actual time=0.002..0.002 rows=0 loops=1218)
                      Index Cond: ((space_id = '6d702c09-8795-4185-abb3-dc6b3e8907dc'::uuid) AND (id = notification.activity_id))
                      Heap Fetches: 1
  Planning time: 0.484 ms
  Execution time: 4.428 ms
  </code></pre>
  
  <p>The one thing that still bothers me about this query is the <code>rows=1218</code> and <code>loops=1218</code>. This query is looping through all of the read user notifications and querying against the activities table. </p>
  
  <p>I would expect to be able to create a single index to read all of this in a manner that would mimic denormalizing this data. For example, if I add space_id, type, and end_time to the notification table, I could create the following index and read in fractions of a millisecond.</p>
  
  <pre><code>create index tmp_index_3 on notification using btree (
      user_id,
      space_id,
      end_time desc
  ) where (
      read = true 
      and type != 'commented'
  );
  </code></pre>
  
  <p>Is this not currently possible within Postgres without denormalizing?</p>