Home > Enterprise >  How to compute SQL query complexity
How to compute SQL query complexity

Time:06-13

I have a table with only 3 columns: id, name and timestamp , and it is required to extract for each id (and therefore for each name) the most recent timestamp.

For example having this table:

id name timestamp
1 foo 2022-02-02
1 foo 2022-03-02
2 bar 2022-01-01
2 bar 2022-04-01

It is expected to get as result:

1,foo,2022-03-02
2,bar,2022-04-01

One implementation could be:

select id, name, timestamp
from
(select 
    *,
    row_NUMBER() over(partition by id order by timestamp desc ) ranking
from sample) a
where a.ranking=1

Another possible solution would be this:

select *
from
(select id,max(timestamp) max_timestamp
from sample
group by id) foo,
sample s
where foo.id=a.id
and a.timestamp=foo.max_timestamp

but I think is less efficient.

How can I formally compute the space complexity of the first solution and compare it with the second one?

CodePudding user response:

If we want to take last timestamp from each id, and name must be from this last record, then:

select 
  distinct on (id) id,
  name,
  timestamp 
from sample 
order by id,timestamp desc

Complexity can be checked by using EXPLAIN keyword before query. EXPLAIN show estimates, EXPLAIN ANALYZE additionally run query and shows real time consumed by query. Efficiency depends on table definition and indexes.

CodePudding user response:

You can easily use group by and max functions to get the last timestamp for each id.

select id
      ,name
      ,max(timestamp)
from t
group by id, name 
id name max
1 foo 2022-03-02 00:00:00
2 bar 2022-04-01 00:00:00

Fiddle

  • Related