A first inquiry suggests the following:

• iotax_queryTransactionBlocks (filters txs by checkpoint id) performs consistently with what is reported here (~14,15 sec)
• A naive 1+N query (iota_getCheckpoint + iota_getTransactionBlocks) performs much better (~4s) but still has large latency.
• GraphQL responds rapidly

  {
    checkpoint(id: {sequenceNumber: 10843159}) {
      transactionBlocks {
        nodes {
          digest
          sender {
            address
          }
          gasInput {
            gasPrice
            gasBudget
          }
          effects {
            status
            errors
            timestamp
            objectChanges {
              edges {
                node {
                  idCreated
                  idDeleted
                }
              }
            }
          }
        }
      }
    }
  }    

So it seems that we can seek to optimize the query in the indexer JSON-RPC server, following the call in the graphQL server.

Replicated the slowness on local setup by artificially increasing indexer DB size to contain ~20M records (I believe it's a bit above 40M on testnet now) in transactions table.

Calling:

curl 'localhost:9005/'   -H 'content-type: application/json'   --data-raw '{
      "jsonrpc":"2.0",
      "id":4,
      "method":"iotax_queryTransactionBlocks",
      "params":[{"filter":{"Checkpoint":"10"},"options":{"showEffects":true,"showInput":true}},null,20,true]}'

Makes diesel generate and execute a query similar to the following:

SELECT *
FROM transactions
WHERE checkpoint_sequence_number = 10
ORDER by tx_sequence_number DESC;

which is slow (~40s) because of missing index on checkpoint_sequence_number (the only index is tx_sequence_number).

I didn't deeply investigate what graphql does internally, but since the entrypoint of the query is the checkpoint object, I assume that it may start looking at the checkpoints table, get transaction ids from there and then go for transactions table.
Such approach would be very fast, even without additional indexes.

The following query takes only 0.1s, producing the same results as the query above.

SELECT *
FROM transactions
WHERE tx_sequence_number between (
	select min_tx_sequence_number from checkpoints where sequence_number = 10
) and (
	select max_tx_sequence_number from checkpoints where sequence_number = 10
)
ORDER BY tx_sequence_number DESC;

Creating the index:

CREATE INDEX transactions_checkpoint_sequence_number ON public.transactions USING btree (checkpoint_sequence_number)

makes the original query perform really fast (<0.01s) and also speeds up iotax_queryTransactionBlocks endpoint to around 0.3s.

I didn't deeply investigate what graphql does internally, but since the entrypoint of the query is the checkpoint object, I assume that it may start looking at the checkpoints table, get transaction ids from there and then go for transactions table.
Such approach would be very fast, even without additional indexes.

Ideally we would like to avoid adding a new index, as it will affect insertion time and hence transaction effects latency with the current setting.

So this solution seems like a good candidate. At any case, I would suggest that you resolve the exact query used by GraphQL. I would assume to be the optimal solution.

@tomxey this upstream patch might be relevant too.

What graphql is doing is:

First it gets the range of transaction ids for given checkpoint via query:

SELECT network_total_transactions
FROM checkpoints
WHERE sequence_number IN (16, 17)
ORDER BY network_total_transactions ASC;

It queries for network_total_transactions of checkpoint that is being queried, and one checkpoint before it.

Which is followed by a second query:

SELECT *
FROM transactions
WHERE tx_sequence_number >= 63
  AND tx_sequence_number < 67
ORDER BY tx_sequence_number ASC
LIMIT 22;

which is using values from the previous one to filter tx_sequence_number.

I wonder why it's not using the min_tx_sequence_number and max_tx_sequence_number, but otherwise the approach seems to be very similar to the one suggested in #4516 (comment) and in the upstream patch.