Horton

Thread

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Fix possibly uninitialized HeapScanDesc.rs_startblock

  2. Add parallelism support for TID Range Scans

  3. Avoid repeating loads of frozen ID values.

  1. Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-04-29T22:35:59Z

    Hello

 

When using ctid as a
restriction clause with lower and upper bounds, PostgreSQL's planner will use
TID range scan plan to handle such query. This works and generally fine.
However, if the ctid range covers a huge amount of data, the planner will not
use parallel worker to perform ctid range scan because it is not supported. It could, however,
still choose to use parallel sequential scan to complete the scan if ti costs less. 

 

In one of our
migration scenarios, we rely on tid range scan to migrate huge table from one
database to another once the lower and upper ctid bound is determined. With the
support of parallel ctid range scan, this process could be done much quicker.

 

The attached patch
is my approach to add parallel ctid range scan to PostgreSQL's planner and executor. In my
tests, I do see an increase in performance using parallel tid range scan over
the single worker tid range scan and it is also faster than parallel sequential
scan covering similar ranges. Of course, the table needs to be large enough to
reflect the performance increase.

 

below is the timing to complete a select query covering all the records in a simple 2-column
table with 40 million records,

 

 - tid range scan takes 10216ms

 - tid range scan with 2 workers takes 7109ms

 - sequential scan with 2 workers takes 8499ms

 

Having the support
for parallel ctid range scan is definitely helpful in our migration case, I am
sure it could be useful in other cases as well. I am sharing the patch here and
if someone could provide a quick feedback or review that would be greatly appreciated.

 

Thank you!

 

Cary Huang

-------------

HighGo Software Inc. (Canada)

mailto:cary.huang@highgo.ca

http://www.highgo.ca

  2. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2024-04-29T23:14:37Z

    On Tue, 30 Apr 2024 at 10:36, Cary Huang <cary.huang@highgo.ca> wrote:
> In one of our migration scenarios, we rely on tid range scan to migrate huge table from one database to another once the lower and upper ctid bound is determined. With the support of parallel ctid range scan, this process could be done much quicker.

I would have thought that the best way to migrate would be to further
divide the TID range into N segments and run N queries, one per
segment to get the data out.

From a CPU point of view, I'd hard to imagine that a SELECT * query
without any other items in the WHERE clause other than the TID range
quals would run faster with multiple workers than with 1.  The problem
is the overhead of pushing tuples to the main process often outweighs
the benefits of the parallelism.  However, from an I/O point of view
on a server with slow enough disks, I can imagine there'd be a
speedup.

> The attached patch is my approach to add parallel ctid range scan to PostgreSQL's planner and executor. In my tests, I do see an increase in performance using parallel tid range scan over the single worker tid range scan and it is also faster than parallel sequential scan covering similar ranges. Of course, the table needs to be large enough to reflect the performance increase.
>
> below is the timing to complete a select query covering all the records in a simple 2-column table with 40 million records,
>
>  - tid range scan takes 10216ms
>  - tid range scan with 2 workers takes 7109ms
>  - sequential scan with 2 workers takes 8499ms

Can you share more details about this test? i.e. the query, what the
times are that you've measured (EXPLAIN ANALYZE, or SELECT, COPY?).
Also, which version/commit did you patch against?  I was wondering if
the read stream code added in v17 would result in the serial case
running faster because the parallelism just resulted in more I/O
concurrency.

Of course, it may be beneficial to have parallel TID Range for other
cases when more row filtering or aggregation is being done as that
requires pushing fewer tuples over from the parallel worker to the
main process. It just would be good to get to the bottom of if there's
still any advantage to parallelism when no filtering other than the
ctid quals is being done now that we've less chance of having to wait
for I/O coming from disk with the read streams code.

David

  3. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-04-30T19:10:12Z

    Hi David

Thank you for your reply.

> From a CPU point of view, I'd hard to imagine that a SELECT * query
> without any other items in the WHERE clause other than the TID range
> quals would run faster with multiple workers than with 1.  The problem
> is the overhead of pushing tuples to the main process often outweighs
> the benefits of the parallelism.  However, from an I/O point of view
> on a server with slow enough disks, I can imagine there'd be a
> speedup.

yeah, this is generally true. With everything set to default, the planner would not choose parallel sequential scan if the scan range covers mostly all tuples of a table (to reduce the overhead of pushing tuples to main proc as you mentioned). It is preferred when the target data is small but the table is huge. In my case, it is also the same, the planner by default uses normal tid range scan, so I had to alter cost parameters to influence the planner's decision. This is where I found that with WHERE clause only containing TID ranges that cover the entire table would result faster with parallel workers, at least in my environment.

> Of course, it may be beneficial to have parallel TID Range for other
> cases when more row filtering or aggregation is being done as that
> requires pushing fewer tuples over from the parallel worker to the
> main process. It just would be good to get to the bottom of if there's
> still any advantage to parallelism when no filtering other than the
> ctid quals is being done now that we've less chance of having to wait
> for I/O coming from disk with the read streams code.

I believe so too. I shared my test procedure below with ctid being the only quals. 

>> below is the timing to complete a select query covering all the records in a simple 2-column table with 40 million records,
>>
>> - tid range scan takes 10216ms
>> - tid range scan with 2 workers takes 7109ms
>> - sequential scan with 2 workers takes 8499ms
>
> Can you share more details about this test? i.e. the query, what the
> times are that you've measured (EXPLAIN ANALYZE, or SELECT, COPY?).
> Also, which version/commit did you patch against? I was wondering if
> the read stream code added in v17 would result in the serial case
> running faster because the parallelism just resulted in more I/O
> concurrency.

Yes of course. These numbers were obtained earlier this year on master with the patch applied most likely without the read stream code you mentioned. The patch attached here is rebased to commit dd0183469bb779247c96e86c2272dca7ff4ec9e7 on master, which is quite recent and should have the read stream code for v17 as I can immediately tell that the serial scans run much faster now in my setup. I increased the records on the test table from 40 to 100 million because serial scans are much faster now. Below is the summary and details of my test. Note that I only include the EXPLAIN ANALYZE details of round1 test. Round2 is the same except for different execution times. 

[env]
- OS: Ubuntu 18.04
- CPU: 4 cores @ 3.40 GHz
- MEM: 16 GB

[test table setup]
initdb with all default values
CREATE TABLE test (a INT, b TEXT);
INSERT INTO test VALUES(generate_series(1,100000000), 'testing');
SELECT min(ctid), max(ctid) from test;
  min  |     max
-------+--------------
 (0,1) | (540540,100)
(1 row)

[summary]
round 1:
tid range scan: 14915ms
tid range scan 2 workers: 12265ms
seq scan with 2 workers: 12675ms

round2:
tid range scan: 12112ms
tid range scan 2 workers: 10649ms
seq scan with 2 workers: 11206ms

[details of EXPLAIN ANALYZE below]

[default tid range scan]
EXPLAIN ANALYZE SELECT a FROM test WHERE ctid >= '(1,0)' AND ctid <= '(540540,100)';
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Tid Range Scan on test  (cost=0.01..1227029.81 rows=68648581 width=4) (actual time=0.188..12280.791 rows=99999815 loops=1)
   TID Cond: ((ctid >= '(1,0)'::tid) AND (ctid <= '(540540,100)'::tid))
 Planning Time: 0.817 ms
 Execution Time: 14915.035 ms
(4 rows)

[parallel tid range scan with 2 workers]
set parallel_setup_cost=0;
set parallel_tuple_cost=0;
set min_parallel_table_scan_size=0;
set max_parallel_workers_per_gather=2;

