0

Let's say I have this table:

create table "Sample"(
    "id" bigserial primary key,
    "source" varchar not null,
    "category" int not null,
    "t1" timestamp with time zone not null
);

this table will become quite large, and there is a I will be running on it that I would want to be as efficient as possible:

-- get least "t1" filtered by "category" and "id"
select
    min("t1")
from "Sample"
where
    "category" in (1,3,5,7,9,3,6,3) -- <-- in a set of about 5-20 values
    and "id">95492583

column details

  • t1: a somewhat random timestamp (though never greater than current_timestamp)
  • category: one of (currently) approx. 1000 possible values. in time the number of possible values will increase (perhaps one day becoming 10000 or 20000)
  • id: I use the id in the condition because my application needs to know if there are any "newer" rows than the id it already has in memory

I am trying to decide what would be the best indices here, for maximum performance (and of course also to learn)

reading various articles (like this one) I get that smaller granularity comes first, so I guess this is what I would do:

create index on "Sample"("category", "id", "t1");

But, does it make any sensor to have the primary key in the multi-column index?

5
  • It depends on the distribution of the data and how fast the query has to be. The ideal index might be CREATE INDEX ON "Sample" (source, value, id) INCLUDE (timestamp), but what is ideal for that one query might not be ideal for your complete workload. Commented Feb 26 at 16:25
  • thanks! the two queries I listed are the ones that will be run, and in practice the only two queries that will matter with regards to performance. so considering your suggestion perhaps CREATE INDEX ON "Sample" (source, value, id) INCLUDE (timestamp) and CREATE INDEX ON "Sample" (value, id) INCLUDE (timestamp) are the best bets?
    – birgersp
    Commented Feb 26 at 16:41
  • 1
    An index in (value, id) seems useless. Perhaps the best is on (value, source, id) INCLUDE (timestamp). Create a realistic amount of test data and experiment. Commented Feb 26 at 17:29
  • Will there always be the exact condition "source" in ('src1', 'src2') - and how many distinct values are there in source? Can anything else be said about the other conditions - and corresponding cardinalities? Write patterns? Newer rows will have greater timestamps? Commented Feb 26 at 22:41
  • Doing some more work on this, I realised the queries I wrote before wasn't that realistic. I changed the example table and queries now and added details about the columns.
    – birgersp
    Commented Feb 27 at 10:05

1 Answer 1

1

If you have several processes inserting concurrently, and you use sequence caching to speed it up, it is possible in some cases to have a lower id inserted after a higher id. Here's an explanation. If you do not use sequence caching, then a higher id means the row was inserted later.

I'll create some test data:

create unlogged table Sample(
    id          int,
    source      int not null,
    category    int not null,
    t1          float
);

INSERT INTO sample SELECT n, random()*1000, random()*1000, random()
FROM generate_series(1,20000000) n;
VACUUM ANALYZE sample;

Let's try the query without any index as baseline:

EXPLAIN ANALYZE SELECT min(t1) FROM Sample 
WHERE category in (1,3,5,7,9,3,6,3) AND id>9492583;

 Finalize Aggregate  (cost=315977.63..315977.64 rows=1 width=8) (actual time=699.530..703.572 rows=1 loops=1)
   ->  Gather  (cost=315977.41..315977.62 rows=2 width=8) (actual time=699.423..703.564 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Partial Aggregate  (cost=314977.41..314977.42 rows=1 width=8) (actual time=439.238..439.238 rows=1 loops=3)
               ->  Parallel Seq Scan on sample  (cost=0.00..314889.68 rows=35095 width=8) (actual time=142.004..437.847 rows=20974 loops=3)
                     Filter: ((id > 9492583) AND (category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])))
                     Rows Removed by Filter: 6645693
 Execution Time: 706.238 ms

We have a condition category=constant and id>constant, which maps well to a range scan of the following index:

CREATE INDEX ON Sample( category, id );
 
 Aggregate  (cost=123238.21..123238.22 rows=1 width=8) (actual time=148.206..148.207 rows=1 loops=1)
   ->  Bitmap Heap Scan on sample  (cost=1794.80..123027.64 rows=84227 width=8) (actual time=11.367..140.951 rows=62922 loops=1)
         Recheck Cond: ((category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])) AND (id > 9492583))
         Heap Blocks: exact=40884
         ->  Bitmap Index Scan on sample_category_id_idx  (cost=0.00..1773.74 rows=84227 width=0) (actual time=6.511..6.511 rows=62922 loops=1)
               Index Cond: ((category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])) AND (id > 9492583))
 Execution Time: 150.305 ms

