Can anything reveal that 2 independant entries were created or updated at the same time? Imaginary example, simplified to better explain the question.
Let's say I have a form with the following fields :


user email
who did you vote for in 2012
who did you vote for in 2016


When submitted, I fill the following PostgreSQL (v.11) DB tables :

"UserList" table


Serial (auto-increment INT)
Email (text)


"UserData" table


Unique_Random (INT)
Vote_2012 (text)
Vote_2016 (text)


The entries are (as far as I can tell) unlinkable across tables because there is no relation between the Serial and the Unique Random ints.

Threat model : attacker gains full control of the postgreSQL DB server (both hardware and software)

If I am correct, UserData entries are not inserted in any specific position when created, so it should not be possible to tell which was added last.

Is there anything else (logs, data position on disk, memory, ...) that can reveal which entries were created or updated at the same time (and thus are linked) ?

If so, what can be done to prevent this ?
Rows inserted at the same time, particularly in the insert-only use case such as yours, will very likely reside next to each other on disk and as a result will have tuple IDs indicating that. They will remain so until you CLUSTER the table using  your unique_random1 column as the index key. You will need to run CLUSTER periodically to shuffle newly inserted rows.

Another bit of information that potentially correlates inserted rows is their transaction ID (XID), which might remain unchanged after the original commit, unless these rows at some later time are updated by separate transactions. I don't believe CLUSTER changes row XIDs.

Basically the same information -- the transaction ID, along with the row data, -- will also be stored in the write-ahead log (WAL). WAL segments will get overwritten at some point, depending on your database's checkpoint frequency.

TL;DR: You probably shouldn't rely on Postgres internals for reliable deidentification of your data. 



1 -- Although, what's truly random, cannot have guaranteed uniqueness. You probably meant some sort of a hash.