Subject: Re: GiST VACUUM
To: Andrey Borodin <x4mmm@yandex-team.ru>
Cc: Thomas Munro <thomas.munro@enterprisedb.com>,
 Robert Haas <robertmhaas@gmail.com>,
 pgsql-hackers <pgsql-hackers@postgresql.org>,
 =?UTF-8?B?0JrQvtGB0YLRjyDQmtGD0LfQvdC10YbQvtCy?= <chapaev28@ya.ru>
References: <77c7023c-18d4-8f04-08ed-a5c5633046ea@iki.fi>
 <50d0105a-bd99-788e-37ee-51f59d81fbec@iki.fi>
 <CA+TgmoZKrUDtWkerVNX+O-yTYoNj2bjUxR5GvmbaCK-TVnDqEw@mail.gmail.com>
 <0E0DF52D-8E01-4A37-A9C5-3B9A7E6E53DD@yandex-team.ru>
 <2DA06ECF-EB35-49B3-9F8D-4BB1800B755D@yandex-team.ru>
 <b015d1dc-67d7-0b10-c5ab-0ae3f20f34eb@iki.fi>
 <ADA3A0B7-A209-48E5-8942-BA913C3FD31D@yandex-team.ru>
 <66dffd3a-b9d5-65cf-15bf-615a83b44301@iki.fi>
 <5A3FD588-BC51-4FC3-B9C3-19453F824C68@yandex-team.ru>
 <927581532000526@myt5-31f0319c46b9.qloud-c.yandex.net>
 <266d7c7e-7431-b6dc-e4af-7ec9f08b5e52@iki.fi>
 <479336FE-B713-4DFB-9661-9BFCCA70F4EF@yandex-team.ru>
 <51675201-3F1C-4796-ADB4-28D0B35E9CF0@yandex-team.ru>
 <651572F0-65C3-4285-85FC-50E81B1199F1@yandex-team.ru>
 <CAEepm=1vznVTZf01f4KNVJEa4m4tCgtBuumgmY8q=g+S=Gdt5A@mail.gmail.com>
 <2AF4B7F1-ABCF-4602-8AF8-06EA45191BFC@yandex-team.ru>
 <844f3373-486e-a34d-d5a1-6a048e19355c@iki.fi>
 <4A1FF988-A69D-4607-8A6E-B3EC0FD6C2CF@yandex-team.ru>
From: Heikki Linnakangas <hlinnaka@iki.fi>
Message-ID: <43f15ab5-dd95-97d4-658b-e9954ca986a6@iki.fi>
Date: Sun, 5 Aug 2018 14:18:59 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.9.1
MIME-Version: 1.0
In-Reply-To: <4A1FF988-A69D-4607-8A6E-B3EC0FD6C2CF@yandex-team.ru>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 31/07/18 23:06, Andrey Borodin wrote:
>> On a typical GiST index, what's the ratio of leaf vs. internal
>> pages? Perhaps an array would indeed be better.
 >
> Typical GiST has around 200 tuples per internal page. I've switched
> to List since it's more efficient than bitmap.

Hmm. A ListCell is 16 bytes, plus the AllocChunk header, 16 bytes. 32
bytes per internal page in total, while a bitmap consumes one bit per 
page, leaf or internal. If I'm doing
my math right, assuming the ratio of leaf pages vs internal pages is
1:200, a List actually consumes more memory than a bitmap; 256 bits per
internal page, vs. 200 bits. An array, with 4 bytes per block number,
would be the winner here.

> But I have to note that default growth strategy of Bitmap is not 
> good: we will be repallocing byte by byte.

True, that repallocing seems bad. You could force it to be pre-allocated
by setting the last bit. Or add a function to explicitly enlarge the bitmap.

- Heikki