EXPLAIN ANALYZE SELECT a FROM test WHERE ctid >= '(1,0)' AND ctid <= '(540540,100)';
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Gather  (cost=0.01..511262.43 rows=68648581 width=4) (actual time=1.322..9249.197 rows=99999815 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Tid Range Scan on test  (cost=0.01..511262.43 rows=28603575 width=4) (actual time=0.332..4906.262 rows=33333272 loops=3)
         TID Cond: ((ctid >= '(1,0)'::tid) AND (ctid <= '(540540,100)'::tid))
 Planning Time: 0.213 ms
 Execution Time: 12265.873 ms
(7 rows)

[parallel seq scan with 2 workers]
set enable_tidscan = 'off';

EXPLAIN ANALYZE SELECT a FROM test WHERE ctid >= '(1,0)' AND ctid <= '(540540,100)';
                                                            QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
 Gather  (cost=0.00..969595.42 rows=68648581 width=4) (actual time=4.489..9713.299 rows=99999815 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on test  (cost=0.00..969595.42 rows=28603575 width=4) (actual time=0.995..5541.178 rows=33333272 loops=3)
         Filter: ((ctid >= '(1,0)'::tid) AND (ctid <= '(540540,100)'::tid))
         Rows Removed by Filter: 62
 Planning Time: 0.129 ms
 Execution Time: 12675.681 ms
(8 rows)


Best regards

Cary Huang
-------------
HighGo Software Inc. (Canada)
cary.huang@highgo.ca
www.highgo.ca

  4. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2024-05-01T07:53:01Z

    On Wed, 1 May 2024 at 07:10, Cary Huang <cary.huang@highgo.ca> wrote:
> Yes of course. These numbers were obtained earlier this year on master with the patch applied most likely without the read stream code you mentioned. The patch attached here is rebased to commit dd0183469bb779247c96e86c2272dca7ff4ec9e7 on master, which is quite recent and should have the read stream code for v17 as I can immediately tell that the serial scans run much faster now in my setup. I increased the records on the test table from 40 to 100 million because serial scans are much faster now. Below is the summary and details of my test. Note that I only include the EXPLAIN ANALYZE details of round1 test. Round2 is the same except for different execution times.

It would be good to see the EXPLAIN (ANALYZE, BUFFERS) with SET
track_io_timing = 1;

Here's a quick review

1. Does not produce correct results:

-- serial plan
postgres=# select count(*) from t where ctid >= '(0,0)' and ctid < '(10,0)';
 count
-------
  2260
(1 row)

-- parallel plan
postgres=# set max_parallel_workers_per_gather=2;
SET
postgres=# select count(*) from t where ctid >= '(0,0)' and ctid < '(10,0)';
 count
-------
     0
(1 row)

I've not really looked into why, but I see you're not calling
heap_setscanlimits() in parallel mode. You need to somehow restrict
the block range of the scan to the range specified in the quals. You
might need to do more work to make the scan limits work with parallel
scans.

If you look at heap_scan_stream_read_next_serial(), it's calling
heapgettup_advance_block(), where there's  "if (--scan->rs_numblocks
== 0)".  But no such equivalent code in
table_block_parallelscan_nextpage() called by
heap_scan_stream_read_next_parallel().  To make Parallel TID Range
work, you'll need heap_scan_stream_read_next_parallel() to abide by
the scan limits.

2. There's a 4 line comment you've added to cost_tidrangescan() which
is just a copy and paste from cost_seqscan().  If you look at the
seqscan costing, the comment is true in that scenario, but not true in
where you've pasted it.  The I/O cost is all tied in to run_cost.

+ /* The CPU cost is divided among all the workers. */
+ run_cost /= parallel_divisor;
+
+ /*
+ * It may be possible to amortize some of the I/O cost, but probably
+ * not very much, because most operating systems already do aggressive
+ * prefetching.  For now, we assume that the disk run cost can't be
+ * amortized at all.
+ */

3. Calling TidRangeQualFromRestrictInfoList() once for the serial path
and again for the partial path isn't great. It would be good to just
call that function once and use the result for both path types.

4. create_tidrangescan_subpaths() seems like a weird name for a
function.  That seems to imply that scans have subpaths. Scans are
always leaf paths and have no subpaths.

This isn't a complete review. It's just that this seems enough to keep
you busy for a while. I can look a bit harder when the patch is
working correctly. I think you should have enough feedback to allow
that now.

David

  5. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-05-01T16:44:14Z

     > This isn't a complete review. It's just that this seems enough to keep
 > you busy for a while. I can look a bit harder when the patch is
 > working correctly. I think you should have enough feedback to allow
 > that now.

Thanks for the test, review and feedback. They are greatly appreciated! 
I will polish the patch some more following your feedback and share new
results / patch when I have them. 

Thanks again!

Cary

  6. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-05-03T18:55:01Z

    Hello

> -- parallel plan
> postgres=# set max_parallel_workers_per_gather=2;
> SET
> postgres=# select count(*) from t where ctid >= '(0,0)' and ctid < '(10,0)';
>  count
> -------
>      0
> (1 row)
> 
> I've not really looked into why, but I see you're not calling
> heap_setscanlimits() in parallel mode. You need to somehow restrict
> the block range of the scan to the range specified in the quals. You
> might need to do more work to make the scan limits work with parallel
> scans.

I found that select count(*) using parallel tid rangescan for the very first time,
it would return the correct result, but the same subsequent queries would
result in 0 as you stated. This is due to the "pscan->phs_syncscan" set to true
in ExecTidRangeScanInitializeDSM(), inherited from parallel seq scan case.
With syncscan enabled, the "table_block_parallelscan_nextpage()" would
return the next block since the end of the first tid rangescan instead of the
correct start block that should be scanned. I see that single tid rangescan
does not have SO_ALLOW_SYNC set, so I figure syncscan should also be
disabled in parallel case. With this change, then it would be okay to call
heap_setscanlimits() in parallel case, so I added this call back to
heap_set_tidrange() in both serial and parallel cases.


> 2. There's a 4 line comment you've added to cost_tidrangescan() which
> is just a copy and paste from cost_seqscan().  If you look at the
> seqscan costing, the comment is true in that scenario, but not true in
> where you've pasted it.  The I/O cost is all tied in to run_cost.

thanks for pointing out, I have removed these incorrect comments

> 3. Calling TidRangeQualFromRestrictInfoList() once for the serial path
> and again for the partial path isn't great. It would be good to just
> call that function once and use the result for both path types.

good point. I moved the adding of tid range scan partial path inside
create_tidscan_paths() where it makes a TidRangeQualFromRestrictInfoList()
call for serial path, so I can just reuse tidrangequals if it is appropriate to
consider parallel tid rangescan.

> 4. create_tidrangescan_subpaths() seems like a weird name for a
> function.  That seems to imply that scans have subpaths. Scans are
> always leaf paths and have no subpaths.

I removed this function with weird name; it is not needed because the logic inside
is moved to create_tidscan_paths() where it can reuse tidrangequals.

> It would be good to see the EXPLAIN (ANALYZE, BUFFERS) with SET
> track_io_timing = 1;

the v2 patch is attached that should address the issues above. Below are the EXPLAIN
outputs with track_io_timing = 1 in my environment. Generally, parallel tid range scan
results in more I/O timings and shorter execution time.


SET track_io_timing = 1;

===serial tid rangescan===

EXPLAIN (ANALYZE, BUFFERS) select a from test where ctid >= '(0,0)' and ctid < '(216216,40)';
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Tid Range Scan on test  (cost=0.01..490815.59 rows=27459559 width=4) (actual time=0.072..10143.770 rows=39999999 loops=1)
   TID Cond: ((ctid >= '(0,0)'::tid) AND (ctid < '(216216,40)'::tid))
   Buffers: shared hit=298 read=215919 written=12972
   I/O Timings: shared read=440.277 write=58.525
 Planning:
   Buffers: shared hit=2
 Planning Time: 0.289 ms
 Execution Time: 12497.081 ms
(8 rows)

set parallel_setup_cost=0;
set parallel_tuple_cost=0;
set min_parallel_table_scan_size=0;
set max_parallel_workers_per_gather=2;

===parallel tid rangescan===

EXPLAIN (ANALYZE, BUFFERS) select a from test where ctid >= '(0,0)' and ctid < '(216216,40)';
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Gather  (cost=0.01..256758.88 rows=40000130 width=4) (actual time=0.878..7083.705 rows=39999999 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   Buffers: shared read=216217
   I/O Timings: shared read=1224.153
   ->  Parallel Tid Range Scan on test  (cost=0.01..256758.88 rows=16666721 width=4) (actual time=0.256..3980.770 rows=13333333 loops=3)
         TID Cond: ((ctid >= '(0,0)'::tid) AND (ctid < '(216216,40)'::tid))
         Buffers: shared read=216217
         I/O Timings: shared read=1224.153
 Planning Time: 0.258 ms
 Execution Time: 9731.800 ms
(11 rows)

===serial tid rangescan with aggregate===

set max_parallel_workers_per_gather=0;

EXPLAIN (ANALYZE, BUFFERS) select count(a) from test where ctid >= '(0,0)' and ctid < '(216216,40)';
                                                           QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=716221.63..716221.64 rows=1 width=8) (actual time=12931.695..12931.696 rows=1 loops=1)
   Buffers: shared read=216217
   I/O Timings: shared read=599.331
   ->  Tid Range Scan on test  (cost=0.01..616221.31 rows=40000130 width=4) (actual time=0.079..6800.482 rows=39999999 loops=1)
         TID Cond: ((ctid >= '(0,0)'::tid) AND (ctid < '(216216,40)'::tid))
         Buffers: shared read=216217
         I/O Timings: shared read=599.331
 Planning:
   Buffers: shared hit=1 read=2
   I/O Timings: shared read=0.124
 Planning Time: 0.917 ms
 Execution Time: 12932.348 ms
(12 rows)

===parallel tid rangescan with aggregate===

set max_parallel_workers_per_gather=2;
EXPLAIN (ANALYZE, BUFFERS) select count(a) from test where ctid >= '(0,0)' and ctid < '(216216,40)';
                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=298425.70..298425.71 rows=1 width=8) (actual time=4842.512..4847.863 rows=1 loops=1)
   Buffers: shared read=216217
   I/O Timings: shared read=1155.321
   ->  Gather  (cost=298425.68..298425.69 rows=2 width=8) (actual time=4842.020..4847.851 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared read=216217
         I/O Timings: shared read=1155.321
         ->  Partial Aggregate  (cost=298425.68..298425.69 rows=1 width=8) (actual time=4824.730..4824.731 rows=1 loops=3)
               Buffers: shared read=216217
               I/O Timings: shared read=1155.321
               ->  Parallel Tid Range Scan on test  (cost=0.01..256758.88 rows=16666721 width=4) (actual time=0.098..2614.108 rows=13333333 loops=3)
                     TID Cond: ((ctid >= '(0,0)'::tid) AND (ctid < '(216216,40)'::tid))
                     Buffers: shared read=216217
                     I/O Timings: shared read=1155.321
 Planning:
   Buffers: shared read=3
   I/O Timings: shared read=3.323
 Planning Time: 4.124 ms
 Execution Time: 4847.992 ms
(20 rows)


Cary Huang
-------------
HighGo Software Inc. (Canada)
cary.huang@highgo.ca
www.highgo.ca

  7. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2024-05-04T01:14:16Z

    On Sat, 4 May 2024 at 06:55, Cary Huang <cary.huang@highgo.ca> wrote:
> With syncscan enabled, the "table_block_parallelscan_nextpage()" would
> return the next block since the end of the first tid rangescan instead of the
> correct start block that should be scanned. I see that single tid rangescan
> does not have SO_ALLOW_SYNC set, so I figure syncscan should also be
> disabled in parallel case. With this change, then it would be okay to call
> heap_setscanlimits() in parallel case, so I added this call back to
> heap_set_tidrange() in both serial and parallel cases.

This now calls heap_setscanlimits() for the parallel version, it's
just that table_block_parallelscan_nextpage() does nothing to obey
those limits.

The only reason the code isn't reading the entire table is due to the
optimisation in heap_getnextslot_tidrange() which returns false when
the ctid goes out of range. i.e, this code:

/*
* When scanning forward, the TIDs will be in ascending order.
* Future tuples in this direction will be higher still, so we can
* just return false to indicate there will be no more tuples.
*/
if (ScanDirectionIsForward(direction))
    return false;

If I comment out that line, I see all pages are accessed:

postgres=# explain (analyze, buffers) select count(*) from a where
ctid >= '(0,1)' and ctid < '(11,0)';
                                                            QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=18.80..18.81 rows=1 width=8) (actual
time=33.530..36.118 rows=1 loops=1)
   Buffers: shared read=4425
   ->  Gather  (cost=18.78..18.79 rows=2 width=8) (actual
time=33.456..36.102 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared read=4425
         ->  Partial Aggregate  (cost=18.78..18.79 rows=1 width=8)
(actual time=20.389..20.390 rows=1 loops=3)
               Buffers: shared read=4425
               ->  Parallel Tid Range Scan on a  (cost=0.01..16.19
rows=1035 width=0) (actual time=9.375..20.349 rows=829 loops=3)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid <
'(11,0)'::tid))
                     Buffers: shared read=4425 <----  this is all
