Depende de como você pesquisa.
Se você pesquisar assim:
/* Given a value from table1, find all related values from table2 */
SELECT *
FROM table1 t1
JOIN table_table tt ON (tt.table_1 = t1.id)
JOIN table2 t2 ON (t2.id = tt.table_2)
WHERE t1.id = @id
então você precisa:
ALTER TABLE table_table ADD CONSTRAINT pk_table1_table2 (table_1, table_2)
Nesse caso,
table1 estará liderando em NESTED LOOPS e seu índice será utilizável somente quando table1 é indexado primeiro. Se você pesquisar assim:
/* Given a value from table2, find all related values from table1 */
SELECT *
FROM table2 t2
JOIN table_table tt ON (tt.table_2 = t2.id)
JOIN table1 t1 ON (t1.id = tt.table_1)
WHERE t2.id = @id
então você precisa:
ALTER TABLE table_table ADD CONSTRAINT pk_table1_table2 (table_2, table_1)
pelos motivos acima.
Você não precisa de índices independentes aqui. Um índice composto pode ser usado em todos os lugares onde um índice simples na primeira coluna pode ser usado. Se você usar índices independentes, não poderá pesquisar com eficiência os dois valores:
/* Check if relationship exists between two given values */
SELECT 1
FROM table_table
WHERE table_1 = @id1
AND table_2 = @id2
Para uma consulta como essa, você precisará de pelo menos um índice em ambas as colunas.
Nunca é ruim ter um índice adicional para o segundo campo:
ALTER TABLE table_table ADD CONSTRAINT pk_table1_table2 PRIMARY KEY (table_1, table_2)
CREATE INDEX ix_table2 ON table_table (table_2)
A chave primária será usada para pesquisas
on both values e para pesquisas baseadas no valor de table_1 , o índice adicional será usado para pesquisas com base no valor de table_2 . 
