Hi, This is a preliminary proposal for Minmax indexes. I'm experimenting with the code, but it's too crude to post yet, so here's a document explaining what they are and how they work, so that reviewers can poke holes to have the design improved. My intention is to have a patch to show for CF2, so please do have a look at this and comment.
This is part of the AXLE project http://www.axleproject.eu and the intention is to support tables of very large size. In a quick experiment, I have a table of ~12 GB and its corresponding index is 65 kB in size, making the time to do the equivalent of a seqscan a small fraction of that taken by a real seqscan. This technique sits between a bitmap scan of a normal btree, and a seqscan: the minmax index tells the bitmap heap scan what pages to seqscan, allowing it to skip a large fraction of pages that are known not to contain tuples matching the query quals. This is a huge win for large data warehouses. Without further ado, here's what I propose. Minmax Range Indexes ==================== Minmax indexes are a new access method intended to enable very fast scanning of extremely large tables. The essential idea of a minmax index is to keep track of the min() and max() values in consecutive groups of heap pages (page ranges). These values can be used by constraint exclusion to avoid scanning such pages, depending on query quals. The main drawback of this is having to update the stored min/max values of each page range as tuples are inserted into them. Other database systems already have this feature. Some examples: * Oracle Exadata calls this "storage indexes" http://richardfoote.wordpress.com/category/storage-indexes/ * Netezza has "zone maps" http://nztips.com/2010/11/netezza-integer-join-keys/ * Infobright has this automatically within their "data packs" http://www.infobright.org/Blog/Entry/organizing_data_and_more_about_rough_data_contest/ * MonetDB seems to have it http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.2662 "Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS" Grammar ------- To create a minmax index, we use CREATE INDEX foo_minmax_idx ON foo USING MINMAX (a, b, e); Partial indexes are not supported; since an index is concerned with minimum and maximum values of the involved columns across all the pages in the table, it doesn't make sense to exclude values. Another way to see "partial" indexes here would be those that only considered some pages in the table instead of all of them; but this would be difficult to implement and manage and, most likely, pointless. Expressional indexes can probably be supported in the future, but we disallow them initially for conceptual simplicity. Having multiple minmax indexes in the same table is acceptable, though most of the time it would make more sense to have a single index covering all the interesting columns. Multiple indexes might be useful for columns added later. Access Method Design -------------------- Since item pointers are not stored inside indexes of this type, it is not possible to support the amgettuple interface. Instead, we only provide amgetbitmap support; scanning a relation using this index requires a recheck node on top. The amgetbitmap routine would return a TIDBitmap comprising all the pages in those page groups that comply with the query quals; the recheck node prunes tuples that are not visible per snapshot and those that are not visible per query quals. For each supported datatype, we need an opclass with the following catalog entries: - support functions (pg_amproc) * pg_proc entry for min() * pg_proc entry for max() - support operators (pg_amop): same as btree (<, <=, =, >=, >) The min() and max() support functions are used during index construction. The support operators are used in the optimizer, so that the index is chosen when queries on the indexed table are planned. (Also, we use them in the amgetbitmap routine, to compare ScanKeys and decide whether to emit a certain block or not). In each index tuple (corresponding to one page range), we store: - first block this tuple applies to - last block this tuple applies to - for each indexed column: * min() value across all tuples in the range * max() value across all tuples in the range * nulls present in any tuple? With the default INDEX_MAX_KEYS of 32, and considering columns of 8-byte length types (timestamptz, bigint), each tuple would be 524 bytes in length, which seems reasonable. Of course, larger columns are possible, such as varchar, but creating minmax indexes on such columns seems of little practical usefulness. This maximum index tuple size is calculated as: BlockNumber (4 bytes) * 2 + data value (8 bytes) * 32 * 2 + null bitmap (4 bytes) Block ranges mentioned in index entries shouldn't overlap. However, there can be gaps where some pages have no covering index entry. (In particular, the last few pages of the table would commonly not be summarized.) In order to scan a table, a sequential scan of the index is done; for each tuple for which the range limits (min/max) are proven to be required to be scanned by the ScanKeys, we obtain the block range covered by that tuple, and return a lossy TIDBitmap of pages in the page range; any unsummarized pages and invalid page ranges (see below) must also be returned. Note that we store pg_proc entries for aggregate functions. It is the responsibility of the access method to obtain the pg_aggregate rows starting from the pg_proc rows; we avoid the parser code that deals with aggregates, because the mechanism it uses to resolve from parser to executor starts from aggregate names; this is not useful for our purposes. Also, running the aggregate is not done through the executor support for aggregates either, because that code is very specialized to running inside a node with a child node feeding tuples, which IndexBuildHeapScan cannot do. Instead, the AM is in charge of initializing state and running the transition functions for each new tuple read by the index-build heap scan. Data changes in the heap ------------------------ Value changes in columns that are part of a minmax index, and tuple insertion in summarized pages, would invalidate the stored min/max values. To support this, each minmax index has a validity map; a range can only be considered in a scan if it hasn't been invalidated by such changes (A range "not considered" in the scan needs to be returned in whole regardless of the stored min/max values, that is, it cannot be pruned per query quals). The validity map is very similar to the visibility map in terms of performance characteristics: quick enough that it's not contentious, allowing updates and insertions to proceed even when data values violate the minmax index conditions. An invalidated range can be made valid by re-summarization (see below). Re-summarization is relatively expensive, because the complete page range has to be scanned. To avoid this, a table having a minmax index would be configured so that inserts only go to the page(s) at the end of the table; this avoids frequent invalidation of ranges in the middle of the table. We provide a table reloption that tweaks the FSM behavior, so that summarized pages are not candidates for insertion. A possible optimization is that whenever an update does not modify the values covered by minmax indexes, or whenever the value changes are not outside the min()/max() interval for the corresponding page range, the page range does not need to be marked invalid. This is particularly useful when considering same-page updates (i.e. updates which find enough empty space in the same page that the new tuple fits in it), and HOT (which frees space used by previous updates). This suggests we ought to recommend lower-than-100 fillfactor values to permit these features to kick in. When tuples are added to unsummarized pages, nothing needs to happen to the index. Tuples can be removed from anywhere without restriction. See below for more on vacuuming. Summarization ------------- At index creation time, the whole table is scanned; for each page range the min() and max() values and nulls bitmap are collected, and stored in the index. The possibly-incomplete range at the end of the table is also included. Once in a while, it is necessary to summarize a bunch of unsummarized pages (because the table has grown since the index was created), or re-summarize a range that has been marked invalid. This is simple: scan the page range calculating the min() and max() for each indexed column, then insert the new index entry at the end of the index. The main interesting questions are: a) when to do it The perfect time to do it is as soon as a complete page range of the configured range size has been filled (assuming page ranges are constant size). b) who does it (what process) It doesn't seem a good idea to have a client-connected process do it; it would incur unwanted latency. Three other options are (i) to spawn a specialized process to do it, which perhaps can be signalled by a client-connected process that executes a scan and notices the need to run summarization; or (ii) to let autovacuum do it, as a separate new maintenance task. This seems simple enough to bolt on top of already existing autovacuum infrastructure. The timing constraints of autovacuum might be undesirable, though. (iii) wait for user command. The easiest way to go around this seems to have vacuum do it. That way we can simply do re-summarization on the amvacuumcleanup routine. Other answers would mean we need a separate AM routine, which appears unwarranted at this stage. Vacuuming --------- Vacuuming a table that has a minmax index does not represent a significant challenge. Since no CTIDs are stored, it's not necessary to scan the index when heap tuples are removed. It might be that some min() value can be incremented, or some max() value can be decremented; but this would represent an optimization opportunity only, not a correctness issue. Perhaps it's simpler to represent this as the need to re-run summarization on the affected page range. Note that if there are no indexes on the table other than the minmax index, usage of maintenance_work_mem by vacuum can be decreased significantly, because no detailed index scan needs to take place (and thus it's not necessary for vacuum to save TIDs to remove). This optimization opportunity is best left for future improvement. Optimizer --------- In order to make this all work, the only thing we need to do is ensure we have a good enough opclass and amcostestimate. With this, the optimizer is able to pick up the index on its own. Open questions -------------- * Same-size page ranges? Current related literature seems to consider that each "index entry" in a minmax index must cover the same number of pages. There doesn't seem to be a hard reason for this to be so; it might make sense to allow the index to self-tune so that some index entries cover smaller page ranges, if this allows the min()/max() values to be more compact. This would incur larger space overhead for the index itself, but might allow better pruning of page ranges during scan. In the limit of one index tuple per page, the index itself would occupy too much space, even though we would be able to skip reading the most heap pages, because the min()/max() ranges are tight; in the opposite limit of a single tuple that summarizes the whole table, we wouldn't be able to prune anything from the seqscan even though the index is very small. * More compact representation for TIDBitmap? TIDBitmap is the structure currently used to represent bitmap scans. The representation of lossy page ranges is not optimal for our purposes, because it uses a Bitmapset to represent pages in the range; since we're going to return all pages in a large range, it might be more convenient to allow for a struct that instead uses start and end page numbers to represent the range. This is mentioned in passing in tidbitmap.c comments, so perhaps the time has come for its implementation. (In experimentation, tidbitmap has no trouble with ranges of a thousand pages.) References: Email thread on pgsql-hackers http://www.postgresql.org/message-id/1199296574.7260.149.ca...@ebony.site From: Simon Riggs To: pgsql-hackers Subject: Dynamic Partitioning using Segment Visibility Map http://wiki.postgresql.org/wiki/Segment_Exclusion http://wiki.postgresql.org/wiki/Segment_Visibility_Map -- Álvaro Herrera http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
