Let me correct myself here.
In general, if there is an equality predicate, an index is a must. partitioning is usually not required however it is recommended when the size of data is larger and efficient management (loading, building indexes, archiving, etc.) of that data is required.
Azure SQL will be able to locate the correct partition and then use index for search.
Should i create clustered index on (store_id, dep_id, timestamp)?
If the goal is just to make this one query perform well, then probably yes.
You should not create the clustered index for just one query, or even for a type of queries. There are many factors to consider, including column data types, the read and write workloads against the table, other indexes that may be needed, etc. Without all of that data, we cannot make a recommendation as to what the right clustered index should be in this case.
We recommend reading a series of blogs on sqlskills.com to learn the relevant considerations when selecting the clustered index, for example: More considerations for the clustering key – the clustered index debate continues! – Kimberly L. Tripp (sqlskills.com)
Regards,
Oury