Proposal: Global Index

A global index by very definition is a single index on the parent table that maps to many

underlying table partitions. The parent table itself does not have any underlying storage,

so it must, therefore, retrieve the data satisfying index constraints from the underlying tables.

In very crude terms, it is an accumulation of data from table partitions so that data spanning

across multiple partitions are accessed in one go as opposed to individually querying each

partition.

For the initial version of this work, we are only considering to build b-tree global indexes.

- Partitioned Index (Index Partitioning)

When global indexes become too large, then those are partitioned to keep the performance

and maintenance overhead manageable. These are not within the scope of this work.


- Local Index
A local index is an index that is local to a specific table partition; i.e. it doesn’t span across

multiple partitions. So, when we create an index on a parent table, it will create a separate

index for all its partitions. Unfortunately, PostgreSQL uses the terminology of “partitioned index”

when it refers to local indexes. This work with fix this terminology for PostgreSQL so that the

nomenclature remains consistent with other DBMS.


- Why We Need Global Index?
A global index is expected to give two very important upgrades to the partitioning feature set in

PostgreSQL. It is expected to give a significant improvement in read-performance for queries

targeting multiple local indexes of partitions. It also adds a unique constraint across partitions.


- Unique Constraint
Data uniqueness is a critical requirement for building an index. For global indexes that span across

multiple partitions, uniqueness will have to be enforced on index column(s). This effectively translates

into a unique constraint.


- Performance
Currently, the pseudo index created on the parent table of partitions does not contain any

data. Rather, it dereferences to the local indexes when an index search is required. This

means that multiple indexes will have to be evaluated and data to be combined thereafter.

However, with the global indexes, data will reside with global index declared on the parent

table. This avoids the need for multi-level index lookups. So read performance is expected

to be significantly higher in cases. There will however be a negative performance impact

during write (insert/update) of data. This is discussed in more detail later on.


- Creating a GLOBAL Index - Syntax
A global index may be created with the addition of a “GLOBAL” keyword to the index statement.

Alternatively, one could specify the “LOCAL” keyword to create local indexes on partitions.

We are suggesting to call this set of keywords: “partition_index_type”. By default,

partition_index_type will be set as LOCAL. Here is a sample of the create index syntax.

CREATE Index idx parent (columns) [GLOBAL | LOCAL];

Note: There is no shift/reduced by adding these options.


- Pointing Index to Tuple
Currently, CTID carries a page and offset information for a known heap (table name). However,

in the context of global indexes, this information within an index is insufficient. Since the index is

expected to carry tuples from multiple partitions (heaps), CTID alone will not be able to link an index

node to a tuple. This requires carrying additional data for the heap name to be stored with each

index node.

How this should be implemented is a point to be discussed. A few possibilities are listed below:

-- Expand CTID to include a relfilenode id. In PostgreSQL-Conf Asia, Bruce suggested having the OID

instead of relfilenode as relfilenode can be duplicated across tablespaces.
      -- Using OID introduces another complication where we would need to query catalog for OID to

         heap mapping.

-- The second option is to have a variable-length CTID. We can reserve some top-level bit for segregation of

Global CTID or Standard CTID. Robert Haas suggested in PostgreSQL-EU to discuss this with Peter Geoghegan.
      -- I discussed it with Peter and he believes that it is a very invasive approach that requires a whole lot of

         the effort to get committed.

-- Heikki pointed me to include heap specific information using the INCLUDE keyword so that heap information

is stored with each index node as data.
      -- We (Peter and I) also discussed that option and this looks a more easy and non-invasive option.

- Optimizer
The challenge with optimizer is a selection between local and global indexes when both are present.

How do we: 

-- Evaluate the cost of scanning a global index?
-- When should the LOCAL index be preferred over the GLOBAL index and vice versa?
        -- Should we hit a GLOBAL index when the query is targeting a couple of partitions only?
        -- We need to consider the sizes of those partitions being hit and the sizes of partitions not being hit.
-- Bruce suggested that we prioritize a GLOBAL index in the first version so that in every case,

the GLOBAL index is utilized.


- Write Performance and Vacuum
There will be some write performance degradation because every change in partition tables must

propagate upwards to the GLOBAL index on the parent table. This can be thought of as another index

on a table, however, the [slight] performance degradation will be due to the fact that the GLOBAL

index may carry a much bigger dataset with data from multiple partitions resulting in a higher tree

traversal and update time. This applies to both write and vacuum processes.

It is still an open question though on how this will be handled within the code and how we can better

optimize this process.

I have a POC patch and working on finalizing the patch, Hamid Akhtar is also working with me on this

work.



--
Ibrar Ahmed