CREATE TABLE reftable (id INT NOT NULL PRIMARY KEY)
CREATE TABLE mytable (id INT NOT NULL, ref INT NOT NULL)
ALTER TABLE mytable
ADD CONSTRAINT fk_mytable_ref_reftable
FOREIGN KEY (ref) REFERENCES reftable (id)
CREATE INDEX ix_mytable_ref ON mytable (ref)
Столбец в другой таблице (той, на которую вы ссылаетесь) должен быть PRIMARY KEY
или иметь ограничение UNIQUE
, определенное для него, что означает, что у него уже есть индекс.