Thread: Table AM modifications to accept column projection lists

Hello,

This patch introduces a set of changes to the table AM APIs, making them
accept a column projection list. That helps columnar table AMs, so that
they don't need to fetch all columns from disk, but only the ones
actually needed.

The set of changes in this patch is not exhaustive -
there are many more opportunities that are discussed in the TODO section
below. Before digging deeper, we want to elicit early feedback on the
API changes and the column extraction logic.

TableAM APIs that have been modified are:

1. Sequential scan APIs
2. Index scan APIs
3. API to lock and return a row
4. API to fetch a single row

We have seen performance benefits in Zedstore for many of the optimized
operations [0]. This patch is extracted from the larger patch shared in
[0].

------------------------------------------------------------------------
Building the column projection set:

In terms of building the column projection set necessary for each of
these APIs, this patch builds off of the scanCols patch [1], which
Ashwin and Melanie had started earlier. As noted in [1], there are cases
where the scanCols set is not representative of the columns to be
projected. For instance, in a DELETE .. RETURNING query, there is
typically a sequential scan and a separate invocation of
tuple_fetch_row_version() in order to satisfy the RETURNING clause (see
ExecDelete()). So for a query such as:

  DELETE from foo WHERE i < 100 && j < 1000 RETURNING k, l;

We need to pass the set (i, j) to the scan and (k, l) to the
tuple_fetch_row_version() invocation. This is why we had to introduce
the returningCols field.

In the same spirit, separate column projection sets are computed for any
operations that involve an EPQ check (INSERT, DELETE, UPDATE, row-level
locking etc), the columns involved in an ON CONFLICT UPDATE etc.

Recognizing and collecting these sets of columns is done at various
stages: analyze and rewrite, planner and executor - depending on the
type of operation for which the subset of columns is calculated. The
column bitmaps are stored in different places as well - such as the ones
for scans and RETURNING are stored in RangeTblEntry, whereas the set of
columns for ON CONFLICT UPDATE are stored in OnConflictSetState.

------------------------------------------------------------------------
Table AM API changes:

The changes made to the table AM API, introducing the column projection
set, come in different flavors. We would like feedback on what style
we need to converge to or if we should use different styles depending
on the situation.

- A new function variant that takes a column projection list, such as:

  TableScanDesc (*scan_begin) (Relation rel,
    Snapshot snapshot,
    int nkeys, struct ScanKeyData *key,
    ParallelTableScanDesc pscan,
    uint32 flags);
->

  TableScanDesc (*scan_begin_with_column_projection)(Relation relation,
     Snapshot snapshot,
     int nkeys, struct ScanKeyData *key,
     ParallelTableScanDesc parallel_scan,
     uint32 flags,
     Bitmapset *project_columns);

- Modifying the existing function to take a column projection list, such
as:

  TM_Result (*tuple_lock) (Relation rel,
     ItemPointer tid,
     Snapshot snapshot,
     TupleTableSlot *slot,
     CommandId cid,
     LockTupleMode mode,
     LockWaitPolicy wait_policy,
     uint8 flags,
     TM_FailureData *tmfd);

->

  TM_Result (*tuple_lock) (Relation rel,
     ItemPointer tid,
     Snapshot snapshot,
     TupleTableSlot *slot,
     CommandId cid,
     LockTupleMode mode,
     LockWaitPolicy wait_policy,
     uint8 flags,
     TM_FailureData *tmfd,
     Bitmapset *project_cols);

- A new function index_fetch_set_column_projection() to be called after
index_beginscan() to set the column projection set, which will be used
later by index_getnext_slot().

  void (*index_fetch_set_column_projection) (struct IndexFetchTableData *data,
     Bitmapset *project_columns);

The set of columns expected by the new/modified functions is represented
as a Bitmapset of attnums for a specific base relation. An empty/NULL
bitmap signals to the AM that no data columns are needed. A bitmap
containing the single element 0 indicates that we want all data columns
to be fetched.

The bitmaps do not include system columns.

Additionally, the TupleTableSlots populated by functions such
as table_scan_getnextslot(), need to be densely filled upto the highest
numbered column in the projection list (any column not in the projection
list should be populated with NULL). This is due to the implicit
assumptions of the slot_get_***() APIs.

------------------------------------------------------------------------
TODOs:

- Explore opportunities to push the column extraction logic to the
planner or pre-planner stages from the executor stage (like scanCols and
returningCols), or at least elevate the column extraction logic to be
done once per executor run instead of once per tuple.

