{"push_id":1231702755,"size":6,"distinct_size":6,"ref":"refs/heads/mvstats","head":"45153966ede2912d400e349f58099c9ae86ed0e0","before":"e46079b11be5c828b4e04f55063347334a4cdf4c","commits":[{"sha":"c1a91bb23a0e7c1ea286b70d01c16dcbc257bee6","author":{"name":"Tomas Vondra","email":"b285496aecb7891a95952a3b19256e1b4b08826d@fuzzy.cz"},"message":"shared infrastructure and functional dependencies\n\nBasic infrastructure shared by all kinds of multivariate stats, most\nimportantly:\n\n- adds a new system catalog (pg_mv_statistic)\n- CREATE STATISTICS name ON table (columns) WITH (options)\n- DROP STATISTICS name\n- ALTER STATISTICS ... OWNER TO / SET SCHEMA / RENAME\n- implementation of functional dependencies (the simplest type of\n  multivariate statistics)\n- building functional dependencies in ANALYZE\n- updates existing regression tests (new catalog etc.)\n- adds a new regression test for functional dependencies\n\nThis does not include any changes to the optimizer, i.e. it does not\ninfluence the query planning (subject to follow-up patches).\n\nThe current implementation requires a valid 'ltopr' for the columns, so\nthat we can sort the sample rows in various ways, both in this patch\nand other kinds of statistics. Maybe this restriction could be relaxed\nin the future, requiring just 'eqopr' in case of stats not sorting the\ndata (e.g. functional dependencies and MCV lists).\n\nMaybe some of the stats (functional dependencies and MCV list with\nlimited functionality) might be made to work with hashes of the values,\nwhich is sufficient for equality comparisons. But the queries would\nrequire the equality operator anyway, so it's not really a weaker\nrequirement. The hashes might reduce space requirements, though.\n\nThe algorithm detecting the dependencies is rather simple and probably\nneeds improvements, so that it detects more complicated dependencies,\nand also validation of the math.\n\nThe name 'functional dependencies' is more correct (than 'association\nrules') as it's exactly the name used in relational theory (esp. Normal\nForms) for tracking column-level dependencies.\n\nThe multivariate statistics are automatically removed in two situations\n\n (a) after a DROP TABLE (obviously)\n\n (b) after ALTER TABLE ... DROP COLUMN, if the statistics would be\n     defined on less than 2 columns (remaining)\n\nIf there are more at least two remaining columns, we keep the\nstatistics but perform cleanup on the next ANALYZE. The dropped columns\nare removed from stakeys, and the new statistics is built on the\nsmaller set.\n\nWe can't do this at DROP COLUMN, because that'd leave us with invalid\nstatistics, or we'd have to throw it away although we can still use it.\nThis lazy approach lets us use the statistics although some of the\ncolumns are dead.\n\nThis also adds a simple list of statistics to \\d in psql.\n\nThis means the statistics are created within a schema by using a\nqualified name (or using the default schema)\n\n   CREATE STATISTICS schema.statistics ON ...\n\nand then dropped by specifying qualified name\n\n   DROP STATISTICS schema.statistics\n\nor searching through search_path (just like with other objects).\n\nThis also gets rid of the \"(opt_)stats_name\" definitions in gram.y and\ninstead replaces them with just \"opt_any_name\", although the optional\ncase is not really handled currently - there's no generated name yet\n(so either we should drop it or implement it).\n\nI'm not entirely sure making statistics schema-specific is that a great\nidea. Maybe it should be \"global\", but that does not seem right (e.g.\nit makes multi-tenant systems based on schemas more difficult to\nmanage, because tenants would interact).","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/c1a91bb23a0e7c1ea286b70d01c16dcbc257bee6"},{"sha":"7e1a20ea7bf862c41ebbca66e12d9293290e3c83","author":{"name":"Tomas Vondra","email":"626e76f982a26e560d4cdf7e0019853d5ec4c071@pgaddict.com"},"message":"clause reduction using functional dependencies\n\nDuring planning, use functional dependencies to decide which clauses to\nskip during cardinality estimation. Initial and rather simplistic\nimplementation.\n\nThis only works with regular WHERE clauses, not clauses used for join\nclauses.\n\nNote: The clause_is_mv_compatible() needs to identify the relation (so\nthat we can fetch the list of multivariate stats by OID).\nplanner_rt_fetch() seems like the appropriate way to get the relation\nOID, but apparently it only works with simple vars. Maybe\nexamine_variable() would make this work with more complex vars too?\n\nIncludes regression tests analyzing functional dependencies (part of\nANALYZE) on several datasets (no dependencies, no transitive\ndependencies, ...).\n\nChecks that a query with conditions on two columns, where one (B) is\nfunctionally dependent on the other one (A), correctly ignores the\nclause on (B) and chooses bitmap index scan instead of plain index scan\n(which is what happens otherwise, thanks to assumption of\nindependence).\n\nNote: Functional dependencies only work with equality clauses, no\ninequalities etc.","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/7e1a20ea7bf862c41ebbca66e12d9293290e3c83"},{"sha":"2a575631f667ffc2a1eb5f6a35339d1e49cd0566","author":{"name":"Tomas Vondra","email":"626e76f982a26e560d4cdf7e0019853d5ec4c071@pgaddict.com"},"message":"multivariate MCV lists\n\n- extends the pg_mv_statistic catalog (add 'mcv' fields)\n- building the MCV lists during ANALYZE\n- simple estimation while planning the queries\n\nIncludes regression tests, mostly equal to regression tests for\nfunctional dependencies.","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/2a575631f667ffc2a1eb5f6a35339d1e49cd0566"},{"sha":"97caa6307e4c3991af22c93498e1aa774ad971d9","author":{"name":"Tomas Vondra","email":"b285496aecb7891a95952a3b19256e1b4b08826d@fuzzy.cz"},"message":"multivariate histograms\n\n- extends the pg_mv_statistic catalog (add 'hist' fields)\n- building the histograms during ANALYZE\n- simple estimation while planning the queries\n\nIncludes regression tests mostly equal to those for functional\ndependencies / MCV lists.","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/97caa6307e4c3991af22c93498e1aa774ad971d9"},{"sha":"9ca1fe4110a8c567bdeef173b1ba98697eefe37c","author":{"name":"Tomas Vondra","email":"626e76f982a26e560d4cdf7e0019853d5ec4c071@pgaddict.com"},"message":"multi-statistics estimation\n\nThe general idea is that a probability (which is what selectivity is)\ncan be split into a product of conditional probabilities like this:\n\n    P(A & B & C) = P(A & B) * P(C|A & B)\n\nIf we assume that C and B are independent, the last part may be\nsimplified like this\n\n    P(A & B & C) = P(A & B) * P(C|A)\n\nwe only need probabilities on [A,B] and [C,A] to compute the original\nprobability.\n\nThe implementation works in the other direction, though. We know what\nprobability P(A & B & C) we need to compute, and also what statistics\nare available.\n\nSo we search for a combinations of statistics, covering the clauses in\nan optimal way (most clauses covered, most dependencies exploited).\n\nThere are two possible approaches - exhaustive and greedy. The\nexhaustive one walks through all permutations of stats using dynamic\nprogramming, so it's guaranteed to find the optimal solution, but it\nsoon gets very slow as it's roughly O(N!). The dynamic programming may\nimprove that a bit, but it's still far too expensive for large numbers\nof statistics (on a single table).\n\nThe greedy algorithm is very simple - in every step choose the best\nsolution. That may not guarantee the best solution globally (but maybe\nit does?), but it only needs N steps to find the solution, so it's very\nfast (processing the selected stats is usually way more expensive).\n\nThere's a GUC for selecting the search algorithm\n\n    mvstat_search = {'greedy', 'exhaustive'}\n\nThe default value is 'greedy' as that's much safer (with respect to\nruntime). See choose_mv_statistics().\n\nOnce we have found a sequence of statistics, we apply them to the\nclauses using the conditional probabilities. We process the selected\nstats one by one, and for each we select the estimated clauses and\nconditions. See clauselist_selectivity() for more details.\n\nLimitations\n-----------\n\nIt's still true that each clause at a given level has to be covered by\na single MV statistics. So with this query\n\n    WHERE (clause1) AND (clause2) AND (clause3 OR clause4)\n\neach parenthesized clause has to be covered by a single multivariate\nstatistics.\n\nClauses not covered by a single statistics at this level will be passed\nto clause_selectivity() but this will treat them as a collection of\nsimpler clauses (connected by AND or OR), and the clauses from the\nprevious level will be used as conditions.\n\nSo using the same example, the last clause will be passed to\nclause_selectivity() with 'clause1' and 'clause2' as conditions, and it\nwill be processed using multivariate stats if possible.\n\nThe other limitation is that all the expressions have to be\nmv-compatible, i.e. there can't be a mix of expressions. If this is\nviolated, the clause may be passed to the next level (just like with\nlist of clauses not covered by a single statistics), which splits that\ninto clauses handled by multivariate stats and clauses handler by\nregular statistics.\n\nrework clauselist_selectivity_or to handle OR-clauses correctly\n\nWe might invent a completely new set of functions here, resembling\nclauselist_selectivity but adapting the ideas to OR-clauses.\n\nBut luckily we know that each OR-clause\n\n    (a OR b OR c)\n\nmay be rewritten as an equivalent AND-clause using negation:\n\n    NOT ((NOT a) AND (NOT b) AND (NOT c))\n\nAnd that's something we can pass to clauselist_selectivity.","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/9ca1fe4110a8c567bdeef173b1ba98697eefe37c"},{"sha":"45153966ede2912d400e349f58099c9ae86ed0e0","author":{"name":"Tomas Vondra","email":"626e76f982a26e560d4cdf7e0019853d5ec4c071@pgaddict.com"},"message":"multivariate ndistinct coefficients","distinct":true,"url":"https://api.github.com/repos/tvondra/postgres/commits/45153966ede2912d400e349f58099c9ae86ed0e0"}]}
{"actor":{"display_login":"tvondra"}}