Does not make much sense that every physical operator gets a JoinStats field. It only has estimated cost/cardinality. Can we rename this to something more general, i.e., EstimatedProperties?

The same goes for the logical operators

We use nullptr instead of NULL

Rather than copying each field individually here, can we implement a Copy method for JoinStats (or whatever name we decide to give it)?

unused import

CamelCase instead of snake_case for functions

I'd suggest using static constexpr double, and re-naming to CAPITAL letters (to conform with code style)

To prevent nesting the code more and more like you are doing here:

for (auto &expr : exprs) {
  if (expr.property == ...) {
    auto &derived = (DerivedClass &)*expr;
    if (derived.property == ...) {
      // Do something
    }
  }
}

I would suggest using the following pattern:

for (auto &expr : exprs) {
  if (expr.property != ...) {
    continue;
  }
  auto &derived = (DerivedClass &)*expr;
  if (derived.property != ...) {
    continue;
  }
  // Do something
}

It requires a few more lines of code, but results in more readable code because the level of nested ifs stays manageable, making lines less wide.

This is a really long method with tons of nested for/if-statements. Can we split this up into methods with descriptive names and try to reduce the nestedness?

Can we wrap this into a struct instead of creating this somewhat human-readable integer?

We already have all the code you need for this. The table, col pair can be stored in a ColumnBinding, and we already have a way to create an unordered_map that goes from ColumnBinding -> whatever, which is the column_binding_map_t, defined in column_binding_map.hpp.

I see that you're also using it in an unordered_map, you can also easily create a column_binding_set_t by re using the same code

The way this copy function is formulated seems a bit strange to me. Why does it need an argument? Can we not do:

unique_ptr<EstimatedProperties> Copy() {
    auto result = make_unique<EstimatedProperties>();
    result->cost = cost;
    result->cardinality = cardinality;
    return result;
}

We shouldn't need this hash function for column bindings. We already have a hash function for ColumnBinding in column_binding_map.hpp, which also defines column_binding_map_t, which is a mapping from ColumnBinding to whatever type you need, as wel as column_binding_set_t.

Using this, you can have a map/set like this:

#include "duckdb/planner/column_binding_map.hpp"

// ...

auto my_map = column_binding_map<idx_t>(); // map from ColumnBinding to idx_t
ColumnBinding my_binding(4, 2);
my_map[my_binding] = 42; // lookup using column binding directly

auto my_set = column_binding_set_t();
my_set.insert(my_binding);
my_set.insert(my_binding); // was already in set

I think we can still remove some of the nesting from this method:

	if (filter_info->left_set && filter_info->right_set) {
		// Both set
		return false;
	}
	//! Filter on one relation, (i.e string or range filter on a column).
 	//! Grab the relation (should always be 1) and add it to the
 	//! the equivalence_relations
 	D_ASSERT(filter_info->set->count == 1);
 	for (auto &i_set : equivalent_relations) {
 		if (i_set.count(filter_info->left_binding) > 0) {
			// Found an equivalent filter
 			return true;
 		}
 	}
 	D_ASSERT(filter_info->set->relations[0] == filter_info->left_binding.table_index);
 	auto key = ColumnBinding(filter_info->set->relations[0],
 	                         filter_info->left_binding.column_index);
 	unordered_set<ColumnBinding> tmp({key});
 	equivalent_relations.push_back(tmp);
 	return true;

We can immediately return false if the condition doesn't hold, which removes one level of nesting for the whole method. Then, we looking for equivalent filters, we can immediately return true if we find one, which removes a level of nesting for the remainder of the method.

Not that nesting is evil or anything. Sometimes it can make code more readable! But in this case I think it's more readable with less nesting.

If you have a loop that needs an index, I'd suggest just using a for-loop, instead of a smart loop that increments an index:

for (idx_t ind = 0; ind < equivalent_relations.size(); ind++) {
	// Feel free to use 'auto' instead of the more verbose 'unordered_set<ColumnBinding>&'
	const auto &i_set = equivalent_relations[ind];
	if (i_set.count(key) != 1) {
		continue; // Remove 1 level of nesting from the loop
	}
	// Rest of the logic here
	// Etc.
}

Our code style requires

if (!table_filters) {
	return cardinality_after_filters;
}

In the top-level folder of the duckdb repo we have .clang-format and .clang-tidy files, which CLion understands. If you point it to these files CLion will help you with code style. You can even do command + option + L to auto-format.

This can be made more concise:

for (const auto &filter_pair : table_filters->filters) {
	auto &filter = filter_pair.second;
	if (filter.filter_type == TableFilterType::CONJUNCTION_AND) {
		// Etc.
	}
}

Can remove some more nesting by doing

