We have a foreign key constraint that references (label, state_machine). This has a corresponding btree index, where the ordering of the components of the contraint matter.
This means that queries, which typically filter on state machines, are often taking much longer than they need to because they can't use the index to filter history entries.
We should reverse the order of the components in the foreign key constraint.