pages in the table instead of 11 pages.

With that code still commented out, the non-parallel version still
won't read all pages due to the setscanlimits being obeyed.

postgres=# set max_parallel_workers_per_gather=0;
SET
postgres=# explain (analyze, buffers) select count(*) from a where
ctid >= '(0,1)' and ctid < '(11,0)';
                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=45.07..45.08 rows=1 width=8) (actual
time=0.302..0.302 rows=1 loops=1)
   Buffers: shared hit=11
   ->  Tid Range Scan on a  (cost=0.01..38.86 rows=2485 width=0)
(actual time=0.019..0.188 rows=2486 loops=1)
         TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid < '(11,0)'::tid))
         Buffers: shared hit=11


If I put that code back in, how many pages are read depends on the
number of parallel workers as workers will keep running with higher
page numbers and heap_getnextslot_tidrange() will just (inefficiently)
filter those out.

max_parallel_workers_per_gather=2;
               ->  Parallel Tid Range Scan on a  (cost=0.01..16.19
rows=1035 width=0) (actual time=0.191..0.310 rows=829 loops=3)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid <
'(11,0)'::tid))
                     Buffers: shared read=17

max_parallel_workers_per_gather=3;
               ->  Parallel Tid Range Scan on a  (cost=0.01..12.54
rows=802 width=0) (actual time=0.012..0.114 rows=622 loops=4)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid <
'(11,0)'::tid))
                     Buffers: shared hit=19

max_parallel_workers_per_gather=4;
               ->  Parallel Tid Range Scan on a  (cost=0.01..9.72
rows=621 width=0) (actual time=0.014..0.135 rows=497 loops=5)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid <
'(11,0)'::tid))
                     Buffers: shared hit=21

To fix this you need to make table_block_parallelscan_nextpage obey
the limits imposed by heap_setscanlimits().

The equivalent code in the non-parallel version is in
heapgettup_advance_block().

/* check if the limit imposed by heap_setscanlimits() is met */
if (scan->rs_numblocks != InvalidBlockNumber)
{
    if (--scan->rs_numblocks == 0)
        return InvalidBlockNumber;
}

I've not studied exactly how you'd get the rs_numblock information
down to the parallel scan descriptor.  But when you figure that out,
just remember that you can't do the --scan->rs_numblocks from
table_block_parallelscan_nextpage() as that's not parallel safe. You
might be able to add an or condition to: "if (nallocated >=
pbscan->phs_nblocks)" to make it "if (nallocated >=
pbscan->phs_nblocks || nallocated >= pbscan->phs_numblocks)",
although the field names don't seem very intuitive there. It would be
nicer if the HeapScanDesc field was called rs_blocklimit rather than
rs_numblocks.  It's not for this patch to go messing with that,
however.

David

  8. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-05-08T22:23:55Z

    Thank you very much for the test and review. Greatly appreciated!
 
> This now calls heap_setscanlimits() for the parallel version, it's
> just that table_block_parallelscan_nextpage() does nothing to obey
> those limits.

yes, you are absolutely right. Though heap_setscanlimits() is now called by
parallel tid range scan,  table_block_parallelscan_nextpage() does nothing
to obey these limits, resulting in more blocks being inefficiently filtered out
by the optimization code you mentioned in heap_getnextslot_tidrange().

> I've not studied exactly how you'd get the rs_numblock information
> down to the parallel scan descriptor.  But when you figure that out,
> just remember that you can't do the --scan->rs_numblocks from
> table_block_parallelscan_nextpage() as that's not parallel safe. You
> might be able to add an or condition to: "if (nallocated >=
> pbscan->phs_nblocks)" to make it "if (nallocated >=
> pbscan->phs_nblocks || nallocated >= pbscan->phs_numblocks)",
> although the field names don't seem very intuitive there. It would be
> nicer if the HeapScanDesc field was called rs_blocklimit rather than
> rs_numblocks.  It's not for this patch to go messing with that,
> however.

rs_numblock was not passed down to the parallel scan context and
table_block_parallelscan_nextpage() did not seem to have a logic to limit
the block scan range set by heap_setscanlimits() in parallel scan. Also, I
noticed that the rs_startblock was also not passed to the parallel scan
context, which causes the parallel scan always start from 0 even when a
lower ctid bound is specified.

so I added a logic in heap_set_tidrange() to pass these 2 values to parallel
scan descriptor as "phs_startblock" and "phs_numblock". These will be
available in table_block_parallelscan_nextpage() in parallel scan. 

I followed your recommendation and modified the condition to:

if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock != 0 &&
    nallocated >= pbscan->phs_numblock))

so that the parallel tid range scan will stop when the upper scan limit is
reached. With these changes, I see that the number of buffer reads is
consistent between single and parallel ctid range scans. The v3 patch is
attached.


postgres=# explain (analyze, buffers) select count(*) from test where ctid >= '(0,1)' and ctid < '(11,0)';
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=39.43..39.44 rows=1 width=8) (actual time=1.007..1.008 rows=1 loops=1)
   Buffers: shared read=11
   ->  Tid Range Scan on test  (cost=0.01..34.35 rows=2034 width=0) (actual time=0.076..0.639 rows=2035 loops=1)
         TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid < '(11,0)'::tid))
         Buffers: shared read=11

