Mejorar performance de un maestro detalle

Gente:
Tengo un programa que se encarga de trabajar con pedidos a clientes
y basicamente su core se compone de cabecera y detalle:

El volumen de datos es bastante alto (aprox 500.000 registros de
detalle) y cada pedir por detalle suele no ser > 6 registros.

El problema que me aparece es que en cualquier consulta en la que
participan estas dos tablas, la misma se vuelve considerablemente lenta.
Para asegurar esto hice un explain tanto de una consulta donde estas
tablas formaban parte como asi tambien lo hice con estas dos tablas
solas y tambien obtengo el resultado malo en cuanto a tiempos.

Lo que quiero pedir es alguna experiencia, sugerencia, quizas el metodo
del indice o cualquier cosa que me pueda ayudar con esto ya que el
impacto hoy por hoy es alto para el aplicativo y viendolo en forma
optimista, si le encuentro alguna solucion .... digamos que todo lo
lento se arregla.
Saludos.

(dejo solo lo que importa):

CABECERA
CREATE TABLE pedidos_cabe
(
idpedido_cabe numeric(18,0) NOT NULL DEFAULT
nextval('seq_pedidos_cabe'::regclass),
....
idempresa numeric(18,0) NOT NULL,
CONSTRAINT pk_pedidos_cabe PRIMARY KEY (idpedido_cabe , idempresa ),
....
)
WITH (
OIDS=TRUE
);

Detalle:
CREATE TABLE pedidos_deta
(
idpedido_deta numeric(18,0) NOT NULL DEFAULT
nextval('seq_pedidosdeta'::regclass),
idpedido_cabe numeric(18,0) NOT NULL,
....
idempresa numeric(18,0) NOT NULL,
CONSTRAINT pk_pedidos_deta PRIMARY KEY (idpedido_deta , idempresa ),
CONSTRAINT fk_pedidos_deta_cabe FOREIGN KEY (idpedido_cabe, idempresa)
REFERENCES pedidos_cabe (idpedido_cabe, idempresa) MATCH SIMPLE
..
)
WITH (
OIDS=TRUE
);