despair1ладно попытаюсь спросить более конкретно:

чему пропорционально время выполнения запроса
"select * from table where primary_key == x"

len(table) или lg len(table) или len (x ) ?

чему пропроционально время выполнения запроса:

" select * from temp_table LEFT OUTER JOIN table ON (temp_table.pk == table.pk) where table.pk==NULL "

где pk - primary key

len(table)*len(temp_table) или len(table)+len(temp_table) ?

1)для вас на вашем уровне время выполнения "select * from table where primary_key == x" от размера таблицы не зависит и является констаной принимающей 2 занения приблизительно 0.01 ms если нужная строка в памяти и 10ms если нужная строка находится на неперегруженном диске + сетевые расходы если запрос производится по сети (0.2-5ms на запрос)

2)смотря от размера временной таблицы конечно но если он <<< размера основной таблицы то длинна временной таблицы * константу из п1 за вычетом сетевых расходов


если запросы выполняются по сети - то 5секунд на выполнение 2000-8000 запросов вполне нормальный результат.

despair1есть таблица в которой будет около 100к-1кк записей

после запроса пользователя в нее нужно внести до 1к-4к записей, содержащих primary key, часть из которых уже может находиться в таблице

без оптимизации алгоритм типа:
для каждой записи пользователя:
проверить наличие pk в таблице, если нет внести запись в таблицу

выполняется 5 секунд, на полупустой базе данных, как можно оптимизировать его исполнение?

вообще быстрее всего
create temp table ...
copy from stdin to temp table
analyze temp table
insert ... select * from temptable where not exists (select * from table);

как то так...

Это спасет вас от сетевых задержек но если вопрос упирается в доступ к диску то сильно быстрее чем было не станет.

--Maxim Boguk
www.postgresql-consulting.ru