The Knowledge Article: 000006007 - Custom indexes for an organization to help improve performance lists the following in relations to indexes on formula fields:
Formula field can also be indexed since Summer 12. The following rules have to be true in order to index a formula field:
- The formula contains fields from a single object only (not relationship fields).
- The formula field doesn't reference any non-deterministic functions (e.g. SYSDATE).
- The formula field doesn't reference any non-supported fields for including in indexes. This list isn't documented anywhere specifically (there are lots of special cases), but in Spring 12(176), createdById was non-supported, but in Summer 12 (178), it is supported. Same story for CreatedDate.
- The formula field contains references to Primary Keys (e.g Id)
If one of the condition above is false, the "Add index" does not display on the BT of the field.
Referencing a date function that returns a different result each day is a clear example of something that would be non-deterministic.
What else would make a formula non-deterministic and therefore not available for a custom index?