query lenta solo cuando uso OR

[Patriarka]

Hola gente,
tengpo una query que relaciona 2 tablas con 3 y 5 millones de registros cada una,
el problema es que cuando agrego un OR tarda años en ejecutarse:
el filtro con el problema:

AND (
COLUMNA1 = '9999999999' OR COLUMNA2 = '9999999999' OR COLUMNA3 = '9999999999'
);

en caso que solo filtre por una columna cualquiera de las mencionadas la query se ejecuta al instante:


AND COLUMNA1 = '9999999999';

NOTA: las columnas COLUMNA1 , COLUMNA2 y COLUMNA3 son indices en una tabla


qué podria estar pasando? sospecho que el OR esta el problema de la lentitud pero no puedo comprobarlo, alguna ayuda?