Implement table partitioning.

Table partitioning is like table inheritance and reuses much of the
existing infrastructure, but there are some important differences.
The parent is called a partitioned table and is always empty; it may
not have indexes or non-inherited constraints, since those make no
sense for a relation with no data of its own.  The children are called
partitions and contain all of the actual data.  Each partition has an
implicit partitioning constraint.  Multiple inheritance is not
allowed, and partitioning and inheritance can't be mixed.  Partitions
can't have extra columns and may not allow nulls unless the parent
does.  Tuples inserted into the parent are automatically routed to the
correct partition, so tuple-routing ON INSERT triggers are not needed.
Tuple routing isn't yet supported for partitions which are foreign
tables, and it doesn't handle updates that cross partition boundaries.

Currently, tables can be range-partitioned or list-partitioned.  List
partitioning is limited to a single column, but range partitioning can
involve multiple columns.  A partitioning "column" can be an
expression.

Because table partitioning is less general than table inheritance, it
is hoped that it will be easier to reason about properties of
partitions, and therefore that this will serve as a better foundation
for a variety of possible optimizations, including query planner
optimizations.  The tuple routing based which this patch does based on
the implicit partitioning constraints is an example of this, but it
seems likely that many other useful optimizations are also possible.

Amit Langote, reviewed and tested by Robert Haas, Ashutosh Bapat,
Amit Kapila, Rajkumar Raghuwanshi, Corey Huinker, Jaime Casanova,
Rushabh Lathia, Erik Rijkers, among others.  Minor revisions by me.

1 files changed, 413 insertions, 0 deletions

diff --git a/src/test/regress/expected/create_table.out b/src/test/regress/expected/create_table.out
index 41ceb874e8..b40a18aec2 100644
--- a/src/test/regress/expected/create_table.out
+++ b/src/test/regress/expected/create_table.out
@@ -253,3 +253,416 @@ DROP TABLE as_select1;
 -- check that the oid column is added before the primary key is checked
 CREATE TABLE oid_pk (f1 INT, PRIMARY KEY(oid)) WITH OIDS;
 DROP TABLE oid_pk;
