Indexed columns are a great way to improve performance. Especially the SiteMapProviders (used by a CQWP) benefit from the indexes. I know there are some performance-tests out there, but just try to index every field you use in a Content Query Webpart and you'll know the difference. 

It's a shame not every fieldtype can be indexed. In my experience only Text, Number, Date and Choice can be indexed. So what about Lookups, Calculated values or Custom fieldtypes?

My workaround is to copy the values of those field types to a plain textfield and to index those textfields. This can easily be done by a workflow or an event handler:

public override void HandleEvent(SPItemEventProperties properties)
{
    if (properties.EventType == SPEventReceiverType.ItemUpdated || properties.EventType == SPEventReceiverType.ItemAdded)
    {
        SPListItem item = properties.ListItem;

        // Copy contents of the Lookup to a text field for indexing
        SPFieldLookupValueCollection values = item["LOOKUP"] as SPFieldLookupValueCollection;
        if (values != null)
        {
            foreach (SPFieldLookupValue value in values)
            {
                item["LOOKUP_INDEXED"] += ", " + value.LookupValue;
            }

            // update the item without user/time-stamp 
            item.SystemUpdate(false);
        }
    }
}