Problema con borrado de tablas relacionadas.

Buenos días amigos Listeros.

Acudo a ustedes con un problema que me está pateando fuertemente. Tengo
estas dos tablas relacionadas a través de un Foreign Key

CREATE TABLE titulos
(
cod_titulo numeric(8) NOT NULL,
titulo character varying(512),
caracter_orden numeric(4),
titulo_salida character varying(512),
CONSTRAINT pk_titulos PRIMARY KEY (cod_titulo)
)

CREATE INDEX titulo
ON titulos
USING btree
(titulo);

CREATE TABLE codtit
(
acceso character varying(13),
ext_acceso numeric(4),
cod_titulo numeric(8),
tipo_tit character varying(5),
portada character varying(1),
orden numeric(4),
tipo_doc character varying(8),
id_cod_titulo numeric(10) NOT NULL DEFAULT
nextval('codtit_id_cod_titulo_seq'::regclass),
CONSTRAINT pk_codtit PRIMARY KEY (id_cod_titulo),
CONSTRAINT fk_cod_titulo03 FOREIGN KEY (cod_titulo)
REFERENCES titulos (cod_titulo) MATCH SIMPLE
ON UPDATE CASCADE ON DELETE RESTRICT,
CONSTRAINT idx_id_cod_titulo UNIQUE (id_cod_titulo)
)

-- Index: cod_titulo

-- DROP INDEX cod_titulo;

CREATE INDEX cod_titulo
ON codtit
USING btree
(cod_titulo);

-- Index: idx_codtitulo01

-- DROP INDEX idx_codtitulo01;

CREATE INDEX idx_codtitulo01
ON codtit
USING btree
(acceso, ext_acceso, cod_titulo, tipo_tit);

Perdonen la cantidad de SQL pero es para ilustrar mejor el ejemplo. La tabla
títulos posee 310.000 registros y la tabla codtit 370.000 registros. Estan
relacionados por la FK "fk_cod_titulo03", ahora bien si se desea hacer
DELETE FROM TITULOS WHERE cod_titulo = XXXXXXX y ese cod_titulo existe en la
tabla codtit, el manejador retorna error de clave foranea, lo cual está bien
pues en el ON DELETE está marcado como RESTRICT, pero si el cod_titulo no
está, el delete tarda 200 segundos, lo cual es un tiempo excesivo. Traté de
pedir explain de la consulta y el explain pasó de 1 hora y no dió resultado,
al cancerlo el pgsql me mostro esto: "SELECT 1 FROM ONLY "public"."codtit" x
WHERE "cod_titulo" = $1 FOR SHARE OF x". No entiendo porque esta situación
si el ya sabe que no existe registros referenciados.

Mucho le agradezco puedan ayudarme a clarificar la falla.

Atte.
Leonardo Castillo L.