pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Robert Haas <robertmhaas@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
Date: Tue, 16 Aug 2011 15:04:37 +0300
Message-ID: <4E4A5CD5.2040601@enterprisedb.com> (raw)
In-Reply-To: <CAPpHfdtMe6yizpbT+Lsx0mWSW9thPV9KosSrUsSEMNRBHUWUPw@mail.gmail.com>
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@mail.gmail.com>
	<4E31D03D.70206@enterprisedb.com>
	<CAPpHfdtmgwOjNr7J15eCe6sXrtmq_c_52oNh-=D934SKekoGxg@mail.gmail.com>
	<CAPpHfdv=HQDmUGTARKjH+AiHMDpXa+8+WwuqjUSfZnVdC-LJbQ@mail.gmail.com>
	<CAPpHfduAhSNo8LHMPj_pqQ_2W6ZDPzdQBPzHbnpqaKz6kf4nrw@mail.gmail.com>
	<4E3977D8.1020506@enterprisedb.com>
	<CAPpHfducs8Ussw+t8iP3WS3ZTuX2J-77FOY=jAZUg-K6AuOC0g@mail.gmail.com>
	<CAPpHfdusd_b_dtvNY2uuJict6=VEUTGAS8ELXGck=o=kOdMnOw@mail.gmail.com>
	<4E3FAB1D.1060105@enterprisedb.com>
	<CAPpHfdsovwbgs30TojJc_zDsc+0ghapm+-AALfP58UaHiYjr2A@mail.gmail.com>
	<CAPpHfdvi5WZKdRD+s60R+pdm8dLczRQ5_RYt4L8OA_bhorPjpg@mail.gmail.com>
	<4E42DFCE.3050904@enterprisedb.com>
	<CAPpHfdvhoYKUUCVaC-yFbDaE5j2QTa94cVgYuKnzX4xwWUjSTg@mail.gmail.com>
	<CA+TgmoZoON6aAE3NB9=GF9oAdF=Kkz21+MmoE5P_kA9aKN-OQA@mail.gmail.com>
	<CAPpHfdu4DusbHtMLE+csQJj61rMg_JtFOGSwrQVoOF5wPBkixQ@mail.gmail.com>
	<CAPpHfdtMe6yizpbT+Lsx0mWSW9thPV9KosSrUsSEMNRBHUWUPw@mail.gmail.com>

Looking at the calculation of levelStep:

> + 	/*
> + 	 * Calculate levelStep by available amount of memory. We should be able to
> + 	 * load into main memory one page of each underlying node buffer (which
> + 	 * are in levelStep below). That give constraint over
> + 	 * maintenance_work_mem. Also we should be able to have subtree of
> + 	 * levelStep level in cache. That give constraint over
> + 	 * effective_cache_size.
> + 	 *
> + 	 * i'th underlying level of sub-tree can consists of
> + 	 * i^maxIndexTuplesPerPage pages at maximum. So, subtree of levelStep
> + 	 * levels can't be greater then 2 * maxIndexTuplesPerPage ^ levelStep
> + 	 * pages. We use some more reserve due to we probably can't take whole
> + 	 * effective cache and use formula 4 * maxIndexTuplesPerPage ^ levelStep =
> + 	 * effectiveCache. We use similar logic with maintenance_work_mem. We
> + 	 * should be able to store at least last pages of all buffers where we are
> + 	 * emptying current buffer to.
> + 	 */
> + 	effectiveMemory = Min(maintenance_work_mem * 1024 / BLCKSZ,
> + 						  effective_cache_size);
> + 	levelStep = (int) log((double) effectiveMemory / 4.0) /
> + 		log((double) maxIndexTuplesPerPage);
> +

I can see that that's equal to the formula given in the paper, 
log_B(M/4B), but I couldn't see any explanation for that formula in the 
paper. Your explanation makes sense, but where did it come from?

It seems a bit pessimistic: while it's true that the a subtree can't be 
larger than 2 * maxIndexTuplesPerPage ^ levelStep, you can put a tighter 
upper bound on it. The max size of a subtree of depth n can be 
calculated as the geometric series:

r^0 + r^1 + r^2 + ... + r^n = (1 - r^(n + 1)) / (1 - r)

where r = maxIndexTuplesPerPage. For r=2 those formulas are equal, but 
for a large r and small n (which is typical), the 2 * 
maxIndexTuplesPerPage^levelStep formula gives a value that's almost 
twice as large as the real max size of a subtree.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com



view thread (114+ messages)  latest in thread

Message-ID: <4E4A5CD5.2040601@enterprisedb.com>
Permalink:  ../4E4A5CD5.2040601@enterprisedb.com/
Also on:    postgresql.org/message-id/4E4A5CD5.2040601@enterprisedb.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-hackers@postgresql.org
  Cc: heikki.linnakangas@enterprisedb.com, aekorotkov@gmail.com, robertmhaas@gmail.com
  Subject: Re: WIP: Fast GiST index build
  In-Reply-To: <4E4A5CD5.2040601@enterprisedb.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox