How can I speed up performance of this Firestore query loop? Comparing phone contact list to Firestore database for matches

I am comparing a list of contacts' emails in the user's phone to a list of user's emails in my Firestore Database, and then creating a new list of "contactsInApp".

First, I get the entire collection of users from firestore database. Then for each user, I create a forEach loop, checking each contact in my list of phone contacts for a match. If there is a match, it creates a new list of "androidContactsInApp". It works fine when there are a small amount of users, but when I tested it with 5,000 users, it takes much longer - about 30 seconds. I thought firestore was supposed to scale well, so wondering if there is problem with my code.

Here is my code:

fsDB.collection("users")
                .get().addOnSuccessListener(new OnSuccessListener<QuerySnapshot>() {
            @Override
            public void onSuccess(QuerySnapshot documentSnapshots) {
                for (DocumentSnapshot document : documentSnapshots) {

                    String userEmail = document.get("email").toString();

                    for (UserInfoForRequest android_contact: arrayListAndroidContacts) {
                        String isEmailInDatabase = android_contact.getUserEmail();
                        String trimmedEmail = isEmailInDatabase.trim();
                        if (userEmail.equals(trimmedEmail)) {
                            String userID = document.getId();


                            UserInfoForRequest android_contact2 = new UserInfoForRequest();
                            android_contact2.setUserName(document.get("username").toString());
                            android_contact2.setUserEmail(userEmail);
                            android_contact2.setCurrentUID(currentUID);
                            android_contact2.setContactsUID(userID);
                            arrayListAndroidContactsInApp.add(android_contact2);

                        }


                    }

                }
                adapterWithApp.notifyDataSetChanged();
                adapterNoApp.notifyDataSetChanged();
            }
        });

I have also tried inverting the loop. Doing it that way, I get each contact within my list of phone contacts, and I perform a query for each phone contact. This means I don't have download the entire collection of users. This method is much, much slower - multitudes slower. I think that is because I perform separate, individual queries. Here is my code:

        for (final UserInfoForRequest android_contact: arrayListAndroidContacts) {

            String contactsEmail = android_contact.getUserEmail();
            String trimmedEmail = contactsEmail.trim();

            fsDB.collection("users").whereEqualTo("email", trimmedEmail).get().addOnSuccessListener(new OnSuccessListener<QuerySnapshot>() {
                @Override
                public void onSuccess(QuerySnapshot documentSnapshots) {

                    if (documentSnapshots.isEmpty()) {
                        Log.d("FOUNDEMAIL", " document is empty ");

                    }
                    else {

                        List list = documentSnapshots.getDocuments();

                        DocumentSnapshot doc = (DocumentSnapshot) list.get(0);

                        UserInfoForRequest android_contact2 = new UserInfoForRequest();
                        android_contact2.setUserName(doc.get("username").toString());
                        android_contact2.setUserEmail(doc.get("email").toString());
                        android_contact2.setCurrentUID(currentUID);
                        android_contact2.setContactsUID(doc.getId());
                        arrayListAndroidContactsInApp.add(android_contact2);


                        adapterWithApp.notifyDataSetChanged();
                        adapterNoApp.notifyDataSetChanged();

                    }
                }
            })

Edit: Ok, so I did some tests. When I used "Snapshot Listener" instead of using .get, I was able to save 4 seconds to retrieve the document Snapshots, going from 27.5s down to 23.5 seconds. I also found that the loop itself is only taking 4 seconds - the retrieval of documents takes 19.

I then deleted the 5,000 users and tested with 1,000 users. The load time for 1,000 users is 6.5 seconds, and the loop itself was. 1 second. Is this just an issue that firebase needs to address in order to speed this up?