Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dAFvx-0006ER-IA for pgsql-hackers@arkaria.postgresql.org; Mon, 15 May 2017 13:21:10 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.84_2) (envelope-from ) id 1dAFvx-0006ug-4w for pgsql-hackers@arkaria.postgresql.org; Mon, 15 May 2017 13:21:09 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1dAFtB-0003mS-Se for pgsql-hackers@postgresql.org; Mon, 15 May 2017 13:18:18 +0000 Received: from mail.postgrespro.ru ([93.174.131.138]) by makus.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dAFt7-0005UM-2X for pgsql-hackers@postgresql.org; Mon, 15 May 2017 13:18:16 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id 4F4D621C070E; Mon, 15 May 2017 16:18:10 +0300 (MSK) X-Virus-Scanned: Debian amavisd-new at postgrespro.ru MIME-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1494854290; bh=USY/1Q5pVv5QDNZLKx2Vt4FDTWCwgw63dEZnVt8pHLA=; h=Date:From:To:Cc:Subject:In-Reply-To:References; b=dpZmP+NTvQ2LRF+2PC9tuUg5PJiqTyGdLvwc20p/VywRq8T/Aw6BASPv5z9ELlr5x Mczjd4VGjC/8GsL4VNoqU3rHu3sJhDzgkvMiyxImobJKgXs8OzHBJTTvcg/8aph7VV +vuX2wXmSwtXdXQ+A/noVMkD818VFLwDBs778IY0= Content-Type: multipart/mixed; boundary="=_5778ed9e6d9675b5bfcc7867b7e62884" Date: Mon, 15 May 2017 16:18:10 +0300 From: Sokolov Yura To: Heikki Linnakangas Cc: pgsql-hackers@postgresql.org, Heikki Linnakangas Subject: Re: Small improvement to compactify_tuples Organization: Postgres Professional In-Reply-To: <0dcb7a5afa3fae6001bd1712253cf81d@postgrespro.ru> References: <3c6ff1d3a2ff429ee80d0031e6c69cb7@postgrespro.ru> <6d8cd37e-3d78-451e-a9a1-418650397639@iki.fi> <0dcb7a5afa3fae6001bd1712253cf81d@postgrespro.ru> Message-ID: X-Sender: funny.falcon@postgrespro.ru User-Agent: Roundcube Webmail/1.2.4 X-Pg-Spam-Score: -2.0 (--) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org --=_5778ed9e6d9675b5bfcc7867b7e62884 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8; format=flowed Sokolov Yura писал 2017-05-15 15:08: > Heikki Linnakangas писал 2017-05-15 12:06: >> On 05/14/2017 09:47 PM, Sokolov Yura wrote: >>> Good day, everyone. >>> >>> I've been playing a bit with unlogged tables - just random updates on >>> simple >>> key-value table. I've noticed amount of cpu spent in a >>> compactify_tuples >>> (called by PageRepareFragmentaion). Most of time were spent in qsort >>> of >>> itemidbase items. >> >> Ah, I played with this too a couple of years ago, see >> https://www.postgresql.org/message-id/546B89DE.7030906%40vmware.com, >> but got distracted by other things and never got around to commit >> that. >> >>> itemidbase array is bounded by number of tuples in a page, and >>> itemIdSortData >>> structure is simple, so specialized version could be a better choice. >>> >>> Attached patch adds combination of one pass of prefix sort with >>> insertion >>> sort for larger array and shell sort for smaller array. >>> Insertion sort and shell sort are implemented as macros and could be >>> reused. >> >> Cool! Could you compare that against the bucket sort I posted in the >> above thread, please? >> >> At a quick glance, your "prefix sort" seems to be the the same >> algorithm as the bucket sort that I implemented. You chose 256 >> buckets, where I picked 32. And you're adding a shell sort >> implementation, for small arrays, while I used a straight insertion >> sort. Not sure what these differences mean in practice. >> >> - Heikki > > Thank you for attention. > > My first version of big page sort was almost exactly same to yours. > I had a bug in my insertion sort, so I had to refactor it. > (bug were fixed) > > I found that items in itemidbase are almost sorted, so it is important > to try keep its order in prefix sort. So I've changed --count[i] to > count[i+1]++. > > And it looks like it is better to have more buckets: > - with 256 buckets, size of single bucket is almost always less than 2, > so array is almost always sorted after prefix sort pass. > > But it looks like it is better to sort each bucket separately, as you > did, and as it was in my early version. > > Also I used your names for functions and some comments. > > I attached new version of the patch. > > I left memcpy intact cause it looks like it doesn't take noticable > cpu time. In a sequel, I propose to simplify PageRepairFragmentation in attached patch. -- Sokolov Yura aka funny.falcon Postgres Professional: https://postgrespro.ru The Russian Postgres Company --=_5778ed9e6d9675b5bfcc7867b7e62884 Content-Transfer-Encoding: base64 Content-Type: text/x-diff; name=0002-bufpage.c-simplify-PageRepairFragmentation.patch Content-Disposition: attachment; filename=0002-bufpage.c-simplify-PageRepairFragmentation.patch; size=3339 RnJvbSAyY2RlNGNiNmIwYzRjNTg2OGQ5OWUxMzc4OWIwYWMzMzM2NGQ3MzE1 IE1vbiBTZXAgMTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBTb2tvbG92IFl1cmEg PGZ1bm55LmZhbGNvbkBwb3N0Z3Jlc3Byby5ydT4KRGF0ZTogTW9uLCAxNSBN YXkgMjAxNyAxNjowNDoxNCArMDMwMApTdWJqZWN0OiBbUEFUQ0ggMi8yXSBi dWZwYWdlLmM6IHNpbXBsaWZ5IFBhZ2VSZXBhaXJGcmFnbWVudGF0aW9uCgpJ biBhc3N1bXB0aW9uIHRoYXQgcGFnZSB1c3VhbGx5IGRvZXNuJ3QgYmVjb21l IGVtcHR5LCBtZXJnZSBzZWNvbmQgbG9vcApib2R5IChjb2xsZWN0aW5nIGl0 ZW1zIHdpdGggc3RvcmFnZSkgaW50byBmaXJzdCAoY291bnRpbmcga2luZHMg b2YKaXRlbXMpLgotLS0KIHNyYy9iYWNrZW5kL3N0b3JhZ2UvcGFnZS9idWZw YWdlLmMgfCA0NiArKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0tLS0t LS0tLQogMSBmaWxlIGNoYW5nZWQsIDE4IGluc2VydGlvbnMoKyksIDI4IGRl bGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3N0b3JhZ2Uv cGFnZS9idWZwYWdlLmMgYi9zcmMvYmFja2VuZC9zdG9yYWdlL3BhZ2UvYnVm cGFnZS5jCmluZGV4IGM1NjMwZTgwOGIuLjYxNzM4ZjI0MWYgMTAwNjQ0Ci0t LSBhL3NyYy9iYWNrZW5kL3N0b3JhZ2UvcGFnZS9idWZwYWdlLmMKKysrIGIv c3JjL2JhY2tlbmQvc3RvcmFnZS9wYWdlL2J1ZnBhZ2UuYwpAQCAtNTU1LDEw ICs1NTUsMTEgQEAgUGFnZVJlcGFpckZyYWdtZW50YXRpb24oUGFnZSBwYWdl KQogCU9mZnNldAkJcGRfc3BlY2lhbCA9ICgoUGFnZUhlYWRlcikgcGFnZSkt PnBkX3NwZWNpYWw7CiAJSXRlbUlkCQlscDsKIAlpbnQJCQlubGluZSwKLQkJ CQluc3RvcmFnZSwKIAkJCQludW51c2VkOwogCWludAkJCWk7CiAJU2l6ZQkJ dG90YWxsZW47CisJaXRlbUlkU29ydERhdGEgaXRlbWlkYmFzZVtNYXhIZWFw VHVwbGVzUGVyUGFnZV07CisJaXRlbUlkU29ydAlpdGVtaWRwdHIgPSBpdGVt aWRiYXNlOwogCiAJLyoKIAkgKiBJdCdzIHdvcnRoIHRoZSB0cm91YmxlIHRv IGJlIG1vcmUgcGFyYW5vaWQgaGVyZSB0aGFuIGluIG1vc3QgcGxhY2VzLApA QCAtNTc4LDE0ICs1NzksMjYgQEAgUGFnZVJlcGFpckZyYWdtZW50YXRpb24o UGFnZSBwYWdlKQogCQkJCQkJcGRfbG93ZXIsIHBkX3VwcGVyLCBwZF9zcGVj aWFsKSkpOwogCiAJbmxpbmUgPSBQYWdlR2V0TWF4T2Zmc2V0TnVtYmVyKHBh Z2UpOwotCW51bnVzZWQgPSBuc3RvcmFnZSA9IDA7CisJbnVudXNlZCA9IHRv dGFsbGVuID0gMDsKIAlmb3IgKGkgPSBGaXJzdE9mZnNldE51bWJlcjsgaSA8 PSBubGluZTsgaSsrKQogCXsKIAkJbHAgPSBQYWdlR2V0SXRlbUlkKHBhZ2Us IGkpOwogCQlpZiAoSXRlbUlkSXNVc2VkKGxwKSkKIAkJewogCQkJaWYgKEl0 ZW1JZEhhc1N0b3JhZ2UobHApKQotCQkJCW5zdG9yYWdlKys7CisJCQl7CisJ CQkJaXRlbWlkcHRyLT5vZmZzZXRpbmRleCA9IGkgLSAxOworCQkJCWl0ZW1p ZHB0ci0+aXRlbW9mZiA9IEl0ZW1JZEdldE9mZnNldChscCk7CisJCQkJaWYg KHVubGlrZWx5KGl0ZW1pZHB0ci0+aXRlbW9mZiA8IChpbnQpIHBkX3VwcGVy IHx8CisJCQkJCQkJIGl0ZW1pZHB0ci0+aXRlbW9mZiA+PSAoaW50KSBwZF9z cGVjaWFsKSkKKwkJCQkJZXJlcG9ydChFUlJPUiwKKwkJCQkJCQkoZXJyY29k ZShFUlJDT0RFX0RBVEFfQ09SUlVQVEVEKSwKKwkJCQkJCQkgZXJybXNnKCJj b3JydXB0ZWQgaXRlbSBwb2ludGVyOiAldSIsCisJCQkJCQkJCQlpdGVtaWRw dHItPml0ZW1vZmYpKSk7CisJCQkJaXRlbWlkcHRyLT5hbGlnbmVkbGVuID0g TUFYQUxJR04oSXRlbUlkR2V0TGVuZ3RoKGxwKSk7CisJCQkJdG90YWxsZW4g Kz0gaXRlbWlkcHRyLT5hbGlnbmVkbGVuOworCQkJCWl0ZW1pZHB0cisrOwor CQkJfQogCQl9CiAJCWVsc2UKIAkJewpAQCAtNTk1LDcgKzYwOCw3IEBAIFBh Z2VSZXBhaXJGcmFnbWVudGF0aW9uKFBhZ2UgcGFnZSkKIAkJfQogCX0KIAot CWlmIChuc3RvcmFnZSA9PSAwKQorCWlmIChpdGVtaWRwdHIgPT0gaXRlbWlk YmFzZSkKIAl7CiAJCS8qIFBhZ2UgaXMgY29tcGxldGVseSBlbXB0eSwgc28g anVzdCByZXNldCBpdCBxdWlja2x5ICovCiAJCSgoUGFnZUhlYWRlcikgcGFn ZSktPnBkX3VwcGVyID0gcGRfc3BlY2lhbDsKQEAgLTYwMywzNiArNjE2LDEz IEBAIFBhZ2VSZXBhaXJGcmFnbWVudGF0aW9uKFBhZ2UgcGFnZSkKIAllbHNl CiAJewogCQkvKiBOZWVkIHRvIGNvbXBhY3QgdGhlIHBhZ2UgdGhlIGhhcmQg d2F5ICovCi0JCWl0ZW1JZFNvcnREYXRhIGl0ZW1pZGJhc2VbTWF4SGVhcFR1 cGxlc1BlclBhZ2VdOwotCQlpdGVtSWRTb3J0CWl0ZW1pZHB0ciA9IGl0ZW1p ZGJhc2U7Ci0KLQkJdG90YWxsZW4gPSAwOwotCQlmb3IgKGkgPSAwOyBpIDwg bmxpbmU7IGkrKykKLQkJewotCQkJbHAgPSBQYWdlR2V0SXRlbUlkKHBhZ2Us IGkgKyAxKTsKLQkJCWlmIChJdGVtSWRIYXNTdG9yYWdlKGxwKSkKLQkJCXsK LQkJCQlpdGVtaWRwdHItPm9mZnNldGluZGV4ID0gaTsKLQkJCQlpdGVtaWRw dHItPml0ZW1vZmYgPSBJdGVtSWRHZXRPZmZzZXQobHApOwotCQkJCWlmIChp dGVtaWRwdHItPml0ZW1vZmYgPCAoaW50KSBwZF91cHBlciB8fAotCQkJCQlp dGVtaWRwdHItPml0ZW1vZmYgPj0gKGludCkgcGRfc3BlY2lhbCkKLQkJCQkJ ZXJlcG9ydChFUlJPUiwKLQkJCQkJCQkoZXJyY29kZShFUlJDT0RFX0RBVEFf Q09SUlVQVEVEKSwKLQkJCQkJCQkgZXJybXNnKCJjb3JydXB0ZWQgaXRlbSBw b2ludGVyOiAldSIsCi0JCQkJCQkJCQlpdGVtaWRwdHItPml0ZW1vZmYpKSk7 Ci0JCQkJaXRlbWlkcHRyLT5hbGlnbmVkbGVuID0gTUFYQUxJR04oSXRlbUlk R2V0TGVuZ3RoKGxwKSk7Ci0JCQkJdG90YWxsZW4gKz0gaXRlbWlkcHRyLT5h bGlnbmVkbGVuOwotCQkJCWl0ZW1pZHB0cisrOwotCQkJfQotCQl9Ci0KIAkJ aWYgKHRvdGFsbGVuID4gKFNpemUpIChwZF9zcGVjaWFsIC0gcGRfbG93ZXIp KQogCQkJZXJlcG9ydChFUlJPUiwKIAkJCQkJKGVycmNvZGUoRVJSQ09ERV9E QVRBX0NPUlJVUFRFRCksCiAJCQkgICBlcnJtc2coImNvcnJ1cHRlZCBpdGVt IGxlbmd0aHM6IHRvdGFsICV1LCBhdmFpbGFibGUgc3BhY2UgJXUiLAogCQkJ CQkgICh1bnNpZ25lZCBpbnQpIHRvdGFsbGVuLCBwZF9zcGVjaWFsIC0gcGRf bG93ZXIpKSk7CiAKLQkJY29tcGFjdGlmeV90dXBsZXMoaXRlbWlkYmFzZSwg bnN0b3JhZ2UsIHBhZ2UpOworCQljb21wYWN0aWZ5X3R1cGxlcyhpdGVtaWRi YXNlLCAoaW50KSAoaXRlbWlkcHRyIC0gaXRlbWlkYmFzZSksIHBhZ2UpOwog CX0KIAogCS8qIFNldCBoaW50IGJpdCBmb3IgUGFnZUFkZEl0ZW0gKi8KLS0g CjIuMTEuMAoK --=_5778ed9e6d9675b5bfcc7867b7e62884 Content-Type: text/plain Content-Disposition: inline Content-Transfer-Encoding: 8bit MIME-Version: 1.0 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers --=_5778ed9e6d9675b5bfcc7867b7e62884--