From dd7a8f66ed278eef2f001a98e2312336c61ee527 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 25 Jul 2015 14:39:00 -0400 Subject: Redesign tablesample method API, and do extensive code review. The original implementation of TABLESAMPLE modeled the tablesample method API on index access methods, which wasn't a good choice because, without specialized DDL commands, there's no way to build an extension that can implement a TSM. (Raw inserts into system catalogs are not an acceptable thing to do, because we can't undo them during DROP EXTENSION, nor will pg_upgrade behave sanely.) Instead adopt an API more like procedural language handlers or foreign data wrappers, wherein the only SQL-level support object needed is a single handler function identified by having a special return type. This lets us get rid of the supporting catalog altogether, so that no custom DDL support is needed for the feature. Adjust the API so that it can support non-constant tablesample arguments (the original coding assumed we could evaluate the argument expressions at ExecInitSampleScan time, which is undesirable even if it weren't outright unsafe), and discourage sampling methods from looking at invisible tuples. Make sure that the BERNOULLI and SYSTEM methods are genuinely repeatable within and across queries, as required by the SQL standard, and deal more honestly with methods that can't support that requirement. Make a full code-review pass over the tablesample additions, and fix assorted bugs, omissions, infelicities, and cosmetic issues (such as failure to put the added code stanzas in a consistent ordering). Improve EXPLAIN's output of tablesample plans, too. Back-patch to 9.5 so that we don't have to support the original API in production. --- doc/src/sgml/catalogs.sgml | 120 ------------- doc/src/sgml/datatype.sgml | 11 +- doc/src/sgml/postgres.sgml | 2 +- doc/src/sgml/ref/select.sgml | 126 +++++++------- doc/src/sgml/tablesample-method.sgml | 322 ++++++++++++++++++++++++++--------- doc/src/sgml/tsm-system-rows.sgml | 39 +++-- doc/src/sgml/tsm-system-time.sgml | 42 +++-- 7 files changed, 374 insertions(+), 288 deletions(-) (limited to 'doc/src') diff --git a/doc/src/sgml/catalogs.sgml b/doc/src/sgml/catalogs.sgml index 2c2190f13d3..9096ee5d517 100644 --- a/doc/src/sgml/catalogs.sgml +++ b/doc/src/sgml/catalogs.sgml @@ -278,11 +278,6 @@ planner statistics - - pg_tablesample_method - table sampling methods - - pg_tablespace tablespaces within this database cluster @@ -6132,121 +6127,6 @@ - - <structname>pg_tabesample_method</structname> - - - pg_am - - - - The catalog pg_tablesample_method stores - information about table sampling methods which can be used in - TABLESAMPLE clause of a SELECT - statement. - - - - <structname>pg_tablesample_method</> Columns - - - - - Name - Type - References - Description - - - - - - oid - oid - - Row identifier (hidden attribute; must be explicitly selected) - - - - tsmname - name - - Name of the sampling method - - - - tsmseqscan - bool - - If true, the sampling method scans the whole table sequentially. - - - - - tsmpagemode - bool - - If true, the sampling method always reads the pages completely. - - - - - tsminit - regproc - pg_proc.oid - Initialize the sampling scan function - - - - tsmnextblock - regproc - pg_proc.oid - Get next block number function - - - - tsmnexttuple - regproc - pg_proc.oid - Get next tuple offset function - - - - tsmexaminetuple - regproc - pg_proc.oid - Function which examines the tuple contents and decides if to - return it, or zero if none - - - - tsmend - regproc - pg_proc.oid - End the sampling scan function - - - - tsmreset - regproc - pg_proc.oid - Restart the state of sampling scan function - - - - tsmcost - regproc - pg_proc.oid - Costing function - - - - -
- - - - <structname>pg_tablespace</structname> diff --git a/doc/src/sgml/datatype.sgml b/doc/src/sgml/datatype.sgml index 8e13555a3aa..8113ddf8179 100644 --- a/doc/src/sgml/datatype.sgml +++ b/doc/src/sgml/datatype.sgml @@ -4346,7 +4346,7 @@ SET xmloption TO { DOCUMENT | CONTENT }; an object identifier. There are also several alias types for oid: regproc, regprocedure, regoper, regoperator, regclass, - regtype, regrole, regnamespace, + regtype, regrole, regnamespace, regconfig, and regdictionary. shows an overview. @@ -4622,6 +4622,10 @@ SELECT * FROM pg_attribute fdw_handler + + tsm_handler + + cstring @@ -4716,6 +4720,11 @@ SELECT * FROM pg_attribute A foreign-data wrapper handler is declared to return fdw_handler. + + tsm_handler + A tablesample method handler is declared to return tsm_handler. + + record Identifies a function returning an unspecified row type. diff --git a/doc/src/sgml/postgres.sgml b/doc/src/sgml/postgres.sgml index d1703e9c01f..7e82cdc3b12 100644 --- a/doc/src/sgml/postgres.sgml +++ b/doc/src/sgml/postgres.sgml @@ -243,6 +243,7 @@ &nls; &plhandler; &fdwhandler; + &tablesample-method; &custom-scan; &geqo; &indexam; @@ -250,7 +251,6 @@ &spgist; &gin; &brin; - &tablesample-method; &storage; &bki; &planstats; diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index 632d7935cb4..44810f4909c 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -49,7 +49,8 @@ SELECT [ ALL | DISTINCT [ ON ( expressionwhere from_item can be one of: - [ ONLY ] table_name [ * ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ] [ TABLESAMPLE sampling_method ( argument [, ...] ) [ REPEATABLE ( seed ) ] ] + [ ONLY ] table_name [ * ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ] + [ TABLESAMPLE sampling_method ( argument [, ...] ) [ REPEATABLE ( seed ) ] ] [ LATERAL ] ( select ) [ AS ] alias [ ( column_alias [, ...] ) ] with_query_name [ [ AS ] alias [ ( column_alias [, ...] ) ] ] [ LATERAL ] function_name ( [ argument [, ...] ] ) @@ -325,50 +326,6 @@ TABLE [ ONLY ] table_name [ * ] - - TABLESAMPLE sampling_method ( argument [, ...] ) [ REPEATABLE ( seed ) ] - - - Table sample clause after - table_name indicates that - a sampling_method should - be used to retrieve subset of rows in the table. - The sampling_method can be - any sampling method installed in the database. There are currently two - sampling methods available in the standard - PostgreSQL distribution: - - - SYSTEM - - - BERNOULLI - - - Both of these sampling methods currently accept only single argument - which is the percent (floating point from 0 to 100) of the rows to - be returned. - The SYSTEM sampling method does block level - sampling with each block having the same chance of being selected and - returns all rows from each selected block. - The BERNOULLI scans whole table and returns - individual rows with equal probability. Additional sampling methods - may be installed in the database via extensions. - - - The optional parameter REPEATABLE uses the seed - parameter, which can be a number or expression producing a number, as - a random seed for sampling. Note that subsequent commands may return - different results even if same REPEATABLE clause was - specified. This happens because DML statements and - maintenance operations such as VACUUM may affect physical - distribution of data. The setseed() function will not - affect the sampling result when the REPEATABLE - parameter is used. - - - - alias @@ -387,6 +344,61 @@ TABLE [ ONLY ] table_name [ * ] + + TABLESAMPLE sampling_method ( argument [, ...] ) [ REPEATABLE ( seed ) ] + + + A TABLESAMPLE clause after + a table_name indicates that the + specified sampling_method + should be used to retrieve a subset of the rows in that table. + This sampling precedes the application of any other filters such + as WHERE clauses. + The standard PostgreSQL distribution + includes two sampling methods, BERNOULLI + and SYSTEM, and other sampling methods can be + installed in the database via extensions. + + + + The BERNOULLI and SYSTEM sampling methods + each accept a single argument + which is the fraction of the table to sample, expressed as a + percentage between 0 and 100. This argument can be + any real-valued expression. (Other sampling methods might + accept more or different arguments.) These two methods each return + a randomly-chosen sample of the table that will contain + approximately the specified percentage of the table's rows. + The BERNOULLI method scans the whole table and + selects or ignores individual rows independently with the specified + probability. + The SYSTEM method does block-level sampling with + each block having the specified chance of being selected; all rows + in each selected block are returned. + The SYSTEM method is significantly faster than + the BERNOULLI method when small sampling + percentages are specified, but it may return a less-random sample of + the table as a result of clustering effects. + + + + The optional REPEATABLE clause specifies + a seed number or expression to use + for generating random numbers within the sampling method. The seed + value can be any non-null floating-point value. Two queries that + specify the same seed and argument + values will select the same sample of the table, if the table has + not been changed meanwhile. But different seed values will usually + produce different samples. + If REPEATABLE is not given then a new random + sample is selected for each query. + Note that some add-on sampling methods do not + accept REPEATABLE, and will always produce new + samples on each use. + + + + select @@ -1870,6 +1882,16 @@ SELECT distributors.* WHERE distributors.name = 'Westward'; + + <literal>TABLESAMPLE</literal> Clause Restrictions + + + The TABLESAMPLE clause is currently accepted only on + regular tables and materialized views. According to the SQL standard + it should be possible to apply it to any FROM item. + + + Function Calls in <literal>FROM</literal> @@ -1993,19 +2015,5 @@ SELECT distributors.* WHERE distributors.name = 'Westward'; - - <literal>TABLESAMPLE</literal> clause - - - The TABLESAMPLE clause is currently accepted only on physical - relations and materialized views. - - - - Additional modules allow you to install custom sampling methods and use - them instead of the SQL standard methods. - - - diff --git a/doc/src/sgml/tablesample-method.sgml b/doc/src/sgml/tablesample-method.sgml index 48eb7fe84ea..22f8bbe19aa 100644 --- a/doc/src/sgml/tablesample-method.sgml +++ b/doc/src/sgml/tablesample-method.sgml @@ -1,139 +1,301 @@ - Writing A TABLESAMPLE Sampling Method + Writing A Table Sampling Method - tablesample method + table sampling method + + + + TABLESAMPLE method - The TABLESAMPLE clause implementation in - PostgreSQL supports creating a custom sampling methods. - These methods control what sample of the table will be returned when the - TABLESAMPLE clause is used. + PostgreSQL's implementation of the TABLESAMPLE + clause supports custom table sampling methods, in addition to + the BERNOULLI and SYSTEM methods that are required + by the SQL standard. The sampling method determines which rows of the + table will be selected when the TABLESAMPLE clause is used. - - Tablesample Method Functions + + At the SQL level, a table sampling method is represented by a single SQL + function, typically implemented in C, having the signature + +method_name(internal) RETURNS tsm_handler + + The name of the function is the same method name appearing in the + TABLESAMPLE clause. The internal argument is a dummy + (always having value zero) that simply serves to prevent this function from + being called directly from a SQL command. + The result of the function must be a palloc'd struct of + type TsmRoutine, which contains pointers to support functions for + the sampling method. These support functions are plain C functions and + are not visible or callable at the SQL level. The support functions are + described in . + + + + In addition to function pointers, the TsmRoutine struct must + provide these additional fields: + + + + + List *parameterTypes + + + This is an OID list containing the data type OIDs of the parameter(s) + that will be accepted by the TABLESAMPLE clause when this + sampling method is used. For example, for the built-in methods, this + list contains a single item with value FLOAT4OID, which + represents the sampling percentage. Custom sampling methods can have + more or different parameters. + + + + + + bool repeatable_across_queries + + + If true, the sampling method can deliver identical samples + across successive queries, if the same parameters + and REPEATABLE seed value are supplied each time and the + table contents have not changed. When this is false, + the REPEATABLE clause is not accepted for use with the + sampling method. + + + + + + bool repeatable_across_scans + + + If true, the sampling method can deliver identical samples + across successive scans in the same query (assuming unchanging + parameters, seed value, and snapshot). + When this is false, the planner will not select plans that + would require scanning the sampled table more than once, since that + might result in inconsistent query output. + + + + + + + The TsmRoutine struct type is declared + in src/include/access/tsmapi.h, which see for additional + details. + + + + The table sampling methods included in the standard distribution are good + references when trying to write your own. Look into + the src/backend/access/tablesample subdirectory of the source + tree for the built-in sampling methods, and into the contrib + subdirectory for add-on methods. + + + + Sampling Method Support Functions - The tablesample method must provide following set of functions: + The TSM handler function returns a palloc'd TsmRoutine struct + containing pointers to the support functions described below. Most of + the functions are required, but some are optional, and those pointers can + be NULL. void -tsm_init (TableSampleDesc *desc, - uint32 seed, ...); +SampleScanGetSampleSize (PlannerInfo *root, + RelOptInfo *baserel, + List *paramexprs, + BlockNumber *pages, + double *tuples); - Initialize the tablesample scan. The function is called at the beginning - of each relation scan. + + This function is called during planning. It must estimate the number of + relation pages that will be read during a sample scan, and the number of + tuples that will be selected by the scan. (For example, these might be + determined by estimating the sampling fraction, and then multiplying + the baserel->pages and baserel->tuples + numbers by that, being sure to round the results to integral values.) + The paramexprs list holds the expression(s) that are + parameters to the TABLESAMPLE clause. It is recommended to + use estimate_expression_value() to try to reduce these + expressions to constants, if their values are needed for estimation + purposes; but the function must provide size estimates even if they cannot + be reduced, and it should not fail even if the values appear invalid + (remember that they're only estimates of what the run-time values will be). + The pages and tuples parameters are outputs. + - Note that the first two parameters are required but you can specify - additional parameters which then will be used by the TABLESAMPLE - clause to determine the required user input in the query itself. - This means that if your function will specify additional float4 parameter - named percent, the user will have to call the tablesample method with - expression which evaluates (or can be coerced) to float4. - For example this definition: -tsm_init (TableSampleDesc *desc, - uint32 seed, float4 pct); - -Will lead to SQL call like this: - -... TABLESAMPLE yourmethod(0.5) ... +void +InitSampleScan (SampleScanState *node, + int eflags); + + Initialize for execution of a SampleScan plan node. + This is called during executor startup. + It should perform any initialization needed before processing can start. + The SampleScanState node has already been created, but + its tsm_state field is NULL. + The InitSampleScan function can palloc whatever internal + state data is needed by the sampling method, and store a pointer to + it in node->tsm_state. + Information about the table to scan is accessible through other fields + of the SampleScanState node (but note that the + node->ss.ss_currentScanDesc scan descriptor is not set + up yet). + eflags contains flag bits describing the executor's + operating mode for this plan node. - -BlockNumber -tsm_nextblock (TableSampleDesc *desc); - - Returns the block number of next page to be scanned. InvalidBlockNumber - should be returned if the sampling has reached end of the relation. + When (eflags & EXEC_FLAG_EXPLAIN_ONLY) is true, + the scan will not actually be performed, so this function should only do + the minimum required to make the node state valid for EXPLAIN + and EndSampleScan. - -OffsetNumber -tsm_nexttuple (TableSampleDesc *desc, BlockNumber blockno, - OffsetNumber maxoffset); - - Return next tuple offset for the current page. InvalidOffsetNumber should - be returned if the sampling has reached end of the page. + This function can be omitted (set the pointer to NULL), in which case + BeginSampleScan must perform all initialization needed + by the sampling method. void -tsm_end (TableSampleDesc *desc); +BeginSampleScan (SampleScanState *node, + Datum *params, + int nparams, + uint32 seed); - The scan has finished, cleanup any left over state. + + Begin execution of a sampling scan. + This is called just before the first attempt to fetch a tuple, and + may be called again if the scan needs to be restarted. + Information about the table to scan is accessible through fields + of the SampleScanState node (but note that the + node->ss.ss_currentScanDesc scan descriptor is not set + up yet). + The params array, of length nparams, contains the + values of the parameters supplied in the TABLESAMPLE clause. + These will have the number and types specified in the sampling + method's parameterTypes list, and have been checked + to not be null. + seed contains a seed to use for any random numbers generated + within the sampling method; it is either a hash derived from the + REPEATABLE value if one was given, or the result + of random() if not. - -void -tsm_reset (TableSampleDesc *desc); - - The scan needs to rescan the relation again, reset any tablesample method - state. + This function may adjust the fields node->use_bulkread + and node->use_pagemode. + If node->use_bulkread is true, which it is by + default, the scan will use a buffer access strategy that encourages + recycling buffers after use. It might be reasonable to set this + to false if the scan will visit only a small fraction of the + table's pages. + If node->use_pagemode is true, which it is by + default, the scan will perform visibility checking in a single pass for + all tuples on each visited page. It might be reasonable to set this + to false if the scan will select only a small fraction of the + tuples on each visited page. That will result in fewer tuple visibility + checks being performed, though each one will be more expensive because it + will require more locking. + + + + If the sampling method is + marked repeatable_across_scans, it must be able to + select the same set of tuples during a rescan as it did originally, that is + a fresh call of BeginSampleScan must lead to selecting the + same tuples as before (if the TABLESAMPLE parameters + and seed don't change). -void -tsm_cost (PlannerInfo *root, Path *path, RelOptInfo *baserel, - List *args, BlockNumber *pages, double *tuples); +BlockNumber +NextSampleBlock (SampleScanState *node); - This function is used by optimizer to decide best plan and is also used - for output of EXPLAIN. + + Returns the block number of the next page to be scanned, or + InvalidBlockNumber if no pages remain to be scanned. - There is one more function which tablesampling method can implement in order - to gain more fine grained control over sampling. This function is optional: + This function can be omitted (set the pointer to NULL), in which case + the core code will perform a sequential scan of the entire relation. + Such a scan can use synchronized scanning, so that the sampling method + cannot assume that the relation pages are visited in the same order on + each scan. -bool -tsm_examinetuple (TableSampleDesc *desc, BlockNumber blockno, - HeapTuple tuple, bool visible); +OffsetNumber +NextSampleTuple (SampleScanState *node, + BlockNumber blockno, + OffsetNumber maxoffset); - Function that enables the sampling method to examine contents of the tuple - (for example to collect some internal statistics). The return value of this - function is used to determine if the tuple should be returned to client. - Note that this function will receive even invisible tuples but it is not - allowed to return true for such tuple (if it does, - PostgreSQL will raise an error). + + Returns the offset number of the next tuple to be sampled on the + specified page, or InvalidOffsetNumber if no tuples remain to + be sampled. maxoffset is the largest offset number in use + on the page. + + + NextSampleTuple is not explicitly told which of the offset + numbers in the range 1 .. maxoffset actually contain valid + tuples. This is not normally a problem since the core code ignores + requests to sample missing or invisible tuples; that should not result in + any bias in the sample. However, if necessary, the function can + examine node->ss.ss_currentScanDesc->rs_vistuples[] + to identify which tuples are valid and visible. (This + requires node->use_pagemode to be true.) + + + + + + NextSampleTuple must not assume + that blockno is the same page number returned by the most + recent NextSampleBlock call. It was returned by some + previous NextSampleBlock call, but the core code is allowed + to call NextSampleBlock in advance of actually scanning + pages, so as to support prefetching. It is OK to assume that once + sampling of a given page begins, successive NextSampleTuple + calls all refer to the same page until InvalidOffsetNumber is + returned. + + + - As you can see most of the tablesample method interfaces get the - TableSampleDesc as a first parameter. This structure holds - state of the current scan and also provides storage for the tablesample - method's state. It is defined as following: -typedef struct TableSampleDesc { - HeapScanDesc heapScan; - TupleDesc tupDesc; - - void *tsmdata; -} TableSampleDesc; +void +EndSampleScan (SampleScanState *node); - Where heapScan is the descriptor of the physical table scan. - It's possible to get table size info from it. The tupDesc - represents the tuple descriptor of the tuples returned by the scan and passed - to the tsm_examinetuple() interface. The tsmdata - can be used by tablesample method itself to store any state info it might - need during the scan. If used by the method, it should be pfreed - in tsm_end() function. + + End the scan and release resources. It is normally not important + to release palloc'd memory, but any externally-visible resources + should be cleaned up. + This function can be omitted (set the pointer to NULL) in the common + case where no such resources exist. + diff --git a/doc/src/sgml/tsm-system-rows.sgml b/doc/src/sgml/tsm-system-rows.sgml index 0c2f1779c9a..93aa5366649 100644 --- a/doc/src/sgml/tsm-system-rows.sgml +++ b/doc/src/sgml/tsm-system-rows.sgml @@ -8,24 +8,37 @@ - The tsm_system_rows module provides the tablesample method - SYSTEM_ROWS, which can be used inside the - TABLESAMPLE clause of a SELECT. + The tsm_system_rows module provides the table sampling method + SYSTEM_ROWS, which can be used in + the TABLESAMPLE clause of a + command. - This tablesample method uses a linear probing algorithm to read sample - of a table and uses actual number of rows as limit (unlike the - SYSTEM tablesample method which limits by percentage - of a table). + This table sampling method accepts a single integer argument that is the + maximum number of rows to read. The resulting sample will always contain + exactly that many rows, unless the table does not contain enough rows, in + which case the whole table is selected. + + + + Like the built-in SYSTEM sampling + method, SYSTEM_ROWS performs block-level sampling, so + that the sample is not completely random but may be subject to clustering + effects, especially if only a small number of rows are requested. + + + + SYSTEM_ROWS does not support + the REPEATABLE clause. Examples - Here is an example of selecting sample of a table with - SYSTEM_ROWS. First install the extension: + Here is an example of selecting a sample of a table with + SYSTEM_ROWS. First install the extension: @@ -33,8 +46,7 @@ CREATE EXTENSION tsm_system_rows; - Then you can use it in SELECT command same way as other - tablesample methods: + Then you can use it in a SELECT command, for instance: SELECT * FROM my_table TABLESAMPLE SYSTEM_ROWS(100); @@ -42,8 +54,9 @@ SELECT * FROM my_table TABLESAMPLE SYSTEM_ROWS(100); - The above command will return a sample of 100 rows from the table my_table - (less if the table does not have 100 visible rows). + This command will return a sample of 100 rows from the + table my_table (unless the table does not have 100 + visible rows, in which case all its rows are returned). diff --git a/doc/src/sgml/tsm-system-time.sgml b/doc/src/sgml/tsm-system-time.sgml index 2343ab16d4f..3f8ff1a026f 100644 --- a/doc/src/sgml/tsm-system-time.sgml +++ b/doc/src/sgml/tsm-system-time.sgml @@ -8,25 +8,39 @@ - The tsm_system_time module provides the tablesample method - SYSTEM_TIME, which can be used inside the - TABLESAMPLE clause of a SELECT. + The tsm_system_time module provides the table sampling method + SYSTEM_TIME, which can be used in + the TABLESAMPLE clause of a + command. - This tablesample method uses a linear probing algorithm to read sample - of a table and uses time in milliseconds as limit (unlike the - SYSTEM tablesample method which limits by percentage - of a table). This gives you some control over the length of execution - of your query. + This table sampling method accepts a single floating-point argument that + is the maximum number of milliseconds to spend reading the table. This + gives you direct control over how long the query takes, at the price that + the size of the sample becomes hard to predict. The resulting sample will + contain as many rows as could be read in the specified time, unless the + whole table has been read first. + + + + Like the built-in SYSTEM sampling + method, SYSTEM_TIME performs block-level sampling, so + that the sample is not completely random but may be subject to clustering + effects, especially if only a small number of rows are selected. + + + + SYSTEM_TIME does not support + the REPEATABLE clause. Examples - Here is an example of selecting sample of a table with - SYSTEM_TIME. First install the extension: + Here is an example of selecting a sample of a table with + SYSTEM_TIME. First install the extension: @@ -34,8 +48,7 @@ CREATE EXTENSION tsm_system_time; - Then you can use it in a SELECT command the same way as - other tablesample methods: + Then you can use it in a SELECT command, for instance: SELECT * FROM my_table TABLESAMPLE SYSTEM_TIME(1000); @@ -43,8 +56,9 @@ SELECT * FROM my_table TABLESAMPLE SYSTEM_TIME(1000); - The above command will return as large a sample of my_table as it can read in - 1 second (or less if it reads whole table faster). + This command will return as large a sample of my_table as + it can read in 1 second (1000 milliseconds). Of course, if the whole + table can be read in under 1 second, all its rows will be returned. -- cgit v1.2.3