diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d01630f..9170b92 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** final_cost_hashjoin(PlannerInfo *root, H
*** 2800,2805 ****
--- 2800,2806 ----
  	double		hashjointuples;
  	double		virtualbuckets;
  	Selectivity innerbucketsize;
+ 	double		inner_bucket_rows;
  	ListCell   *hcl;
  
  	/* Mark the path with the correct row estimate */
*************** final_cost_hashjoin(PlannerInfo *root, H
*** 2894,2899 ****
--- 2895,2914 ----
  	}
  
  	/*
+ 	 * If even a single bucket would exceed work_mem, we don't want to hash
+ 	 * unless there is really no other alternative, so apply disable_cost.
+ 	 * (Because estimate_hash_bucketsize's estimate is mostly driven by the
+ 	 * MCV frequency, this condition suggests that the executor will be unable
+ 	 * to drive the batch size below work_mem no matter how much it splits
+ 	 * buckets: splitting cannot separate values that are equal.)
+ 	 */
+ 	inner_bucket_rows = clamp_row_est(inner_path_rows * innerbucketsize);
+ 	if (relation_byte_size(inner_bucket_rows,
+ 						   inner_path->pathtarget->width) >
+ 		(work_mem * 1024L))
+ 		startup_cost += disable_cost;
+ 
+ 	/*
  	 * Compute cost of the hashquals and qpquals (other restriction clauses)
  	 * separately.
  	 */
*************** final_cost_hashjoin(PlannerInfo *root, H
*** 2964,2970 ****
  		 */
  		startup_cost += hash_qual_cost.startup;
  		run_cost += hash_qual_cost.per_tuple * outer_path_rows *
! 			clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
  
  		/*
  		 * Get approx # tuples passing the hashquals.  We use
--- 2979,2985 ----
  		 */
  		startup_cost += hash_qual_cost.startup;
  		run_cost += hash_qual_cost.per_tuple * outer_path_rows *
! 			inner_bucket_rows * 0.5;
  
  		/*
  		 * Get approx # tuples passing the hashquals.  We use
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 4992048..b2270ca 100644
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** where not exists (
*** 2429,2461 ****
                ) a1 on t3.c2 = a1.c1
    where t1.c1 = t2.c2
  );
!                        QUERY PLAN                        
! ---------------------------------------------------------
!  Hash Anti Join
!    Hash Cond: (t1.c1 = t2.c2)
!    ->  Seq Scan on tt4x t1
!    ->  Hash
!          ->  Merge Right Join
!                Merge Cond: (t5.c1 = t3.c2)
!                ->  Merge Join
!                      Merge Cond: (t4.c2 = t5.c1)
!                      ->  Sort
!                            Sort Key: t4.c2
!                            ->  Seq Scan on tt4x t4
!                      ->  Sort
!                            Sort Key: t5.c1
!                            ->  Seq Scan on tt4x t5
!                ->  Sort
!                      Sort Key: t3.c2
!                      ->  Merge Left Join
!                            Merge Cond: (t2.c3 = t3.c1)
                             ->  Sort
!                                  Sort Key: t2.c3
!                                  ->  Seq Scan on tt4x t2
                             ->  Sort
!                                  Sort Key: t3.c1
!                                  ->  Seq Scan on tt4x t3
! (24 rows)
  
  --
  -- regression test for problems of the sort depicted in bug #3494
--- 2429,2465 ----
                ) a1 on t3.c2 = a1.c1
    where t1.c1 = t2.c2
  );
!                           QUERY PLAN                           
! ---------------------------------------------------------------
!  Merge Anti Join
!    Merge Cond: (t1.c1 = t2.c2)
!    ->  Sort
!          Sort Key: t1.c1
!          ->  Seq Scan on tt4x t1
!    ->  Materialize
!          ->  Sort
!                Sort Key: t2.c2
!                ->  Merge Right Join
!                      Merge Cond: (t5.c1 = t3.c2)
!                      ->  Merge Join
!                            Merge Cond: (t4.c2 = t5.c1)
                             ->  Sort
!                                  Sort Key: t4.c2
!                                  ->  Seq Scan on tt4x t4
                             ->  Sort
!                                  Sort Key: t5.c1
!                                  ->  Seq Scan on tt4x t5
!                      ->  Sort
!                            Sort Key: t3.c2
!                            ->  Merge Left Join
!                                  Merge Cond: (t2.c3 = t3.c1)
!                                  ->  Sort
!                                        Sort Key: t2.c3
!                                        ->  Seq Scan on tt4x t2
!                                  ->  Sort
!                                        Sort Key: t3.c1
!                                        ->  Seq Scan on tt4x t3
! (28 rows)
  
  --
  -- regression test for problems of the sort depicted in bug #3494