I found the culprit. There is the view current_object_state of this form:
CREATE OR REPLACE FORCE EDITIONABLE VIEW "CURRENT_OBJECT_STATE" (
"ZOID",
"TID",
"STATE"
) AS
SELECT
zoid,
tid,
state
FROM object_state
JOIN current_object
USING (zoid, tid);
The table object_state already has an unique index over (ZOID, TID) but the table current_object does not. So I added one manually:
CREATE UNIQUE INDEX "CURRENT_OBJECT_UI" ON "CURRENT_OBJECT" ("ZOID", "TID")
Now the SELECT from my previous post only lasts 55 ms instead of 35 s. So it is over 600 times faster! Now after starting zodbconvert again it is also a lot faster. Instead of 139 transactions after 68 minutes I now got 631 transactions after 8.6 minutes. That is nearly 36 times as fast as before.
I will send that fix to the RelStorage people over at Github.