Reasons to reorder results *within* a transaction?

I *know* that without an ORDER BY clause, the database is free to reorder results in any way it likes. However, I recently ran into a case where the *SAME* query was returning results in a different order *within* a single transaction, which surprised me (we fixed it by adding the missing ORDER BY). I would assume that once a transaction obtains a snapshot, all its read operations would return the same results.

Could concurrent updates in other transactions "move" tuples in the underlying heap files? Could the query optimizer decide to execute a query two different ways for some reason (e.g. statistics collected after the first query?). Clearly the way Postgres works internally is a bit different from what I assumed. Any references to docs I should read would be appreciated.

Roughly speaking, the schema is something like:

create table group_record (id integer primary key, group_id integer, data text);
(plus other tables)

The transaction is something like:

begin;
select * from group_record where group_id = x;

… reads and writes to/from other tables …

select * from group_record where group_id = x; -- returns results in a different order from first time
commit;

Needless to say, this is one of those fun rare bugs that appeared occasionally in the logs in our production server, and we couldn't seem to reproduce it in development.

Thanks!

Evan Jones

--
Work: https://www.mitro.co/ Personal: http://evanjones.ca/