- As was requested in [1], we should guard column projection set
extraction logic with a table_scans_leverage_column_projection() call.
We wouldn't want a non-columnar AM to incur the overhead.

- Standardize the table AM API for passing columns.

- The optimization for DELETE RETURNING does not currently work for
views. We have to populate the list of columns for the base relation
beneath the view properly.

- Currently the benefit of passing in an empty projection set for ON
CONFLICT DO UPDATE (UPSERT) and ON CONFLICT DO NOTHING (see
ExecCheckTIDVisible()) is masked by a preceding call to
check_exclusion_or_unique_constraint() which has not yet been modified
to pass a column projection list to the index scan.

- Compute scanCols earlier than set_base_rel_sizes() and use that
information to produce better relation size estimates (relation size
will depend on the number of columns projected) in the planner.
Essentially, we need to absorb the work done by Pengzhou [2].

- Right now, we do not extract a set of columns for the call to
table_tuple_lock() within GetTupleForTrigger() as it may be hard to
determine the list of columns used in a trigger body [3].

- validateForeignKeyConstraint() should only need to fetch the
foreign key column.

- List of index scan callsites that will benefit from calling
index_fetch_set_column_projection():

  -- table_index_fetch_tuple_check() does not need to fetch any
  columns (we have to pass an empty column bitmap), fetching the tid
  should be enough.

  -- unique_key_recheck() performs a liveness check for which we do
  not need to fetch any columns (we have to pass an empty column
  bitmap)

  -- check_exclusion_or_unique_constraint() needs to only fetch the
  columns that are part of the exclusion or unique constraint.

  -- IndexNextWithReorder() needs to only fetch columns being
  projected along with columns in the index qual and columns in the
  ORDER BY clause.

  -- get_actual_variable_endpoint() only performs visibility checks,
  so we don't need to fetch any columns (we have to pass an empty
  column projection bitmap)

- BitmapHeapScans can benefit from a column projection list the same
way as an IndexScan and SeqScan can. We can possibly pass down scanCols
in ExecInitBitmapHeapScan(). We would have to modify the BitmapHeapScan
table AM calls to take a column projection bitmap.

- There may be more callsites where we can pass a column projection list.

Regards,

Soumyadeep & Jacob

[0] https://www.postgresql.org/message-id/CAE-ML%2B-HwY4X4uTzBesLhOotHF7rUvP2Ur-rvEpqz2PUgK4K3g%40mail.gmail.com
[1]
https://www.postgresql.org/message-id/flat/CAAKRu_Yj%3DQ_ZxiGX%2BpgstNWMbUJApEJX-imvAEwryCk5SLUebg%40mail.gmail.com
[2]
https://www.postgresql.org/message-id/CAG4reAQc9vYdmQXh%3D1D789x8XJ%3DgEkV%2BE%2BfT9%2Bs9tOWDXX3L9Q%40mail.gmail.com
[3] https://www.postgresql.org/message-id/23194.1560618101%40sss.pgh.pa.us

Hi Soumyadeep,

