Best indexing alternative to speed up querying my millions of data in PostgreSQL

Solution 1:

Based on this line from the plan:

Cond: ((m_other_table_id = '14b713d5-fb1a-4dbd-c013-fat4a7f6c8e3'::uuid) AND (m_city_id = 3))

your ideal index should be on (m_other_table_id, m_city_id). Not other_table_id, not city. The plan you showed doesn't really match the query, so it is hard to tell where the typos are - in the shown plan or in the shown query.

Also, since you order by timestamp, we can add it to the index.

So, I would try the following index:

CREATE INDEX idx ON my_schema.my_table USING btree 
    (m_other_table_id, m_city_id, timestamp DESC)

The order of columns here is important.