SERVER-62434 Implement query optimizer based on Path algebra and Cascades

25 files changed, 974 insertions, 0 deletions

diff --git a/jstests/cqf/array_index.js b/jstests/cqf/array_index.js
new file mode 100644
index 00000000000..5a40a3040fb
--- /dev/null
+++ b/jstests/cqf/array_index.js
@@ -0,0 +1,33 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_array_index;
+t.drop();
+
+assert.commandWorked(t.insert({a: [1, 2, 3, 4]}));
+assert.commandWorked(t.insert({a: [2, 3, 4]}));
+assert.commandWorked(t.insert({a: [2]}));
+assert.commandWorked(t.insert({a: 2}));
+assert.commandWorked(t.insert({a: [1, 3]}));
+
+// Generate enough documents for index to be preferable.
+for (let i = 0; i < 100; i++) {
+    assert.commandWorked(t.insert({a: i + 10}));
+}
+
+assert.commandWorked(t.createIndex({a: 1}));
+
+let res = t.explain("executionStats").aggregate([{$match: {a: 2}}]);
+assert.eq(4, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+res = t.explain("executionStats").aggregate([{$match: {a: {$lt: 2}}}]);
+assert.eq(2, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.child.nodeType);
+}());
diff --git a/jstests/cqf/basic_agg.js b/jstests/cqf/basic_agg.js
new file mode 100644
index 00000000000..3165b4403d0
--- /dev/null
+++ b/jstests/cqf/basic_agg.js
@@ -0,0 +1,42 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_basic_index;
+coll.drop();
+
+assert.commandWorked(
+    coll.insert([{a: {b: 1}}, {a: {b: 2}}, {a: {b: 3}}, {a: {b: 4}}, {a: {b: 5}}]));
+
+const extraDocCount = 50;
+// Add extra docs to make sure indexes can be picked.
+for (let i = 0; i < extraDocCount; i++) {
+    assert.commandWorked(coll.insert({a: {b: i + 10}}));
+}
+assert.commandWorked(coll.createIndex({'a.b': 1}));
+
+let res = coll.explain("executionStats").aggregate([{$match: {'a.b': 2}}]);
+assert.eq(1, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+res = coll.explain("executionStats").aggregate([{$match: {'a.b': {$gt: 2}}}]);
+assert.eq(3 + extraDocCount, res.executionStats.nReturned);
+assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+
+res = coll.explain("executionStats").aggregate([{$match: {'a.b': {$gte: 2}}}]);
+assert.eq(4 + extraDocCount, res.executionStats.nReturned);
+assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+
+res = coll.explain("executionStats").aggregate([{$match: {'a.b': {$lt: 2}}}]);
+assert.eq(1, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+res = coll.explain("executionStats").aggregate([{$match: {'a.b': {$lte: 2}}}]);
+assert.eq(2, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}());
diff --git a/jstests/cqf/basic_find.js b/jstests/cqf/basic_find.js
new file mode 100644
index 00000000000..37abd4b5eaa
--- /dev/null
+++ b/jstests/cqf/basic_find.js
@@ -0,0 +1,42 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_basic_find;
+coll.drop();
+
+assert.commandWorked(
+    coll.insert([{a: {b: 1}}, {a: {b: 2}}, {a: {b: 3}}, {a: {b: 4}}, {a: {b: 5}}]));
+
+const extraDocCount = 50;
+// Add extra docs to make sure indexes can be picked.
+for (let i = 0; i < extraDocCount; i++) {
+    assert.commandWorked(coll.insert({a: {b: i + 10}}));
+}
+assert.commandWorked(coll.createIndex({'a.b': 1}));
+
+let res = coll.explain("executionStats").find({'a.b': 2}).finish();
+assert.eq(1, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+res = coll.explain("executionStats").find({'a.b': {$gt: 2}}).finish();
+assert.eq(3 + extraDocCount, res.executionStats.nReturned);
+assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+
+res = coll.explain("executionStats").find({'a.b': {$gte: 2}}).finish();
+assert.eq(4 + extraDocCount, res.executionStats.nReturned);
+assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+
+res = coll.explain("executionStats").find({'a.b': {$lt: 2}}).finish();
+assert.eq(1, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+res = coll.explain("executionStats").find({'a.b': {$lte: 2}}).finish();
+assert.eq(2, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}());
diff --git a/jstests/cqf/basic_unwind.js b/jstests/cqf/basic_unwind.js
new file mode 100644
index 00000000000..c0faa5c0e0d
--- /dev/null
+++ b/jstests/cqf/basic_unwind.js
@@ -0,0 +1,25 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_basic_unwind;
+coll.drop();
+
+assert.commandWorked(coll.insert([
+    {_id: 1},
+    {_id: 2, x: null},
+    {_id: 3, x: []},
+    {_id: 4, x: [1, 2]},
+    {_id: 5, x: [3]},
+    {_id: 6, x: 4}
+]));
+
+let res = coll.explain("executionStats").aggregate([{$unwind: '$x'}]);
+assert.eq(4, res.executionStats.nReturned);
+assert.eq("Unwind", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}());
diff --git a/jstests/cqf/chess.js b/jstests/cqf/chess.js
new file mode 100644
index 00000000000..30124ea99b8
--- /dev/null
+++ b/jstests/cqf/chess.js
@@ -0,0 +1,107 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_chess;
+Random.srand(0);
+
+const players = [
+    "penguingim1",    "aladdin65",       "aleksey472",        "azuaga",       "benpig",
+    "blackboarder",   "bockosrb555",     "bogdan_low_player", "charlytb",     "chchbbuur",
+    "chessexplained", "cmcookiemonster", "crptone",           "cselhu3",      "darkzam",
+    "dmitri31",       "dorado99",        "ericrosen",         "fast-tsunami", "flaneur"
+];
+const sources = [1, 2, 3, 4, 5, 6, 7, 8];
+const variants = [1, 2, 3, 4, 5, 6, 7, 8];
+const results = [1, 2, 3, 4, 5, 6, 7, 8];
+const winColor = [true, false, null];
+
+const nbGames = 1000;  // 1000 * 1000;
+
+function intRandom(max) {
+    return Random.randInt(max);
+}
+function anyOf(as) {
+    return as [intRandom(as.length)];
+}
+
+coll.drop();
+
+print(`Adding ${nbGames} games`);
+const bulk = coll.initializeUnorderedBulkOp();
+for (let i = 0; i < nbGames; i++) {
+    const users = [anyOf(players), anyOf(players)];
+    const winnerIndex = intRandom(2);
+    bulk.insert({
+        users: users,
+        winner: users[winnerIndex],
+        loser: users[1 - winnerIndex],
+        winColor: anyOf(winColor),
+        avgRating: NumberInt(600 + intRandom(2400)),
+        source: NumberInt(anyOf(sources)),
+        variants: NumberInt(anyOf(variants)),
+        mode: !!intRandom(2),
+        turns: NumberInt(1 + intRandom(300)),
+        minutes: NumberInt(30 + intRandom(3600 * 3)),
+        clock: {init: NumberInt(0 + intRandom(10800)), inc: NumberInt(0 + intRandom(180))},
+        result: anyOf(results),
+        date: new Date(Date.now() - intRandom(118719488)),
+        analysed: !!intRandom(2)
+    });
+    if (i % 1000 == 0) {
+        print(`${i} / ${nbGames}`);
+    }
+}
+assert.commandWorked(bulk.execute());
+
+const indexes = [
+    {users: 1},
+    {winner: 1},
+    {loser: 1},
+    {winColor: 1},
+    {avgRating: 1},
+    {source: 1},
+    {variants: 1},
+    {mode: 1},
+    {turns: 1},
+    {minutes: 1},
+    {'clock.init': 1},
+    {'clock.inc': 1},
+    {result: 1},
+    {date: 1},
+    {analysed: 1}
+];
+
+print("Adding indexes");
+indexes.forEach(index => {
+    printjson(index);
+    coll.createIndex(index);
+});
+
+print("Searching");
+
+const res = coll.explain("executionStats").aggregate([
+    {
+        $match: {
+            avgRating: {$gt: 1000},
+            turns: {$lt: 250},
+            'clock.init': {$gt: 1},
+            minutes: {$gt: 2, $lt: 150}
+        }
+    },
+    {$sort: {date: -1}},
+    {$limit: 20}
+]);
+
+// TODO: verify expected results.
+
+// Verify we are using the index on "minutes".
+const indexNode = res.queryPlanner.winningPlan.optimizerPlan.child.child.leftChild;
+assert.eq("IndexScan", indexNode.nodeType);
+assert.eq("minutes_1", indexNode.indexDefName);
+}());
diff --git a/jstests/cqf/empty_results.js b/jstests/cqf/empty_results.js
new file mode 100644
index 00000000000..5eed556189c
--- /dev/null
+++ b/jstests/cqf/empty_results.js
@@ -0,0 +1,18 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_empty_results;
+t.drop();
+
+assert.commandWorked(t.insert([{a: 1}, {a: 2}]));
+
+const res = t.explain("executionStats").aggregate([{$match: {'a': 2}}, {$limit: 1}, {$skip: 10}]);
+assert.eq(0, res.executionStats.nReturned);
+assert.eq("CoScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.child.nodeType);
+}());
diff --git a/jstests/cqf/filter_order.js b/jstests/cqf/filter_order.js
new file mode 100644
index 00000000000..e33e45c661e
--- /dev/null
+++ b/jstests/cqf/filter_order.js
@@ -0,0 +1,22 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_filter_order;
+coll.drop();
+
+const bulk = coll.initializeUnorderedBulkOp();
+for (let i = 0; i < 10000; i++) {
+    // "a" has the most ones, then "b", then "c".
+    bulk.insert({a: (i % 2), b: (i % 3), c: (i % 4)});
+}
+assert.commandWorked(bulk.execute());
+
+let res = coll.aggregate([{$match: {'a': {$eq: 1}, 'b': {$eq: 1}, 'c': {$eq: 1}}}]).toArray();
+// TODO: verify plan that predicate on "c" is applied first (most selective), then "b", then "a".
+}());
diff --git a/jstests/cqf/find_sort.js b/jstests/cqf/find_sort.js
new file mode 100644
index 00000000000..5ead920b48c
--- /dev/null
+++ b/jstests/cqf/find_sort.js
@@ -0,0 +1,41 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_find_sort;
+coll.drop();
+
+const bulk = coll.initializeUnorderedBulkOp();
+const nDocs = 10000;
+let numResults = 0;
+
+Random.srand(0);
+for (let i = 0; i < nDocs; i++) {
+    const va = 100.0 * Random.rand();
+    const vb = 100.0 * Random.rand();
+    if (va < 5.0 && vb < 5.0) {
+        numResults++;
+    }
+    bulk.insert({a: va, b: vb});
+}
+assert.gt(numResults, 0);
+
+assert.commandWorked(bulk.execute());
+
+assert.commandWorked(coll.createIndex({a: 1, b: 1}));
+
+const res = coll.explain("executionStats")
+                .find({a: {$lt: 5}, b: {$lt: 5}}, {a: 1, b: 1})
+                .sort({b: 1})
+                .finish();
+assert.eq(numResults, res.executionStats.nReturned);
+
+const indexScanNode = res.queryPlanner.winningPlan.optimizerPlan.child.child.child.leftChild.child;
+assert.eq("IndexScan", indexScanNode.nodeType);
+assert.eq(5, indexScanNode.interval[0].highBound.bound.value);
+}());
diff --git a/jstests/cqf/group.js b/jstests/cqf/group.js
new file mode 100644
index 00000000000..4af1ad6b021
--- /dev/null
+++ b/jstests/cqf/group.js
@@ -0,0 +1,27 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_group;
+coll.drop();
+
+assert.commandWorked(coll.insert([
+    {a: 1, b: 1, c: 1},
+    {a: 1, b: 2, c: 2},
+    {a: 1, b: 2, c: 3},
+    {a: 2, b: 1, c: 4},
+    {a: 2, b: 1, c: 5},
+    {a: 2, b: 2, c: 6},
+]));
+
+const res = coll.explain("executionStats").aggregate([
+    {$group: {_id: {a: '$a', b: '$b'}, sum: {$sum: '$c'}, avg: {$avg: '$c'}}}
+]);
+assert.eq("GroupBy", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+assert.eq(4, res.executionStats.nReturned);
+}());
diff --git a/jstests/cqf/index_intersect.js b/jstests/cqf/index_intersect.js
new file mode 100644
index 00000000000..66ad1935996
--- /dev/null
+++ b/jstests/cqf/index_intersect.js
@@ -0,0 +1,47 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_index_intersect;
+t.drop();
+
+const nMatches = 60;
+
+assert.commandWorked(t.insert({a: 1, b: 1, c: 1}));
+assert.commandWorked(t.insert({a: 3, b: 2, c: 1}));
+for (let i = 0; i < nMatches; i++) {
+    assert.commandWorked(t.insert({a: 3, b: 3, c: i}));
+}
+assert.commandWorked(t.insert({a: 4, b: 3, c: 2}));
+assert.commandWorked(t.insert({a: 5, b: 5, c: 2}));
+
+for (let i = 1; i < nMatches + 100; i++) {
+    assert.commandWorked(t.insert({a: i + nMatches, b: i + nMatches, c: i + nMatches}));
+}
+
+assert.commandWorked(t.createIndex({'a': 1}));
+assert.commandWorked(t.createIndex({'b': 1}));
+
+let res = t.explain("executionStats").aggregate([{$match: {'a': 3, 'b': 3}}]);
+assert.eq(nMatches, res.executionStats.nReturned);
+
+// Verify we can place a MergeJoin
+let joinNode = res.queryPlanner.winningPlan.optimizerPlan.child.leftChild;
+assert.eq("MergeJoin", joinNode.nodeType);
+assert.eq("IndexScan", joinNode.leftChild.nodeType);
+assert.eq("IndexScan", joinNode.rightChild.children[0].child.nodeType);
+
+// One side is not equality, and we use a HashJoin.
+res = t.explain("executionStats").aggregate([{$match: {'a': {$lte: 3}, 'b': 3}}]);
+assert.eq(nMatches, res.executionStats.nReturned);
+
+joinNode = res.queryPlanner.winningPlan.optimizerPlan.child.leftChild;
+assert.eq("HashJoin", joinNode.nodeType);
+assert.eq("IndexScan", joinNode.leftChild.nodeType);
+assert.eq("IndexScan", joinNode.rightChild.children[0].child.nodeType);
+}());
diff --git a/jstests/cqf/index_intersect1.js b/jstests/cqf/index_intersect1.js
new file mode 100644
index 00000000000..fcf0036c974
--- /dev/null
+++ b/jstests/cqf/index_intersect1.js
@@ -0,0 +1,35 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_index_intersect1;
+t.drop();
+
+assert.commandWorked(t.insert({a: 50}));
+assert.commandWorked(t.insert({a: 70}));
+assert.commandWorked(t.insert({a: 90}));
+assert.commandWorked(t.insert({a: 110}));
+assert.commandWorked(t.insert({a: 130}));
+
+// Generate enough documents for index to be preferable.
+for (let i = 0; i < 100; i++) {
+    assert.commandWorked(t.insert({a: 200 + i}));
+}
+
+assert.commandWorked(t.createIndex({'a': 1}));
+
+let res = t.explain("executionStats").aggregate([{$match: {'a': {$gt: 60, $lt: 100}}}]);
+assert.eq(2, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+
+// Should get a covered plan.
+res = t.explain("executionStats")
+          .aggregate([{$project: {'_id': 0, 'a': 1}}, {$match: {'a': {$gt: 60, $lt: 100}}}]);
+assert.eq(2, res.executionStats.nReturned);
+assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/no_collection.js b/jstests/cqf/no_collection.js
new file mode 100644
index 00000000000..3c7ecae4c32
--- /dev/null
+++ b/jstests/cqf/no_collection.js
@@ -0,0 +1,15 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+let t = db.cqf_no_collection;
+t.drop();
+
+const res = t.explain("executionStats").aggregate([{$match: {'a': 2}}]);
+assert.eq(0, res.executionStats.nReturned);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/nonselective_index.js b/jstests/cqf/nonselective_index.js
new file mode 100644
index 00000000000..f951ae7dc40
--- /dev/null
+++ b/jstests/cqf/nonselective_index.js
@@ -0,0 +1,30 @@
+/**
+ * Tests scenario related to SERVER-13065.
+ */
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_nonselective_index;
+t.drop();
+
+const bulk = t.initializeUnorderedBulkOp();
+const nDocs = 1000;
+for (let i = 0; i < nDocs; i++) {
+    bulk.insert({a: i});
+}
+assert.commandWorked(bulk.execute());
+
+assert.commandWorked(t.createIndex({a: 1}));
+
+// We pick collection scan since the query is not selective.
+const res = t.explain("executionStats").aggregate([{$match: {a: {$gte: 0}}}]);
+assert.eq(nDocs, res.executionStats.nReturned);
+
+assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/object_elemMatch.js b/jstests/cqf/object_elemMatch.js
new file mode 100644
index 00000000000..f402c590658
--- /dev/null
+++ b/jstests/cqf/object_elemMatch.js
@@ -0,0 +1,33 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_object_elemMatch;
+
+t.drop();
+assert.commandWorked(t.insert({a: [{a: 1, b: 1}, {a: 1, b: 2}]}));
+assert.commandWorked(t.insert({a: [{a: 2, b: 1}, {a: 2, b: 2}]}));
+assert.commandWorked(t.insert({a: {a: 2, b: 1}}));
+assert.commandWorked(t.insert({a: [{b: [1, 2], c: [3, 4]}]}));
+
+{
+    // Object elemMatch. Currently we do not support index here.
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$elemMatch: {a: 2, b: 1}}}}]);
+    assert.eq(1, res.executionStats.nReturned);
+    assert.eq("PhysicalScan",
+              res.queryPlanner.winningPlan.optimizerPlan.child.child.child.nodeType);
+}
+
+{
+    // Should not be getting any results.
+    const res = t.explain("executionStats").aggregate([
+        {$match: {a: {$elemMatch: {b: {$elemMatch: {}}, c: {$elemMatch: {}}}}}}
+    ]);
+    assert.eq(0, res.executionStats.nReturned);
+}
+}());
diff --git a/jstests/cqf/partial_index.js b/jstests/cqf/partial_index.js
new file mode 100644
index 00000000000..d8196c8cea8
--- /dev/null
+++ b/jstests/cqf/partial_index.js
@@ -0,0 +1,34 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_partial_index;
+t.drop();
+
+assert.commandWorked(t.insert({a: 1, b: 1, c: 1}));
+assert.commandWorked(t.insert({a: 3, b: 2, c: 1}));
+assert.commandWorked(t.insert({a: 3, b: 3, c: 1}));
+assert.commandWorked(t.insert({a: 3, b: 3, c: 2}));
+assert.commandWorked(t.insert({a: 4, b: 3, c: 2}));
+assert.commandWorked(t.insert({a: 5, b: 5, c: 2}));
+
+for (let i = 0; i < 40; i++) {
+    assert.commandWorked(t.insert({a: i + 10, b: i + 10, c: i + 10}));
+}
+
+assert.commandWorked(t.createIndex({'a': 1}, {partialFilterExpression: {'b': 2}}));
+// assert.commandWorked(t.createIndex({'a': 1}));
+
+// TODO: verify with explain the plan should use the index.
+let res = t.aggregate([{$match: {'a': 3, 'b': 2}}]).toArray();
+assert.eq(1, res.length);
+
+// TODO: verify with explain the plan should not use the index.
+res = t.aggregate([{$match: {'a': 3, 'b': 3}}]).toArray();
+assert.eq(2, res.length);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/residual_pred_costing.js b/jstests/cqf/residual_pred_costing.js
new file mode 100644
index 00000000000..07bc7211836
--- /dev/null
+++ b/jstests/cqf/residual_pred_costing.js
@@ -0,0 +1,35 @@
+/**
+ * Tests scenario related to SERVER-21697.
+ */
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_residual_pred_costing;
+t.drop();
+
+const bulk = t.initializeUnorderedBulkOp();
+const nDocs = 2000;
+for (let i = 0; i < nDocs; i++) {
+    bulk.insert({a: i % 10, b: i % 10, c: i % 10, d: i % 10});
+}
+assert.commandWorked(bulk.execute());
+
+assert.commandWorked(t.createIndex({a: 1, b: 1, c: 1, d: 1}));
+assert.commandWorked(t.createIndex({a: 1, b: 1, d: 1}));
+assert.commandWorked(t.createIndex({a: 1, d: 1}));
+
+let res = t.explain("executionStats")
+              .aggregate([{$match: {a: {$eq: 0}, b: {$eq: 0}, c: {$eq: 0}}}, {$sort: {d: 1}}]);
+assert.eq(nDocs * 0.1, res.executionStats.nReturned);
+
+// Demonstrate we can pick the indexing covering most fields.
+const indexNode = res.queryPlanner.winningPlan.optimizerPlan.child.leftChild;
+assert.eq("IndexScan", indexNode.nodeType);
+assert.eq("a_1_b_1_c_1_d_1", indexNode.indexDefName);
+}());
diff --git a/jstests/cqf/sampling.js b/jstests/cqf/sampling.js
new file mode 100644
index 00000000000..37dd0ae0e44
--- /dev/null
+++ b/jstests/cqf/sampling.js
@@ -0,0 +1,31 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const coll = db.cqf_sampling;
+coll.drop();
+
+const bulk = coll.initializeUnorderedBulkOp();
+const nDocs = 10000;
+
+Random.srand(0);
+for (let i = 0; i < nDocs; i++) {
+    const valA = 10.0 * Random.rand();
+    const valB = 10.0 * Random.rand();
+    bulk.insert({a: valA, b: valB});
+}
+assert.commandWorked(bulk.execute());
+
+const res = coll.explain().aggregate([{$match: {'a': {$lt: 2}}}]);
+assert(res.queryPlanner.winningPlan.optimizerPlan.hasOwnProperty("properties"));
+const props = res.queryPlanner.winningPlan.optimizerPlan.properties;
+
+// Verify the winning plan cardinality is within roughly 25% of the expected documents.
+assert.lt(nDocs * 0.2 * 0.75, props.adjustedCE);
+assert.gt(nDocs * 0.2 * 1.25, props.adjustedCE);
+}());
diff --git a/jstests/cqf/selective_index.js b/jstests/cqf/selective_index.js
new file mode 100644
index 00000000000..722f04e75c7
--- /dev/null
+++ b/jstests/cqf/selective_index.js
@@ -0,0 +1,34 @@
+/**
+ * Tests scenario related to SERVER-20616.
+ */
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_selective_index;
+t.drop();
+
+const bulk = t.initializeUnorderedBulkOp();
+const nDocs = 1000;
+for (let i = 0; i < nDocs; i++) {
+    bulk.insert({a: i % 10, b: i});
+}
+assert.commandWorked(bulk.execute());
+
+assert.commandWorked(t.createIndex({a: 1}));
+assert.commandWorked(t.createIndex({b: 1}));
+
+// Predicate on "b" is more selective than the one on "a": 0.1% vs 10%.
+const res = t.explain("executionStats").aggregate([{$match: {a: {$eq: 0}, b: {$eq: 0}}}]);
+assert.eq(1, res.executionStats.nReturned);
+
+// Demonstrate we can pick index on "b".
+const indexNode = res.queryPlanner.winningPlan.optimizerPlan.child.leftChild;
+assert.eq("IndexScan", indexNode.nodeType);
+assert.eq("b_1", indexNode.indexDefName);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/sort.js b/jstests/cqf/sort.js
new file mode 100644
index 00000000000..1a9f4582262
--- /dev/null
+++ b/jstests/cqf/sort.js
@@ -0,0 +1,22 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_basic_unwind1;
+t.drop();
+
+assert.commandWorked(t.insert({_id: 1}));
+assert.commandWorked(t.insert({_id: 2, x: null}));
+assert.commandWorked(t.insert({_id: 3, x: []}));
+assert.commandWorked(t.insert({_id: 4, x: [1, 2]}));
+assert.commandWorked(t.insert({_id: 5, x: [10]}));
+assert.commandWorked(t.insert({_id: 6, x: 4}));
+
+const res = t.aggregate([{$unwind: '$x'}, {$sort: {'x': 1}}]).toArray();
+assert.eq(4, res.length);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/sort_match.js b/jstests/cqf/sort_match.js
new file mode 100644
index 00000000000..54a22a64071
--- /dev/null
+++ b/jstests/cqf/sort_match.js
@@ -0,0 +1,33 @@
+/**
+ * Tests scenario related to SERVER-12923.
+ */
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_sort_match;
+t.drop();
+
+const bulk = t.initializeUnorderedBulkOp();
+const nDocs = 1000;
+for (let i = 0; i < nDocs; i++) {
+    bulk.insert({a: i, b: i % 10});
+}
+assert.commandWorked(bulk.execute());
+
+assert.commandWorked(t.createIndex({a: 1}));
+assert.commandWorked(t.createIndex({b: 1}));
+
+let res = t.explain("executionStats").aggregate([{$sort: {b: 1}}, {$match: {a: {$eq: 0}}}]);
+assert.eq(1, res.executionStats.nReturned);
+
+// Index on "a" is preferred.
+const indexNode = res.queryPlanner.winningPlan.optimizerPlan.child.child.leftChild;
+assert.eq("IndexScan", indexNode.nodeType);
+assert.eq("a_1", indexNode.indexDefName);
+}());
\ No newline at end of file
diff --git a/jstests/cqf/sort_project.js b/jstests/cqf/sort_project.js
new file mode 100644
index 00000000000..49beb912191
--- /dev/null
+++ b/jstests/cqf/sort_project.js
@@ -0,0 +1,74 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+var coll = db.cqf_testCovIndxScan;
+
+coll.drop();
+
+coll.createIndex({f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1});
+coll.getIndexes();
+
+coll.insertMany([
+    {f_0: 2, f_1: 8, f_2: 2, f_3: 0, f_4: 2}, {f_0: 7, f_1: 9, f_2: 8, f_3: 3, f_4: 3},
+    {f_0: 6, f_1: 6, f_2: 2, f_3: 8, f_4: 3}, {f_0: 9, f_1: 2, f_2: 3, f_3: 5, f_4: 7},
+    {f_0: 7, f_1: 8, f_2: 8, f_3: 2, f_4: 9}, {f_0: 7, f_1: 1, f_2: 7, f_3: 3, f_4: 1},
+    {f_0: 7, f_1: 3, f_2: 4, f_3: 0, f_4: 7}, {f_0: 8, f_1: 4, f_2: 5, f_3: 6, f_4: 0},
+    {f_0: 5, f_1: 2, f_2: 0, f_3: 7, f_4: 0}, {f_0: 0, f_1: 2, f_2: 1, f_3: 9, f_4: 2},
+    {f_0: 6, f_1: 0, f_2: 5, f_3: 9, f_4: 1}, {f_0: 0, f_1: 1, f_2: 6, f_3: 8, f_4: 6},
+    {f_0: 6, f_1: 5, f_2: 3, f_3: 8, f_4: 5}, {f_0: 2, f_1: 9, f_2: 7, f_3: 2, f_4: 3},
+    {f_0: 0, f_1: 6, f_2: 9, f_3: 6, f_4: 8}, {f_0: 5, f_1: 7, f_2: 8, f_3: 1, f_4: 4},
+    {f_0: 8, f_1: 5, f_2: 1, f_3: 4, f_4: 6}, {f_0: 6, f_1: 2, f_2: 8, f_3: 4, f_4: 3},
+    {f_0: 1, f_1: 6, f_2: 2, f_3: 0, f_4: 3}, {f_0: 1, f_1: 8, f_2: 2, f_3: 5, f_4: 2}
+]);
+
+const nDocs = 20;
+
+var pln0 = [{'$project': {_id: 0, f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}}];
+
+var pln1 = [{'$sort': {f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}}];
+
+var pln2 = [
+    {'$project': {_id: 0, f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}},
+    {'$sort': {f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}}
+];
+
+var pln3 = [
+    {'$sort': {f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}},
+    {'$project': {_id: 0, f_0: 1, f_1: 1, f_2: 1, f_3: 1, f_4: 1}}
+];
+
+{
+    // Covered plan. Still chooses collection scan because there is no field size/count statistics.
+    // Also an index scan on all fields is not cheaper than a collection scan.
+    let res = coll.explain("executionStats").aggregate(pln0);
+    assert.eq(nDocs, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+
+{
+    // Covered plan.
+    let res = coll.explain("executionStats").aggregate(pln1);
+    assert.eq(nDocs, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+
+{
+    // Covered plan.
+    let res = coll.explain("executionStats").aggregate(pln2);
+    assert.eq(nDocs, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+
+{
+    // Covered plan.
+    let res = coll.explain("executionStats").aggregate(pln3);
+    assert.eq(nDocs, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+}());
diff --git a/jstests/cqf/type_bracket.js b/jstests/cqf/type_bracket.js
new file mode 100644
index 00000000000..1cacba0df2e
--- /dev/null
+++ b/jstests/cqf/type_bracket.js
@@ -0,0 +1,62 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_type_bracket;
+t.drop();
+
+// Generate enough documents for index to be preferable if it exists.
+for (let i = 0; i < 100; i++) {
+    assert.commandWorked(t.insert({a: i}));
+    assert.commandWorked(t.insert({a: i.toString()}));
+}
+
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$lt: "2"}}}]);
+    assert.eq(12, res.executionStats.nReturned);
+    assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$gt: "95"}}}]);
+    assert.eq(4, res.executionStats.nReturned);
+    assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$lt: 2}}}]);
+    assert.eq(2, res.executionStats.nReturned);
+    assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$gt: 95}}}]);
+    assert.eq(4, res.executionStats.nReturned);
+    assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+
+assert.commandWorked(t.createIndex({a: 1}));
+
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$lt: "2"}}}]);
+    assert.eq(12, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$gt: "95"}}}]);
+    assert.eq(4, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$lt: 2}}}]);
+    assert.eq(2, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$gt: 95}}}]);
+    assert.eq(4, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+}());
\ No newline at end of file
diff --git a/jstests/cqf/type_predicate.js b/jstests/cqf/type_predicate.js
new file mode 100644
index 00000000000..eb8de44b3f6
--- /dev/null
+++ b/jstests/cqf/type_predicate.js
@@ -0,0 +1,26 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_type_predicate;
+t.drop();
+
+for (let i = 0; i < 10; i++) {
+    assert.commandWorked(t.insert({a: i}));
+    assert.commandWorked(t.insert({a: i.toString()}));
+}
+
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$type: "string"}}}]);
+    assert.eq(10, res.executionStats.nReturned);
+}
+{
+    const res = t.explain("executionStats").aggregate([{$match: {a: {$type: "double"}}}]);
+    assert.eq(10, res.executionStats.nReturned);
+}
+}());
\ No newline at end of file
diff --git a/jstests/cqf/unionWith.js b/jstests/cqf/unionWith.js
new file mode 100644
index 00000000000..63dedc9d750
--- /dev/null
+++ b/jstests/cqf/unionWith.js
@@ -0,0 +1,54 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+load("jstests/aggregation/extras/utils.js");
+
+const collA = db.collA;
+collA.drop();
+
+const collB = db.collB;
+collB.drop();
+
+assert.commandWorked(collA.insert({_id: 0, a: 1}));
+assert.commandWorked(collB.insert({_id: 0, a: 2}));
+
+let res = collA.aggregate([{$unionWith: "collB"}]).toArray();
+assert.eq(2, res.length);
+assert.eq([{_id: 0, a: 1}, {_id: 0, a: 2}], res);
+
+// Test a filter after the union which can be pushed down to each branch.
+res = collA.aggregate([{$unionWith: "collB"}, {$match: {a: {$lt: 2}}}]).toArray();
+assert.eq(1, res.length);
+assert.eq([{_id: 0, a: 1}], res);
+
+// Test a non-simple inner pipeline.
+res = collA.aggregate([{$unionWith: {coll: "collB", pipeline: [{$match: {a: 2}}]}}]).toArray();
+assert.eq(2, res.length);
+assert.eq([{_id: 0, a: 1}, {_id: 0, a: 2}], res);
+
+// Test a union with non-existent collection.
+res = collA.aggregate([{$unionWith: "non_existent"}]).toArray();
+assert.eq(1, res.length);
+assert.eq([{_id: 0, a: 1}], res);
+
+// Test union alongside projections. This is meant to test the pipeline translation logic that adds
+// a projection to the inner pipeline when necessary.
+res = collA.aggregate([{$project: {_id: 0, a: 1}}, {$unionWith: "collB"}]).toArray();
+assert.eq(2, res.length);
+assert.eq([{a: 1}, {_id: 0, a: 2}], res);
+
+res = collA.aggregate([{$unionWith: {coll: "collB", pipeline: [{$project: {_id: 0, a: 1}}]}}])
+          .toArray();
+assert.eq(2, res.length);
+assert.eq([{_id: 0, a: 1}, {a: 2}], res);
+
+res = collA.aggregate([{$unionWith: "collB"}, {$project: {_id: 0, a: 1}}]).toArray();
+assert.eq(2, res.length);
+assert.eq([{a: 1}, {a: 2}], res);
+}());
diff --git a/jstests/cqf/value_elemMatch.js b/jstests/cqf/value_elemMatch.js
new file mode 100644
index 00000000000..4bb46e6f1a7
--- /dev/null
+++ b/jstests/cqf/value_elemMatch.js
@@ -0,0 +1,52 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_value_elemMatch;
+t.drop();
+
+assert.commandWorked(t.insert({a: [1, 2, 3, 4, 5, 6]}));
+assert.commandWorked(t.insert({a: [5, 6, 7, 8, 9]}));
+assert.commandWorked(t.insert({a: [1, 2, 3]}));
+assert.commandWorked(t.insert({a: []}));
+assert.commandWorked(t.insert({a: [1]}));
+assert.commandWorked(t.insert({a: [10]}));
+assert.commandWorked(t.insert({a: 5}));
+assert.commandWorked(t.insert({a: 6}));
+
+// Generate enough documents for index to be preferable.
+const nDocs = 400;
+for (let i = 0; i < nDocs; i++) {
+    assert.commandWorked(t.insert({a: i + 10}));
+}
+
+assert.commandWorked(t.createIndex({a: 1}));
+
+{
+    // Value elemMatch. Demonstrate we can use an index.
+    const res =
+        t.explain("executionStats").aggregate([{$match: {a: {$elemMatch: {$gte: 5, $lte: 6}}}}]);
+    assert.eq(2, res.executionStats.nReturned);
+    assert.eq("IndexScan",
+              res.queryPlanner.winningPlan.optimizerPlan.child.child.leftChild.child.nodeType);
+}
+{
+    const res =
+        t.explain("executionStats").aggregate([{$match: {a: {$elemMatch: {$lt: 11, $gt: 9}}}}]);
+    assert.eq(1, res.executionStats.nReturned);
+    assert.eq("IndexScan",
+              res.queryPlanner.winningPlan.optimizerPlan.child.child.leftChild.child.nodeType);
+}
+{
+    // Contradiction.
+    const res =
+        t.explain("executionStats").aggregate([{$match: {a: {$elemMatch: {$lt: 5, $gt: 6}}}}]);
+    assert.eq(0, res.executionStats.nReturned);
+    assert.eq("CoScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.child.nodeType);
+}
+}());