On Sat, Nov 14, 2020 at 3:02 AM Soumyadeep Chakraborty
<soumyadeep2007@gmail.com> wrote:
>
> Hello,
>
> This patch introduces a set of changes to the table AM APIs, making them
> accept a column projection list. That helps columnar table AMs, so that
> they don't need to fetch all columns from disk, but only the ones
> actually needed.
>
> The set of changes in this patch is not exhaustive -
> there are many more opportunities that are discussed in the TODO section
> below. Before digging deeper, we want to elicit early feedback on the
> API changes and the column extraction logic.
>
> TableAM APIs that have been modified are:
>
> 1. Sequential scan APIs
> 2. Index scan APIs
> 3. API to lock and return a row
> 4. API to fetch a single row
>
> We have seen performance benefits in Zedstore for many of the optimized
> operations [0]. This patch is extracted from the larger patch shared in
> [0].
>
> ------------------------------------------------------------------------
> Building the column projection set:
>
> In terms of building the column projection set necessary for each of
> these APIs, this patch builds off of the scanCols patch [1], which
> Ashwin and Melanie had started earlier. As noted in [1], there are cases
> where the scanCols set is not representative of the columns to be
> projected. For instance, in a DELETE .. RETURNING query, there is
> typically a sequential scan and a separate invocation of
> tuple_fetch_row_version() in order to satisfy the RETURNING clause (see
> ExecDelete()). So for a query such as:
>
>   DELETE from foo WHERE i < 100 && j < 1000 RETURNING k, l;
>
> We need to pass the set (i, j) to the scan and (k, l) to the
> tuple_fetch_row_version() invocation. This is why we had to introduce
> the returningCols field.
>
> In the same spirit, separate column projection sets are computed for any
> operations that involve an EPQ check (INSERT, DELETE, UPDATE, row-level
> locking etc), the columns involved in an ON CONFLICT UPDATE etc.
>
> Recognizing and collecting these sets of columns is done at various
> stages: analyze and rewrite, planner and executor - depending on the
> type of operation for which the subset of columns is calculated. The
> column bitmaps are stored in different places as well - such as the ones
> for scans and RETURNING are stored in RangeTblEntry, whereas the set of
> columns for ON CONFLICT UPDATE are stored in OnConflictSetState.
>
> ------------------------------------------------------------------------
> Table AM API changes:
>
> The changes made to the table AM API, introducing the column projection
> set, come in different flavors. We would like feedback on what style
> we need to converge to or if we should use different styles depending
> on the situation.
>
> - A new function variant that takes a column projection list, such as:
>
>   TableScanDesc (*scan_begin) (Relation rel,
>     Snapshot snapshot,
>     int nkeys, struct ScanKeyData *key,
>     ParallelTableScanDesc pscan,
>     uint32 flags);
> ->
>
>   TableScanDesc (*scan_begin_with_column_projection)(Relation relation,
>      Snapshot snapshot,
>      int nkeys, struct ScanKeyData *key,
>      ParallelTableScanDesc parallel_scan,
>      uint32 flags,
>      Bitmapset *project_columns);
>
> - Modifying the existing function to take a column projection list, such
> as:
>
>   TM_Result (*tuple_lock) (Relation rel,
>      ItemPointer tid,
>      Snapshot snapshot,
>      TupleTableSlot *slot,
>      CommandId cid,
>      LockTupleMode mode,
>      LockWaitPolicy wait_policy,
>      uint8 flags,
>      TM_FailureData *tmfd);
>
> ->
>
>   TM_Result (*tuple_lock) (Relation rel,
>      ItemPointer tid,
>      Snapshot snapshot,
>      TupleTableSlot *slot,
>      CommandId cid,
>      LockTupleMode mode,
>      LockWaitPolicy wait_policy,
>      uint8 flags,
>      TM_FailureData *tmfd,
>      Bitmapset *project_cols);
>
> - A new function index_fetch_set_column_projection() to be called after
> index_beginscan() to set the column projection set, which will be used
> later by index_getnext_slot().
>
>   void (*index_fetch_set_column_projection) (struct IndexFetchTableData *data,
>      Bitmapset *project_columns);
>
> The set of columns expected by the new/modified functions is represented
> as a Bitmapset of attnums for a specific base relation. An empty/NULL
> bitmap signals to the AM that no data columns are needed. A bitmap
> containing the single element 0 indicates that we want all data columns
> to be fetched.
>
> The bitmaps do not include system columns.
>
> Additionally, the TupleTableSlots populated by functions such
> as table_scan_getnextslot(), need to be densely filled upto the highest
> numbered column in the projection list (any column not in the projection
> list should be populated with NULL). This is due to the implicit
> assumptions of the slot_get_***() APIs.
>
> ------------------------------------------------------------------------
> TODOs:
>
> - Explore opportunities to push the column extraction logic to the
> planner or pre-planner stages from the executor stage (like scanCols and
> returningCols), or at least elevate the column extraction logic to be
> done once per executor run instead of once per tuple.
>
> - As was requested in [1], we should guard column projection set
> extraction logic with a table_scans_leverage_column_projection() call.
> We wouldn't want a non-columnar AM to incur the overhead.
>
> - Standardize the table AM API for passing columns.
>
> - The optimization for DELETE RETURNING does not currently work for
> views. We have to populate the list of columns for the base relation
> beneath the view properly.
>
> - Currently the benefit of passing in an empty projection set for ON
> CONFLICT DO UPDATE (UPSERT) and ON CONFLICT DO NOTHING (see
> ExecCheckTIDVisible()) is masked by a preceding call to
> check_exclusion_or_unique_constraint() which has not yet been modified
> to pass a column projection list to the index scan.
>
> - Compute scanCols earlier than set_base_rel_sizes() and use that
> information to produce better relation size estimates (relation size
> will depend on the number of columns projected) in the planner.
> Essentially, we need to absorb the work done by Pengzhou [2].
>
> - Right now, we do not extract a set of columns for the call to
> table_tuple_lock() within GetTupleForTrigger() as it may be hard to
> determine the list of columns used in a trigger body [3].
>
> - validateForeignKeyConstraint() should only need to fetch the
> foreign key column.
>
> - List of index scan callsites that will benefit from calling
> index_fetch_set_column_projection():
>
>   -- table_index_fetch_tuple_check() does not need to fetch any
>   columns (we have to pass an empty column bitmap), fetching the tid
>   should be enough.
>
>   -- unique_key_recheck() performs a liveness check for which we do
>   not need to fetch any columns (we have to pass an empty column
>   bitmap)
>
>   -- check_exclusion_or_unique_constraint() needs to only fetch the
>   columns that are part of the exclusion or unique constraint.
>
>   -- IndexNextWithReorder() needs to only fetch columns being
>   projected along with columns in the index qual and columns in the
>   ORDER BY clause.
>
>   -- get_actual_variable_endpoint() only performs visibility checks,
>   so we don't need to fetch any columns (we have to pass an empty
>   column projection bitmap)
>
> - BitmapHeapScans can benefit from a column projection list the same
> way as an IndexScan and SeqScan can. We can possibly pass down scanCols
> in ExecInitBitmapHeapScan(). We would have to modify the BitmapHeapScan
> table AM calls to take a column projection bitmap.
>
> - There may be more callsites where we can pass a column projection list.
>