+--
+-- Partitioned tables
+--
+-- cannot combine INHERITS and PARTITION BY (although grammar allows)
+CREATE TABLE partitioned (
+	a int
+) INHERITS (some_table) PARTITION BY LIST (a);
+ERROR:  cannot create partitioned table as inheritance child
+-- cannot use more than 1 column as partition key for list partitioned table
+CREATE TABLE partitioned (
+	a1 int,
+	a2 int
+) PARTITION BY LIST (a1, a2);	-- fail
+ERROR:  cannot list partition using more than one column
+-- unsupported constraint type for partitioned tables
+CREATE TABLE partitioned (
+	a int PRIMARY KEY
+) PARTITION BY RANGE (a);
+ERROR:  primary key constraints are not supported on partitioned tables
+LINE 2:  a int PRIMARY KEY
+               ^
+CREATE TABLE pkrel (
+	a int PRIMARY KEY
+);
+CREATE TABLE partitioned (
+	a int REFERENCES pkrel(a)
+) PARTITION BY RANGE (a);
+ERROR:  foreign key constraints are not supported on partitioned tables
+LINE 2:  a int REFERENCES pkrel(a)
+               ^
+DROP TABLE pkrel;
+CREATE TABLE partitioned (
+	a int UNIQUE
+) PARTITION BY RANGE (a);
+ERROR:  unique constraints are not supported on partitioned tables
+LINE 2:  a int UNIQUE
+               ^
+CREATE TABLE partitioned (
+	a int,
+	EXCLUDE USING gist (a WITH &&)
+) PARTITION BY RANGE (a);
+ERROR:  exclusion constraints are not supported on partitioned tables
+LINE 3:  EXCLUDE USING gist (a WITH &&)
+         ^
+-- prevent column from being used twice in the partition key
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (a, a);
+ERROR:  column "a" appears more than once in partition key
+-- prevent using prohibited expressions in the key
+CREATE FUNCTION retset (a int) RETURNS SETOF int AS $$ SELECT 1; $$ LANGUAGE SQL IMMUTABLE;
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (retset(a));
+ERROR:  set-returning functions are not allowed in partition key expression
+DROP FUNCTION retset(int);
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE ((avg(a)));
+ERROR:  aggregate functions are not allowed in partition key expression
+CREATE TABLE partitioned (
+	a int,
+	b int
+) PARTITION BY RANGE ((avg(a) OVER (PARTITION BY b)));
+ERROR:  window functions are not allowed in partition key expression
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY LIST ((a LIKE (SELECT 1)));
+ERROR:  cannot use subquery in partition key expression
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (('a'));
+ERROR:  cannot use constant expression as partition key
+CREATE FUNCTION const_func () RETURNS int AS $$ SELECT 1; $$ LANGUAGE SQL IMMUTABLE;
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (const_func());
+ERROR:  cannot use constant expression as partition key
+DROP FUNCTION const_func();
+-- only accept "list" and "range" as partitioning strategy
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY HASH (a);
+ERROR:  unrecognized partitioning strategy "hash"
+-- specified column must be present in the table
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (b);
+ERROR:  column "b" named in partition key does not exist
+-- cannot use system columns in partition key
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (xmin);
+ERROR:  cannot use system column "xmin" in partition key
+-- functions in key must be immutable
+CREATE FUNCTION immut_func (a int) RETURNS int AS $$ SELECT a + random()::int; $$ LANGUAGE SQL;
+CREATE TABLE partitioned (
+	a int
+) PARTITION BY RANGE (immut_func(a));
+ERROR:  functions in partition key expression must be marked IMMUTABLE
+DROP FUNCTION immut_func(int);
+-- cannot contain whole-row references
+CREATE TABLE partitioned (
+	a	int
+) PARTITION BY RANGE ((partitioned));
+ERROR:  partition key expressions cannot contain whole-row references
+-- prevent using columns of unsupported types in key (type must have a btree operator class)
+CREATE TABLE partitioned (
+	a point
+) PARTITION BY LIST (a);
+ERROR:  data type point has no default btree operator class
+HINT:  You must specify a btree operator class or define a default btree operator class for the data type.
+CREATE TABLE partitioned (
+	a point
+) PARTITION BY LIST (a point_ops);
+ERROR:  operator class "point_ops" does not exist for access method "btree"
+CREATE TABLE partitioned (
+	a point
+) PARTITION BY RANGE (a);
+ERROR:  data type point has no default btree operator class
+HINT:  You must specify a btree operator class or define a default btree operator class for the data type.
+CREATE TABLE partitioned (
+	a point
+) PARTITION BY RANGE (a point_ops);
+ERROR:  operator class "point_ops" does not exist for access method "btree"
+-- cannot add NO INHERIT constraints to partitioned tables
+CREATE TABLE partitioned (
+	a int,
+	CONSTRAINT check_a CHECK (a > 0) NO INHERIT
+) PARTITION BY RANGE (a);
+ERROR:  cannot add NO INHERIT constraint to partitioned table "partitioned"
+-- some checks after successful creation of a partitioned table
+CREATE FUNCTION plusone(a int) RETURNS INT AS $$ SELECT a+1; $$ LANGUAGE SQL;
+CREATE TABLE partitioned (
+	a int,
+	b int,
+	c text,
+	d text
+) PARTITION BY RANGE (a oid_ops, plusone(b), c collate "default", d collate "en_US");
+-- check relkind
+SELECT relkind FROM pg_class WHERE relname = 'partitioned';
+ relkind 
+---------
+ P
+(1 row)
+
+-- check that range partition key columns are marked NOT NULL
+SELECT attname, attnotnull FROM pg_attribute WHERE attrelid = 'partitioned'::regclass AND attnum > 0;
+ attname | attnotnull 
+---------+------------
+ a       | t
+ b       | f
+ c       | t
+ d       | t
+(4 rows)
+
+-- prevent a function referenced in partition key from being dropped
+DROP FUNCTION plusone(int);
+ERROR:  cannot drop function plusone(integer) because other objects depend on it
+DETAIL:  table partitioned depends on function plusone(integer)
+HINT:  Use DROP ... CASCADE to drop the dependent objects too.
+-- partitioned table cannot partiticipate in regular inheritance
+CREATE TABLE partitioned2 (
+	a int
+) PARTITION BY LIST ((a+1));
+CREATE TABLE fail () INHERITS (partitioned2);
+ERROR:  cannot inherit from partitioned table "partitioned2"
+-- Partition key in describe output
+\d partitioned
+            Table "public.partitioned"
+ Column |  Type   | Collation | Nullable | Default 
+--------+---------+-----------+----------+---------
+ a      | integer |           | not null | 
+ b      | integer |           |          | 
+ c      | text    |           | not null | 
+ d      | text    |           | not null | 
+Partition key: RANGE (a oid_ops, plusone(b), c, d COLLATE "en_US")
+
+\d partitioned2
+            Table "public.partitioned2"
+ Column |  Type   | Collation | Nullable | Default 
+--------+---------+-----------+----------+---------
+ a      | integer |           |          | 
+Partition key: LIST ((a + 1))
+
+DROP TABLE partitioned, partitioned2;
+--
+-- Partitions
+--
+-- check partition bound syntax
+CREATE TABLE list_parted (
+	a int
+) PARTITION BY LIST (a);
+-- syntax allows only string literal, numeric literal and null to be
+-- specified for a partition bound value
+CREATE TABLE part_1 PARTITION OF list_parted FOR VALUES IN ('1');
+CREATE TABLE part_2 PARTITION OF list_parted FOR VALUES IN (2);
+CREATE TABLE part_null PARTITION OF list_parted FOR VALUES IN (null);
+CREATE TABLE fail_part PARTITION OF list_parted FOR VALUES IN (int '1');
+ERROR:  syntax error at or near "int"
+LINE 1: ... fail_part PARTITION OF list_parted FOR VALUES IN (int '1');
+                                                              ^
+CREATE TABLE fail_part PARTITION OF list_parted FOR VALUES IN ('1'::int);
+ERROR:  syntax error at or near "::"
+LINE 1: ...fail_part PARTITION OF list_parted FOR VALUES IN ('1'::int);
+                                                                ^
+-- syntax does not allow empty list of values for list partitions
+CREATE TABLE fail_part PARTITION OF list_parted FOR VALUES IN ();
+ERROR:  syntax error at or near ")"
+LINE 1: ...E TABLE fail_part PARTITION OF list_parted FOR VALUES IN ();
+                                                                     ^
+-- trying to specify range for list partitioned table
+CREATE TABLE fail_part PARTITION OF list_parted FOR VALUES FROM (1) TO (2);
+ERROR:  invalid bound specification for a list partition
+LINE 1: ...BLE fail_part PARTITION OF list_parted FOR VALUES FROM (1) T...
+                                                             ^
+-- specified literal can't be cast to the partition column data type
+CREATE TABLE bools (
+	a bool
+) PARTITION BY LIST (a);
+CREATE TABLE bools_true PARTITION OF bools FOR VALUES IN (1);
+ERROR:  specified value cannot be cast to type "boolean" of column "a"
+LINE 1: ...REATE TABLE bools_true PARTITION OF bools FOR VALUES IN (1);
+                                                                    ^
+DROP TABLE bools;
+CREATE TABLE range_parted (
+	a date
+) PARTITION BY RANGE (a);
+-- trying to specify list for range partitioned table
+CREATE TABLE fail_part PARTITION OF range_parted FOR VALUES IN ('a');
+ERROR:  invalid bound specification for a range partition
+LINE 1: ...BLE fail_part PARTITION OF range_parted FOR VALUES IN ('a');
+                                                              ^
+-- each of start and end bounds must have same number of values as the
+-- length of the partition key
+CREATE TABLE fail_part PARTITION OF range_parted FOR VALUES FROM ('a', 1) TO ('z');
+ERROR:  FROM must specify exactly one value per partitioning column
+CREATE TABLE fail_part PARTITION OF range_parted FOR VALUES FROM ('a') TO ('z', 1);
+ERROR:  TO must specify exactly one value per partitioning column
+-- cannot specify null values in range bounds
+CREATE TABLE fail_part PARTITION OF range_parted FOR VALUES FROM (null) TO (unbounded);
+ERROR:  cannot specify NULL in range bound
+-- check if compatible with the specified parent
+-- cannot create as partition of a non-partitioned table
+CREATE TABLE unparted (
+	a int
+);
+CREATE TABLE fail_part PARTITION OF unparted FOR VALUES IN ('a');
+ERROR:  "unparted" is not partitioned
+DROP TABLE unparted;
+-- cannot create a permanent rel as partition of a temp rel
+CREATE TEMP TABLE temp_parted (
+	a int
+) PARTITION BY LIST (a);
+CREATE TABLE fail_part PARTITION OF temp_parted FOR VALUES IN ('a');
+ERROR:  cannot create a permanent relation as partition of temporary relation "temp_parted"
+DROP TABLE temp_parted;
+-- cannot create a table with oids as partition of table without oids
+CREATE TABLE no_oids_parted (
+	a int
+) PARTITION BY RANGE (a) WITHOUT OIDS;
+CREATE TABLE fail_part PARTITION OF no_oids_parted FOR VALUES FROM (1) TO (10 )WITH OIDS;
+ERROR:  cannot create table with OIDs as partition of table without OIDs
+DROP TABLE no_oids_parted;
+-- likewise, the reverse if also true
+CREATE TABLE oids_parted (
+	a int
+) PARTITION BY RANGE (a) WITH OIDS;
+CREATE TABLE fail_part PARTITION OF oids_parted FOR VALUES FROM (1) TO (10 ) WITHOUT OIDS;
+ERROR:  cannot create table without OIDs as partition of table with OIDs
+DROP TABLE oids_parted;
+-- check for partition bound overlap and other invalid specifications
+CREATE TABLE list_parted2 (
+	a varchar
+) PARTITION BY LIST (a);
+CREATE TABLE part_null_z PARTITION OF list_parted2 FOR VALUES IN (null, 'z');
+CREATE TABLE part_ab PARTITION OF list_parted2 FOR VALUES IN ('a', 'b');
+CREATE TABLE fail_part PARTITION OF list_parted2 FOR VALUES IN (null);
+ERROR:  partition "fail_part" would overlap partition "part_null_z"
+CREATE TABLE fail_part PARTITION OF list_parted2 FOR VALUES IN ('b', 'c');
+ERROR:  partition "fail_part" would overlap partition "part_ab"
+CREATE TABLE range_parted2 (
+	a int
+) PARTITION BY RANGE (a);
+-- trying to create range partition with empty range
+CREATE TABLE fail_part PARTITION OF range_parted2 FOR VALUES FROM (1) TO (0);
+ERROR:  cannot create range partition with empty range
+-- note that the range '[1, 1)' has no elements
+CREATE TABLE fail_part PARTITION OF range_parted2 FOR VALUES FROM (1) TO (1);
+ERROR:  cannot create range partition with empty range
+CREATE TABLE part0 PARTITION OF range_parted2 FOR VALUES FROM (unbounded) TO (1);
+CREATE TABLE fail_part PARTITION OF range_parted2 FOR VALUES FROM (unbounded) TO (2);
+ERROR:  partition "fail_part" would overlap partition "part0"
+CREATE TABLE part1 PARTITION OF range_parted2 FOR VALUES FROM (1) TO (10);
+CREATE TABLE fail_part PARTITION OF range_parted2 FOR VALUES FROM (9) TO (unbounded);
+ERROR:  partition "fail_part" would overlap partition "part1"
+-- now check for multi-column range partition key
+CREATE TABLE range_parted3 (
+	a int,
+	b int
+) PARTITION BY RANGE (a, (b+1));
+CREATE TABLE part00 PARTITION OF range_parted3 FOR VALUES FROM (0, unbounded) TO (0, unbounded);
+CREATE TABLE fail_part PARTITION OF range_parted3 FOR VALUES FROM (0, unbounded) TO (0, 1);
+ERROR:  partition "fail_part" would overlap partition "part00"
+CREATE TABLE part10 PARTITION OF range_parted3 FOR VALUES FROM (1, unbounded) TO (1, 1);
+CREATE TABLE part11 PARTITION OF range_parted3 FOR VALUES FROM (1, 1) TO (1, 10);
+CREATE TABLE part12 PARTITION OF range_parted3 FOR VALUES FROM (1, 10) TO (1, unbounded);
+CREATE TABLE fail_part PARTITION OF range_parted3 FOR VALUES FROM (1, 10) TO (1, 20);
+ERROR:  partition "fail_part" would overlap partition "part12"
+-- cannot create a partition that says column b is allowed to range
+-- from -infinity to +infinity, while there exist partitions that have
+-- more specific ranges
+CREATE TABLE fail_part PARTITION OF range_parted3 FOR VALUES FROM (1, unbounded) TO (1, unbounded);
+ERROR:  partition "fail_part" would overlap partition "part10"
+-- check schema propagation from parent
+CREATE TABLE parted (
+	a text,
+	b int NOT NULL DEFAULT 0,
+	CONSTRAINT check_a CHECK (length(a) > 0)
+) PARTITION BY LIST (a);
+CREATE TABLE part_a PARTITION OF parted FOR VALUES IN ('a');
+-- only inherited attributes (never local ones)
+SELECT attname, attislocal, attinhcount FROM pg_attribute WHERE attrelid = 'part_a'::regclass and attnum > 0;
+ attname | attislocal | attinhcount 
+---------+------------+-------------
+ a       | f          |           1
+ b       | f          |           1
+(2 rows)
+
+-- able to specify column default, column constraint, and table constraint
+CREATE TABLE part_b PARTITION OF parted (
+	b NOT NULL DEFAULT 1 CHECK (b >= 0),
+	CONSTRAINT check_a CHECK (length(a) > 0)
+) FOR VALUES IN ('b');
+NOTICE:  merging constraint "check_a" with inherited definition
+-- conislocal should be false for any merged constraints
+SELECT conislocal, coninhcount FROM pg_constraint WHERE conrelid = 'part_b'::regclass AND conname = 'check_a';
+ conislocal | coninhcount 
+------------+-------------
+ f          |           1
+(1 row)
+
+-- specify PARTITION BY for a partition
+CREATE TABLE fail_part_col_not_found PARTITION OF parted FOR VALUES IN ('c') PARTITION BY RANGE (c);
+ERROR:  column "c" named in partition key does not exist
+CREATE TABLE part_c PARTITION OF parted FOR VALUES IN ('c') PARTITION BY RANGE ((b));
+-- create a level-2 partition
+CREATE TABLE part_c_1_10 PARTITION OF part_c FOR VALUES FROM (1) TO (10);
+-- Partition bound in describe output
+\d part_b
+               Table "public.part_b"
+ Column |  Type   | Collation | Nullable | Default 
+--------+---------+-----------+----------+---------
+ a      | text    |           |          | 
+ b      | integer |           | not null | 1
+Partition of: parted FOR VALUES IN ('b')
+Check constraints:
+    "check_a" CHECK (length(a) > 0)
+    "part_b_b_check" CHECK (b >= 0)
+
+-- Both partition bound and partition key in describe output
+\d part_c
+               Table "public.part_c"
+ Column |  Type   | Collation | Nullable | Default 
+--------+---------+-----------+----------+---------
+ a      | text    |           |          | 
+ b      | integer |           | not null | 0
+Partition of: parted FOR VALUES IN ('c')
+Partition key: RANGE (b)
+Check constraints:
+    "check_a" CHECK (length(a) > 0)
+Number of partitions: 1 (Use \d+ to list them.)
+
+-- Show partition count in the parent's describe output
+-- Tempted to include \d+ output listing partitions with bound info but
+-- output could vary depending on the order in which partition oids are
+-- returned.
+\d parted
+               Table "public.parted"
+ Column |  Type   | Collation | Nullable | Default 
+--------+---------+-----------+----------+---------
+ a      | text    |           |          | 
+ b      | integer |           | not null | 0
+Partition key: LIST (a)
+Check constraints:
+    "check_a" CHECK (length(a) > 0)
+Number of partitions: 3 (Use \d+ to list them.)
+
+-- partitions cannot be dropped directly
+DROP TABLE part_a;
+-- need to specify CASCADE to drop partitions along with the parent
+DROP TABLE parted;
+ERROR:  cannot drop table parted because other objects depend on it
+DETAIL:  table part_b depends on table parted
+table part_c depends on table parted
+table part_c_1_10 depends on table part_c
+HINT:  Use DROP ... CASCADE to drop the dependent objects too.
+DROP TABLE parted, list_parted, range_parted, list_parted2, range_parted2, range_parted3 CASCADE;
+NOTICE:  drop cascades to 14 other objects
+DETAIL:  drop cascades to table part00
+drop cascades to table part10
+drop cascades to table part11
+drop cascades to table part12
+drop cascades to table part0
+drop cascades to table part1
+drop cascades to table part_null_z
+drop cascades to table part_ab
+drop cascades to table part_1
+drop cascades to table part_2
+drop cascades to table part_null
+drop cascades to table part_b
+drop cascades to table part_c
+drop cascades to table part_c_1_10