diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
index 6d52706..b9f48e6 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
@@ -776,7 +776,10 @@
             pn.setRightPlanIndex(PlanNode.NO_PLAN); // There ane no plans below this plan.
             pn.setOpCost(totalCost);
             pn.setScanMethod(PlanNode.ScanMethod.INDEX_SCAN);
-            pn.indexHint = mandatoryIndexesInfo.size() > 0;
+            if (mandatoryIndexesInfo.size() > 0) {
+                pn.indexHint = true;
+                pn.numHintsUsed = 1;
+            }
             pn.setTotalCost(totalCost);
             allPlans.add(pn);
             this.planIndexesArray.add(pn.allPlansIndex);
@@ -949,6 +952,11 @@
                 pn.setRightPlanIndex(rightPlan.allPlansIndex);
                 pn.joinOp = PlanNode.JoinMethod.HYBRID_HASH_JOIN; // need to check that all the conditions have equality predicates ONLY.
                 pn.joinHint = hintHashJoin;
+                pn.numHintsUsed = allPlans.get(pn.getLeftPlanIndex()).numHintsUsed
+                        + allPlans.get(pn.getRightPlanIndex()).numHintsUsed;
+                if (hintHashJoin != null) {
+                    pn.numHintsUsed++;
+                }
                 pn.side = HashJoinExpressionAnnotation.BuildSide.RIGHT;
                 pn.joinExpr = hashJoinExpr;
                 pn.opCost = hjCost;
@@ -1018,6 +1026,11 @@
                 pn.setRightPlanIndex(rightPlan.allPlansIndex);
                 pn.joinOp = PlanNode.JoinMethod.BROADCAST_HASH_JOIN; // need to check that all the conditions have equality predicates ONLY.
                 pn.joinHint = hintBroadcastHashJoin;
+                pn.numHintsUsed = allPlans.get(pn.getLeftPlanIndex()).numHintsUsed
+                        + allPlans.get(pn.getRightPlanIndex()).numHintsUsed;
+                if (hintBroadcastHashJoin != null) {
+                    pn.numHintsUsed++;
+                }
                 pn.side = HashJoinExpressionAnnotation.BuildSide.RIGHT;
                 pn.joinExpr = hashJoinExpr;
                 pn.opCost = bcastHjCost;
@@ -1083,6 +1096,11 @@
             pn.setRightPlanIndex(rightPlan.allPlansIndex);
             pn.joinOp = PlanNode.JoinMethod.INDEX_NESTED_LOOP_JOIN;
             pn.joinHint = hintNLJoin;
+            pn.numHintsUsed = allPlans.get(pn.getLeftPlanIndex()).numHintsUsed
+                    + allPlans.get(pn.getRightPlanIndex()).numHintsUsed;
+            if (hintNLJoin != null) {
+                pn.numHintsUsed++;
+            }
             pn.joinExpr = nestedLoopJoinExpr; // save it so can be used to add the NESTED annotation in getNewTree.
             pn.opCost = nljCost;
             pn.totalCost = totalCost;
@@ -1431,29 +1449,25 @@
         List<PlanNode> allPlans = joinEnum.allPlans;
         ICost cheapestCost = joinEnum.getCostHandle().maxCost();
         PlanNode cheapestPlanNode = null;