You sent in your patch to pgsql-hackers on Nov 14, but you did not
post it to the next CommitFest[1].  If this was intentional, then you
need to take no action.  However, if you want your patch to be
reviewed as part of the upcoming CommitFest, then you need to add it
yourself and may need to rebase the patch to the current HEAD before
2021-01-01 AOE[2]. Thanks for your contributions.

Regards,

[1] https://commitfest.postgresql.org/31/
[2] https://en.wikipedia.org/wiki/Anywhere_on_Earth


--
Masahiko Sawada
EnterpriseDB:  https://www.enterprisedb.com/

Hey Masahiko,

I added it to the Jan CF (https://commitfest.postgresql.org/31/2922/).

PFA a rebased version against latest head.

Regards,
Soumyadeep

On Tue, 2021-06-01 at 15:38 +0300, Aleksander Alekseev wrote:
> I came across this patch and noticed that it rotted a little,
> especially after removing inheritance_planner() in 86dc9005. I
> managed to resolve the conflicts on current `master` (eb89cb43), see
> the attached patch. The code compiles but doesn't pass the tests. I'm
> currently in the process of reviewing it and didn't figure out what
> the issue is yet. Just wanted to let you know.

Hi Alexsander, thanks!

In your patch's transformInsertStmt(), I see what I think is an
extraneous call to transformReturningList() right before the ON
CONFLICT processing. That call is already done later in the function,
during the RETURNING processing (this change came in with 6c0373ab77).
Other than that, your rebased patch looks the same as mine.

>  I also believe changing the patch status to "Waiting on Author"
> would be appropriate.

Agreed. I'm going to double-check with Deep that the new calls
to table_tuple_fetch_row_version() should be projecting the full row,
then post an updated patch some time next week.

Thanks again!
--Jacob

On Sat, 2021-06-05 at 09:47 -0700, Zhihong Yu wrote:
> On Fri, Jun 4, 2021 at 4:14 PM Jacob Champion <pchampion@vmware.com> wrote:
> > Agreed. I'm going to double-check with Deep that the new calls
> > to table_tuple_fetch_row_version() should be projecting the full row,
> > then post an updated patch some time next week.

(The discussions over the fallout of the inheritance_planner fallout
are still going, but in the meantime here's an updated v4 that builds
and passes `make check`.)

> +       return relation->rd_tableam->scan_begin_with_column_projection(relation, snapshot, 0, NULL,
> +                                           parallel_scan, flags, proj);
> 
> scan_begin_with_column_projection() adds a parameter to scan_begin().
> Can scan_begin() be enhanced with this projection parameter ?
> Otherwise in the future we may have scan_begin_with_column_projection_with_x_y ...

Maybe; I agree that would match the current "extension" APIs a little
better. I'll let Deep and/or Ashwin chime in on why this design was
chosen.

> +   /* Make sure the the new slot is not dependent on the original tuple */
> 
> Double 'the' in the comment. More than one place with duplicate 'the'
> in the patch.

Fixed.

> +typedef struct neededColumnContext
> +{
> +   Bitmapset **mask;
> +   int n;
> 
> Should field n be named ncol ? 'n' seems too general.

Agreed; changed to ncol.

> +        * TODO: Remove this hack!! This should be done once at the start of the tid scan.
> 
> Would the above be addressed in the next patch ?

I have not had time to get to this in v4, sorry.

> Toward the end of extract_scan_columns():
> 
> +                       bms_free(rte->scanCols);
> +                       rte->scanCols = bms_make_singleton(0);
> +                       break;
> 
> Should 'goto outer;' be in place of 'break;' (since rte->scanCols has
> been assigned for whole-row) ?

Agreed and fixed. Thank you!

--Jacob

Hi all,

Ashwin, Deep, and I were discussing this patch today. We agree that
it's fairly difficult to review in its current state, and the lack of a
concrete implementation of the new API isn't helping. (A big chunk of
the context for the patch exists in the zedstore megathread, which
isn't exactly light reading.)

We'd like to improve that, but with current time constraints, we won't
be able to get to it for the July commitfest. So I'll mark this patch
Withdrawn for now, to reduce the review load. (239 Needs Review and
counting!) We hope to revisit in the September timeframe.

Thanks for all the reviews and input!

--Jacob

On Thu, Jul 1, 2021 at 7:42 AM Jacob Champion <pchampion@vmware.com> wrote:
>
> Hi all,
>
> Ashwin, Deep, and I were discussing this patch today. We agree that
> it's fairly difficult to review in its current state, and the lack of a
> concrete implementation of the new API isn't helping. (A big chunk of
> the context for the patch exists in the zedstore megathread, which
> isn't exactly light reading.)
>
> We'd like to improve that, but with current time constraints, we won't
> be able to get to it for the July commitfest. So I'll mark this patch
> Withdrawn for now, to reduce the review load. (239 Needs Review and
> counting!) We hope to revisit in the September timeframe.
>
> Thanks for all the reviews and input!
>
> --Jacob

Since this thread is mentioned again, I want to share some thoughts on the lazy
material part[1].  If we go with that direction, we may not need the AM for pass
projection to heapam.  we just need something like AM like

Datum fetch_column_value_for_column(..,  rowid,  colid);

I worked in this direction with a small step and stopped quickly because of some
other reasons.  I would like to share my work so far here [2], However
lazy material
is not always good.

[1] https://stratos.seas.harvard.edu/files/stratos/files/columnstoresfntdbs.pdf
[2] https://github.com/zhihuiFan/postgres/tree/lazy_material_v2


-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

On Mon, Sep 05, 2022 at 05:38:51PM +0300, Nikita Malakhov wrote:
> Due to experiments with columnar data storage I've decided to revive this
> thread - Table AM modifications to accept column projection lists
> <https://www.postgresql.org/message-id/flat/CAE-ML+9RmTNzKCNTZPQf8O3b-UjHWGFbSoXpQa3Wvuc8YBbEQw@mail.gmail.com>
> 
> To remind:
> 
> This patch introduces a set of changes to the table AM APIs, making them
> accept a column projection list. That helps columnar table AMs, so that
> they don't need to fetch all columns from disk, but only the ones
> actually needed.
> 
> The set of changes in this patch is not exhaustive -
> there are many more opportunities that are discussed in the TODO section
> below. Before digging deeper, we want to elicit early feedback on the
> API changes and the column extraction logic.
> 
> TableAM APIs that have been modified are:
> 
> 1. Sequential scan APIs
> 2. Index scan APIs
> 3. API to lock and return a row
> 4. API to fetch a single row
> 
> We have seen performance benefits in Zedstore for many of the optimized
> operations [0]. This patch is extracted from the larger patch shared in
> [0].

What parts of the original patch were left out ?  This seems to be the
same size as the original.

With some special build options like -DWRITE_READ_PARSE_PLAN_TREES, this
currently fails with:

WARNING:  outfuncs/readfuncs failed to produce equal parse tree

There's poor code coverage in PopulateNeededColumnsForScan()
IndexNext(), check_default_partition_contents() and nodeSeqscan.c.
https://cirrus-ci.com/task/5516554904272896
https://api.cirrus-ci.com/v1/artifact/task/5516554904272896/coverage/coverage/00-index.html

Is it currently possible to hit those code paths in postgres ?  If not,
you may need to invent a minimal columnar extension to allow excercising
that.

Note that the cirrusci link is on top of my branch which runs "extended"
checks in cirrusci, but you can also run code coverage report locally
with --enable-coverage.

When you mail next, please run pgindent first (BTW there's a debian
package in PGDG for pgindent).

-- 
Justin