Postgresql – Postgres10 picks very slow query plan, when faster plans seem available

we are using Postgres 10.

We are seeing a situation where, for the same query, with one value it picks a super ineficient query plan, but with another value it picks a good query plan.

SELECT
   "sfe_procedure"."*"
FROM "sfe_procedure" INNER JOIN "sfe_claim"
   ON ("sfe_procedure"."claim_id" = "sfe_claim"."id")
WHERE (
   "sfe_procedure"."patient_id" = 100
   AND "sfe_claim"."from_date" >= '2011-01-01'::date
   AND "sfe_claim"."from_date" <= '2020-02-13'::date
   AND "sfe_procedure"."code" IN (
       SELECT U0."code"
       FROM "medical_codes_hediscode" U0
       WHERE U0."value_set_name" = 'Colonoscopy'
   )
)
ORDER BY "sfe_claim"."from_date" DESC LIMIT 1;

It picks this query plan:

 Limit  (cost=1001.30..5784.38 rows=1 width=46)
   ->  Nested Loop Semi Join  (cost=1001.30..2459500.48 rows=514 width=46)
         Join Filter: ((sfe_procedure.code)::text = (u0.code)::text)
         ->  Gather Merge  (cost=1000.89..2455885.11 rows=4369 width=46)
               Workers Planned: 2
               ->  Nested Loop  (cost=0.86..2454380.80 rows=1820 width=46)
                     ->  Parallel Index Scan Backward using sfe_claim_from_da_3d3cc6_idx on sfe_claim  (cost=0.43..771392.17 rows=1427744 width=8)
                           Index Cond: ((from_date >= '2011-01-01'::date) AND (from_date <= '2020-02-13'::date))
                     ->  Index Scan using sfe_procedure_claim_id_f0f8a72b on sfe_procedure  (cost=0.43..1.17 rows=1 width=42)
                           Index Cond: (claim_id = sfe_claim.id)
                           Filter: (patient_id = 100)
         ->  Materialize  (cost=0.42..11.08 rows=55 width=7)
               ->  Index Scan using medical_cod_value_s_e3a75d_idx on medical_codes_hediscode u0  (cost=0.42..10.81 rows=55 width=7)
                     Index Cond: ((value_set_name)::text = 'Colonoscopy'::text)
(14 rows)

Notice especially this row:

Parallel Index Scan Backward using sfe_claim_from_da_3d3cc6_idx 
  on sfe_claim  (cost=0.43..771392.17 rows=1427744 width=8)

Which seems to suggest that its best bet is to load 1.4 mil rows, and take 771 seconds? Am I reading this wrong?

On a different value for patient_id, the query plan is sane and the query is blazing fast:

Limit  (cost=4173.67..4173.67 rows=1 width=48)
  ->  Sort  (cost=4173.67..4174.12 rows=180 width=48)
        Sort Key: sfe_claim.from_date DESC
        ->  Nested Loop  (cost=18.73..4172.77 rows=180 width=48)
              ->  Hash Semi Join  (cost=18.29..2722.51 rows=180 width=44)
                    Hash Cond: ((sfe_procedure.code)::text = (u0.code)::text)
                    ->  Index Scan using sfe_procedure_patient_id_4bcdc9ad on sfe_procedure  (cost=0.43..2677.30 rows=3829 width=44)
                          Index Cond: (patient_id = 200)
                    ->  Hash  (cost=16.82..16.82 rows=83 width=7)
                          ->  Index Scan using medical_cod_value_s_e3a75d_idx on medical_codes_hediscode u0  (cost=0.42..16.82 rows=83 width=7)
                                Index Cond: ((value_set_name)::text = 'Colonoscopy'::text)"
              ->  Index Scan using sfe_claim_pkey on sfe_claim  (cost=0.43..8.06 rows=1 width=8)
                    Index Cond: (id = sfe_procedure.claim_id)
                    Filter: ((from_date >= '2011-01-01'::date) AND (from_date <= '2020-02-13'::date))"

The DB has had ANALYZE run on it recently, so it doesn't seem like the DB is confused about the amount of work that it's signing up for… but it still seems to pick that.

Questions

• Is there a way to understand why other query plans were not picked?
• Am I missing something obvious – a multiple-index doesn't seem to work – that could help Postgres see a better plan faster?
• Do I need to rewrite the query?

Thank you for any help or pointers!