opt: take into account ON conditions for join costing

[andy-kimball]

Repro:
Create the schema and statistics shown below, and then run the following query:

SELECT w, x, y, z
FROM wxyz
INNER JOIN abcde
ON w = a AND x = b AND y = c
WHERE w = 'foo' AND x = '2AB23800-06B1-4E19-A3BB-DF3768B808D2'
ORDER BY d
LIMIT 10;

EXPECTED: This query should use the idx_abcd index, because it's more selective.
ACTUAL: This query uses the idx_abd index.

The problem is that the coster does not take into account any remainder ON predicates. While idx_abcd has fewer remainder predicates, it is actually considered as more expensive than idx_abd. To fix this, we'll need to incorporate remainder predicates into the cost estimation somehow.

CREATE TABLE abcde (
	a TEXT NOT NULL,
	b UUID NOT NULL,
	c UUID NOT NULL,
	d VARCHAR(255) NOT NULL,
	e TEXT NOT NULL,
	CONSTRAINT "primary" PRIMARY KEY (a, b, c),
	UNIQUE INDEX idx_abd (a, b, d),
	UNIQUE INDEX idx_abcd (a, b, c, d)
);

ALTER TABLE abcde INJECT STATISTICS '[
  {
    "columns": ["a"],
    "created_at": "2019-02-08 04:10:40.001179+00:00",
    "row_count": 250000,
    "distinct_count": 1
  },
  {
    "columns": ["b"],
    "created_at": "2019-02-08 04:10:40.119954+00:00",
    "row_count": 250000,
    "distinct_count": 2
  },
  {
    "columns": ["d"],
    "created_at": "2019-02-08 04:10:40.119954+00:00",
    "row_count": 250000,
    "distinct_count": 125000
  }
]';

CREATE TABLE wxyz (
	w TEXT NOT NULL,
	x UUID NOT NULL,
	y UUID NOT NULL,
	z TEXT NOT NULL,
	CONSTRAINT "primary" PRIMARY KEY (w, x, y),
	CONSTRAINT "foreign" FOREIGN KEY (w, x, y) REFERENCES abcde (a, b, c)
);

ALTER TABLE wxyz INJECT STATISTICS '[
  {
    "columns": ["w"],
    "created_at": "2019-02-08 04:10:40.001179+00:00",
    "row_count": 10000,
    "distinct_count": 1
  },
  {
    "columns": ["x"],
    "created_at": "2019-02-08 04:10:40.119954+00:00",
    "row_count": 10000,
    "distinct_count": 1
  },
  {
    "columns": ["y"],
    "created_at": "2019-02-08 04:10:40.119954+00:00",
    "row_count": 10000,
    "distinct_count": 2500
  }
]';

[RaduBerinde]

I think merge joins have the same issue.

[RaduBerinde]

A fix has been merged but I am keeping the issue open for a more general change.

[RaduBerinde]

Pasting from #35587:

The core problem is that we don't take into account that if we have an
ON condition, not only there's a cost to evaluate it on each row, but
we are generating more internal rows to get a given number of output
rows.

I attempted to do a more general fix (for all join types), where I
tried to estimate the "internal" number of rows using
unknownFilterSelectivity for each ON condition. There were two
problems:

• in some cases (especially with lookup joins) we have an extra ON
  condition that doesn't actually do anything:
  ab JOIN xy ON a=x AND a=10 becomes
  ab JOIN xy ON a=x AND a=10 AND x=10
  and a=10 could remain as an ON condition. This results in bad
  query plans in important cases (e.g. TPCC) where it prefers to do
  an extra lookup join (due to a non-covering index) just because of
  that condition.

• we don't have the equality columns readily available for hash join
  (and didn't want to extract them each time we cost). In the future
  we may split the planning into a logical and physical stage, and we
  should then separate the logical joins from hash join.

For 19.1, we simply simply add a cost for lookup joins that is
proportional to the number of remaining ON conditions. This is the
least disruptive method that still fixes the case observed in #34810.
I will leave the issue open to address this properly in the next
release.

Note that although hash joins and merge joins have the same issue in
principle, in practice we always generate these expressions with
equality on all possible columns.

[RaduBerinde]

Adding more folks to the issue because this came up recently and we need more brainstorming on this.

[rytaft]

A big issue with lookup joins is that we don't track the number of rows scanned during the lookup. I wonder if it makes sense to add an extra field to the Statistics struct. In addition to RowCount (the number of output rows), we could have RowsProcessed (the number of rows processed by the operator). In most cases RowsProcessed is equal to the number of input rows, but it would be different for lookup joins.

[RaduBerinde]

The problem is that Statistics are per group and RowProcessed changes depending on the particular expression (e.g. a lookup join that constrains columns x,y and one that constrains just column x could be in the same group).

[andy-kimball]

Yeah, I think this means we need more logic in the Coster. There may be some shared code between the StatisticsBuilder and the Coster.

[rytaft]

Similar to how @ridwanmsharif used RequestColStat, we can add a utility function like GetRowsProcessed which calls into the statisticsBuilder for a given relational expression.

[RaduBerinde]

We've been bit by this again, this time with FK checks. For TPCC, some of the lookup joins inside FK checks don't use the correct index. @rytaft would you be able to look at fixing this?

[RoachietheSupportRoach]

Zendesk ticket #3600 has been linked to this issue.