Query JPA using Paging is taking longer as the page number increases, and generating timeout

Question

I’m running a query with JPA on a cloud server of the google app engine, this query should bring me millions of records, and so I’m using Pageable on it, to avoid bank timeout, the problem is that as the page number increases more time it takes to load the logs, I discovered this through the logs I put in. for example the page 0 tail 1000 records in 0,18 seconds, already the page 942 which is the last before making a mistake behind the 1000 records only after 174 seconds and after error 404 on the server. This is the query I am running:

@Query(value = "SELECT DISTINCT c.idCliente, tel.idTelefone, tel.numeroSemMascara "  
        + "FROM Cliente AS c LEFT JOIN ("  
            + "SELECT cfa.idCliente, cfa.tempoDuracaoBotija, max(cfa.dataCadastro) AS ultimoCadastro " 
            + "FROM ClienteFogasAvisa AS cfa GROUP BY cfa.idCliente, cfa.tempoDuracaoBotija " 
            + ") AS fa "
        + "ON c.idCliente = fa.idCliente "  
        + "INNER JOIN Telefone as tel "  
        + "ON c.idCliente = tel.idCliente "  
        + "INNER JOIN Endereco as e "  
        + "ON c.idCliente = e.idCliente "  
        + "WHERE c.idCliente NOT IN ("
            + "SELECT ec.idCliente FROM EnvioCampanha AS ec "
            + "WHERE c.idCliente = ec.idCliente "
            + "AND ec.idMensagem = 'NFS10' "
            + "AND ec.situacao = 'Enviado' "
            + "AND DATEDIFF(CURDATE(), ec.dataEnvio) < 365) "   
        + "AND c.situacao = 'Ativo' " 
        + "AND tel.situacao = 'Ativo' AND tel.tipoTelefone = 'Celular' AND (tel.envioSMS IS NULL OR tel.envioSMS = 1) " 
        + "AND tel.numeroSemMascara IS NOT NULL " 
        + "AND (COALESCE(:idClientes) IS NULL OR (c.idCliente in (:idClientes))) " 
        + "AND (COALESCE(:siglaEstados) IS NULL OR (e.siglaEstado in (:siglaEstados))) "
        + "AND (COALESCE(:cidades) IS NULL OR (e.cidade in (:cidades))) " 
        + "AND e.situacao = 'Ativo' " 
        + "AND (fa.idCliente is null " 
        + "OR ((fa.tempoDuracaoBotija is null or fa.tempoDuracaoBotija = 0) and DATEDIFF(CURDATE(), fa.ultimoCadastro) >= 365) " 
        + "OR (DATEDIFF(CURDATE(), fa.ultimoCadastro) >= 1095))", nativeQuery = true)
public List<Object[]> getClientesMuitoTempoSemResponderFogasAvisa(@Param("idClientes") List<Integer> idClientes,
        @Param("siglaEstados") List<String> siglaEstados, @Param("cidades") List<String> cidades, Pageable page);

This is the method that is using the query:

@Override
public List<ClienteCampanhaDTO> getClientes(List<Integer> idClientes, List<String> siglaEstados,
        List<String> cidades, Campanha camp) {
    int pagina = 0;
    List<ClienteCampanhaDTO> clientes = new ArrayList<>();
    List<Object[]> clientesTuple = new ArrayList<>();

    tracer.info("iniciou a busca dos clientes da NFS 10");

    /**
     * se a nfs 10 para de dar erro 404 apagar esses logs de calculo de tempo depois disso
     */
    do {
        Long inicioBuscaBanco = Calendar.getInstance().getTimeInMillis();
        clientesTuple = clienteRepository.getClientesMuitoTempoSemResponderFogasAvisa(idClientes, siglaEstados,
                cidades, PageRequest.of(pagina, MIL));
        Long fimBuscaBanco = Calendar.getInstance().getTimeInMillis();
        Long inicioMontagemCliente = Calendar.getInstance().getTimeInMillis();
        criarClientes(clientesTuple, clientes);
        Long fimMontagemCliente = Calendar.getInstance().getTimeInMillis();

        Long duracaoBuscaBanco = fimBuscaBanco - inicioBuscaBanco;
        Long duracaoMontagemCliente = fimMontagemCliente - inicioMontagemCliente;

        Float duracaoBuscaBancoEmSegundos = duracaoBuscaBanco / 1000f;
        Float duracaoMontagemClienteEmSegundos = duracaoMontagemCliente / 1000f;

        tracer.info("Demorou " + String.format("%.2f", duracaoBuscaBancoEmSegundos) + " para buscar os clientes da pagina " + pagina);
        tracer.info("Demorou " + String.format("%.2f", duracaoMontagemClienteEmSegundos) + " para instanciar os clientes da pagina " + pagina);

        pagina++;
    } while (CollectionUtils.isNotEmpty(clientesTuple));

    tracer.info("finalizou a busca dos clientes da NFS 10");

    return clientes;
}

And this is the method that takes the returned tuple and creates a client(no problem here, I put it just to not leave the incomplete code)

/**
 * Pega a tupla de colunas buscadas do banco de dados e instancia um objeto do
 * tipo cliente e depois o adiciona a lista final de clientes
 * 
 * @param clientesTuple - lista com todas a colunas buscadas no banco de dados
 * @param clientes      - lista final de clientes que receberão a mensagem
 */
private void criarClientes(List<Object[]> clientesTuple, List<ClienteCampanhaDTO> clientes) {
    for (Object[] cliente : clientesTuple) {
        try {
            ClienteCampanhaDTO clienteEncontrado = new ClienteCampanhaDTO();
            clienteEncontrado.setIdCliente((Integer) cliente[ID_CLIENTE]);
            clienteEncontrado.setIdTelefone((Integer) cliente[ID_TELEFONE]);
            clienteEncontrado.setTelefoneCliente((String) cliente[NUMERO_SEM_MASCARA]);
            clientes.add(clienteEncontrado);
        } catch (Exception e) {
            tracer.error("Houve um erro ao instanciar um cliente na NFS10");
        }
    }
}

How do I make sure the number of pages does not influence the search speed?