Segment Exclusion

Simon Riggs, 2ndQuadrant

Segment Exclusion is also known as Storage Indexes in Oracle and MinMax Indexes in Vectorwise, though both of those implementations come later than the first mention on Postgres hackers.

Recap: Very Large Table Use Case

Many large tables have a regular access pattern:

• new rows inserted frequently
• some updates and deletes on the "recent" data
• older data becomes effectively read-only
• at some point data may be removed in bulk from the table

Most tables vary on what "recent" means; some are insert only, many not. A typical example might be a large history table where the last 6 months data is updated, but after that the data has almost zero change.

Partitioning relies on knowledge of the physical location of data to exclude sections of data from a scan.

Currently the partitioning knowledge is provided by user declarations in the form of constraints on tables linked together by views or inheritance. We also currently do this in "constraint-first" fashion, i.e. we put the data where the constraints say we should, rather than deriving the constraints from the data.

In-table Partitioning

In the common use-case there is a clear affinity between certain data columns and the physical placement of data in a table. This is true for columns such as LOG_DATE or TRANSACTION_DATE, but is also true for any columns where the id column is assigned by a Sequence. HOT helps this to remain true over time.

Given the above use case, when there is an affinity between data values and data placement *and* we know that older data tends to become read only, we can then realise that certain physical sections of a table will become effectively read only. (My experience is that the larger the table, the less random the write pattern - whatever the guys that wrote TPC-C say).

If we were able to keep track of which sections of a table are now read-only then we would be able to record information about the data in that section and use it to help solve queries. This is turning the current thinking on its head: we could derive the constraints from the data, rather than placing the data according to the constraints. That would be much more natural: load data into the table and have the system work out the rest.

We can imagine that we do this within a single table. Imagine: split a table up into 100 sections, then record the min/max values of all tuples in those sections. When we perform a SeqScan we could skip over sections that could be proved would never satisfy the query predicate. Same thing as partitioning, but within the table.

Currently tables are already broken up into 1GB file segments, so it seems fairly natural to pick that as our section size. That fits reasonably well with recommendations for ideal partition size. It is also easy with this technique to provide variable sized sections, by using a storage parameter at table-level, like fillfactor.

Segment Exclusion

After we note that a segment is read-only we can scan the segment and record min/max values for all columns. These are then "implicit constraints", which can then be used for segment exclusion in a similar manner as we do with the current constraint exclusion mechanism.

The implicit constraints can then allow SeqScans to assess segment exclusion for each segment at execution time, i.e. a scan can skip a whole segment if constraints don't match. If a segment does not (yet) have implicit constraints it will always be scanned in full. This allows partitioning, synch scans and buffer recycling to work much better together than they currently do.

Other scans types might also use segment exclusion, though this would only be useful for scans retrieving many rows, otherwise the overhead of segment exclusion might not be worthwhile.

This would also allow a Merge Join to utilise exclusion for the inner plan at execution time. Instead of scanning the whole inner table plan from the start, we would be able to start the scan from the appropriate segment. (This would be for the first tuple from the inner table, not for every inner tuple). This would require us to pass the current value of the outer plan down into the inner plan. The typical executor nodes on the inner plan would be a SortNode and below that a SeqScan. In that case the executor would need to pass the outer value from the MergeJoinNode down thru the SortNode to the SeqScan node. The SeqScan node could then perform partition exclusion, reducing the time for that scan and also reducing the time for the resulting sort. This sounds like it might be worth doing in normal cases also. It might turn out that the potentially applicable cases are already excluded during planning, I haven't thought about that aspect in enough detail yet.

If we collect data for all columns then many of our implicit constraints would be useless. e.g. if a column only has a few values and these are present in all segments. Matching our predicate against all constraints would be expensive, so we must weed out poor constraints. We would do this by removing any constraint that overlapped more than 10% of other segments. Various heuristics would likely need to be discovered during development to make this work without resorting to manual commands.

Note that all of this exclusion is happening in the executor, not the planner. That allows this form of exclusion to work with stable functions and parameters without problem.

It would also be possible to exclude some types of value in the planner only, but this only works when the planner and executor are run at the same time.

One potential objection to this approach is that immutable functions and constants cannot be removed by the planner in a prepared query because the partition constraints are dynamic.

Noting which segments are read-only

