Big O notation of Postgresql Max with timescaledb index

December 15, 2021

I am writing some scripts that need to determine the last timestamp a timeseries datastream that can be interupted.

I am currently working out the most efficient way to do this, the simplest would be to look for the largest timestamp using MAX. As the tables in question are timescaledb hypertables they are indexed, so in theory it should be a case of following the index to find the largest and this should be very efficient operation. However, I am not sure if this is actually true and was wondering if anyone knew how max scales if it’s working down an index, I know it’s an O(n) function normally.

>Solution :

If there is an index on the column, max can use the index and will become O(1):

EXPLAIN (COSTS OFF) SELECT max(attrelid) FROM pg_attribute;

                                          QUERY PLAN                                          
══════════════════════════════════════════════════════════════════════════════════════════════
 Result
   InitPlan 1 (returns $0)
     ->  Limit
           ->  Index Only Scan Backward using pg_attribute_relid_attnum_index on pg_attribute
                 Index Cond: (attrelid IS NOT NULL)
(5 rows)