Retrieving changed rows only from a table with 10^7 rows
If the version was 9.3 or newer, I would try this rewrite of the query:

SELECT
    w.stamp,
    w.column1,
    w.column2,
    w.column3
FROM 
    "table_name" AS w
  JOIN LATERAL
    ( SELECT p.column1, p.column2, p.column3
      FROM "table_name" AS p
      WHERE p.stamp &lt; w.stamp
        AND p.stamp &gt;= '2015-12-01'::timestamp
      ORDER BY p.stamp DESC
      LIMIT 1
    ) AS p
    ON (w.column1, w.column2, w.column3)
       IS DISTINCT FROM
       (p.column1, p.column2, p.column3)
WHERE w.obj_id = 42 
  AND w.stamp &gt;= '2015-12-01'::timestamp
  AND w.stamp &lt;= '2016-01-23'::timestamp 
ORDER BY w.stamp DESC 
LIMIT 100 ;


with the index you have and with an index on (obj_id, stamp DESC)



Unrelated to efficiency: are you sure that you want to use BETWEEN with timestamps? It's more common to work with inclusive-exclusive ranges. In other words, shouldn't this condition:

  AND w.stamp &lt;= '2016-01-23'::timestamp 


be?:

  AND w.stamp  &lt; '2016-01-23'::timestamp 


With BETWEEN (and &lt;=), you are searching though a range that is 53 whole days long + 1 microsecond (or whatever the accuracy of timestamp is).