Everything so far has relied upon our ability to note which segments of a table are read-only. We could do this in two ways

• 1) have the system automatically keep track of non-changing data
• 2) have the DBA issue a command to "mark" a segment as read-only now

Probably a combination of the two is better, so we have three states for segments

• READ_WRITE_ALLOWED
• EFFECTIVE_READ_ONLY (set by 1 only)
• MARKED_READ_ONLY (set by 2 only)

Having said that I want to concentrate on (1), though consider the other one also in case requested by reviewers.

Visibility Map

So *how* would we mark segments as read only? It turns out that attempting to do this is extremely similar to Heikki's Visibility Map idea, so I'll describe it in those terms, even though there are some differences. It also brings to mind Andrew Sullivan's read-only tuples concept.

We would keep a dynamic visibility map at *segment* level, showing which segments have all rows as 100% visible. No freespace map data would be held at this level.

Most everything about Heikki's Visibility Map idea holds, just that we have a bit for each segment in the table, rather than each block. The map is very small and hardly ever changes for a table, so we can cache it easily on each backend. If the map does change we can perform a relcache invalidation to make everybody re-read the map.

No dynamic shared memory cache is required because any concurrent changes to the table would be ignored by a Scan anyway, so it doesn't matter if an INSERT, UPDATE or DELETE occurs while we are scanning. Any new scans that start will attempt to lock the table and then perform a rel cache check before continuing. So the visibility will be set correctly for *that* scan at least.

In most cases the visibility map can be summarised as a single boolean to show whether any 100% visible segments exist. That makes accessing the map very cheap in the common, unset case.

The check to see if the rel cache has changed in essentially free, since we do it already when we grab a lock. The only case this isn't true for is when we attempt to lock a table that we have already locked in this transaction, since that is currently optimised away. In that case we would check the rel cache only for tables that had read only segments when we *first* accessed the map during the transaction. We will always have a map to allow us to make the check at this time, and we only need to re-check if we had values set. If segments go from read write to effective read only during our access we don't need to worry. So the overhead in the non-partitioned case is a single boolean test, whilst for partitioned tables we would need to re-access the cache for each statement against the table. That seems acceptable because we may use the visibility information to increase performance considerably in many cases.

Setting the Visibility Map

We need another intermediate state in the VM to cope with concurrent changes while we are setting the map, called this READ_ONLY_PENDING.

VACUUM would scan all READ_WRITE_ALLOWED segments and mark some of them as READ_ONLY_PENDING if 100% of the remaining rows that it has seen are visible to all current backends. Marking the map will cause a rel cache invalidation.

We would then re-scan newly marked segments to derive min/max values for implicit constraints, performed by autovacuum worker processes. If we see a change made by a transaction after the xmin of the VACUUM, then we will abort this scan and reset the map to READ_WRITE_ALLOWED. This allows us to capture concurrent changes behind the first VACUUM scan.

Changes to the table after the first VACUUM but behind the scan point of the second scan will see the READ_ONLY_PENDING state and clear it back to READ_WRITE_ALLOWED.

If the second scan of a READ_ONLY_PENDING segment does not find any new changes then it can successfully update the map to EFFECTIVE_READ_ONLY.

We would never mark the highest numbered segment EFFECTIVE_READ_ONLY, since it is likely to expand when INSERTs occur. This is also a useful way of excluding smaller tables from the overheads involved for this feature.

In an insert-only table this would mean that only the last 1 or 2 segments would be read write, so VACUUM would always run in a bounded time, no matter how large the table.

When would we attempt to set the visibility map? If we do this aggressively, then it will be quickly unset. If we wait too long then we might lose some of the benefits of this approach.

First, we recognise that read only segments will change the autovacuum calculation - we simply exclude them entirely. This will mean that VACUUMs are run more regularly than they are now, but when they do run they will be quicker. (Note that currently, VACUUMs on a growing table get further and further apart as the table grows, assuming constant write rate).

My feeling is that VACUUMs are sufficiently infrequent that we should set the visibility map aggressively after each VACUUM. If the map is quickly unset, then we wait some time before trying again. Unsetting seems to be relatively low contention (see below), so that seems acceptable.

So setting and unsetting of the visibility map makes this partitioning approach "volatile" and would not be able to be relied upon to provide performance if the update pattern were inconsistent.

