3

I have a table of data which is be outputted into a stream, so the upper bound of the cost doesn't matter as much as the lower bound. The table contains about 200M rows. The question is how to structurize indexes and queries with order by such that Postgres would use the index instead of doing additional sorting.

Each entry is characterized by 5 fields each of which is not unique on its own:

  • date of occurrence (timestamp)
  • num (order within a timestamp)
  • type1
  • type2
  • id_in_type2 (never used without type2)

A typical query for this data is bounded by date (say, from 1 day before now until now) and zero or more (about 5 actually) filters by any combination of type1, type2 and id_in_type2 connected by OR, and expects a stream of data (it doesn't matter how long it takes to output it completely, but it should start streaming as fast as possible), example:

SELECT *
FROM MY_TABLE
WHERE date > ?
AND (
  (type1 = ?)
  OR (type2 = ?)
  OR (type2 = ? AND associated_id = ?)
  OR ...
)
ORDER BY date, num;

When there are no additional filters or there is just one, a simple index by (date, num, type1, type2, associated_id) works perfectly - since the results are stored along the sort order of the index, there's no problem to start outputting the results.

However, when things get more complicated, no combination of structures of my indexes and my queries seem to yield satisfying results. Here's roughly what I tried so far:

Indexes: I tried having a separate index for (date, num) and 3 separate ones for other fields (like in the example below), I tried adding date to filters 2-4, i tried putting date and num as first fields in the index as well as the last ones.

CREATE INDEX my_table_1 ON my_table (date, num);
CREATE INDEX my_table_2 ON my_table (type1);
CREATE INDEX my_table_3 ON my_table (type2, id_in_type2);
CREATE INDEX my_table_4 ON my_table (type1, type2, id_in_type2);

Queries: I tried to select by date range and then by filters, I tried putting the filter by date to the end, I tried splitting the filters to separate ones and make a union.

No matter what I do, it won't apply the filters along the (date, num) index order, it will always do the sorting, yielding lower cost about the same as the upper cost.

Oh yes the table is also partitioned by date.

Any ideas on structurizing the indexes? Maybe I'd be better off returning all results with matching date and make the filtering in the app that's reading the stream?

Here's an execution plan for a naively constructed query with index setting as shown above (I ran this one on a test DB which is not partitioned and has 2M rows total, I'm presuming that on production table numbers will be different but orders of magnitude of difference between lower cost and upper cost are going to be about the same)

explain analyze
select * from my_table
where date >= now() - '1 day'::interval
  and (
    (type2 = 'T2A' and type1 = 'T1A')
    or (type2 = 'T2B' and type1 = 'T1B1')
    or (type1 = 'T1C')
    or (type2 = 'T2B' and type1 = 'T1B2')
  )
order by date, num;

Sort  (cost=157714.25..158431.63 rows=286949 width=262) (actual time=2153.327..2313.075 rows=600314 loops=1)
  Sort Key: date, num
  Sort Method: external merge  Disk: 144376kB
  ->  Bitmap Heap Scan on my_table  (cost=16602.76..96390.20 rows=286949 width=262) (actual time=199.193..1281.214 rows=600314 loops=1)
        Recheck Cond: (((type1)::text = 'T1A'::text) OR (((type1)::text = 'T1B1'::text) AND ((type2)::text = 'T2B'::text)) OR ((type1)::text = 'T1C'::text) OR (((type1)::text = 'T1B2'::text) AND ((type2)::text = 'T2B'::text)))
        Rows Removed by Index Recheck: 455892
        Filter: ((date >= (now() - '1 day'::interval)) AND ((((type2)::text = 'T2A'::text) AND ((type1)::text = 'T1A'::text)) OR (((type2)::text = 'T2B'::text) AND ((type1)::text = 'T1B1'::text)) OR ((type1)::text = 'T1C'::text) OR (((type2)::text = 'T2B'::text) AND ((type1)::text = 'T1B2'::text))))
        Rows Removed by Filter: 2
        Heap Blocks: exact=42763 lossy=26546
        ->  BitmapOr  (cost=16602.76..16602.76 rows=299384 width=0) (actual time=188.980..188.980 rows=0 loops=1)
              ->  Bitmap Index Scan on my_table_2  (cost=0.00..4.44 rows=1 width=0) (actual time=0.037..0.037 rows=30 loops=1)
                    Index Cond: ((type1)::text = 'T1A'::text)
              ->  Bitmap Index Scan on my_table_4  (cost=0.00..8094.98 rows=148643 width=0) (actual time=93.562..93.562 rows=300240 loops=1)
                    Index Cond: (((type1)::text = 'T1B1'::text) AND ((type2)::text = 'T2B'::text))
              ->  Bitmap Index Scan on my_table_2  (cost=0.00..4.44 rows=1 width=0) (actual time=0.059..0.059 rows=28 loops=1)
                    Index Cond: ((type1)::text = 'T1C'::text)
              ->  Bitmap Index Scan on my_table_4  (cost=0.00..8211.96 rows=150741 width=0) (actual time=95.315..95.315 rows=300018 loops=1)
                    Index Cond: (((type1)::text = 'T1B2'::text) AND ((type2)::text = 'T2B'::text))
