How to optimize selection of pairs from one column of the table (self-join)?
Postgresql 9.5.19 has windowing functions that prove helpful in such situation. The lead() function give you access to the next row in a "partition".

You could try something like that :

SELECT
  user_name,
  place_name AS r1_place,
  tm AS r1_tm,
  lead(place_name) OVER (PARTITION BY user_name ORDER BY tm) AS r2_place,
  lead(tm) OVER (PARTITION BY user_name ORDER BY tm) AS r2_tm
FROM example
ORDER BY 1, 3;


resulting in :

user_name|r1_place|r1_tm              |r2_place|r2_tm              |
---------|--------|-------------------|--------|-------------------|
user_1   |place_1 |2020-02-25 00:00:19|place_2 |2020-03-25 00:00:19|
user_1   |place_2 |2020-03-25 00:00:19|        |                   |
user_2   |place_1 |2020-02-25 00:00:19|        |                   |
user_3   |place_2 |2020-02-25 00:00:19|place_1 |2020-03-25 00:00:19|
user_3   |place_1 |2020-03-25 00:00:19|        |                   |


Not sure about the performance part however... you should make some tests.

Of course, you can filter out null results:

SELECT * FROM (
  SELECT
    user_name,
    place_name AS r1_place,
    tm AS r1_tm,
    lead(place_name) OVER (PARTITION BY user_name ORDER BY tm) AS r2_place,
    lead(tm) OVER (PARTITION BY user_name ORDER BY tm) AS r2_tm
  FROM example
  ORDER BY 1, 3) req
WHERE r2_place IS NOT null