Avoiding rewrite in ALTER TABLE ALTER TYPE

ALTER TABLE ALTER TYPE always rewrites the table heap and its indexes. In some
cases, we can determine that doing so is unhelpful, and that the conversion
shall always succeed:

CREATE DOMAIN loosedom AS text;
CREATE TABLE t (c varchar(2));
ALTER TABLE t ALTER c TYPE varchar(4);
ALTER TABLE t ALTER c TYPE text;
ALTER TABLE t ALTER c TYPE loosedom;

In other cases, we can determine that the rewrite is unhelpful, but a cast could
still throw an error:

CREATE DOMAIN tightdom AS text CHECK (value LIKE '<%/>');
CREATE TABLE t (c text);
ALTER TABLE t ALTER c TYPE xml USING c::xml;
ALTER TABLE t ALTER c TYPE varchar(64);
ALTER TABLE t ALTER c TYPE tightdom;

I wish to replace table rewrites with table verification scans where possible,
then skip those verification scans where possible. I've noted three subproblems
that require distinct treatment. In the following discussion, "tuple" is the
tuple on disk, and "tuple'" is tuple we would form during a rewriting ALTER
TABLE ALTER TYPE. Likewise "col" and "col'" for individual columns.

1. The table heap rewrite itself

To legitimately leave the table heap intact, we must confirm datumIsEqual(col,
col') for every tuple and column. Without any specific configuration to suggest
when this might be true, we can always determine its truth through a
_verification scan_ of the table. If the datumIsEqual test fails for any tuple
during the verification scan, terminate the scan and proceed with a table
rewrite. When should we attempt the verification scan in the first place, as
opposed to proceeding directly to a rewrite? For some time, I thought it best
to automatically attempt it when the type change degenerates to a single binary
coercion. Cases like the text->xml and timestamp->timestamptz [timezone=UTC]
are more difficult to identify mechanically, so I supposed to let the user
identify them via a new keyword to ALTER TABLE ALTER TYPE. Having thought on it
more, though, it actually seems best to attempt the verification scan *every*
time. In most ineligible conversions, an inequality will appear very early, so
the scan is effectively O(1) in the negative case. A notable exception is
something like char(6)->varchar(6) in a table with a billion tuples having
length(col) = 6 and one with length(col) = 5. The verification scan might read
most of the table before finding the one tuple that forces a rewrite. That
isn't a particularly regular scenario in my experience, so the "just do the
right thing" aspect of preceding every potential rewrite with a verification
scan seems to win out.

Certain very popular type changes (see introduction) can be _exempt_ from the
verification scan: we can determine that they will always succeed. To capture
that, I propose extending CREATE CAST with the notion of an exemptor function:

CREATE CAST (source_type AS target_type)
{ WITH FUNCTION function_name (argument_type [, ...])
[ WITH EXEMPTOR function_name ] |
WITHOUT FUNCTION |
WITH INOUT }
[ AS ASSIGNMENT | AS IMPLICIT ]

The exemptor shall have this signature:

exemptor_func(
integer, -- source_typmod
integer -- dest_typmod
) RETURNS boolean

The exemptor shall return true iff datumIsEqual(x, x::target_type(dest_typmod))
for every x in source_type most recently coerced to source_type(source_typmod).
When the cast is WITHOUT FUNCTION (a binary coercion) and target_type lacks a
length coercion cast, the cast has an implicit exemption, and an exemptor is
superfluous: code can assume an exemptor that always returns true. Use of WITH
EXEMPTOR mainly makes sense alongside multi-arg WITH FUNCTION (should probably
raise an error upon other uses).

When ATPrepAlterColumnType determines that a transformation expression is merely
a series of casts (or perhaps some stronger condition), and every such cast has
an exemptor or implicit exemption, it will call those exemptors with the old and
new typmods. If the exemptors all return true and this continues to hold for
all other ALTER TYPE subcommands of this ALTER TABLE, we will skip the
verification scan and table rewrite.

I will add exemptors to length coercion casts of types other than "character"
and "bit", which are exempt only in the no-change case. The candidates that are
not pure length coercions, int8->bit and int4->bit, would not benefit.

2. CHECK constraints, index predicates, and expression indexes

CHECK constraints, index predicates, and indexed expressions can change behavior
without limitation when the types of columns they reference change. An exempt
typmod change alone will not affect them. While there are some other safe cases
("CHECK (length(col) = 2", over a varchar->text conversion), I don't have a
general framework in mind for identifying them. For now, an exempt change that
includes a type change, such as varchar(2)->text, will still require a
verification scan whenever a CHECK constraint, index predicate, or indexed
expression references the column. The verification scan will confirm that
datumIsEqual(expr(tuple), expr(tuple')) for all tuples and all affected
expressions. Are there any nice ways to detect a broader selection of the
expressions that do not require verification?

3. reindex when an operator class change crosses operator families

Having avoided a heap rewrite, we may still need to reindex indexes that just
received new operator classes. Consider a type "reverseint4" that stores just
like an int4, but its default btree operator class sorts opposite int4_ops.
Converting int4->reverseint4 would not touch the table heap, but we would need
to reindex any indexes on the changing column. I'm not aware of any affected
core data types (albeit not having investigated systematically), but we still
need to get this case right.

Conveniently, operator families cover exactly this notion of operator class
compatibility. When the old and new operator classes share an operator family,
we can skip the reindex without verification. This covers the primary case of
varchar/text, plus a bonus of timestamp<->timestamptz and inet<->cidr. Indexes
on expressions can use the same check; we will have verified the actual bits of
the computed expressions during the verification scan. Index predicates need no
special handling at this stage.

For changes having no operator family to vindicate them, we can just reindex.
Though we could introduce an index variant of the verification scan, confirming
that v_n::target_type <= v_n+1::target_type for all values, it seems relatively
unimportant: operator families cover the notable use cases nicely.

4. NOTE: other constraint types
UNIQUE, PRIMARY KEY and EXCLUDE constraints remain valid as the indexes
implementing them remain valid. This proposal does not affect foreign key
constraints.

I see this breaking down into various patches:
1. Add the verification scan to the vicinity of ATRewriteTable and skip the
table rewrite when it finds no changes. Full reindex remains.
2. In the no-rewrite case, narrow us from reindexing the entire table to merely
reindexing those indexes touched by the operator class changes.
3. Further skip reindex operations when the operator class has changed but the
operator family has not.
4. Modify ATPrepAlterColumnType to detect implicit exemptions, and modify
ATRewriteTable to skip the verification scan in light of those discoveries.
5. Add pg_cast.castexemptor and modify CREATE CAST to populate it. Define an
exemptor for the varchar length coercion cast. Modify ATPrepAlterColumnType to
use pg_cast.castexemptor and combine their outcomes with implicit exemptions.
6. Define exemptors for time, timetz, timestamp, timestamptz, and interval.
7. Define exemptor for bit varying.
8. Define exemptor for numeric.

These threads, referenced from the TODO entry concerning a subset of this plan,
were most helpful in revealing the scope of problems to address:
http://archives.postgresql.org/message-id/200903040137.n241bAUV035002@wwwmaster.postgresql.org
http://archives.postgresql.org/pgsql-patches/2006-10/msg00154.php

What have I missed? I welcome any corrections/unaddressed problems/questions.

Thanks,
nm