Re: WIP: BRIN multi-range indexes

On 3/17/21 7:59 PM, John Naylor wrote:
> On Thu, Mar 11, 2021 at 12:26 PM Tomas Vondra
> <tomas(dot)vondra(at)enterprisedb(dot)com <mailto:tomas(dot)vondra(at)enterprisedb(dot)com>>
> wrote:
>>
>> Hi,
>>
>> Here is an updated version of the patch series.
>>
>> It fixes the assert failure (just remove the multiplication from it) and
>> adds a simple regression test that exercises this.
>>
>> Based on the discussion so far, I've decided to keep just the new
>> signature of the consistent function. That's a bit simpler than having
>> to support both 3 and 4 parameters, and it would not deal with the NULL
>> changes anyway (mostly harmless code duplication, but still). I've also
>> realized the API documentation in SGML needs updating.
>>
>> At this point, I think 0001-0006 parts are mostly committable.
>
> I think so. I've marked it RFC for this six.
>
>> As for the remaining two parts, the one dealing with correlation may not
>> be strictly necessary, but not having it (or something like it) may
>> result in not picking the BRIN index in some cases.
>>
>> But maybe it's not a major problem. I tried the example from [1] but it
>> no longer triggers the issue for me - I'm not entirely sure why, but the
>> costing changed for some reason. It used to look like this:
>
>> ...
>
>> The index scan cost is about the same, but the heap scan is about half
>> the cost. The row estimates are a bit different, perhaps that's related.
>> The seqscan cost (169248) and duration (~500ms) is still about the same,
>> but so now we still pick the bitmap heap scan.
>
> With only 0001-0006, I get a parallel bitmap scan in both cases:
>
>                                                             QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------
>  Gather  (cost=6542.42..52779.35 rows=10 width=4) (actual
> time=3.283..22.308 rows=10 loops=1)
>    Workers Planned: 2
>    Workers Launched: 2
>    ->  Parallel Bitmap Heap Scan on t0  (cost=5542.42..51778.35 rows=4
> width=4) (actual time=3.434..17.257 rows=3 loops=3)
>          Recheck Cond: (a = 10000)
>          Rows Removed by Index Recheck: 83165
>          Heap Blocks: lossy=421
>          ->  Bitmap Index Scan on t0_a_idx  (cost=0.00..5542.42
> rows=381682 width=0) (actual time=2.996..2.996 rows=11040 loops=1)
>                Index Cond: (a = 10000)
>  Planning Time: 0.088 ms
>  Execution Time: 22.341 ms
> (11 rows)
>
>> Not sure we can rely on
>> this, though. Would be quite sad if we had new improved opclasses but
>> the planner often decided not to use them.
>
> Yeah, I'm not sure what to do here. It might be okay to leave it out now
> and study it further as a PG14 open item or PG15 improvement.
>

Yeah, that's definitely an option.

>> I had an idea of tweaking choose_bitmap_and to consider both the cost
>> and selectivity (similarly to how add_path considers statup/total cost),
>> and that did indeed resolve this particular case. This is what the 0008
>> part does.
>>
>> But it may also have negative consequence, as demonstrated by the
>> reproducer2.sql script. So maybe the logic would need to be more
>> complicated. Or maybe there's no reliable solution, considering how
>> tricky/unreliable BRIN estimates are.
>
> Ok, so with 0008 in reproducer2, it chooses the more selective path,
> even though it has a higher total cost:
>
> 0001-0007:
>
>                                                      QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on t2  (cost=29.03..24032.28 rows=1 width=8) (actual
> time=0.498..1.755 rows=1 loops=1)
>    Recheck Cond: (a = 1000)
>    Rows Removed by Index Recheck: 7167
>    Heap Blocks: lossy=128
>    ->  Bitmap Index Scan on idx_2  (cost=0.00..29.03 rows=7163 width=0)
> (actual time=0.278..0.278 rows=1280 loops=1)
>          Index Cond: (a = 1000)
>  Planning Time: 0.148 ms
>  Execution Time: 1.774 ms
> (8 rows)
>
> DROP INDEX
>                                                     QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on t2  (cost=656.00..1531.00 rows=1 width=8) (actual
> time=9.695..9.708 rows=1 loops=1)
>    Recheck Cond: (a = 1000)
>    Rows Removed by Index Recheck: 223
>    Heap Blocks: lossy=4
>    ->  Bitmap Index Scan on idx_1  (cost=0.00..656.00 rows=224 width=0)
> (actual time=9.675..9.675 rows=40 loops=1)
>          Index Cond: (a = 1000)
>  Planning Time: 0.110 ms
>  Execution Time: 9.727 ms
> (8 rows)
>
> and with 0008:
>
>                                                     QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on t2  (cost=656.00..1531.00 rows=1 width=8) (actual
> time=8.540..8.577 rows=1 loops=1)
>    Recheck Cond: (a = 1000)
>    Rows Removed by Index Recheck: 223
>    Heap Blocks: lossy=4
>    ->  Bitmap Index Scan on idx_1  (cost=0.00..656.00 rows=224 width=0)
> (actual time=8.507..8.508 rows=40 loops=1)
>          Index Cond: (a = 1000)
>  Planning Time: 0.175 ms
>  Execution Time: 8.601 ms
> (8 rows)
>
> DROP INDEX
>                                                     QUERY PLAN
> -------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on t2  (cost=656.00..1531.00 rows=1 width=8) (actual
> time=9.712..9.725 rows=1 loops=1)
>    Recheck Cond: (a = 1000)
>    Rows Removed by Index Recheck: 223
>    Heap Blocks: lossy=4
>    ->  Bitmap Index Scan on idx_1  (cost=0.00..656.00 rows=224 width=0)
> (actual time=9.691..9.692 rows=40 loops=1)
>          Index Cond: (a = 1000)
>  Planning Time: 0.104 ms
>  Execution Time: 9.746 ms
> (8 rows)
>
>
>> That being said, I don't think this is something we need to solve here,
>> and it may not actually be an issue at all. For this to happen there
>> need to be a terrible index on the same attribute (like the minmax index
>> in the example above). But why keeping such index anyway? Dropping it
>> would make the issue go away. If we have two indexes that both perform
>> reasonably (say, bloom and minmax-multi), the consequences are not that
>> bad. so this is interesting, but probably fine.
>
> Yeah, I suspect this is unlikely to be a problem in practice.
>
> --
> I've run a similar test based on an earlier example from some months ago
> (attached).
>

