Query with WHERE clause that would only return 1 row is throwing "System.QueryException: Non-selective query against large object type"

Question

From what I've read, this error should only occur when there is no WHERE clause, or when the WHERE clause isn't restrictive enough. In my case, neither is true. I am querying against a text formula field on the Campaign Member object that concatenates the contact Id and campaign Id, thus creating a unique key on each member record. Below is my code, and it's the CampaignMember query that's failing.

I've re-created verbatim one of these failed queries in the dev console. As expected, it returns one row. Could the issue have to do with querying against a formula field? I imagine since this presumably forces a broad calculation of every record's value to check the filter that this may be the problem, but am hoping to confirm before going through the effort of re-creating the formula as a logic-driven text field (ugh). Your help is appreciated!

    public static void AddToCampaign (List<Contact> triggerList, Map<Id,Contact> oldMap)
{
    Map<Contact,CampaignMember> contactMemberMap = new Map<Contact,CampaignMember>();
    Map<Contact,String> keyMap = new Map<Contact,String>();

    for (Contact c : triggerList)
    {
        if (c.AddToCampaign__c != null && c.AddToCampaign__c != oldMap.get(c.Id).AddToCampaign__c)// && c.AddToCampaignStatus__c != null)
        {
            String campaignId = c.AddToCampaign__c.substringBefore(' - ');
            String status = c.AddToCampaign__c.substringAfter(' - ');

            system.debug('contact: ' + c.Id + ', campaignId: ' + campaignId + ', status: ' + status);
            system.debug('adding key value ' + string.valueOf(c.Id).left(15) + ' | ' + string.valueOf(campaignId).left(15) + ' to keyMap');

            contactMemberMap.put(c,new CampaignMember(Status = status,ContactId = c.Id,CampaignId = campaignId));
            keyMap.put(c,string.valueOf(c.Id).left(15) + ' | ' + string.valueOf(campaignId).left(15));
        }
        c.AddToCampaign__c = null;
    }
    if (!contactMemberMap.isEmpty())
    {
        List<CampaignMember> members = new List<CampaignMember>();
        Map<String,CampaignMember> memberMap = new Map<String,CampaignMember>();
        Map<String,Integer> statusRank = new Map<String,Integer>{'Sent' => 1,'Opened' => 2,'Clicked' => 3,'Replied' => 4,'Meeting Booked' => 5};

        for (String k : keyMap.values())
            system.debug('key: ' + k);

        system.debug('executing query, map size: ' + keyMap.size());

        // THIS IS THE FAILING QUERY
        for (CampaignMember m : [SELECT Id, Status, MemberKey__c FROM CampaignMember WHERE MemberKey__c IN :keyMap.values()])
        {
            if (new Set<String>(keyMap.values()).contains(m.MemberKey__c))
                memberMap.put(m.MemberKey__c,m);
        }
        for (Contact c : contactMemberMap.keySet())
        {
            String memberKey = keyMap.get(c);
            CampaignMember m = contactMemberMap.get(c);

            if (memberMap.containsKey(memberKey))
            {
                CampaignMember m2 = memberMap.get(memberKey);

                if (statusRank.get(m2.Status) < statusRank.get(m.Status))
                {
                    system.debug('new statusRank is higher, updating existing member for ' + memberKey);
                    m.Id = m2.Id;
                    members.add(m);
                }
            }
            else
            {
                system.debug('creating new member for ' + memberKey);
                members.add(m);
            }
        }
        if (!members.isEmpty())
            upsert members;
    }
}

Answer 1

By default, formulas do not actually store their results, and therefore a full table scan is necessary, even if there would conceptually be only a single value. In other words, you're absolutely correct that the formula is not doing what you think it does, and that you need an alternative solution. There are three basic options for this solution.

Option 1 is to request a Custom Index on the formula field. This only works if the formula is deterministic (which is true in this case, so you could go that route). You can read about it in this question, this blog post, etc.

Option 2 is to use a text field and populate it with a Process Builder, Workflow Rule, or Apex Trigger. This is actually pretty trivial, should only take a couple of minutes to set up. The worst part is dealing with the data load afterwards.

Option 3 is to just use the two fields separately. Both fields are indexed, so if you query them, it'll return the values you expect. I would do this in a Map.

Your code is pretty complicated, it could be a lot simpler with a bit of a design tweak. For example, you could use two fields, a Campaign Lookup and a Status Picklist or something. Or a custom import process written in a component or Apex or something.

There's plenty of easier ways to get where you're going. In fact, using just normal insert operations against the campaign id, contact id, and status would be enough to overwrite the previous status, if that's doable. You might want to take a step back and rethink how you're going about accomplishing your task (and perhaps write a separate, detailed question about that process). You may want to read more about the X-Y Problem, as this probably applies here.