We would then re-scan newly marked segments to derive min/max values for implicit constraints, performed by autovacuum worker processes. The best way seems to be that an ANALYZE command would automatically detect that a segment has been recently set EFFECTIVE_READ_ONLY and perform an all-rows scan rather than just a sample. (We would keep min/max values only for datatypes with valid btree sort operators, just as ANALYZE already does).

A later VACUUM will still be required to freeze the rows, though that can happen later when we hit the frozen limit, or earlier if we run an explicit VACUUM FREEZE. We would need to store the oldest xid for each segment, so we know when to kick off a FREEZE on that part of the table.

This departs completely from the idea that the visibility map and the freespace map are related somehow. However, there is a change required in the FSM to ensure the proposed technique is stable and useful: If we scan a segment and it is 100% visible, if there is freespace in just one of the blocks in the segment then we will soon find that our visibility-bit will be set to off again very quickly.

If there is more than 5% freespace total in the segment then we will not set EFFECTIVE_READ_ONLY, nor report blocks in a segment to the FSM. That way, small amounts of freespace won't destroy the benefits of segment exclusion. VACUUM currently overwrites FSM information, though if this was not the case then we would have to actively remove it for the newly read only segments. Perhaps that limit would be (100 - fillfactor)%, which is normally set according to a user's expectation of the number of updates likely on a table.

Storing the visibility map

The visibility map is small enough to be cached on each backend, but it could still be challenging to store it on pg_class if we have more than about 20 segments.

There are three items that need to be stored

• the visibility map - segment status flags
• relfrozenxids for each segment
• segment boundary values
• segment aggregates (e.g. number of tuples in that segment)

None of these items will be stored in pg_class, to avoid bloat.

The visibility map needs to store these states for each segment

• 0x01 READ_WRITE_ALLOWED or EFFECTIVE_READ_ONLY
• 0x02 PENDING_READ_ONLY
• 0x04 MARKED_READ_ONLY
• 0x08 spare status flag

So we need to store 4 bits per segment

The relfrozenxids need 4 bytes per segment. We will also store relfrozenxid for each table on pg_class, which is the minimum value of any segment. This is mainly examined by autovacuum to see when to initiate vac freezes.