-        boolean isCheapestPlanHinted = false;
-        boolean isPlanHinted;
+        int numHintsUsedInCheapestPlan = 0;
 
         for (int planIndex : this.planIndexesArray) {
             PlanNode plan = allPlans.get(planIndex);
-            isPlanHinted = plan.joinHint != null || plan.indexHint;
-
-            if (isPlanHinted && !isCheapestPlanHinted) {
-                // The hinted plan wins!
+            if (plan.numHintsUsed > numHintsUsedInCheapestPlan) {
+                // "plan" has used more hints than "cheapestPlan", "plan" wins!
                 cheapestPlanNode = plan;
                 cheapestCost = plan.totalCost;
-                isCheapestPlanHinted = true;
-            } else if (isPlanHinted || !isCheapestPlanHinted) {
-                // Either both plans are hinted, or both are non-hinted.
+                numHintsUsedInCheapestPlan = plan.numHintsUsed;
+            } else if (plan.numHintsUsed == numHintsUsedInCheapestPlan) {
+                // Either both "plan" and "cheapestPlan" are hinted, or both are non-hinted.
                 // Cost is the decider.
                 if (plan.totalCost.costLT(cheapestCost)) {
                     cheapestPlanNode = plan;
                     cheapestCost = plan.totalCost;
-                    isCheapestPlanHinted = isPlanHinted;
                 }
             } else {
-                // this is the case where isPlanHinted == false AND isCheapestPlanHinted == true
-                // Nothing to do.
+                // This is the case where "plan" has used fewer hints than "cheapestPlan".
+                // We have already captured the cheapest plan, nothing to do.
             }
         }
         return cheapestPlanNode;
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java
index b017140..ba02c1a 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java
@@ -32,7 +32,7 @@
     protected static int NO_PLAN = -1;
 
     private final JoinEnum joinEnum;
-    boolean outerJoin = false;
+    protected boolean outerJoin;
     protected int allPlansIndex;
     protected int[] planIndexes;
     protected int[] jnIndexes;
@@ -45,6 +45,9 @@
     protected JoinMethod joinOp;
     protected boolean indexHint;
     protected IExpressionAnnotation joinHint;
+
+    protected int numHintsUsed;
+
     // Used to indicate which side to build for HJ and which side to broadcast for BHJ.
     protected HashJoinExpressionAnnotation.BuildSide side;
     protected ScanMethod scanOp;
@@ -69,6 +72,10 @@
         joinEnum = joinE;
         planIndexes = new int[2]; // 0 is for left, 1 is for right
         jnIndexes = new int[2]; // join node index(es)
+        outerJoin = false;
+        indexHint = false;
+        joinHint = null;
+        numHintsUsed = 0;
     }
 
     public int getIndex() {
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
index cd5de62..2b4179a 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
@@ -17,12 +17,12 @@
                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                   -- STREAM_PROJECT  |PARTITIONED|
                     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                      -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
-                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
+                        -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
                           -- STREAM_PROJECT  |PARTITIONED|
                             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                              -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
-                                -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
+                              -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
+                                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                   -- STREAM_PROJECT  |PARTITIONED|
                                     -- STREAM_SELECT  |PARTITIONED|
                                       -- ASSIGN  |PARTITIONED|
@@ -31,13 +31,13 @@
                                             -- DATASOURCE_SCAN (tpch.LineItem)  |PARTITIONED|
                                               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                 -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                                -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
-                                  -- STREAM_PROJECT  |PARTITIONED|
-                                    -- ASSIGN  |PARTITIONED|
-                                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                        -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
-                                          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                        -- BROADCAST_EXCHANGE  |PARTITIONED|
-                          -- UNNEST  |UNPARTITIONED|
-                            -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                                -- BROADCAST_EXCHANGE  |PARTITIONED|
+                                  -- UNNEST  |UNPARTITIONED|
+                                    -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                        -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
+                          -- STREAM_PROJECT  |PARTITIONED|
+                            -- ASSIGN  |PARTITIONED|
+                              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
+                                  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                    -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
index 03a4f96..0d00f7b 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
@@ -23,12 +23,12 @@
                             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                               -- STREAM_PROJECT  |PARTITIONED|
                                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                  -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
-                                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                  -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
+                                    -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
                                       -- STREAM_PROJECT  |PARTITIONED|
                                         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                          -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
-                                            -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
+                                          -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
+                                            -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                               -- STREAM_PROJECT  |PARTITIONED|
                                                 -- STREAM_SELECT  |PARTITIONED|
                                                   -- ASSIGN  |PARTITIONED|
@@ -37,16 +37,16 @@
                                                         -- DATASOURCE_SCAN (tpch.LineItem)  |PARTITIONED|
                                                           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                             -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                                            -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
-                                              -- STREAM_PROJECT  |PARTITIONED|
-                                                -- ASSIGN  |PARTITIONED|
-                                                  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                    -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
-                                                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                        -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                                    -- BROADCAST_EXCHANGE  |PARTITIONED|
-                                      -- UNNEST  |UNPARTITIONED|
-                                        -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                                            -- BROADCAST_EXCHANGE  |PARTITIONED|
+                                              -- UNNEST  |UNPARTITIONED|
+                                                -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                                    -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
+                                      -- STREAM_PROJECT  |PARTITIONED|
+                                        -- ASSIGN  |PARTITIONED|
+                                          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                            -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
+                                              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
                 -- BROADCAST_EXCHANGE  |PARTITIONED|
                   -- AGGREGATE  |UNPARTITIONED|
                     -- RANDOM_MERGE_EXCHANGE  |PARTITIONED|
@@ -69,12 +69,12 @@
                                       -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                         -- STREAM_PROJECT  |PARTITIONED|
                                           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                            -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
-                                              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                            -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
+                                              -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
                                                 -- STREAM_PROJECT  |PARTITIONED|
                                                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                    -- HYBRID_HASH_JOIN [$$126][$$122]  |PARTITIONED|
-                                                      -- HASH_PARTITION_EXCHANGE [$$126]  |PARTITIONED|
+                                                    -- HYBRID_HASH_JOIN [$$118][$$124]  |PARTITIONED|
+                                                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                         -- STREAM_PROJECT  |PARTITIONED|
                                                           -- STREAM_SELECT  |PARTITIONED|
                                                             -- ASSIGN  |PARTITIONED|
@@ -83,13 +83,13 @@
                                                                   -- DATASOURCE_SCAN (tpch.LineItem)  |PARTITIONED|
                                                                     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                                       -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                                                      -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
-                                                        -- STREAM_PROJECT  |PARTITIONED|
-                                                          -- ASSIGN  |PARTITIONED|
-                                                            -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                              -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
-                                                                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                                  -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-                                              -- BROADCAST_EXCHANGE  |PARTITIONED|
-                                                -- UNNEST  |UNPARTITIONED|
-                                                  -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                                                      -- BROADCAST_EXCHANGE  |PARTITIONED|
+                                                        -- UNNEST  |UNPARTITIONED|
+                                                          -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+                                              -- HASH_PARTITION_EXCHANGE [$$122]  |PARTITIONED|
+                                                -- STREAM_PROJECT  |PARTITIONED|
+                                                  -- ASSIGN  |PARTITIONED|
+                                                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                                      -- DATASOURCE_SCAN (tpch.Orders)  |PARTITIONED|
+                                                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                                          -- EMPTY_TUPLE_SOURCE  |PARTITIONED|