postgres=# set max_parallel_workers_per_gather=2;
SET
postgres=# explain (analyze, buffers) select count(*) from test where ctid >= '(0,1)' and ctid < '(11,0)';
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=16.45..16.46 rows=1 width=8) (actual time=14.329..16.840 rows=1 loops=1)
   Buffers: shared hit=11
   ->  Gather  (cost=16.43..16.44 rows=2 width=8) (actual time=3.197..16.814 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared hit=11
         ->  Partial Aggregate  (cost=16.43..16.44 rows=1 width=8) (actual time=0.705..0.706 rows=1 loops=3)
               Buffers: shared hit=11
               ->  Parallel Tid Range Scan on test  (cost=0.01..14.31 rows=848 width=0) (actual time=0.022..0.423 rows=678 loops=3)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid < '(11,0)'::tid))
                     Buffers: shared hit=11

postgres=# set max_parallel_workers_per_gather=3;
SET
postgres=# explain (analyze, buffers) select count(*) from test where ctid >= '(0,1)' and ctid < '(11,0)';
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=12.74..12.75 rows=1 width=8) (actual time=16.793..19.053 rows=1 loops=1)
   Buffers: shared hit=11
   ->  Gather  (cost=12.72..12.73 rows=3 width=8) (actual time=2.827..19.012 rows=4 loops=1)
         Workers Planned: 3
         Workers Launched: 3
         Buffers: shared hit=11
         ->  Partial Aggregate  (cost=12.72..12.73 rows=1 width=8) (actual time=0.563..0.565 rows=1 loops=4)
               Buffers: shared hit=11
               ->  Parallel Tid Range Scan on test  (cost=0.01..11.08 rows=656 width=0) (actual time=0.018..0.338 rows=509 loops=4)
                     TID Cond: ((ctid >= '(0,1)'::tid) AND (ctid < '(11,0)'::tid))
                     Buffers: shared hit=11


thank you!

Cary Huang
-------------
HighGo Software Inc. (Canada)
cary.huang@highgo.ca
www.highgo.ca

  9. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2024-05-09T03:16:30Z

    On Thu, 9 May 2024 at 10:23, Cary Huang <cary.huang@highgo.ca> wrote:
> The v3 patch is attached.

I've not looked at the patch, but please add it to the July CF.  I'll
try and look in more detail then.

David

  10. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-05-09T17:16:32Z

     > I've not looked at the patch, but please add it to the July CF.  I'll
 > try and look in more detail then.

Thanks David, I have added this patch on July commitfest under the
server feature category. 

I understand that the regression tests for parallel ctid range scan is a
bit lacking now. It only has a few EXPLAIN clauses to ensure parallel 
workers are used when tid ranges are specified. They are added as
part of select_parallel.sql test. I am not sure if it is more appropriate
to have them as part of tidrangescan.sql test instead. So basically
re-run the same test cases in tidrangescan.sql but in parallel? 

thank you

Cary

  11. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2024-05-11T00:35:15Z

    On Fri, 10 May 2024 at 05:16, Cary Huang <cary.huang@highgo.ca> wrote:
> I understand that the regression tests for parallel ctid range scan is a
> bit lacking now. It only has a few EXPLAIN clauses to ensure parallel
> workers are used when tid ranges are specified. They are added as
> part of select_parallel.sql test. I am not sure if it is more appropriate
> to have them as part of tidrangescan.sql test instead. So basically
> re-run the same test cases in tidrangescan.sql but in parallel?

I think tidrangescan.sql is a more suitable location than
select_parallel.sql I don't think you need to repeat all the tests as
many of them are testing the tid qual processing which is the same
code as it is in the parallel version.

You should add a test that creates a table with a very low fillfactor,
low enough so only 1 tuple can fit on each page and insert a few dozen
tuples. The test would do SELECT COUNT(*) to ensure you find the
correct subset of tuples. You'd maybe want MIN(ctid) and MAX(ctid) in
there too for extra coverage to ensure that the correct tuples are
being counted.  Just make sure and EXPLAIN (COSTS OFF) the query first
in the test to ensure that it's always testing the plan you're
expecting to test.

David

  12. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2024-05-14T21:33:43Z

    > You should add a test that creates a table with a very low fillfactor,
> low enough so only 1 tuple can fit on each page and insert a few dozen
> tuples. The test would do SELECT COUNT(*) to ensure you find the
> correct subset of tuples. You'd maybe want MIN(ctid) and MAX(ctid) in
> there too for extra coverage to ensure that the correct tuples are
> being counted.  Just make sure and EXPLAIN (COSTS OFF) the query first
> in the test to ensure that it's always testing the plan you're
> expecting to test.

thank you for the test suggestion. I moved the regress tests from select_parallel
to tidrangescan instead. I follow the existing test table creation in tidrangescan
with the lowest fillfactor of 10, I am able to get consistent 5 tuples per page
instead of 1. It should be okay as long as it is consistently 5 tuples per page so
the tuple count results from parallel tests would be in multiples of 5.

The attached v4 patch includes the improved regression tests.

Thank you very much!

Cary Huang
-------------
HighGo Software Inc. (Canada)
cary.huang@highgo.ca
www.highgo.ca

  13. Re: Support tid range scan in parallel?

    Junwang Zhao <zhjwpku@gmail.com> — 2024-08-11T07:03:28Z

    Hi Cary,

On Wed, May 15, 2024 at 5:33 AM Cary Huang <cary.huang@highgo.ca> wrote:
>
> > You should add a test that creates a table with a very low fillfactor,
> > low enough so only 1 tuple can fit on each page and insert a few dozen
> > tuples. The test would do SELECT COUNT(*) to ensure you find the
> > correct subset of tuples. You'd maybe want MIN(ctid) and MAX(ctid) in
> > there too for extra coverage to ensure that the correct tuples are
> > being counted.  Just make sure and EXPLAIN (COSTS OFF) the query first
> > in the test to ensure that it's always testing the plan you're
> > expecting to test.
>
> thank you for the test suggestion. I moved the regress tests from select_parallel
> to tidrangescan instead. I follow the existing test table creation in tidrangescan
> with the lowest fillfactor of 10, I am able to get consistent 5 tuples per page
> instead of 1. It should be okay as long as it is consistently 5 tuples per page so
> the tuple count results from parallel tests would be in multiples of 5.
>
> The attached v4 patch includes the improved regression tests.
>
> Thank you very much!
>
> Cary Huang
> -------------
> HighGo Software Inc. (Canada)
> cary.huang@highgo.ca
> www.highgo.ca
>

+++ b/src/backend/access/heap/heapam.c
@@ -307,6 +307,7 @@ initscan(HeapScanDesc scan, ScanKey key, bool
keep_startblock)
* results for a non-MVCC snapshot, the caller must hold some higher-level
* lock that ensures the interesting tuple(s) won't change.)
*/
+

I see no reason why you add a blank line here, is it a typo?

+/* ----------------------------------------------------------------
+ * ExecSeqScanInitializeWorker
+ *
+ * Copy relevant information from TOC into planstate.
+ * ----------------------------------------------------------------
+ */
+void
+ExecTidRangeScanInitializeWorker(TidRangeScanState *node,
+ ParallelWorkerContext *pwcxt)
+{
+ ParallelTableScanDesc pscan;

Function name in the comment is not consistent.

@@ -81,6 +81,7 @@ typedef struct ParallelBlockTableScanDescData
BlockNumber phs_startblock; /* starting block number */
pg_atomic_uint64 phs_nallocated; /* number of blocks allocated to
* workers so far. */
+ BlockNumber phs_numblock; /* max number of blocks to scan */
} ParallelBlockTableScanDescData;

Can this be reorganized by putting phs_numblock after phs_startblock?


>
>
>
>
>


-- 
Regards
Junwang Zhao

  14. Re: Support tid range scan in parallel?

    Rafia Sabih <rafia.pghackers@gmail.com> — 2024-08-22T11:29:07Z

    This is a good idea to extend parallelism in postgres.
I went through this patch, and here are a few review comments,

+ Size pscan_len; /* size of parallel tid range scan descriptor */

The other name for this var could be tidrs_PscanLen, following the pattern
in indexScanState and IndexOnlyScanState.
Also add it and its description in the comment above the struct.

/* ----------------------------------------------------------------
 * ExecTidRangeScanInitializeDSM
 *
 * Set up a parallel heap scan descriptor.
 * ----------------------------------------------------------------
 */
This comment doesn't seem right, please correct it to say for Tid range
scan descriptor.

+
+ sscan = relation->rd_tableam->scan_begin(relation, snapshot, 0, NULL,
+ pscan, flags);
+
+ return sscan;