Ummm, no attachment ;-)

> 0001-0006:
>
> At first regular BRIN is faster, and it will choose it if available:
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=404.79..233352.86 rows=1252175 width=57)
> (actual time=2.115..346.351 rows=1252800 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 15936
>    Heap Blocks: lossy=15104
>    ->  Bitmap Index Scan on cd_multi  (cost=0.00..91.74 rows=1256702
> width=0) (actual time=0.972..0.972 rows=151040 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 0.208 ms
>  Execution Time: 412.549 ms
> (8 rows)
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=341.99..233335.81 rows=1256871 width=57)
> (actual time=1.244..170.962 rows=1252800 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 15936
>    Heap Blocks: lossy=15104
>    ->  Bitmap Index Scan on cd_single  (cost=0.00..27.78 rows=1267458
> width=0) (actual time=0.406..0.406 rows=151040 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 0.197 ms
>  Execution Time: 237.146 ms
> (8 rows)
>
>
> After delete, vacuum, and insert, BRIN multi is chosen over seq scan
> even though the correlation should be somewhat off (I didn't go further
> and try to find a case where seq scan is wrongly preferred):
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=428.53..247273.68 rows=1135074 width=57)
> (actual time=1.798..252.494 rows=1128038 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 140698
>    Heap Blocks: lossy=15104
>    ->  Bitmap Index Scan on cd_multi  (cost=0.00..144.76 rows=1598833
> width=0) (actual time=0.940..0.941 rows=151040 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 0.152 ms
>  Execution Time: 311.999 ms
> (8 rows)
>
>
> Add regular BRIN index, and it will get chosen, making the scan slower:
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=308.20..246966.38 rows=1118304 width=57)
> (actual time=5.685..1277.854 rows=1128038 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 7548826
>    Heap Blocks: lossy=103296
>    ->  Bitmap Index Scan on cd_single  (cost=0.00..28.62 rows=1551397
> width=0) (actual time=4.609..4.609 rows=1032960 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 0.211 ms
>  Execution Time: 1338.685 ms
> (8 rows)
>
> Apply 0007 -- no difference:
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=308.20..246966.38 rows=1118304 width=57)
> (actual time=6.988..1358.113 rows=1128038 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 7548826
>    Heap Blocks: lossy=103296
>    ->  Bitmap Index Scan on cd_single  (cost=0.00..28.62 rows=1551397
> width=0) (actual time=5.528..5.528 rows=1032960 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 3.534 ms
>  Execution Time: 1418.194 ms
> (8 rows)
>
> Apply 0008 -- now it chooses minmax-multi:
>
>                                                                        
>   QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Bitmap Heap Scan on iot  (cost=422.94..245412.66 rows=1118304 width=57)
> (actual time=2.750..259.850 rows=1128038 loops=1)
>    Recheck Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp with
> time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp with
> time zone))
>    Rows Removed by Index Recheck: 140698
>    Heap Blocks: lossy=15104
>    ->  Bitmap Index Scan on cd_multi  (cost=0.00..143.36 rows=1128092
> width=0) (actual time=1.609..1.609 rows=151040 loops=1)
>          Index Cond: ((create_dt >= '2020-02-01 00:00:00-04'::timestamp
> with time zone) AND (create_dt < '2020-03-01 00:00:00-04'::timestamp
> with time zone))
>  Planning Time: 1.421 ms
>  Execution Time: 319.891 ms
> (8 rows)
>
>
> So, 0007 doesn't make a difference in this case, but 0008 does.
>

Interesting. Anyway, we picked the BRIN in both cases (over just using
seqscan), and it's unlikely to have two brin indexes with different
opclasses.

Barring objections, I'll get the 0001-0006 parts committed soon, and
then we can continue working on the costing changes for the next major
version.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company