Нужен explain (analyze,buffers), сильно желательно с track_io_timing = on в конфиге.
параметр work_mem на данный запрос не может оказывать почти никакого влияния
Оказывает. Если планировщик решит, что work_mem не хватает - не будет hash join. Для сортировки 27кб, очевидно, без разницы.
Впрочем, зачем вам вообще join подзапроса где одна только группировка подзапроса занимает половину времени ответа? Вам простой exists нужен.
SELECT "t1".* FROM table_1 as t1
where exists (select 1 from table_2 as t2 WHERE t1.primarykey=t2.session)
ORDER BY "starttime" DESC LIMIT 20;
А дальше know your data. Если по starttime DESC быстро находятся нужные exists - будет хорошо. Если exists мало - стоит подумать, а не денормализовать ли этот признак в table_1 с триггером для консистентности в table_2 и частичным индексом по starttime where t2_exists.
Поля session и primarykey в формате uuid
Не очень хорошая идея. Оно и сильно медленнее при сравнении относительно bigint (особенно если речь о varchar, а не uuid типе данных) и из-за случайного распределения несколько сбивает с толку статистику планировщика.