I do not  see any requirement of using this sscan var.

- if (nallocated >= pbscan->phs_nblocks)
+ if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock != 0 &&
+ nallocated >= pbscan->phs_numblock))
  page = InvalidBlockNumber; /* all blocks have been allocated */

Please add a comment for the reason for this change. As far as I
understood, this is only for the case of TIDRangeScan so it requires an
explanation for the case.


On Sun, 11 Aug 2024 at 09:03, Junwang Zhao <zhjwpku@gmail.com> wrote:

> Hi Cary,
>
> On Wed, May 15, 2024 at 5:33 AM Cary Huang <cary.huang@highgo.ca> wrote:
> >
> > > You should add a test that creates a table with a very low fillfactor,
> > > low enough so only 1 tuple can fit on each page and insert a few dozen
> > > tuples. The test would do SELECT COUNT(*) to ensure you find the
> > > correct subset of tuples. You'd maybe want MIN(ctid) and MAX(ctid) in
> > > there too for extra coverage to ensure that the correct tuples are
> > > being counted.  Just make sure and EXPLAIN (COSTS OFF) the query first
> > > in the test to ensure that it's always testing the plan you're
> > > expecting to test.
> >
> > thank you for the test suggestion. I moved the regress tests from
> select_parallel
> > to tidrangescan instead. I follow the existing test table creation in
> tidrangescan
> > with the lowest fillfactor of 10, I am able to get consistent 5 tuples
> per page
> > instead of 1. It should be okay as long as it is consistently 5 tuples
> per page so
> > the tuple count results from parallel tests would be in multiples of 5.
> >
> > The attached v4 patch includes the improved regression tests.
> >
> > Thank you very much!
> >
> > Cary Huang
> > -------------
> > HighGo Software Inc. (Canada)
> > cary.huang@highgo.ca
> > www.highgo.ca
> >
>
> +++ b/src/backend/access/heap/heapam.c
> @@ -307,6 +307,7 @@ initscan(HeapScanDesc scan, ScanKey key, bool
> keep_startblock)
> * results for a non-MVCC snapshot, the caller must hold some higher-level
> * lock that ensures the interesting tuple(s) won't change.)
> */
> +
>
> I see no reason why you add a blank line here, is it a typo?
>
> +/* ----------------------------------------------------------------
> + * ExecSeqScanInitializeWorker
> + *
> + * Copy relevant information from TOC into planstate.
> + * ----------------------------------------------------------------
> + */
> +void
> +ExecTidRangeScanInitializeWorker(TidRangeScanState *node,
> + ParallelWorkerContext *pwcxt)
> +{
> + ParallelTableScanDesc pscan;
>
> Function name in the comment is not consistent.
>
> @@ -81,6 +81,7 @@ typedef struct ParallelBlockTableScanDescData
> BlockNumber phs_startblock; /* starting block number */
> pg_atomic_uint64 phs_nallocated; /* number of blocks allocated to
> * workers so far. */
> + BlockNumber phs_numblock; /* max number of blocks to scan */
> } ParallelBlockTableScanDescData;
>
> Can this be reorganized by putting phs_numblock after phs_startblock?
>
>
> >
> >
> >
> >
> >
>
>
> --
> Regards
> Junwang Zhao
>
>
>

-- 
Regards,
Rafia Sabih

  15. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-06-05T21:24:25Z

    Hello 

Sorry David and all who have reviewed the patch, it's been awhile since the patch
was last worked on :(. Thank you all for the reviews and comments! Attached is
the rebased patch that adds support for parallel TID range scans. This feature is
particularly useful scanning large tables where the data needs to be scanned in
sizable segments using a TID range in the WHERE clause to define each segment.
By enabling parallelism, this approach can improve performance compared to
both non-parallel TID range scans and traditional sequential scans.

Regards

Cary Huang

  16. Re: Support tid range scan in parallel?

    Junwang Zhao <zhjwpku@gmail.com> — 2025-06-08T10:52:47Z

    Hi Cary,

On Fri, Jun 6, 2025 at 5:24 AM Cary Huang <cary.huang@highgo.ca> wrote:
>
> Hello
>
> Sorry David and all who have reviewed the patch, it's been awhile since the patch
> was last worked on :(. Thank you all for the reviews and comments! Attached is
> the rebased patch that adds support for parallel TID range scans. This feature is
> particularly useful scanning large tables where the data needs to be scanned in
> sizable segments using a TID range in the WHERE clause to define each segment.
> By enabling parallelism, this approach can improve performance compared to
> both non-parallel TID range scans and traditional sequential scans.
>
> Regards
>
> Cary Huang

Thanks for updating the patch. I have a few comments on it.

+ /*
+ * if parallel mode is used, store startblock and numblocks in parallel
+ * scan descriptor as well.
+ */
+ if (scan->rs_base.rs_parallel != NULL)
+ {
+ ParallelBlockTableScanDesc bpscan = NULL;
+
+ bpscan = (ParallelBlockTableScanDesc) scan->rs_base.rs_parallel;
+ bpscan->phs_startblock = scan->rs_startblock;
+ bpscan->phs_numblock = scan->rs_numblocks;
+ }

It would be more intuitive and clearer to directly use startBlk and numBlks
to set these values. Since scan->rs_startblock and scan->rs_numblocks
are already set using these variables, using the same approach for bpscan
would make the code easier to understand.

Another nitty-gritty is that you might want to use a capital `If` in the
comments to maintain the same style.

+ if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock != 0 &&
+ nallocated >= pbscan->phs_numblock))

I'd suggest explictly setting phs_numblock to InvalidBlockNumber in
table_block_parallelscan_initialize, and compare with InvalidBlockNumber
here.

-- 
Regards
Junwang Zhao

  17. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-06-09T23:04:16Z

    Hi Junwang 

Thank you so much for the review!

> + /*
 > + * if parallel mode is used, store startblock and numblocks in parallel
 > + * scan descriptor as well.
 > + */
 > + if (scan->rs_base.rs_parallel != NULL)
 > + {
 > + ParallelBlockTableScanDesc bpscan = NULL;
 > +
 > + bpscan = (ParallelBlockTableScanDesc) scan->rs_base.rs_parallel;
 > + bpscan->phs_startblock = scan->rs_startblock;
 > + bpscan->phs_numblock = scan->rs_numblocks;
 > + }
 > 
 > It would be more intuitive and clearer to directly use startBlk and numBlks
 > to set these values. Since scan->rs_startblock and scan->rs_numblocks
 > are already set using these variables, using the same approach for bpscan
 > would make the code easier to understand.
 > 
 > Another nitty-gritty is that you might want to use a capital `If` in the
 > comments to maintain the same style.

Agreed, made the adjustment in the attached patch.


 > + if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock != 0 &&
 > + nallocated >= pbscan->phs_numblock))
 > 
 > I'd suggest explictly setting phs_numblock to InvalidBlockNumber in
 > table_block_parallelscan_initialize, and compare with InvalidBlockNumber
 > here.

Also agreed, phs_numblock should be initialized in
table_block_parallelscan_initialize just like all other parameters in parallel scan
context. You are right, it is much neater to use InvalidBlockNumber rather
than 0 to indicate if an upper bound has been specified in the TID range scan.

I have addressed your comment in the attached v6 patch. Thank you again for
the review.

Best regards
Cary Huang

  18. Re: Support tid range scan in parallel?

    Steven Niu <niushiji@gmail.com> — 2025-06-13T05:41:10Z

    Hi, Cary,

I have two comments:
1. Does table_beginscan_parallel_tidrange() need an assert of relid,
like what table_beginscan_parallel() did?
Assert(RelationGetRelid(relation) == pscan->phs_relid);

2. The new field phs_numblock in ParallelBlockTableScanDescData
structure has almost the same name as another field phs_nblocks. Would
you consider changing it to another name, for example,
phs_maxnumblocktoscan?

Thanks,
Steven


