N1QL: Count query sometimes slow, sometimes not with different possible indexes

We have a simple count query which sometimes returns within 0.5s but sometimes 8s and sometimes it runs into a Timeout (60s).
What could we check to find out the root cause?

Environment
CB Version: 5.0.0 CE
Java SDK: v2.5.1
3 Nodes (each 64GB RAM, 4 CPU Cores, all Index, Data, query)
522k Documents
There is currently no load on the cluster, as we are still evaluating. There is just the query below.

Query:

SELECT COUNT(*) AS size FROM datastoreitems where datastore_id = 'cbbbfe8b-8f20-11e7-abf3-901b0ea49fee';

Expected result:

[
  {
    "size": 189947
  }
]

Possible indexes:

CREATE INDEX `idx_created_at` ON `datastoreitems`(`datastore_id`,(-str_to_millis(`created_at`)))
CREATE INDEX `idx_datastore` ON `datastoreitems`(`datastore_id`,`folder`)
CREATE INDEX `idx_flowrunid` ON `datastoreitems`(`datastore_id`,`flowrun_id`)
CREATE INDEX `idx_lastupdated_at` ON `datastoreitems`(`datastore_id`,(-str_to_millis(`lastupdated_at`)))

Here are some example query plans from Query Console:

Example 1: elapsed: 570.89ms | execution: 570.88ms | count: 1 | size: 38

{
  "plan": {
    "#operator": "Sequence",
    "~children": [
      {
        "#operator": "IndexCountScan2",
        "covers": [
          "cover ((`datastoreitems`.`datastore_id`))",
          "cover ((-str_to_millis((`datastoreitems`.`created_at`))))",
          "cover ((meta(`datastoreitems`).`id`))"
        ],
        "index": "idx_created_at",
        "index_id": "4f5568ba9dd1fbd6",
        "keyspace": "datastoreitems",
        "namespace": "default",
        "spans": [
          {
            "exact": true,
            "range": [
              {
                "high": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\"",
                "inclusion": 3,
                "low": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\""
              }
            ]
          }
        ],
        "using": "gsi"
      },
      {
        "#operator": "IndexCountProject",
        "result_terms": [
          {
            "as": "size",
            "expr": "count(*)"
          }
        ]
      }
    ]
  },
  "text": "SELECT COUNT(*) AS size FROM  datastoreitems where datastore_id = 'cbbbfe8b-8f20-11e7-abf3-901b0ea49fee';"
}

Example 2: elapsed: 8.78s | execution: 8.78s | count: 1 | size: 38

{
  "plan": {
    "#operator": "Sequence",
    "~children": [
      {
        "#operator": "IndexCountScan2",
        "covers": [
          "cover ((`datastoreitems`.`datastore_id`))",
          "cover ((`datastoreitems`.`flowrun_id`))",
          "cover ((meta(`datastoreitems`).`id`))"
        ],
        "index": "idx_flowrunid",
        "index_id": "8cafd50daee76437",
        "keyspace": "datastoreitems",
        "namespace": "default",
        "spans": [
          {
            "exact": true,
            "range": [
              {
                "high": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\"",
                "inclusion": 3,
                "low": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\""
              }
            ]
          }
        ],
        "using": "gsi"
      },
      {
        "#operator": "IndexCountProject",
        "result_terms": [
          {
            "as": "size",
            "expr": "count(*)"
          }
        ]
      }
    ]
  },
  "text": "SELECT COUNT(*) AS size FROM  datastoreitems where datastore_id = 'cbbbfe8b-8f20-11e7-abf3-901b0ea49fee';"
}

Example 3: elapsed: 8.74s | execution: 8.74s | count: 1 | size: 38

{
  "plan": {
    "#operator": "Sequence",
    "~children": [
      {
        "#operator": "IndexCountScan2",
        "covers": [
          "cover ((`datastoreitems`.`datastore_id`))",
          "cover ((`datastoreitems`.`folder`))",
          "cover ((meta(`datastoreitems`).`id`))"
        ],
        "index": "idx_datastore",
        "index_id": "857ea2aec9613055",
        "keyspace": "datastoreitems",
        "namespace": "default",
        "spans": [
          {
            "exact": true,
            "range": [
              {
                "high": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\"",
                "inclusion": 3,
                "low": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\""
              }
            ]
          }
        ],
        "using": "gsi"
      },
      {
        "#operator": "IndexCountProject",
        "result_terms": [
          {
            "as": "size",
            "expr": "count(*)"
          }
        ]
      }
    ]
  },
  "text": "SELECT COUNT(*) AS size FROM  datastoreitems where datastore_id = 'cbbbfe8b-8f20-11e7-abf3-901b0ea49fee';"
}

Example 4: elapsed: 465.54ms | execution: 465.51ms | count: 1 | size: 38
Notice: same index as Example 3, but much faster.

{
          "plan": {
            "#operator": "Sequence",
            "~children": [
              {
                "#operator": "IndexCountScan2",
                "covers": [
                  "cover ((`datastoreitems`.`datastore_id`))",
                  "cover ((`datastoreitems`.`folder`))",
                  "cover ((meta(`datastoreitems`).`id`))"
                ],
                "index": "idx_datastore",
                "index_id": "857ea2aec9613055",
                "keyspace": "datastoreitems",
                "namespace": "default",
                "spans": [
                  {
                    "exact": true,
                    "range": [
                      {
                        "high": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\"",
                        "inclusion": 3,
                        "low": "\"cbbbfe8b-8f20-11e7-abf3-901b0ea49fee\""
                      }
                    ]
                  }
                ],
                "using": "gsi"
              },
              {
                "#operator": "IndexCountProject",
                "result_terms": [
                  {
                    "as": "size",
                    "expr": "count(*)"
                  }
                ]
              }
            ]
          },
          "text": "SELECT COUNT(*) AS size FROM  datastoreitems where datastore_id = 'cbbbfe8b-8f20-11e7-abf3-901b0ea49fee';"
        }