# ADD COLUMN Optimization For Appendonly, Row-Oriented Tables

## Background

Since [PostgreSQL 11](https://www.postgresql.org/docs/11/sql-altertable.html#:~:text=the%20default%20is%20evaluated%20at%20the%20time%20of%20the%20statement), the `ALTER TABLE ... ADD COLUMN` command does not require table rewrite anymore (there's also some implication about whether the default value is NULL or not, but let's ignore that for now). The optimization basically just records the default value for the new column in catalog, and use it when the *attribute is missing* in the tuple.

However, currently in Greenplum, the appendonly tables have some limitation that makes it unable to enjoy the upstream feature. But among the AO-row and AO-column tables, the latter has its own optimization which is to write only the new columns in `ADD COLUMN`, so we are not too concerned with AO-column tables.

Here's the situation of what's being written for Heap vs. AO-row vs. AO-column in Greenplum can be shown in this table:

| | Heap | AO-Row | AO-Column |
| --- | -------- | -------- | -------- |
| GPDB 6 | <span style="color:orange">**Rewrite table**</span> | <span style="color:orange">**Rewrite table**</span> | Write new column |
| GPDB 7 | Write nothing | <span style="color:red">**Rewrite table**</span> | Write new column |

<span style="color:red">The AO-Row table in 7X is what we want to focus on now.</span>
<span style="color:orange">The Heap and AO-Row tables in 6X are cases that we will think about when working on 7X.</span>

The main factor that hinders the optimization is that we don't have **on-disk knowledge about the number of attributes** stored in the AO relation file. As a result, when we read the data, we do not know *how many attributes are missing* in the memtuple, so we could not fill the missing attributes. Therefore, currently AO table always rewrite the whole table for `ADD COLUMN`. So, there's never missing attribute on disk so we never need to worry about filling them up.

## Design choices
Now let's see what's needed to support the optimization for ao-row table.
### Data format change?
We tried to [think about](https://github.com/greenplum-db/gpdb/issues/14929#issuecomment-1456790059) an approach which doesn't require AO data format change, but ultimately it seems that format change is nonetheless needed. And adding the number of attributes stored on disk is most realistic way to achieve our goal.

### Where to add on-disk number of attributes:
We need to decide where exactly do we add the on-disk number of attributes:
1. Memtuple:
The most straightforward way is to let memtuple carry the number of attributes itself. It will be easy to reason about and possibly easier to implement. There's also a good thing that since 7X memtuple is [only used within AO table](https://github.com/greenplum-db/gpdb/issues/14929#issuecomment-1508985949) so the impact is localized.
2. Varblock:
A varblock **cannot** have mixed number of attributes: when a varblock is inserted, it uses the current attribute descriptor of the table to form the tuples, and that cannot change during insert. So we can also add the number of on-disk attributes knowledge to a varblock header. But we will need to figure out how to use that knowledge when we actually read the tuple (though currently I see no big issue rather than just modify a few function APIs in order to pass that knowledge from/to the memtuple layer).

### Supporting old data format
If we do not consider existing database clusters, everything is simple: we implement the optimization and we're done. But we have to consider existing data format for at least two reasons:
* Support the same feature for 6X.
* Support upgrade from 6X->7X.

Therefore, we have to be able to recognize the old data format, read them correctly and transform them into the new format when appropriate. Let's talk about the design choices for that.

#### How to recognize the old format
A version string is the most straightforward way. But where to put it depends on the anwser of the next question.

#### How to transform the old format to new
1. Table-level transform
We rewrite the whole table to use the new format. So a table can either be in old or new format, but not a mix. The table rewrite can be done by the first command that requires it. But until then, new inserted data into the table are still in old format.
2. Tuple- or varblock-level transform:
This is a more seamless way for user experience: any new memtuple/varblock, either being inserted individually, or by table rewrite, will carry the number of attributes. The old memtuple/varblock will not carry it and we won't make an explicit effort to update it until it is updated/deleted by user queries.

#### Where to put the format version
Now let's see where can we put the format version:
1. No addition, just use `formatversion` of the aoseg/aocsseg catalog of the table:
If we choose the table-level transform, we don't need to add a format version number but can just use the existing version information for the table. And the `formatversion` of the aoseg/aocsseg catalog is better than the `version` of pg_appendonly because the [latter doesn't exist in 6X](https://github.com/greenplum-db/gpdb/pull/15063).
2. Memtuple header:
If we choose a more granular way of transform, we have to add a on-disk format version. The first choice is memtuple header. A memtuple has a 32-bit header space to store various info. Currently all of the bits are occupied, but we have plenty of [seemingly unused ones](https://github.com/greenplum-db/gpdb/issues/14929#issuecomment-1508671986) to recycle. We just need one bit to differentiate the "old vs. new". But a question arises: what if we want to make more changes to memtuple in the future? We could take the chance and extend the header to include a format version from now on.
2. Varblock header:
There are four types of varblock and all have a 64-bit header space (`AOSmallContentHeader`, `AOLargeContentHeader`, `AONonBulkDenseContentHeader`, `AOBulkDenseContentHeader`). They all have different number of unused bits. It might make more sense to add the version to the universal header portion `AOHeader` - which requires us to extend that portion as well.

Note that this design choice is independent of the choice to add on-disk number of attributes. For example if we add number of attributes to varblock, we can still add the version to memtuple, and vice versa.