在 2025/6/10 7:04, Cary Huang 写道:
> Hi Junwang
>
> Thank you so much for the review!
>
>> + /*
>   > + * if parallel mode is used, store startblock and numblocks in parallel
>   > + * scan descriptor as well.
>   > + */
>   > + if (scan->rs_base.rs_parallel != NULL)
>   > + {
>   > + ParallelBlockTableScanDesc bpscan = NULL;
>   > +
>   > + bpscan = (ParallelBlockTableScanDesc) scan->rs_base.rs_parallel;
>   > + bpscan->phs_startblock = scan->rs_startblock;
>   > + bpscan->phs_numblock = scan->rs_numblocks;
>   > + }
>   >
>   > It would be more intuitive and clearer to directly use startBlk and numBlks
>   > to set these values. Since scan->rs_startblock and scan->rs_numblocks
>   > are already set using these variables, using the same approach for bpscan
>   > would make the code easier to understand.
>   >
>   > Another nitty-gritty is that you might want to use a capital `If` in the
>   > comments to maintain the same style.
>
> Agreed, made the adjustment in the attached patch.
>
>
>   > + if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock != 0 &&
>   > + nallocated >= pbscan->phs_numblock))
>   >
>   > I'd suggest explictly setting phs_numblock to InvalidBlockNumber in
>   > table_block_parallelscan_initialize, and compare with InvalidBlockNumber
>   > here.
>
> Also agreed, phs_numblock should be initialized in
> table_block_parallelscan_initialize just like all other parameters in parallel scan
> context. You are right, it is much neater to use InvalidBlockNumber rather
> than 0 to indicate if an upper bound has been specified in the TID range scan.
>
> I have addressed your comment in the attached v6 patch. Thank you again for
> the review.
>
> Best regards
> Cary Huang
>

  19. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-06-27T22:07:53Z

    Hi Steven

thanks for the review!

 > I have two comments:
 > 1. Does table_beginscan_parallel_tidrange() need an assert of relid,
 > like what table_beginscan_parallel() did?
 > Assert(RelationGetRelid(relation) == pscan->phs_relid);

In the v6 rebased patch, the assert has become:

Assert(RelFileLocatorEquals(relation->rd_locator, pscan->phs_locator));

rather than:

Assert(RelationGetRelid(relation) == pscan->phs_relid);

table_beginscan_parallel_tidrange() already has the proper assert line
similar to what table_beginscan_parallel() has.

 > 2. The new field phs_numblock in ParallelBlockTableScanDescData
 > structure has almost the same name as another field phs_nblocks. Would
 > you consider changing it to another name, for example,
 > phs_maxnumblocktoscan?

I actually had a similar thought too, phs_nblocks and phs_numblock are
very similar but are quite different. But I still left the name as phs_numblock
because I want to keep it consistent (kind of) with the 'numBlks' used in
heap_set_tidrange() in heapam.c. The comments besides their declaration
should be enough to describe their differences without causing confusion.

Best regards
Cary

  20. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-07-22T01:29:43Z

    On Tue, 10 Jun 2025 at 11:04, Cary Huang <cary.huang@highgo.ca> wrote:
> I have addressed your comment in the attached v6 patch. Thank you again for
> the review.

Here's a review of v6:

1. In cost_tidrangescan() you're dividing the total costs by the
number of workers yet the comment is claiming that's CPU cost. I think
this needs to follow the lead of cost_seqscan() and separate out the
CPU and IO cost then add the IO cost at the end, after the divide by
the number of workers.

2. In execParallel.c, could you move the case for T_TidRangeScanState
below T_ForeignScanState? What you have right now is now quite
following the unwritten standard set out by the other nodes, i.e
non-parallel aware nodes are last. A good spot seems to be putting it
at the end of the scan types... Custom scan seems slightly misplaced,
but probably can ignore that one and put it after T_ForeignScanState

3. The following comment should mention what behaviour occurs when the
field is set to InvalidBlockNumber:

BlockNumber phs_numblock; /* max number of blocks to scan */

Something like /* # of blocks to scan, or InvalidBlockNumber if no limit */

4. I think the following would be clearer if written using an else if:

if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock !=
          InvalidBlockNumber && nallocated >= pbscan->phs_numblock))
    page = InvalidBlockNumber; /* all blocks have been allocated */
else
    page = (nallocated + pbscan->phs_startblock) % pbscan->phs_nblocks;

e.g:

if (nallocated >= pbscan->phs_nblocks)
    page = InvalidBlockNumber; /* all blocks have been allocated */
else if (pbscan->phs_numblock != InvalidBlockNumber &&
            nallocated >= pbscan->phs_numblock)
    page = InvalidBlockNumber; /* upper scan limit reached */
else
    page = (nallocated + pbscan->phs_startblock) % pbscan->phs_nblocks;

That way the comment after the assignment is accurate.

5. For the tests, is there any reason not to reuse the tidrangescan table?

I don't see any other issues, but I've not tested the patch yet. I'll
do that if you can fix the 5 above.

Thanks

David

  21. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-07-24T18:46:46Z

    Hi David

Thank you so much for the review! I have addressed the comments in the
attached v7 patch.

 > 1. In cost_tidrangescan() you're dividing the total costs by the
 > number of workers yet the comment is claiming that's CPU cost. I think
 > this needs to follow the lead of cost_seqscan() and separate out the
 > CPU and IO cost then add the IO cost at the end, after the divide by
 > the number of workers.

I have separated the costs into disk and CPU costs similar to the style in
cost_seqscan().

 > 2. In execParallel.c, could you move the case for T_TidRangeScanState
 > below T_ForeignScanState? What you have right now is now quite
 > following the unwritten standard set out by the other nodes, i.e
 > non-parallel aware nodes are last. A good spot seems to be putting it
 > at the end of the scan types... Custom scan seems slightly misplaced,
 > but probably can ignore that one and put it after T_ForeignScanState

Yes, it's been done.

 > 3. The following comment should mention what behaviour occurs when the
 > field is set to InvalidBlockNumber:

Also addressed 

 > 4. I think the following would be clearer if written using an else if:
 > 
 > if (nallocated >= pbscan->phs_nblocks || (pbscan->phs_numblock !=
 >           InvalidBlockNumber && nallocated >= pbscan->phs_numblock))
 >     page = InvalidBlockNumber; /* all blocks have been allocated */
 > else
 >     page = (nallocated + pbscan->phs_startblock) % pbscan->phs_nblocks;
 > 
 > e.g:
 > 
 > if (nallocated >= pbscan->phs_nblocks)
 >     page = InvalidBlockNumber; /* all blocks have been allocated */
 > else if (pbscan->phs_numblock != InvalidBlockNumber &&
 >             nallocated >= pbscan->phs_numblock)
 >     page = InvalidBlockNumber; /* upper scan limit reached */
 > else
 >     page = (nallocated + pbscan->phs_startblock) % pbscan->phs_nblocks;
 > 
 > That way the comment after the assignment is accurate.

Agreed, and also addressed.

 > 5. For the tests, is there any reason not to reuse the tidrangescan table?

To test TID range scan in parallel, I have a new table created with very low fill
factor such that there will be more pages created with small and fixed amount
of tuples in each. Then, the test would do SELECT COUNT(*) to ensure correct
amount of tuples are being counted by the parallel workers during parallel TID
range scan. With this new table, it is easy to ensure the count is correct since
we know how many tuples exist in each page and how many pages are to be
scanned based on the WHERE predicates. Reusing the tidrangescan table
would be hard to tell if the count is correct in my case. 


thank you!
Cary.

  22. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-07-29T05:11:19Z

    On Fri, 25 Jul 2025 at 06:46, Cary Huang <cary.huang@highgo.ca> wrote:
> Thank you so much for the review! I have addressed the comments in the
> attached v7 patch.

I've now spent quite a bit of time going over this patch and testing
it.  One issue I found was in heap_set_tidrange() where you were not
correctly setting the scan limits for the "if
(ItemPointerCompare(&highestItem, &lowestItem) < 0)" case. Through a
bit of manually overwriting the planner's choice using the debugger, I
could get the executor to read an entire table despite the tid range
being completely empty. I likely could have got this to misbehave
without the debugger if I'd used PREPAREd statements and made the
ctids parameters to that. It's just the planner didn't choose a
parallel plan with an empty TID range due to the costs being too low.

For the record, here's the unpatched output below:

