Re: BRIN cost estimate

- cond := format('%I %s %L', r.colname, r.oper, r.value);
+ cond := format('%s %s %L', r.colname, r.oper, r.value);

Why did you change this? It seems unrelated.

Must be a mistake.

+ indexRel = index_open(index->indexoid, AccessShareLock);
+ pagesPerRange = Min(BrinGetPagesPerRange(indexRel), baserel->pages);
+ Assert(baserel->pages > 0);
+ Assert(pagesPerRange > 0);
+ rangeProportion = (double) pagesPerRange / baserel->pages;
+ numRanges = 1.0 + (double) baserel->pages / pagesPerRange;
+ index_close(indexRel, AccessShareLock);

Why do you add 1.0 to numRanges? This gives one too many ranges.

I have tried to prevent division by zero that can happen later, but your
solution below sounds cleaner to me.

I also don't really like the way you're setting pagesPerRange. I'd suggest
keeping that as the raw value from the index metadata, and doing:

If you want the actual number of ranges then I think this is best expressed
as:

numRanges = Max(ceil(baserel->pages / pagesPerRange), 1.0);

The rangeProportion variable could be calculated based on that
too rangeProportion = 1.0 / numRanges;

That way you don't have to rely on relpages being > 0. It seems like a bad
assumption to make. I see there's some hack in estimate_rel_size() making
that true, but I think it's best not to rely on that hack.

- qual_op_cost = cpu_operator_cost *
- (list_length(indexQuals) + list_length(indexOrderBys));
-
*indexStartupCost += qual_arg_cost;
*indexTotalCost += qual_arg_cost;
- *indexTotalCost += (numTuples * *indexSelectivity) *
(cpu_index_tuple_cost + qual_op_cost);
*indexPages = index->pages;

- /* XXX what about pages_per_range? */
+ /*
+ * Add index qual op costs. Unlike other indexes, we are not processing
+ * tuples but ranges.
+ */
+ qual_op_cost = cpu_operator_cost * list_length(indexQuals);
+ *indexTotalCost += numRanges * qual_op_cost;

What's the reason for removing the + list_length(indexOrderBys) here? I
don't think it's the business of this patch to touch that. BRIN may one day
support that by partition sorting non-overlapping ranges, so that could
well be why it was there in the first place.

I thought it was a mistake. I agree we better not change it, even though I
have no idea how cost of BRIN sorting can be calculated. I guess the
indexOrderBys list would always be empty for now, anyway.

- *indexTotalCost += (numTuples * *indexSelectivity) *
(cpu_index_tuple_cost + qual_op_cost);
+ *indexTotalCost += selec * numTuples * cpu_index_tuple_cost;

Why is this not being charged qual_op_cost anymore?

I must have thought that BRIN doesn't execute the qual unlike btree. I am
not sure what is the best equation to put there. Previously, we were
returning good selectivity, but high cost. I believe things should be
other way around. Maybe what we really need is to use "numRanges" in here
instead of "selec * numTuples".

+ * Our starting point is that BRIN selectivity has to be less than the
+ * selectivity of the btree. We are using a product of logical and

Can you explain why this is the case?

My wording sounds wrong in here. I should have said "worse than" instead
of "less than".

+ * class "minmax", and makes a little sense for the other one "inclusion".

"and" I think should be "but"

I agree.

I think it would also be good to write some regression tests for this. All
the changes I see that you did make to brin.sql seem unrelated to this
patch.

I added an expression index to test getting correlation of expressions.
The BRIN tests would call the estimation functions, but we don't have any
tests to check the result of the functions. We can maybe prepare a test to
check BRIN is prefferred over btree when it would perform better, and maybe
also vice versa.

Unfortunately, I am on vacation for two weeks without my computer. I can
post another version after 18th. I know we are under time pressure for
release. I wouldn't mind if you or Alvaro would change it anyway you like.