Including the t1 column in the index makes it larger, but it avoids having to read the table:

CREATE INDEX ON Sample( category, id ) INCLUDE (t1);

Same query:

 Aggregate  (cost=3210.58..3210.59 rows=1 width=8) (actual time=10.207..10.207 rows=1 loops=1)
   ->  Index Only Scan using sample_category_id_t1_idx on sample  (cost=0.44..3000.01 rows=84227 width=8) (actual time=0.093..7.277 rows=62922 loops=1)
         Index Cond: ((category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])) AND (id > 9492583))
         Heap Fetches: 0
 Planning Time: 0.646 ms
 Execution Time: 10.252 ms

This is quite good. Now, this index is tempting too:

CREATE INDEX ON Sample( category, t1 ) INCLUDE (id);

It allows scanning values of t1 either in order (low to high) or reverse (high to low) for each category. This is sometimes useful for min() and max() because the lowest (or highest) values come first out of the index: if the row satisfies the other conditions, then there is no need to scan more rows.

You say timestamps in t1 are "somewhat random (though never greater than current_timestamp" and I take that as "somewhat monotonous". This means a high timestamp should be correlated with a high value of id.

Thus if you wanted min(t1) where id<constant, scanning t1 in order means the first row that satisfies the condition on id is also the min(t1). With "id<constant" it would probably be the first row out of the index, thus very fast. But with "id>constant", all ids before this will have to be skipped, so this is not a good optimization in this case.

Lets try something else:

create unlogged table Sampled(
    id          int,
    source      int not null,
    category    int not null,
    t1          float,
    part         int
);

"Part" is a bit like a partition key, it could be a day, or month, but in this example case I will just use id/1000000 to slice the table.

INSERT INTO Sampled SELECT id, source, category, t1, id/1000000 FROM Sample;
CREATE INDEX ON Sampled( category, id ) INCLUDE (t1);
CREATE INDEX ON Sampled( category, part, t1 );

Treating id like a date for the sake of explanation, "min(t1) AND id>'May 15'" can be rephrased as: the minimum of (min(t1) between May 15 and June 1, and min(t1) for the following months).

With a bit of a hack, we can index the latter, but it comes with a caveat: it has to be done manually, in order to trigger a nested loop.

Thus, we can rewrite "id>9492583" as "(id>9492583 AND id<10000000) OR (part>=10)". Therefore:

EXPLAIN ANALYZE
SELECT min(t1) FROM (
    SELECT t1 FROM
        (SELECT generate_series(10,20) part) parts CROSS JOIN
        (SELECT unnest(ARRAY[1,3,5,7,9,3,6]) category) cats
        JOIN LATERAL (SELECT t1 FROM Sampled s WHERE s.category=cats.category AND s.part=parts.part ORDER BY t1 LIMIT 1) sm ON (true)
    UNION ALL
        SELECT min(t1) FROM Sampled
        WHERE category in (1,3,5,7,9,3,6,3) AND id>9492583 AND id<10000000
) f;


Aggregate  (cost=219.69..219.70 rows=1 width=8) (actual time=0.983..0.984 rows=1 loops=1)
   ->  Append  (cost=0.56..219.50 rows=78 width=8) (actual time=0.024..0.976 rows=71 loops=1)
         ->  Nested Loop  (cost=0.56..48.19 rows=77 width=8) (actual time=0.023..0.533 rows=70 loops=1)
               ->  ProjectSet  (cost=0.00..0.05 rows=7 width=4) (actual time=0.002..0.003 rows=7 loops=1)
                     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.000..0.001 rows=1 loops=1)
               ->  Nested Loop  (cost=0.56..6.77 rows=11 width=8) (actual time=0.009..0.075 rows=10 loops=7)
                     ->  ProjectSet  (cost=0.00..0.07 rows=11 width=4) (actual time=0.000..0.001 rows=11 loops=7)
                           ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=7)
                     ->  Limit  (cost=0.56..0.60 rows=1 width=8) (actual time=0.006..0.006 rows=1 loops=77)
                           ->  Index Only Scan using sampled_category_part_t1_idx on sampled s  (cost=0.56..36.54 rows=999 width=8) (actual time=0.006..0.006 rows=1 loops=77)
                                 Index Cond: ((category = (unnest('{1,3,5,7,9,3,6}'::integer[]))) AND (part = (generate_series(10, 20))))
                                 Heap Fetches: 0
         ->  Aggregate  (cost=170.91..170.92 rows=1 width=8) (actual time=0.437..0.437 rows=1 loops=1)
               ->  Index Only Scan using sampled_category_id_t1_idx on sampled  (cost=0.44..160.57 rows=4137 width=8) (actual time=0.013..0.317 rows=3017 loops=1)
                     Index Cond: ((category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])) AND (id > 9492583) AND (id < 10000000))
                     Heap Fetches: 0
 Execution Time: 1.013 ms