# explain (analyze) select count(*) from parallel_tidrangescan where
ctid >= '(10,0)' and ctid <= '(9,10)';
 Aggregate  (cost=2.00..2.01 rows=1 width=8) (actual
time=18440.132..18440.174 rows=1.00 loops=1)
   Buffers: shared read=40
   ->  Gather  (cost=0.01..2.00 rows=1 width=0) (actual
time=18440.126..18440.166 rows=0.00 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         Buffers: shared read=40
         ->  Parallel Tid Range Scan on parallel_tidrangescan
(cost=0.01..2.00 rows=1 width=0) (actual time=2414.495..2414.495
rows=0.00 loops=3)
               TID Cond: ((ctid >= '(10,0)'::tid) AND (ctid <= '(9,10)'::tid))
               Buffers: shared read=40

Note the "Buffers: shared read=40", which is this entire table. After
moving the code which sets the ParallelBlockTableScanDesc's limits
into heap_setscanlimits(), I get:

# explain (analyze) select count(*) from parallel_tidrangescan where
ctid >= '(10,0)' and ctid <= '(9,10)';
 Aggregate  (cost=2.00..2.01 rows=1 width=8) (actual
time=17.787..19.531 rows=1.00 loops=1)
   ->  Gather  (cost=0.01..2.00 rows=1 width=0) (actual
time=17.783..19.527 rows=0.00 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Parallel Tid Range Scan on parallel_tidrangescan
(cost=0.01..2.00 rows=1 width=0) (actual time=0.003..0.004 rows=0.00
loops=3)
               TID Cond: ((ctid >= '(10,0)'::tid) AND (ctid <= '(9,10)'::tid))

I'm now trying to convince myself that it's safe to adjust the
ParallelBlockTableScanDesc fields in heap_setscanlimits(). These
fields are being adjusted during the call to TidRangeNext() via
table_rescan_tidrange(), which is *during* execution, so there could
be any number of parallel workers doing this concurrently. I'm unsure
at this stage if all those workers want to be using the same scan
limits, either.

Currently, I think the above is a problem and it doesn't quite feel
like committer duty to fix this part. There's a chance I may get more
time, but if I don't, I've attached your v7 patch plus the adjustments
I've made to it so far.

David

  23. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-08-13T22:03:06Z

    Hello David

Thank you so much for testing the patch more thoroughly and for sharing your patch.
I see that you moved the setting of ParallelBlockTableScanDesc fields from
heap_set_tidrange() to be within heap_setscanlimits() so that the missing case of
(ItemPointerCompare(&highestItem, &lowestItem) < 0) can be covered. This
placement should be fine.

The workers, however, still end up in heap_set_tidrange() during a call to
TidRangeNext() via table_rescan_tidrange() at the beginning of the scan as you have
described. Each of the worker does attempt to update the tid range to basically the
same range to the parallel context shared among the workers in shared memory,
which may seem a little racy here. 

The problem is that the logic in TidRangeNext() is mostly designed as non-parallel
mode and that  table_rescan_tidrange() is incorrectly called in parallel mode, causing
each worker to try to update TID ranges at the same time.

The initialization of scan descriptor, rescan and setting TID ranges in fact take place
at different places between parallel and non-parallel modes. In non-parallel mode,
everything takes place in TidRangeNext() while in parallel mode, they take place in
ExecTidRangeScanInitializeDSM() and ExecTidRangeScanReInitializeDSM() and they
are called only by the leader.

I have updated TidRangeNext() to not do any rescan or set TID limit in parallel mode.

I have also updated ExecTidRangeScanInitializeDSM() to set the TID range after
initializing parallel scan descriptor, which is shared to the workers via shared memory.
Similarly, in ExecTidRangeScanReInitializeDSM(), a new TID range will be set after the
re-initialization of parallel scan descriptor during the rescan case.
ExecTidRangeScanInitializeWorker() is called by each parallel worker and is also
updated such that it will not set the TID limits again. 

Since ExecTidRangeScanInitializeDSM() and ExecTidRangeScanReInitializeDSM() are
only called by the leader process, there will not be any concurrent call to
heap_setscanlimits(), so no locking is needed there. 

On top of the 2 patches you shared, I have attached the third patch with the changes
I describe above, so it is easy to spot the new diffs.

Thank you once again for your review!

Cary

  24. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-08-14T07:14:54Z

    On Thu, 14 Aug 2025 at 10:03, Cary Huang <cary.huang@highgo.ca> wrote:
> ExecTidRangeScanInitializeWorker() is called by each parallel worker and is also
> updated such that it will not set the TID limits again.

This only works for setting the block range. What about the
TableScanDescData.rs_mintid and rs_maxtid? They'll be left unset in
the parallel worker, and heap_getnextslot_tidrange() needs to do
filtering based on those, which isn't going to work correctly when
they don't get set.

Here are the results from scanning a 10 million row table with the v9 patch:

# set parallel_setup_Cost=0;
# set parallel_tuple_cost=0;
# select count(*) from huge where ctid >= '(10,10)' and ctid <= '(10000,10)';
 count
--------
 629175

# select count(*) from huge where ctid >= '(10,10)' and ctid <= '(10000,10)';
 count
--------
 600247


# select count(*) from huge where ctid >= '(10,10)' and ctid <= '(10000,10)';
 count
--------
 621943
(1 row)

The workers are ending their scan early because
heap_getnextslot_tidrange() returns false on the first call from the
parallel worker.

# set max_parallel_workers_per_Gather=0;
# select count(*) from huge where ctid >= '(10,10)' and ctid <= '(10000,10)';
  count
---------
 2257741

David

  25. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-08-29T17:32:20Z

     > The workers are ending their scan early because
 > heap_getnextslot_tidrange() returns false on the first call from the
 > parallel worker.

Hi David, thank you for the testing!

Yes, the previous v9 patch missed setting node->trss_mintid and
node->trss_maxtid, causing the parallel workers to exit early due to
heap_getnextslot_tidrange() returning false. 

With the attached v10 patch, the parallel leader and workers now
have to evaluate (TidRangeEval()) the given TID ranges and set them
via ExecTidRangeScanInitializeDSM(),
ExecTidRangeScanReInitializeDSM() and 
ExecTidRangeScanInitializeWorker().

To prevent the leader and the workers from calling heap_setscanlimits()
and trying to set phs_startblock and phs_numblock concurrently in
shared memory, I added a condition to only allow parallel
leader to set them. Since node->trss_mintid and node->trss_maxtid
reside in local memory, the workers still have to call heap_set_tidrange
() to have them set to return correct scan results:

# SET parallel_setup_cost TO 0;
# SET parallel_tuple_cost TO 0;

# select count(*) from test where ctid >=  '(10,10)' and ctid <= '(10000,10)';
  count
---------
 1848151
(1 row)

# SET max_parallel_workers_per_gather TO 0;
=# select count(*) from test where ctid >=  '(10,10)' and ctid <= '(10000,10)';
  count
---------
 1848151
(1 row)

thank you again!

Cary

  26. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-07T05:31:20Z

    On Sat, 30 Aug 2025 at 05:32, Cary Huang <cary.huang@highgo.ca> wrote:
>
>  > The workers are ending their scan early because
>  > heap_getnextslot_tidrange() returns false on the first call from the
>  > parallel worker.

> Yes, the previous v9 patch missed setting node->trss_mintid and
> node->trss_maxtid, causing the parallel workers to exit early due to
> heap_getnextslot_tidrange() returning false.
>
> With the attached v10 patch, the parallel leader and workers now
> have to evaluate (TidRangeEval()) the given TID ranges and set them
> via ExecTidRangeScanInitializeDSM(),
> ExecTidRangeScanReInitializeDSM() and
> ExecTidRangeScanInitializeWorker().
>
> To prevent the leader and the workers from calling heap_setscanlimits()
> and trying to set phs_startblock and phs_numblock concurrently in
> shared memory, I added a condition to only allow parallel
> leader to set them. Since node->trss_mintid and node->trss_maxtid
> reside in local memory, the workers still have to call heap_set_tidrange
> () to have them set to return correct scan results:

I spent quite a bit of time looking at this. I didn't like the way
heap_setscanlimits() did:

+ /* set the limits in the ParallelBlockTableScanDesc, when present as leader */
+ if (scan->rs_base.rs_parallel != NULL && !IsParallelWorker())

as it wasn't clear to me that this didn't break completely when the
leader didn't make it there first.

I've made quite a few revisions to the v10 patch, which I've attached
as 11-0002. v11-0001 your v10 rebased atop of master.

Here's a summary of the changes:

1. Moved block limiting logic for parallel scans into
table_block_parallelscan_startblock_init(). There's currently a lock
here to ensure only 1 worker can set the shared memory fields at a
time. I've hooked into the same lock to set the startblock and
numblocks.
2. Fixed chunk size ramp-down code which is meant to divvy up the scan
into smaller and smaller chunks as it nears completion so that one
worker doesn't get left with too much work and leave the others with
nothing.  That code still thought that it was scanning every block in
the table.
3. Changed things around so that the min/max TID for the parallel scan
is specified via table_rescan_tidrange(). This means zero changes to
TidRangeNext, and the only additions to nodeTidrangescan.c are for the
shared memory handling.
4. The rest of the changes are mostly cosmetic.

With this version table_block_parallelscan_startblock_init() has grown
2 extra fields. I considered we should instead rename this function
append "_with_limit" to its name then add another function with the
original name that calls the renamed function passing in
InvalidBlockNumber for both new fields. I didn't do that as we only
have a single call to the existing function, so doing that would only
be for the benefit of extensions that happen to use that function. It
doesn't seem overly difficult for them to adjust their code. I didn't
find any code using that function in codesearch.debian.net.

I still need to do a bit more testing on this, but in the meantime
thought I'd share what I've done with it so that other people can look
in parallel.

David

  27. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-18T01:51:59Z

    On Fri, 7 Nov 2025 at 18:31, David Rowley <dgrowleyml@gmail.com> wrote:
> I still need to do a bit more testing on this, but in the meantime
> thought I'd share what I've done with it so that other people can look
> in parallel.

I've been looking at the v11 patch again. I did some testing and can't break it.

I noted down a couple of things:

1. table_parallelscan_initialize() is called first in a parallel TID
Range Scan which calls table_block_parallelscan_initialize() and may
set phs_syncscan to true.  We directly then call
table_beginscan_parallel_tidrange(), which sets phs_syncscan = false
unconditionally. No bugs, but it is a little strange. One way to get
around this weirdness would be to move the responsibility of setting
phs_syncscan into table_parallelscan_initialize() and then use
table_beginscan_parallel_tidrange() to set phs_syncscan = false. I
wasn't overly concerned about this, so I didn't do that. I just wanted
to mention it here as someone else might think it's worth making
better.

2. I've made it so each worker calls TidRangeEval() to figure out the
TID range to scan. The first worker to get the lock in
table_block_parallelscan_startblock_init() gets to set the range of
blocks to scan for all workers. In the planner, the suitability of the
TID Range quals are checked with IsBinaryTidClause(), which allows
OpExprs with the ctid column compared to a Var-less expression that
contains no volatile functions.  If someone coded up a parallel safe
volatile function and marked it as stable, each worker could end up
with different ctid values and one worker would win the race to set
the blocks to scan based on the TID values it got, which wouldn't
really suit the other workers and the tid values they ended up with.
I'm thinking of someone marks the volatile function as stable, then
we're entitled to having things behave strangely for them. To make
this right, I'd have to make it so only 1 worker evaluates the TID
expressions and then sets those somehow for the other workers. There'd
have to be some additional shared memory for that, and I don't think
the complexity of making that work is worthwhile.  Mentioning it as
someone else might feel differently.

I've attached v12, which adds a mention in the docs about Parallel TID
Range scans being supported. It also does very minor adjustments to
the comments. Again, I've kept Cary's v10 and the changes I've made
separate. Of course, I'd squash these before commit.

Does anyone have any opinions on #1 or #2 or want to look at this? I'd
like to get this in soon.

David

  28. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-27T01:07:03Z

    On Tue, 18 Nov 2025 at 14:51, David Rowley <dgrowleyml@gmail.com> wrote:
> I've attached v12, which adds a mention in the docs about Parallel TID
> Range scans being supported. It also does very minor adjustments to
> the comments. Again, I've kept Cary's v10 and the changes I've made
> separate. Of course, I'd squash these before commit.

I went over this again today and only made a few whitespace
adjustments in the tests. I've now pushed the resulting patch.

David

  29. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-27T05:48:11Z

    On Thu, 27 Nov 2025 at 14:07, David Rowley <dgrowleyml@gmail.com> wrote:
> I went over this again today and only made a few whitespace
> adjustments in the tests. I've now pushed the resulting patch.

This seems to have caused issues on skink [1] under Valgrind.  The
problem seems to be that initscan() does not always initialise
rs_startblock. I'm now trying to figure out if there's some reason for
that, or if that's been overlooked at some point.

David

[1] https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=skink&dt=2025-11-27%2002%3A17%3A35

  30. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-27T13:31:05Z

    On Thu, 27 Nov 2025 at 18:48, David Rowley <dgrowleyml@gmail.com> wrote:
> This seems to have caused issues on skink [1] under Valgrind.  The
> problem seems to be that initscan() does not always initialise
> rs_startblock. I'm now trying to figure out if there's some reason for
> that, or if that's been overlooked at some point.

I've written the attached patch to address the uninitialised
rs_startblock field.

The patch basically adds:

if (!keep_startblock)
    scan->rs_startblock = InvalidBlockNumber;

to initscan() when in parallel mode. The rest of the patch is a small
refactor to make it clearer which parts are for parallel and which are
for serial. I also added a comment to mention that the syncscan start
location is figured out in table_block_parallelscan_startblock_init()
for parallel scans.

David

> [1] https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=skink&dt=2025-11-27%2002%3A17%3A35

  31. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-11-27T23:42:14Z

    On Fri, 28 Nov 2025 at 02:31, David Rowley <dgrowleyml@gmail.com> wrote:
> The patch basically adds:
>
> if (!keep_startblock)
>     scan->rs_startblock = InvalidBlockNumber;

I've pushed that patch.

David

  32. Re: Support tid range scan in parallel?

    Cary Huang <cary.huang@highgo.ca> — 2025-12-05T20:12:50Z

    Hi David,

Thanks a lot for the detailed review, the fixes, and for pushing this
forward. I really appreciate the time you spent going through the
patch set

> 1. Moved block limiting logic for parallel scans into
> table_block_parallelscan_startblock_init(). There's currently a lock
> here to ensure only 1 worker can set the shared memory fields at a
> time. I've hooked into the same lock to set the startblock and
> numblocks.

I agree this is a much better location than heap_setscanlimits() to
ensure only the leader can set parallel scan limits for all workers.
You are right, the condition I put in heap_setscanlimits() cannot
guarentee the leader would get there first. Thanks for pointing
this out.

> 1. table_parallelscan_initialize() is called first in a parallel TID
> Range Scan which calls table_block_parallelscan_initialize() and may
> set phs_syncscan to true.  We directly then call
> table_beginscan_parallel_tidrange(), which sets phs_syncscan = false
> unconditionally. No bugs, but it is a little strange. One way to get
> around this weirdness would be to move the responsibility of setting
> phs_syncscan into table_parallelscan_initialize() and then use
> table_beginscan_parallel_tidrange() to set phs_syncscan = false. I
> wasn't overly concerned about this, so I didn't do that. I just wanted
> to mention it here as someone else might think it's worth making
> better.

Nice catch. Yes it is a bit weird but harmless. I agree to leave it as is
now. 

>          within each worker process.
>        </para>
>      </listitem>
> +    <listitem>
> +      <para>
> +        In a <emphasis>parallel tid range scan</emphasis>, the range of blocks
> +        will be subdivided into smaller ranges which are shared among the
> +        cooperating processes.  Each worker process will complete the scanning
> +        of its given range of blocks before requesting an additional range of
> +        blocks.
> +      </para>
> +    </listitem>
>    </itemizedlist>

I may be missing some info or wrong but my impression is that
the range of blocks is actually set by the leader worker and is
the same among all the cooperating workers rather than
subdivided. The workers fetches as many blocks to process as
they can (similar to sequential scan in parllel) as long as the
block falls within the TID range. Current block number is
stored in parallel scan descriptor in shared memory so workers
will not fetch the same block during scan.

Thanks again for all the help and improvements!

Cary Huang
www.highgo.ca

  33. Re: Support tid range scan in parallel?

    David Rowley <dgrowleyml@gmail.com> — 2025-12-07T20:35:26Z

    On Sat, 6 Dec 2025 at 09:12, Cary Huang <cary.huang@highgo.ca> wrote:
> >          within each worker process.
> >        </para>
> >      </listitem>
> > +    <listitem>
> > +      <para>
> > +        In a <emphasis>parallel tid range scan</emphasis>, the range of blocks
> > +        will be subdivided into smaller ranges which are shared among the
> > +        cooperating processes.  Each worker process will complete the scanning
> > +        of its given range of blocks before requesting an additional range of
> > +        blocks.
> > +      </para>
> > +    </listitem>
> >    </itemizedlist>
>
> I may be missing some info or wrong but my impression is that
> the range of blocks is actually set by the leader worker and is
> the same among all the cooperating workers rather than
> subdivided. The workers fetches as many blocks to process as
> they can (similar to sequential scan in parllel) as long as the
> block falls within the TID range. Current block number is
> stored in parallel scan descriptor in shared memory so workers
> will not fetch the same block during scan.

If you look at what's written for Seq Scans, namely "In a parallel
sequential scan, the table's blocks will be divided into ranges and
shared among the cooperating processes.", this is talking about how
the blocks are shared between workers, i.e no two workers operate on
the same block. If that happened we'd get wrong results. The "range"
that this is talking about was introduced in 56788d215 to fix the
kernel readhead detection issue with Parallel Seq Scans (the kernel
was not detecting sequential file access due to multiple processes
cooperating on the sequential access).  With Parallel TID Range Scans,
we already have the "TID Range" of blocks to scan, so I had to come up
with wording that didn't say "we divide the range into ranges and
distribute ...", so I used "subdivided".  I'm happy if someone comes
up with better wording, but I don't see anything factually wrong with
what's there.

The TID Range of blocks is set by whichever worker process gets there
first. That might not be the leader.

David