GitHub user leborchuk added a comment to the discussion: [Ideas] Bloom filter
performance: four experiments
Also it will be wise to study here the full set of TPC-DS queries. Some of them
show as increased performance, some - decresed.
Here the good examples.
1. Query 72. Decreased performance
Query has a join condition
```
postgres=# SELECT tpcds.show(72);
show
----------------------------------------------------------------------------------------------------
select
...
from catalog_sales
join inventory on (cs_item_sk = inv_item_sk)
join warehouse on (w_warehouse_sk=inv_warehouse_sk)
...
limit 100;
```
That section leads to execution plan fragment
```
...
Hash Key: item.i_item_desc,
warehouse.w_warehouse_name, d1.d_week_seq
-> Hash Join (cost=0.00..69939.92 rows=55804
width=126) (actual time=24962.331..38251.844 rows=21459 loops=1)
Hash Cond: (inventory.inv_warehouse_sk =
warehouse.w_warehouse_sk)
Extra Text: (seg0) Hash chain length
1.0 avg, 1 max, using 10 of 32768 buckets.
...
-> Hash (cost=1675.58..1675.58
rows=66555000 width=16) (actual time=23497.119..23497.120 rows=66631200 loops=1)
Buckets: 65536 Batches: 512
Memory Usage: 6659kB
-> Seq Scan on inventory
(cost=0.00..1675.58 rows=66555000 width=16) (actual time=0.872..10718.740
rows=66631200 loops=1)
-> Hash (cost=431.00..431.00 rows=10
width=20) (actual time=0.809..0.810 rows=10 loops=1)
Buckets: 32768 Batches: 1 Memory
Usage: 257kB
-> Seq Scan on warehouse
(cost=0.00..431.00 rows=10 width=20) (actual time=0.793..0.800 rows=10 loops=1)
```
When we instrument with bloom filters we will add additional 11 seconds to
pefrorm hash probes of 66555000 rows from `inventory`. None of them actually
discarded so we need hash it once again and join with `warehouse` table.
Here the execution plan example
```
-> Hash (cost=1675.58..1675.58
rows=66555000 width=16) (actual time=38039.900..38039.902 rows=66631200 loops=1)
Buckets: 65536 Batches: 512
Memory Usage: 6659kB
-> Custom Scan (Anser Bloom
Consumer) (cost=0.00..1675.58 rows=66555000 width=16) (actual
time=4.064..22880.960 rows=66631200 loops=1)
Bloom Filter Size:
1048576 bytes
Bloom Filter Stats:
memory=1024kB checked=66631199 rejected=0
Rows Removed by Bloom
Filter: 0
-> Seq Scan on
inventory (cost=0.00..1675.58 rows=66555000 width=16) (actual
time=4.062..11939.815 rows=66631200 loops=1)
-> Hash (cost=431.00..431.00 rows=10
width=20) (actual time=23.976..23.977 rows=10 loops=1)
Buckets: 32768 Batches: 1 Memory
Usage: 257kB
-> Custom Scan (Anser Bloom
Producer) (cost=0.00..431.00 rows=10 width=20) (actual time=1.746..23.968
rows=10 loops=1)
Bloom Filter Size: 1048576
bytes
Bloom Filter Stats:
memory=1024kB
-> Seq Scan on warehouse
(cost=0.00..431.00 rows=10 width=20) (actual time=1.744..1.751 rows=10 loops=1)
```
Also `catalog_sales` table has a chain of bloom filters. They work great, but
not all of them are worth probing. Here the example:
```
-> Hash Join (cost=0.00..5477.80 rows=9926238 width=44) (actual
time=818.554..3580.306 rows=347767 loops=1)
Hash Cond: (catalog_sales.cs_sold_date_sk = d1.d_date_sk)
Extra Text: (seg0) Hash chain length 7.1 avg, 14 max,
using 359 of 32768 buckets.
-> Custom Scan (Anser Bloom Consumer) (cost=0.00..1179.47
rows=7200292 width=36) (actual time=2.982..3511.342 rows=62555 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB checked=249379
rejected=199562
Rows Removed by Bloom Filter: 199562
-> Custom Scan (Anser Bloom Consumer)
(cost=0.00..1179.47 rows=7200292 width=36) (actual time=2.980..3339.517
rows=262117 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB checked=262116
rejected=0
Rows Removed by Bloom Filter: 0
-> Custom Scan (Anser Bloom Consumer)
(cost=0.00..1179.47 rows=7200292 width=36) (actual time=2.980..3246.299
rows=262117 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB
checked=249415 rejected=0
Rows Removed by Bloom Filter: 0
-> Custom Scan (Anser Bloom Consumer)
(cost=0.00..1179.47 rows=7200292 width=36) (actual time=2.979..3108.408
rows=262117 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB
checked=1443924 rejected=1203667
Rows Removed by Bloom Filter: 1203667
-> Custom Scan (Anser Bloom
Consumer) (cost=0.00..1179.47 rows=7200292 width=36) (actual
time=2.978..2945.627 rows=1465784 loops=1)
Bloom Filter Size: 1048576
bytes
Bloom Filter Stats:
memory=1024kB checked=7171372 rejected=5742079
Rows Removed by Bloom Filter:
5742079
-> Seq Scan on catalog_sales
(cost=0.00..1179.47 rows=7200292 width=36) (actual time=2.977..2354.727
rows=7207863 loops=1)
```
2. Query 78. Increase performance
All bloom filters in that query works gret, each remove not needed to join
rows. The strongest filter is on `store_sales`.
Query has join condition
```
cs as
(select
...
from catalog_sales
left join catalog_returns on cr_order_number=cs_order_number and
cs_item_sk=cr_item_sk
join date_dim on cs_sold_date_sk = d_date_sk
```
The original query executes like
```
-> Hash Join
(cost=0.00..14439.51 rows=2550966 width=28) (actual time=421.843..18198.710
rows=2496287 loops=1)
Hash Cond:
(store_sales.ss_sold_date_sk = date_dim.d_date_sk)
Extra Text: (seg0)
Hash chain length 1.0 avg, 2 max, using 365 of 65536 buckets.
-> Result
(cost=0.00..11295.57 rows=12883440 width=28) (actual time=421.668..16583.966
rows=12969878 loops=1)
Filter:
(store_returns.sr_ticket_number IS NULL)
-> Hash Left
Join (cost=0.00..10821.86 rows=14398447 width=36) (actual
time=421.666..15005.890 rows=14412078 loops=1)
Hash Cond:
((store_sales.ss_ticket_number = store_returns.sr_ticket_number) AND
(store_sales.ss_item_sk = store_returns.sr_item_sk))
-> Seq
Scan on store_sales (cost=0.00..1484.25 rows=14398447 width=36) (actual
time=2.518..3774.327 rows=14412078 loops=1)
-> Hash
(cost=526.07..526.07 rows=1440509 width=12) (actual time=419.010..419.011
rows=1442200 loops=1)
Buckets: 65536 Batches: 8 Memory Usage: 8964kB
->
Seq Scan on store_returns (cost=0.00..526.07 rows=1440509 width=12) (actual
time=0.518..174.468 rows=1442200 loops=1)
-> Hash
(cost=435.01..435.01 rows=362 width=8) (actual time=0.079..0.079 rows=366
loops=1)
Buckets: 65536
Batches: 1 Memory Usage: 527kB
-> Broadcast
Motion 2:2 (slice2; segments: 2) (cost=0.00..435.01 rows=362 width=8) (actual
time=0.017..0.044 rows=366 loops=1)
-> Seq
Scan on date_dim (cost=0.00..434.94 rows=181 width=8) (actual
time=3.191..5.160 rows=192 loops=1)
Filter: (d_year = 2000)
```
But `cs_sold_date_sk = d_date_sk` is quite selective and will be great to
filter out `store_sales` table before join. We did it with produced bloom
filters
```
-> Hash Join
(cost=0.00..14439.51 rows=2550966 width=28) (actual time=495.379..9903.791
rows=2496287 loops=1)
Hash Cond:
(store_sales.ss_sold_date_sk = date_dim.d_date_sk)
Extra Text: (seg0)
Hash chain length 1.0 avg, 2 max, using 365 of 65536 buckets.
-> Result
(cost=0.00..11295.57 rows=12883440 width=28) (actual time=495.245..9260.823
rows=3079578 loops=1)
Filter:
(store_returns.sr_ticket_number IS NULL)
-> Hash Left
Join (cost=0.00..10821.86 rows=14398447 width=36) (actual
time=495.243..8851.450 rows=3422009 loops=1)
Hash Cond:
((store_sales.ss_ticket_number = store_returns.sr_ticket_number) AND
(store_sales.ss_item_sk = store_returns.sr_item_sk))
-> Custom
Scan (Anser Bloom Consumer) (cost=0.00..1484.25 rows=14398447 width=36)
(actual time=2.476..5400.603 rows=3422009 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB checked=13763811 rejected=10990069
Rows
Removed by Bloom Filter: 10990069
->
Seq Scan on store_sales (cost=0.00..1484.25 rows=14398447 width=36) (actual
time=2.473..3952.991 rows=14412078 loops=1)
-> Hash
(cost=526.07..526.07 rows=1440509 width=12) (actual time=473.979..473.981
rows=1442200 loops=1)
Buckets: 65536 Batches: 8 Memory Usage: 8964kB
->
Seq Scan on store_returns (cost=0.00..526.07 rows=1440509 width=12) (actual
time=1.536..222.554 rows=1442200 loops=1)
-> Hash
(cost=435.01..435.01 rows=362 width=8) (actual time=0.076..0.077 rows=366
loops=1)
Buckets: 65536
Batches: 1 Memory Usage: 527kB
-> Broadcast
Motion 2:2 (slice2; segments: 2) (cost=0.00..435.01 rows=362 width=8) (actual
time=0.016..0.042 rows=366 loops=1)
-> Custom
Scan (Anser Bloom Producer) (cost=0.00..434.94 rows=181 width=8) (actual
time=2.581..45.734 rows=192 loops=1)
Bloom Filter Size: 1048576 bytes
Bloom Filter Stats: memory=1024kB
->
Seq Scan on date_dim (cost=0.00..434.94 rows=181 width=8) (actual
time=2.578..4.053 rows=192 loops=1)
Filter: (d_year = 2000)
```
All example for me shows the same issue RPT+ tries to solve using various
heuristics. I believe we could take RPT+ approach to rearrange bloom filters
and decide which of them worth using.
GitHub link:
https://github.com/apache/cloudberry/discussions/1959#discussioncomment-18600093
----
This is an automatically sent email for [email protected].
To unsubscribe, please send an email to: [email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
