Received: from malur.postgresql.org ([2a02:16a8:dc51::56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1g0RFS-0005ip-QR for pgsql-hackers@arkaria.postgresql.org; Thu, 13 Sep 2018 13:01:31 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1g0RFR-0000Oj-1x for pgsql-hackers@arkaria.postgresql.org; Thu, 13 Sep 2018 13:01:29 +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_SHA384:256) (Exim 4.89) (envelope-from ) id 1g0RFQ-0000Oc-P2 for pgsql-hackers@lists.postgresql.org; Thu, 13 Sep 2018 13:01:28 +0000 Received: from mail.postgrespro.ru ([93.174.131.138]) by magus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1g0RFD-0001K5-GT for pgsql-hackers@postgresql.org; Thu, 13 Sep 2018 13:01:25 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id E824821C28CB; Thu, 13 Sep 2018 16:01:13 +0300 (MSK) X-Virus-Scanned: Debian amavisd-new at postgrespro.ru X-Spam-Flag: NO X-Spam-Score: 0 X-Spam-Level: X-Spam-Status: No, score=x tagged_above=-99 required=4 WHITELISTED tests=[] autolearn=unavailable Received: from [192.168.27.132] (gw.postgrespro.ru [93.174.131.141]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mail.postgrespro.ru (Postfix) with ESMTPSA id 9A2C521C2881; Thu, 13 Sep 2018 16:01:13 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1536843673; bh=r6Efda9CucD80dC7e6w1d4pbBKH3iTMfieycNO2q1PQ=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=G1FPBiy0FRttLt5ZrQpYotALyjXJKQxxmy/AFfT/dNv+U5xfoaRHklohbQY8dR1t/ 3rji2EpGkh+Ys8Ue3gbJ+j93K4QxrU0vQvUdWb8crrDeBfylk2aOyOEp06/cCM4eyd a8Nlm6XanJvjgLtLjG7SGnxNl5JsQJYqiLNKNwao= Subject: Re: Index Skip Scan To: jesper.pedersen@redhat.com, Dmitry Dolgov <9erthalion6@gmail.com> Cc: pg@bowt.ie, Thomas Munro , bhushan.uparkar@gmail.com, PostgreSQL-development , Alexander Korotkov References: <707b6f68-16fa-7aa7-96e5-eeb4865e6a30@redhat.com> <89F84E17-D684-4717-B66F-0F05CB00168E@gmail.com> From: Alexander Kuzmenkov Message-ID: <522092c7-3cb7-a1ec-410b-dfa97ae722f3@postgrespro.ru> Date: Thu, 13 Sep 2018 16:01:13 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------B9349D216E58BE7DE13952D8" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multi-part message in MIME format. --------------B9349D216E58BE7DE13952D8 Content-Type: multipart/alternative; boundary="------------AEBB296DC841FFD89F823F1A" --------------AEBB296DC841FFD89F823F1A Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Hi Jesper, While testing this patch I noticed that current implementation doesn't perform well when we have lots of small groups of equal values. Here is the execution time of index skip scan vs unique over index scan, in ms, depending on the size of group. The benchmark script is attached. group size    skip        unique 1             2,293.85    132.55 5             464.40      106.59 10            239.61      102.02 50            56.59       98.74 100           32.56       103.04 500           6.08        97.09 So, the current implementation can lead to performance regression, and the choice of the plan depends on the notoriously unreliable ndistinct statistics. The regression is probably because skip scan always does _bt_search to find the next unique tuple. I think we can improve this, and the skip scan can be strictly faster than index scan regardless of the data. As a first approximation, imagine that we somehow skipped equal tuples inside _bt_next instead of sending them to the parent Unique node. This would already be marginally faster than Unique + Index scan. A more practical implementation would be to remember our position in tree (that is, BTStack returned by _bt_search) and use it to skip pages in bulk. This looks straightforward to implement for a tree that does not change, but I'm not sure how to make it work with concurrent modifications. Still, this looks a worthwhile direction to me, because if we have a strictly faster skip scan, we can just use it always and not worry about our unreliable statistics. What do you think? -- Alexander Kuzmenkov Postgres Professional: http://www.postgrespro.com The Russian Postgres Company --------------AEBB296DC841FFD89F823F1A Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

Hi Jesper,

While testing this patch I noticed that current implementation doesn't perform well when we have lots of small groups of equal values. Here is the execution time of index skip scan vs unique over index scan, in ms, depending on the size of group. The benchmark script is attached.

group size    skip        unique
1             2,293.85    132.55
5             464.40      106.59
10            239.61      102.02
50            56.59       98.74
100           32.56       103.04
500           6.08        97.09

So, the current implementation can lead to performance regression, and the choice of the plan depends on the notoriously unreliable ndistinct statistics. The regression is probably because skip scan always does _bt_search to find the next unique tuple. I think we can improve this, and the skip scan can be strictly faster than index scan regardless of the data. As a first approximation, imagine that we somehow skipped equal tuples inside _bt_next instead of sending them to the parent Unique node. This would already be marginally faster than Unique + Index scan. A more practical implementation would be to remember our position in tree (that is, BTStack returned by _bt_search) and use it to skip pages in bulk. This looks straightforward to implement for a tree that does not change, but I'm not sure how to make it work with concurrent modifications. Still, this looks a worthwhile direction to me, because if we have a strictly faster skip scan, we can just use it always and not worry about our unreliable statistics. What do you think?
-- 
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
--------------AEBB296DC841FFD89F823F1A-- --------------B9349D216E58BE7DE13952D8 Content-Type: application/sql; name="test-skip.sql" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="test-skip.sql" XHNldCBuIDEwMDAwMDAKLS1cc2V0IG0gMTAKXHNldCBxICdleHBsYWluIGFuYWx5emUgc2Vs ZWN0IGRpc3RpbmN0IGEgZnJvbSB0IHdoZXJlIGEgPiA6biAvIDptIC8gMyBhbmQgYSA8IDIg KiA6biAvIDptIC8zJwotLVxzZXQgcSAnZXhwbGFpbiBhbmFseXplIHNlbGVjdCBkaXN0aW5j dCBhIGZyb20gdCcKCnJlc2V0IGFsbDsKZHJvcCB0YWJsZSB0IGNhc2NhZGU7CmNyZWF0ZSB0 YWJsZSB0KGEpIGFzIHNlbGVjdCBnZW5lcmF0ZV9zZXJpZXMoMSwgOm4pIC8gOm07CmNyZWF0 ZSBpbmRleCBpZHhfdF9hIG9uIHQoYSk7CmFuYWx5emUgdDsKCi0tIHByZXdhcm0Kc2V0IGVu YWJsZV9zZXFzY2FuIHRvIG9mZjsKZXhwbGFpbiBhbmFseXplIHNlbGVjdCAqIGZyb20gdDsK cmVzZXQgZW5hYmxlX3NlcXNjYW47CmV4cGxhaW4gYW5hbHl6ZSBzZWxlY3QgKiBmcm9tIHQ7 CgpcZWNobyA6cQpcZWNobyBncm91cC1zaXplIDptCi0tIGJlbmNobWFyawo6cTsKCnNldCBl bmFibGVfaGFzaGFnZyB0byBvZmY7CjpxOwoKc2V0IGVuYWJsZV9pbmRleHNraXBzY2FuIHRv IG9mZjsKOnE7ClxlY2hvIGJlbmNobWFyay1kb25lCg== --------------B9349D216E58BE7DE13952D8--