Segment boundary values would be stored within the stats tables, as part of the histogram values. This would allow them to be used as histograms for use in planning. (XXX needs more thought as to storage - we want the planner to use the values as stats, but we also want to make it easy to access them, plus we don't want ANALYZE to overwrite them)

Segment aggregates could be stored also. reltuples would require an array of integers.

Unsetting the visibility map

For EFFECTIVE_READ_ONLY, INSERTs, UPDATEs and DELETEs are still possible. For MARKED_READ_ONLY it would be explicitly refused.

The relcache invalidation caused by making a segment EFFECTIVE_READ_ONLY can flush the rd_targBlock for the relation in each backend. Other INSERTs are not possible since all current code-paths either use extension or the FSM when the table is non-empty, and neither of those will cause a problem. Extension only touches last segment, which will never by EFFECTIVE_READ_ONLY. The FSM contains no entries for an EFFECTIVE_READ_ONLY segment.

UPDATEs or DELETEs are possible on EFFECTIVE_READ_ONLY segments, but we don't expect it often. If this occurs, we will simply reset the visibility map for the table. This can be handled with a non-transactional overwrite - the bit always exists already, so the overwritten data is always same size. That's pessimistic, since it resets the state even if the UPDATE/DELETE aborts, but its better than holding the row locked until the transaction completes, which might prevent other things from happening. We probably also want VACUUM to clear up any aborted transactions anyway.

The user may also wish to clear down very old data, so allowing DELETEs can ensure the user can still remove old data from the table. By carefully choosing the values to be deleted, a whole segment can be deleted and then returned to the FSM.

Running a huge DELETE will likely perform a SeqScan that avoids all but the deleting data. The following VACUUM will also ignore the other segments, so removing older data seems fairly well optimised already, in comparison with now. It would be possible to optimise this to perform a segment-level truncate, but since the partitioning will already improve the DELETE and VACUUM, I'm not proposing that yet, if ever.

SHARE locks currently write to data blocks, but since they represent transient state we do not need to unset either the partitioning or the visibility map.

Utilities

It would be possible and probably desirable to have a segment-aware CLUSTER. That would require us to use another flag in the visibility map to indicate clustered, unclustered. It also requires us to rebuild sections of indexes that refer to the clusters, which will require full table locks. An on-line version of CLUSTER would be required to make this work sensibly.

Overlap with Visibility Map Proposal

This proposal offers many of the advantages of the earlier Visibility Map proposal, yet without major changes to heap structure. Since the segment-level visibility map is more granular it would only be 80% as effective as the more detailed block-level map. Having said that, the bookkeeping overheads will also be considerably reduced, so it does seem a good joint approach. It also allows freezing to be handled fully, which was a problem with the original visibility map proposal. WAL logging visibility map changes is also now much easier.

My thoughts have been targeted directly at partitioning, yet I have to admit that this idea overlaps, and in my world view, replaces the Visibility Map proposal. I very much like the name Visibility Map though. I've re-read the earlier thread and agree with Jeff Davis that we *could* have multiple kinds of visibility map, but also agree with Heikki that it seems like too much work. It was never my intent to address both challenges in one proposal and this is just pure coincidence, or possibly just luck, depending upon how you like the proposal.

If we do need to differentiate between the two proposals, we can refer to this one as the Segment Visibility Map (SVM).

Index Scans

Index-only scans would look at the Visibility Map, just as they would have done in the earlier proposal.

It would be costly for an index scan to repeatedly check the visibility map, but probably worth it to do so.

Other Changes

We can handle select count(*) by scanning the non-100% visible segments of a table, then adding the stored counts for each segment to get a final total. Not sure if its really worth doing, but it does sound like an added bonus.

There would be additional complexity in selectivity estimation and plan costing. The above proposal allows dynamic segment exclusion, which cannot be assessed at planning time anyway, so suggestions welcome...

I think it would be prudent to have an override option on VACUUM to allow us to scan a table in full, checking rather than using the visibility map. This mode would be called VACUUM CHECK.

None of the above blocks earlier proposals for read only tables, and the two features could work together very straightforwardly.

Comparison with other Partitioning approaches

Once I realised this was possible in fairly automatic way, I've tried hard to keep away from manual overrides, commands and new DDL.

Declarative partitioning is a big overhead, though worth it for large databases. No overhead is *much* better though.

This approach to partitioning solves the following challenges

• allows automated table extension, so works automatically with Slony
• responds dynamically to changing data
• allows stable functions, nested loop joins and parametrised queries
• allows RI via SHARE locks
• avoids the need for operator push-down through Append nodes
• allows unique indexes
• allows both global indexes (because we only have one table)
• allows advanced planning/execution using read-only/visible data
• works naturally with synchronous scans and buffer recycling

All of the above are going to take considerably longer to do in any of the other ways I've come up with so far...

And yes, this is a different conclusion to earlier discussions, particularly those in 2005 where I was still thinking in terms of declarative partitioning.

Testing whether this would work for your app

It's probably worth examining existing applications to see how well they would migrate to segmented tables approach. The following query will analyse one column of a table to produce a list of boundary values, given a segment size of 131072 blocks (1 GB).

select substr(ctid::text,2,strpos(ctid::text,',')-2)::integer/131072 as seg, min(PrimaryKey), max(PrimaryKey) from bigtable group by seg;

We should be able to see whether this works for existing use cases, or not fairly easily.

You can change the segment size, but I would expect the practical limit of the number of partitions to be 10-20,000 with a maximum realistic size of 2-5,000 partitions. So change segment size, but not too small on large tables.

Note that the segment size can be changed, but it will take a complete VACUUM of the table to reset the implicit constraints. (We could optimize that also, but don't hold your breath).

Conclusions

General objective is to allow us to manage data more easily above 10TB

This technique would be useful for any table with historical data keyed by date or timestamp. It would also be useful for data where a time-of-insert component is implicit, such as many major entity tables where the object ids are assigned by a sequence. e.g. an Orders table with an OrderId as PK. Once all orders placed in a period have been shipped/resolved/closed then the segments will be marked read-only.

Its not really going to change the code path much for small tables, yet seems likely to work reasonably well for large tables of all shapes and sizes. If a segment is being updated, we leave it alone, and maybe never actually set the visibility map at all. So overall, this idea seems to cover the main use case well, yet with only minimal impact on the existing use cases we support.