Re: GSoC proposal. Index-only scans for GIST

Alexander,

Can you comment on the below proposal?  I'd like your opinion on how
difficult it will be.

On 03/18/2014 06:12 AM, Anastasia Lubennikova wrote:
> Hello!
> Here is the text of my proposal which I've applied to GSoC.
> (and link
> http://www.google-melange.com/gsoc/proposal/public/google/gsoc2014/lubennikovaav/5629499534213120)
> Any suggestions and comments are welcome.
>

> *Project name*

>
> Support for index-only scans for GIST index
>
>
>

> *Brief review*

>
> Currently GiST index don't have index-only scan functionality. Index-only
> scans are a major performance feature added to Postgres 9.2. They allow
> certain types of queries to be satisfied just by retrieving data from
> indexes, and not from tables. This feature for B-trees (implemented since
> PostgreSQL-9.2) allows doing certain types of queries significantly faster.
> This is achieved by reduction in the amount of I/O necessary to satisfy
> queries. I think it will be useful to implement this feature for user
> defined data types that use GiST index.
>
>
>

> *Benefits to the PostgreSQL Community*

>
> Faster GiST index search would be actual for many PostgreSQL applications
> (for example some GIS systems).
>
>

>  *Quantifiable results*

>
> Acceleration of GiST index search.
>
>

> *Project details*

>
> 1. The GiST is a balanced tree structure like a B-tree, containing <key,
> pointer> pairs. GiST key is a member of a user-defined class, and
> represents some property that is true of all data items reachable from the
> pointer associated with the key. The GiST provides a possibility to create
> custom data types with indexed access methods and extensible set of queries.
>
> There are seven methods that an index operator class for GiST must provide,
> and an eighth that is optional.
>
> -consistent
>
> -union
>
> -compress
>
> -decompress
>
> -penalty
>
> -picksplit
>
> -equal
>
> -distance (optional)
>
> I'm going to create new optional method fetch() in addition to existing.
> Thus user can create a method of retrieving data from the index without
> loss. It will be used when performing search queries to speed data
> retrieving.
>
>
>
> 2. gistget algorithm (several parts omitted):
>
> Check the key
> gistindex_keytest() - does this index tuple satisfy the scan key(s)?
>
> Scan all items on the GiST index page and insert them into the queue (or
> directly to output areas)
>
> plain scan
>
> Heap tuple TIDs are returned into so->pageData[]
>
> ordered scan
>
> Heap tuple TIDs are pushed into individual search queue items
>
> If the fetch() is specified by the developer, then using it, algorithm can
> retrieve the data directly to output areas at this stage, without reference
> to the heap.
>
>
> 3. Create function gistcanreturn to check whether fetch() is specified by
> user.
>
> Amcanreturn - Function to check whether index supports index-only scans, or
> zero if none
>
> There is the question of support index-only scans for multicolumn indexes.
> Probably it would require extend the interface to add separate columns
> checking.
>
> To solve this question I need the community's help.
>
>
> 4. Add details for index only scans into gistcostestimate function
>
>
>

>  *Links*

>
> 1)     Hellerstein J. M., Naughton J. F., Pfeffer A. Generalized search
> trees for database systems. - September, 1995.
>
> 2)     http://www.sai.msu.su/~megera/postgres/gist/
>
> 3)     PostgreSQL 9.3.3 Documentation: chapters 11. Indexes, 55. GiST
> Indexes.
>


--

Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com