if (child_filter->filter_type != TableFilterType::CONSTANT_COMPARISON) {
	continue;
}
auto comparison_filter = (ConstantFilter &)*child_filter;
if (comparison_filter.comparison_type != ExpressionType::COMPARE_EQUAL) {
	continue;
}
// Etc.

Of course, if you do this, it becomes more cumbersome to add an else. However, if you're never going to add an else, I'd prefer to remove nesting.

In the end, this may be replaced by filtering a sample anyway, so not sure how much it matters.

With column_binding_map_t, this can be:

vector<column_binding_map_t<ColumnBinding> child_binding_maps({});

The estimated_cardinality was in there before we added the EstimatedProperties, but now it seems like it makes sense to merge them.

You could add a something like

idx_t GetEstimatedCardinality() {
    return estimated_props->estimated_cardinality;
}

We're now using this EstimatedProperties in more places than just the join order optimizer, since it's now a field of PhysicalOperator as well.

Can we move EstimatedProperties to its own header/implementation file, instead of being in the header/implementation file of JoinNode?

For the PR we'll need to clean some of this debugging code up. We don't want commented and/or unused code.

I imagine that some of it is no longer needed, but some of it will be nice to keep. If you look through the code base, you'll see that classes such as LogicalOperator/DataChunk/Pipeline have ToString() and Print() methods.

Could you check if some of the debugging code can be removed and/or refactored to ToString() and Print() methods?

Could you move the symmetry verification to another method? Could be a static method or a private method of the JoinOrderOptimizer.

void VerifySymmetry(args ...) {
#ifdef DEBUG
    // ... verification code
#endif
}

This keeps the code for CreateJoinTree more clean.

Seems like this code would be cleaner with a switch statement:

switch (op->type) {
    case LogicalOperatorType::LOGICAL_GET: {
        // ...
    }
    case LogicalOperatorType::LOGICAL_FILTER: {
        // ...
    }
}

Then you don't need the IsLogicalGet function, and it's easy to extend with more operator types.

We prefer a smart loop here, which is less verbose. Something like:

for (auto &rel_and_col : relation_to_columns[relation_id]) {
    // ...
}

Just a nitpick but we like to keep our methods and fields in separate public/private blocks, i.e.:

class CardinalityEstimator {
public:
	explicit CardinalityEstimator(ClientContext &context) : context(context) {
	}
	// other public functions

public:
	// public fields

private:
	// private functions

private:
	// private fields

Could you write some descriptions for the functions/fields in this header? Especially for the functions that are not immediately clear:

//! Describe function
void Function();

Of course, EstimateCardinality is very descriptive so it doesn't really need a description, but adding one anyway doesn't do any harm either.

For these comments we use just //, not //!.

In general, //! is reserved for describing a function/field, for example in a header file.

The Create by ... should be removed

Can we make a function in CardinalityEstimator for this? It's not really clear what this code does when reading it.

Something like this, or a more descriptive name that makes more sense to you:

cardinality_estimator.AddColumnToRelation(...);

There's a few more instances in this file where you add something to a map or other data structure that belongs to the CardinalityEstimator.

Touching the data structures that belong to CardinalityEstimator from outside of the cardinality_estimator.*pp files should be done sparingly.

The loop at line 212 in this file (under ExtractJoinRelations), for example, adds some key/value pairs to a map in CardinalityEstimator. In those cases, the whole loop should probably be moved to the implementation file cardinality_estimator.cpp, as this has nothing to do with dynamic programming.

If it's some kind of initialisation like in ExtractJoinRelations, we prefer having a single call to some function in CardinalityEstimator, rather than having a few lines here and there that do some stuff related to cardinality estimation in our functions that belong to our DP implementation.

Can we merge relation_to_columns and relation_to_table_name?

For example:

struct MyTable { // not sure about name ...
	string name;
	unordered_set<idx_t> column_ids;
}

// now we can have one map instead of two
unordered_map<idx_t, MyTable> relation_to_table;

This makes it easier to add things later.

clean this up

push this into cardinality estimator

push into cardinality estimator

change this comment back

rename to something with supersets

write a debug verification method

re-word this one more time

Also add D_ASSERT() in the generate Joins call

Please separate methods and fields, and remove unused private: block

I think this method can now be removed? Because you are using the column_binding_{map,set}_t stuff?

Either way, this function and check_all_table_keys_forwarded() should not be in snake_case.

Could you do with with a smart loop instead?

for (auto &equivalent_rel : equivalent_relations) {
    // etc.
}

Could you do something like this here?

//! erase empty equivalent relation sets
std::remove_if(equivalent_relations.begin(), equivalent_relations.end(),
    [](column_binding_set_t &equivalent_rel) {
        return equivalent_rel.empty();
    });

The ::iterator stuff always seems so verbose to me

I think this is unused

I think this is unused

Can we make DEFAULT_SELECTIVITY a private field of `CardinalityEstimator?