Planning time: 0.435 ms
Execution time: 2356.305 ms

The query may return 100s of thousands of rows.

  • Please also show the execution plan for the desirable query plan, where you just specify date and chop off all the OR conditions. – jjanes Nov 17 '16 at 21:02
  • Put all 4 fields in the index starting with the date,num sort key. – eckes Apr 23 '17 at 13:58
  • I am not sure if PostgreSQL will start sending data to the client before the server has completed... So, you can speed-up the query, but I am not sure at all that the server will start sending any data to the client until it has processed all the query. – joanolo Apr 23 '17 at 20:31
0

Have you tried making 4 separate queries, and then using union all, so that you can get rid of the or statements?

Example:

select * from my_table
where date >= now() - '1 day'::interval
  and type2 = 'T2A' 
  and type1 = 'T1A'

union all
select * from my_table
where date >= now() - '1 day'::interval
  and type2 = 'T2B' 
  and type1 = 'T1B1'
...
0

I would try a couple of things. First: instead of using an expression date >= now() - '1 day'::interval, I would compute the constant value on the server side and actually try the query like this:

explain analyze     
select * from my_table
where date >= '2017-04-22'
  and (
    (type2 = 'T2A' and type1 = 'T1A')
    or (type2 = 'T2B' and type1 = 'T1B1')
    or (type1 = 'T1C')
    or (type2 = 'T2B' and type1 = 'T1B2')
    )
order by date, num;

In some experiences, this makes a difference with regard to partitions


Secondly, I'd try to have the query in two stages, to see if this makes it easier for PostgreSQL to use the index more efficiently (if that is actually possible):

SELECT
    *
FROM
    (SELECT
        * 
    FROM
        my_table
    WHERE
      -- This where is *likely* to use index
      date >= '2017-04-22'   -- Use a CONSTANT (compute it on the client side)
      and 
      type1 IN ('T1A', 'T1B1', 'T1C', 'T1B2')
    ) AS s0
WHERE
    -- Now you actually fine-filter result
       (type1 = 'T1A'  and type2 = 'T2A')
    or (type1 = 'T1B1' and type2 = 'T2B')
    or (type1 = 'T1B2' and type2 = 'T2B')
    or (type1 = 'T1C')
ORDER BY
    date, num;

I've trie to simulate your scenario in DBFiddle, but, not knowing your specific data distribution... I don't manage to really simulate it well enough. In any case, in my simulation, the query worked differently when changing the function call with a constant.

These are a bit of "wild guesses". As already commented: I am not sure if PostgreSQL will start sending data to the client before the server has completed processing the whole query... You can probably speed-up the query, but I am not sure at all that the server will start sending any data to the client until it has processed all the query.

  • 1
    The derived table won't make a difference. It the where clause the the inner query really reduces the number of rows substantially, then putting that into a CTE might make a difference though – a_horse_with_no_name Apr 24 '17 at 6:13
  • In the query plan of PostgreSQL 9.6, it just pushes the condition and ANDs both WHEREs. – joanolo Apr 24 '17 at 6:55

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.