Now this is a bit of a hack. I don't really recommend it.

This looks like time series data, so if you want to be able to quickly get rid of old data, I'd recommend partitioning the table, maybe based on id. Say a few million rows per partition.

Then if you really want to optimize the above query, you can create a materialized view. Since old partitions will never be modified, you can create a separate table which stores min(t1) per category, for certain ranges of id.

create unlogged table mat(
    category    int not null,
    part        int not null,
    min_t1      float,
    primary key (category, part)
);
INSERT INTO mat SELECT category, part, min(t1) FROM sampled GROUP BY category, part;
VACUUM ANALYZE mat;

You could also add other statistics, like max() etc. Now, to get the min(), we take one partial slice of id's from the main table, but we can take data about the full slices from the materialized view:

EXPLAIN ANALYZE
SELECT least( 
        (SELECT min(min_t1) FROM mat WHERE category IN (1,3,5,7,9,3,6) AND part>=10),
        (SELECT min(t1) FROM Sample WHERE category in (1,3,5,7,9,3,6,3) AND id>9492583 AND id<10000000)
) f;

 Result  (cost=340.87..340.88 rows=1 width=8) (actual time=0.533..0.534 rows=1 loops=1)
   InitPlan 1 (returns $0)
     ->  Aggregate  (cost=133.52..133.53 rows=1 width=8) (actual time=0.072..0.072 rows=1 loops=1)
           ->  Bitmap Heap Scan on mat  (cost=30.73..133.35 rows=70 width=8) (actual time=0.026..0.065 rows=60 loops=1)
                 Recheck Cond: ((category = ANY ('{1,3,5,7,9,3,6}'::integer[])) AND (part >= 10))
                 Heap Blocks: exact=45
                 ->  Bitmap Index Scan on mat_pkey  (cost=0.00..30.71 rows=70 width=0) (actual time=0.018..0.019 rows=60 loops=1)
                       Index Cond: ((category = ANY ('{1,3,5,7,9,3,6}'::integer[])) AND (part >= 10))
   InitPlan 2 (returns $1)
     ->  Aggregate  (cost=207.33..207.34 rows=1 width=8) (actual time=0.458..0.458 rows=1 loops=1)
           ->  Index Only Scan using sample_category_id_t1_idx on sample  (cost=0.44..196.54 rows=4314 width=8) (actual time=0.014..0.336 rows=3017 loops=1)
                 Index Cond: ((category = ANY ('{1,3,5,7,9,3,6,3}'::integer[])) AND (id > 9492583) AND (id < 10000000))
                 Heap Fetches: 0
 Planning Time: 0.232 ms
 Execution Time: 0.563 ms

This is faster and it uses less space, because it doesn't require two indices on the main table, only one. Plus it works well with partitioning the table, which is a plus.

Since it looks like time series, I also tried Clickhouse.

create table Sample(
    id          Int32 NOT NULL CODEC(Delta,ZSTD(9)),
    source      Int32 NOT NULL CODEC(Delta,ZSTD(9)),
    category    Int32 NOT NULL CODEC(ZSTD(9)),
    t1          float NOT NULL CODEC(ZSTD(9)),
) ENGINE=MergeTree ORDER BY (category,id) PRIMARY KEY (category,id);

SELECT min(t1)
FROM Sample
WHERE (category IN (1, 3, 5, 7, 9, 3, 6, 3)) AND (id > 9492583)

┌─────────min(t1)─┐
│ 0.0000036271535 │
└─────────────────┘

1 row in set. Elapsed: 0.004 sec. Processed 180.22 thousand rows, 1.77 MB (45.81 million rows/s., 449.37 MB/s.)
Peak memory usage: 1.39 MiB.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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