Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1iTubk-000691-3L for pgsql-hackers@arkaria.postgresql.org; Sun, 10 Nov 2019 21:18:52 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1iTubh-0004bt-Jn for pgsql-hackers@arkaria.postgresql.org; Sun, 10 Nov 2019 21:18:49 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1iTubh-0004bl-78 for pgsql-hackers@lists.postgresql.org; Sun, 10 Nov 2019 21:18:49 +0000 Received: from mail-lj1-x244.google.com ([2a00:1450:4864:20::244]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1iTubZ-0002RX-7w for pgsql-hackers@postgresql.org; Sun, 10 Nov 2019 21:18:48 +0000 Received: by mail-lj1-x244.google.com with SMTP id 139so11601484ljf.1 for ; Sun, 10 Nov 2019 13:18:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=2ndquadrant-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=2LjsX5qQEjlbK2CQ378vuc/qCK6fIXnWT5uuaCD+2Ak=; b=P6/BlOCtvLDnhmvYpZeANxuzuYTEELAF1fLqKnEdsI8Sm3hNu9qZHA48lKd0Nn4WUg liYt8/yOsWlHGXBJDssEgE0UPA9d5y4b7fTBufNGnZ7xpNCQ73d7aAlTW+NHBSR9ITOz MqgrSC3clCTjm4qwGlIK5FECcjkurvF6Vxq7hH2Z4/5MVrouPoySYR5p4uFgTplVEV5e mnexvyt3Y+6/mpotayIaLjmoMdKY3Xi6JiDiypnpo2VBBDj4S9WDfiXkl7YXhoqntUx/ d4Q+byuOJewUeqVk9G9L4cBkVDxmwZugXDc0Vx0DRFTlGpbMI+Z1hK9nfAy4ZnN28II8 dBBA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=2LjsX5qQEjlbK2CQ378vuc/qCK6fIXnWT5uuaCD+2Ak=; b=KgctKd1SOONyEpdRi/N+7EM1uWpViA1m9fkGdx4fdQqv09kxCGt7XS5V5Rsb5kPxjZ l4ptVP8OszJSYPjMuzVCNh7aZBYSZUgilBgaHc52qLx5mB/cyAAumvmvcrUk3NBOkZtD XGGrnvNR5mk2RaQRe8N8uqrRziTgE4DJVOhpQyx1NfVTscHEbEB+G6wTOgsztwaSEbG5 ZxIvFVCqgkxNEj46Sh1+vGBnSyV8Z62aY3TMYzoXyzPdpPGo7eGqpPS/Dex2YgWqxjTe FpDb+0KLqccKSnUlCDhJCJpVOGlcM4FaFiiKzmMeyG0Zez5LsrUNfSjW/sR0qMCLEayE ay+Q== X-Gm-Message-State: APjAAAVCEnUJXB4hWD0ZtyUdxfCyYEeznrcFdpfxTj0Tdw+gt38mXwVg ANZKVfxGMXPrW15ttnmEO9eiVg== X-Google-Smtp-Source: APXvYqw3y0naBWLGhe7DHxCDzOsXTTB9wfMAt9bo6T7c/+uTcCbcVrYr9XIiGOSw7jqAslv8Kmu43A== X-Received: by 2002:a2e:9104:: with SMTP id m4mr14184998ljg.63.1573420718909; Sun, 10 Nov 2019 13:18:38 -0800 (PST) Received: from localhost ([217.8.174.100]) by smtp.gmail.com with ESMTPSA id d26sm5268331ljo.54.2019.11.10.13.18.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 10 Nov 2019 13:18:33 -0800 (PST) Date: Sun, 10 Nov 2019 22:18:32 +0100 From: Tomas Vondra To: Dmitry Dolgov <9erthalion6@gmail.com> Cc: Peter Geoghegan , Kyotaro Horiguchi , Alvaro Herrera , Floris Van Nee , Jesper Pedersen , David Rowley , Thomas Munro , James Coleman , Rafia Sabih , Jeff Janes , Bhushan Uparkar , PostgreSQL-development , Alexander Korotkov Subject: Re: Index Skip Scan Message-ID: <20191110211832.vv4jbscszz74jete@development> References: <20190924.174146.159197618.horikyota.ntt@gmail.com> <20190924120627.GA12454@alvherre.pgsql> <20190925.100301.198068449.horikyota.ntt@gmail.com> <20191103164547.oqcvno6467eikizg@localhost> <20191107154358.bvwq3ul2ol7cv3lj@localhost> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="i52pljjnu5px3ffx" Content-Disposition: inline In-Reply-To: <20191107154358.bvwq3ul2ol7cv3lj@localhost> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --i52pljjnu5px3ffx Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline Hi, I've looked at the patch again - in general it seems in pretty good shape, all the issues I found are mostly minor. Firstly, I'd like to point out that not all of the things I complained about in my 2019/06/23 review got addressed. Those were mostly related to formatting and code style, and the attached patch fixes some (but maybe not all) of them. The patch also tweaks wording of some bits in the docs and comments that I found unclear. Would be nice if a native speaker could take a look. A couple more comments: 1) pathkey_is_unique The one additional issue I found is pathkey_is_unique - it's not really explained what "unique" means and hot it's different from "redundant" (which has quite a long explanation before pathkey_is_redundant). My understanding is that pathkey is "unique" when it's EC does not match an EC of another pathkey in the list. But if that's the case, then the function name is wrong - it does exactly the opposite (i.e. it returns 'true' when the pathkey is *not* unique). 2) explain I wonder if we should print the "Skip scan" info always, or similarly to "Inner Unique" which does this: /* try not to be too chatty about this in text mode */ if (es->format != EXPLAIN_FORMAT_TEXT || (es->verbose && ((Join *) plan)->inner_unique)) ExplainPropertyBool("Inner Unique", ((Join *) plan)->inner_unique, es); break; I'd do the same thing for skip scan - print it only in verbose mode, or when using non-text output format. 3) There's an annoying limitation that for this to kick in, the order of expressions in the DISTINCT clause has to match the index, i.e. with index on (a,b,c) the skip scan will only kick in for queries using DISTINCT a DISTINCT a,b DISTINCT a,b,c but not e.g. DISTINCT a,c,b. I don't think there's anything forcing us to sort result of DISTINCT in any particular case, except that we don't consider the other orderings "interesting" so we don't really consider using the index (so no chance of using the skip scan). That leads to pretty annoying speedups/slowdowns due to seemingly irrelevant changes: -- everything great, a,b,c matches an index test=# explain (analyze, verbose) select distinct a,b,c from t; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------- Index Only Scan using t_a_b_c_idx on public.t (cost=0.42..565.25 rows=1330 width=12) (actual time=0.016..10.387 rows=1331 loops=1) Output: a, b, c Skip scan: true Heap Fetches: 1331 Planning Time: 0.106 ms Execution Time: 10.843 ms (6 rows) -- slow, mismatch with index test=# explain (analyze, verbose) select distinct a,c,b from t; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------- HashAggregate (cost=22906.00..22919.30 rows=1330 width=12) (actual time=802.067..802.612 rows=1331 loops=1) Output: a, c, b Group Key: t.a, t.c, t.b -> Seq Scan on public.t (cost=0.00..15406.00 rows=1000000 width=12) (actual time=0.010..355.361 rows=1000000 loops=1) Output: a, b, c Planning Time: 0.076 ms Execution Time: 803.078 ms (7 rows) -- fast again, the extra ordering allows using the index again test=# explain (analyze, verbose) select distinct a,c,b from t order by a,b,c; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------- Index Only Scan using t_a_b_c_idx on public.t (cost=0.42..565.25 rows=1330 width=12) (actual time=0.035..12.120 rows=1331 loops=1) Output: a, c, b Skip scan: true Heap Fetches: 1331 Planning Time: 0.053 ms Execution Time: 12.632 ms (6 rows) This is a more generic issue, not specific to this patch, of course. I think we saw it with the incremental sort patch, IIRC. I wonder how difficult would it be to fix this here (not necessarily in v1). regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services --i52pljjnu5px3ffx Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="skipscan-review.patch" diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml index 73b1b4fcf7..94e09835b4 100644 --- a/doc/src/sgml/indexam.sgml +++ b/doc/src/sgml/indexam.sgml @@ -144,7 +144,7 @@ typedef struct IndexAmRoutine amendscan_function amendscan; ammarkpos_function ammarkpos; /* can be NULL */ amrestrpos_function amrestrpos; /* can be NULL */ - amskip_function amskip; /* can be NULL */ + amskip_function amskip; /* can be NULL */ /* interface functions to support parallel index scans */ amestimateparallelscan_function amestimateparallelscan; /* can be NULL */ diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml index 567141046f..efc5e41389 100644 --- a/doc/src/sgml/indices.sgml +++ b/doc/src/sgml/indices.sgml @@ -1248,15 +1248,14 @@ SELECT target FROM tests WHERE subject = 'some-subject' AND success; - In case if index scan is used to retrieve the distinct values of a column - efficiently, it can be not very efficient, since it requires to scan all - the equal values of a key. In such cases planner will consider apply index - skip scan approach, which is based on the idea of - Loose index scan. Rather than scanning all equal - values of a key, as soon as a new value is found, it will search for a - larger value on the same index page, and if not found, restart the search - by looking for a larger value. This is much faster when the index has many - equal keys. + When the rows retrieved from an index scan are then deduplicated by + eliminating rows matching on a prefix of index keys (e.g. when using + SELECT DISTINCT), the planner will consider + skipping groups of rows with a matching key prefix. When a row with + a particular prefix is found, remaining rows with the same key prefix + are skipped. The larger the number of rows with the same key prefix + rows (i.e. the lower the number of distinct key prefixes in the index), + the more efficient this is. diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 72dcd4d734..74786bf4a2 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -1403,6 +1403,8 @@ _bt_next(IndexScanDesc scan, ScanDirection dir) * * * Advancing backward and reading backward * simple scan with order by desc + * + * TODO Explain why we search the current page first, then do lookup from root? */ bool _bt_skip(IndexScanDesc scan, ScanDirection dir, @@ -1556,7 +1558,7 @@ _bt_skip(IndexScanDesc scan, ScanDirection dir, } /* - * Andvance forward but read backward. At this moment we are at the next + * Advance forward but read backward. At this moment we are at the next * distinct key at the beginning of the series. In case if scan just * started, we can go one step back and read forward without doing * anything else. Otherwise find the next distinct key and the beginning @@ -1564,7 +1566,7 @@ _bt_skip(IndexScanDesc scan, ScanDirection dir, * * An interesting situation can happen if one of distinct keys do not pass * a corresponding index condition at all. In this case reading backward - * can lead to a previous distinc key being found, creating a loop. To + * can lead to a previous distinct key being found, creating a loop. To * avoid that check the value to be returned, and jump one more time if * it's the same as at the beginning. */ diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index ad500de12b..b66296d6c9 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -130,7 +130,7 @@ static void ExplainDummyGroup(const char *objtype, const char *labelname, static void ExplainXMLTag(const char *tagname, int flags, ExplainState *es); static void ExplainJSONLineEnding(ExplainState *es); static void ExplainYAMLLineStarting(ExplainState *es); -static void ExplainIndexSkipScanKeys(ExplainState *es, int skipPrefixSize); +static void ExplainIndexSkipScanKeys(int skipPrefixSize, ExplainState *es); static void escape_yaml(StringInfo buf, const char *str); @@ -1049,7 +1049,7 @@ ExplainPreScanNode(PlanState *planstate, Bitmapset **rels_used) * Can be used to print the skip prefix size. */ static void -ExplainIndexSkipScanKeys(ExplainState *es, int skipPrefixSize) +ExplainIndexSkipScanKeys(int skipPrefixSize, ExplainState *es) { if (skipPrefixSize > 0) { @@ -1380,7 +1380,7 @@ ExplainNode(PlanState *planstate, List *ancestors, { IndexScan *indexscan = (IndexScan *) plan; - ExplainIndexSkipScanKeys(es, indexscan->indexskipprefixsize); + ExplainIndexSkipScanKeys(indexscan->indexskipprefixsize, es); ExplainIndexScanDetails(indexscan->indexid, indexscan->indexorderdir, @@ -1392,7 +1392,7 @@ ExplainNode(PlanState *planstate, List *ancestors, { IndexOnlyScan *indexonlyscan = (IndexOnlyScan *) plan; - ExplainIndexSkipScanKeys(es, indexonlyscan->indexskipprefixsize); + ExplainIndexSkipScanKeys(indexonlyscan->indexskipprefixsize, es); ExplainIndexScanDetails(indexonlyscan->indexid, indexonlyscan->indexorderdir, @@ -1604,9 +1604,7 @@ ExplainNode(PlanState *planstate, List *ancestors, { case T_IndexScan: if (((IndexScan *) plan)->indexskipprefixsize > 0) - { - ExplainPropertyBool("Skip scan mode", true, es); - } + ExplainPropertyBool("Skip scan", true, es); show_scan_qual(((IndexScan *) plan)->indexqualorig, "Index Cond", planstate, ancestors, es); if (((IndexScan *) plan)->indexqualorig) @@ -1621,9 +1619,7 @@ ExplainNode(PlanState *planstate, List *ancestors, break; case T_IndexOnlyScan: if (((IndexOnlyScan *) plan)->indexskipprefixsize > 0) - { - ExplainPropertyBool("Skip scan mode", true, es); - } + ExplainPropertyBool("Skip scan", true, es); show_scan_qual(((IndexOnlyScan *) plan)->indexqual, "Index Cond", planstate, ancestors, es); if (((IndexOnlyScan *) plan)->indexqual) diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 70c1df47a4..5683edcd2f 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -99,9 +99,12 @@ make_canonical_pathkey(PlannerInfo *root, /* * pathkey_is_unique - * Part of pathkey_is_redundant, that is reponsible for the case, when the - * new pathkey's equivalence class is the same as that of any existing - * member of the pathkey list. + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + * + * FIXME This seems to be misnamed, i.e. it returns true/false in a way + * that contradicts the name. If there already is a matching EC. it says + * true, but that means "not unique" no? */ static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) @@ -165,6 +168,10 @@ pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) if (EC_MUST_BE_REDUNDANT(new_ec)) return true; + /* + * FIXME misnamed - this returns true when there is a matching EC, which + * however should ne "not unique" I think. + */ return pathkey_is_unique(new_pathkey, pathkeys); } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 644b8ad356..3f625938e8 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3634,8 +3634,8 @@ standard_qp_callback(PlannerInfo *root, void *extra) } else { - root->distinct_pathkeys = NIL; root->uniq_distinct_pathkeys = NIL; + root->distinct_pathkeys = NIL; } root->sort_pathkeys = --i52pljjnu5px3ffx--