Re: Call flow of btinsert(PG_FUNCTION_ARGS)

Hi All,

I was reading b tree index code and I wanted to the know the calling
function which calls
btinsert<http://doxygen.postgresql.org/nbtree_8c.html#a2b69e4abd6e38fbb317a503b8cf6e00a>
(PG_FUNCTION_ARGS<http://doxygen.postgresql.org/fmgr_8h.html#adf4dec9b7d23f1b4c68477affde8b7ff>)
function in nbtree.c file.
Moreover, my goal behind reading this function was to check how tuple is
inserted in btree.
I want to understand the code flow for b tree index

Please help!!

--
Regards,
Rohit Goyal

On Tue, Nov 19, 2013 at 2:22 AM, Rohit Goyal <rhtgyl(dot)87(at)gmail(dot)com> wrote:
>
> I was reading b tree index code and I wanted to the know the calling
> function which calls btinsert(PG_FUNCTION_ARGS) function in nbtree.c file.
> Moreover, my goal behind reading this function was to check how tuple is
> inserted in btree.
> I want to understand the code flow for b tree index

Take a look at this:

http://www.postgresql.org/docs/9.3/static/index-functions.html

--
Peter Geoghegan

On Tue, Nov 19, 2013 at 11:26 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:

> On Tue, Nov 19, 2013 at 2:22 AM, Rohit Goyal <rhtgyl(dot)87(at)gmail(dot)com> wrote:
> >
> > I was reading b tree index code and I wanted to the know the calling
> > function which calls btinsert(PG_FUNCTION_ARGS) function in nbtree.c
> file.
> > Moreover, my goal behind reading this function was to check how tuple is
> > inserted in btree.
> > I want to understand the code flow for b tree index
>
> Take a look at this:
>
> http://www.postgresql.org/docs/9.3/static/index-functions.html
>
>
> --
> Peter Geoghegan
>
thanks for reply. :) Moreover, I am so confused about reading the nbtree
folder c files or the file which you gave.

For example, If I want to read how the data is inserted in B tree index.
Should I read your link or the btinsert(PG_FUNCTION_ARGS) in nbtree.c file
in nbtree folder.

In future, if i want to modify btree indexing approach, then which files to
look for.?
--
Regards,
Rohit Goyal

On Tue, Nov 19, 2013 at 7:31 PM, Rohit Goyal <rhtgyl(dot)87(at)gmail(dot)com> wrote:
>
>
>
> On Tue, Nov 19, 2013 at 11:26 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>>
>> On Tue, Nov 19, 2013 at 2:22 AM, Rohit Goyal <rhtgyl(dot)87(at)gmail(dot)com> wrote:
>> >
>> > I was reading b tree index code and I wanted to the know the calling
>> > function which calls btinsert(PG_FUNCTION_ARGS) function in nbtree.c
>> > file.
>> > Moreover, my goal behind reading this function was to check how tuple is
>> > inserted in btree.
>> > I want to understand the code flow for b tree index
>>
>> Take a look at this:
>>
>> http://www.postgresql.org/docs/9.3/static/index-functions.html
>>
>>
>> --
>> Peter Geoghegan
>
> thanks for reply. :) Moreover, I am so confused about reading the nbtree
> folder c files or the file which you gave.
>
> For example, If I want to read how the data is inserted in B tree index.
> Should I read your link or the btinsert(PG_FUNCTION_ARGS) in nbtree.c file
> in nbtree folder.
>
> In future, if i want to modify btree indexing approach, then which files to
> look for.?

You could use gdb to debug a simple INSERT.

Take a look at the following also:

[http://www.postgresql.org/docs/devel/static/catalog-pg-am.html]

"The catalog pg_am stores information about index access methods.
There is one row for each index access method supported by the
system."

For example,

postgres=# \x
Expanded display (expanded) is on.
postgres=# select * from pg_am;
-[ RECORD 1 ]---+------------------
amname | btree
amstrategies | 5
amsupport | 2
amcanorder | t
amcanorderbyop | f
amcanbackward | t
amcanunique | t
amcanmulticol | t
amoptionalkey | t
amsearcharray | t
amsearchnulls | t
amstorage | f
amclusterable | t
ampredlocks | t
amkeytype | 0
aminsert | btinsert
ambeginscan | btbeginscan
amgettuple | btgettuple
amgetbitmap | btgetbitmap
amrescan | btrescan
amendscan | btendscan
ammarkpos | btmarkpos
amrestrpos | btrestrpos
ambuild | btbuild
ambuildempty | btbuildempty
ambulkdelete | btbulkdelete
amvacuumcleanup | btvacuumcleanup
amcanreturn | btcanreturn
amcostestimate | btcostestimate
amoptions | btoptions
...
...

Likewise you could find access method (am) details for other index types.

So, if you want to study the flow for a btree insert you could set a
gdb breakpoint in btinsert (listed as 'aminsert' for btree above) to
begin with.

--
Amit

On 11/19/2013 06:22 PM, Rohit Goyal wrote:
> Hi All,
>
> I was reading b tree index code and I wanted to the know the calling
> function which calls btinsert
> <http://doxygen.postgresql.org/nbtree_8c.html#a2b69e4abd6e38fbb317a503b8cf6e00a>(PG_FUNCTION_ARGS
> <http://doxygen.postgresql.org/fmgr_8h.html#adf4dec9b7d23f1b4c68477affde8b7ff>)
> function in nbtree.c file.

It's specified as a member of the btree index access method in
include/catalog/pg_am.h . All invocations are done via index access
method lookups; see the documentation for pg_catalog.pg_am, index access
methods, etc.

It's all abstracted so the core code doesn't know or care whether it's
using a b-tree, GiST, or something completely different. Relevant lines:

$ git grep '\<btinsert\>'

backend/access/nbtree/nbtree.c:btinsert(PG_FUNCTION_ARGS)

include/catalog/pg_am.h:DATA(insert OID = 403 ( btree 5 2 t f
t t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan
btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete
btvacuumcleanup btcanreturn btcostestimate btoptions ));

include/catalog/pg_proc.h:DATA(insert OID = 331 ( btinsert
PGNSP PGUID 12 1 0 0 0 f f f f t f v 6 0 16 "2281 2281 2281 2281 2281
2281" _null_ _null_ _null_ _null_ btinsert _null_ _null_ _null_ ));

See http://www.postgresql.org/docs/current/static/catalog-pg-am.html

In psql:

regress=> \x
regress=> select * from pg_am where amname = 'btree';
-[ RECORD 1 ]---+----------------
amname | btree
... snip ...
aminsert | btinsert
ambeginscan | btbeginscan
... snip ...

pg_catalog.pg_index rows refer to a vector of pg_opclass rows, one per
index column, and that in turns refers to pg_am via the opcmethod column.

http://www.postgresql.org/docs/current/static/catalog-pg-index.html
http://www.postgresql.org/docs/current/static/catalog-pg-am.html
http://www.postgresql.org/docs/current/static/catalog-pg-opclass.html

See:

This query demonstrates the relationship. It'd be smarter to properly
separate out each column but I couldn't be bothered, so it just prints
one row per index column in multicolumn indexes, not preserving order.

regress=> select c.relname, oc.opcname, am.amname, am.aminsert
from pg_index i
inner join pg_class c on (i.indexrelid = c.oid)
inner join pg_opclass oc ON (oc.oid = ANY(i.indclass))
inner join pg_am am ON (oc.opcmethod = am.oid);

All the executor knows is how to ask, eg "for this column of this index,
what opclass was specified, and for that opclass, what is the oid of the
function to perform the insert access-method operation".

It has no idea it's calling btinsert.

Try creating a GiST or GIN index and compare. It might help clarify things.

> I want to understand the code flow for b tree index

It'll take time, but stepping/jumping through it with a debugger will
probably be a good way to do that. Connect a psql session, run "SELECT
pg_backend_pid()", attach gdb to that pid, set breakpoints at the entry
points of interest, cont, then run a command in psql that'll trigger one
of the breakpoints. From there you can step through and watch what it
does, using "next" to skip over function invocations you aren't
interested in and "step" to enter ones you are.

--
Craig Ringer http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Nov 19, 2013 at 11:52 AM, Craig Ringer <craig(at)2ndquadrant(dot)com>wrote:

> On 11/19/2013 06:22 PM, Rohit Goyal wrote:
> > Hi All,
> >
> > I was reading b tree index code and I wanted to the know the calling
> > function which calls btinsert
> > <
> http://doxygen.postgresql.org/nbtree_8c.html#a2b69e4abd6e38fbb317a503b8cf6e00a
> >(PG_FUNCTION_ARGS
> > <
> http://doxygen.postgresql.org/fmgr_8h.html#adf4dec9b7d23f1b4c68477affde8b7ff
> >)
> > function in nbtree.c file.
>
> It's specified as a member of the btree index access method in
> include/catalog/pg_am.h . All invocations are done via index access
> method lookups; see the documentation for pg_catalog.pg_am, index access
> methods, etc.
>
> It's all abstracted so the core code doesn't know or care whether it's
> using a b-tree, GiST, or something completely different. Relevant lines:
>
> $ git grep '\<btinsert\>'
>
> backend/access/nbtree/nbtree.c:btinsert(PG_FUNCTION_ARGS)
>
> include/catalog/pg_am.h:DATA(insert OID = 403 ( btree 5 2 t f
> t t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan
> btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete
> btvacuumcleanup btcanreturn btcostestimate btoptions ));
>
> include/catalog/pg_proc.h:DATA(insert OID = 331 ( btinsert
> PGNSP PGUID 12 1 0 0 0 f f f f t f v 6 0 16 "2281 2281 2281 2281 2281
> 2281" _null_ _null_ _null_ _null_ btinsert _null_ _null_ _null_ ));
>
>
> See http://www.postgresql.org/docs/current/static/catalog-pg-am.html
>
> In psql:
>
> regress=> \x
> regress=> select * from pg_am where amname = 'btree';
> -[ RECORD 1 ]---+----------------
> amname | btree
> ... snip ...
> aminsert | btinsert
> ambeginscan | btbeginscan
> ... snip ...
>
>
> pg_catalog.pg_index rows refer to a vector of pg_opclass rows, one per
> index column, and that in turns refers to pg_am via the opcmethod column.
>
> http://www.postgresql.org/docs/current/static/catalog-pg-index.html
> http://www.postgresql.org/docs/current/static/catalog-pg-am.html
> http://www.postgresql.org/docs/current/static/catalog-pg-opclass.html
>
>
>
> See:
>
> This query demonstrates the relationship. It'd be smarter to properly
> separate out each column but I couldn't be bothered, so it just prints
> one row per index column in multicolumn indexes, not preserving order.
>
>
> regress=> select c.relname, oc.opcname, am.amname, am.aminsert
> from pg_index i
> inner join pg_class c on (i.indexrelid = c.oid)
> inner join pg_opclass oc ON (oc.oid = ANY(i.indclass))
> inner join pg_am am ON (oc.opcmethod = am.oid);
>
>
> All the executor knows is how to ask, eg "for this column of this index,
> what opclass was specified, and for that opclass, what is the oid of the
> function to perform the insert access-method operation".
>
> It has no idea it's calling btinsert.
>
> Try creating a GiST or GIN index and compare. It might help clarify things.
>
> > I want to understand the code flow for b tree index
>
> It'll take time, but stepping/jumping through it with a debugger will
> probably be a good way to do that. Connect a psql session, run "SELECT
> pg_backend_pid()", attach gdb to that pid, set breakpoints at the entry
> points of interest, cont, then run a command in psql that'll trigger one
> of the breakpoints. From there you can step through and watch what it
> does, using "next" to skip over function invocations you aren't
> interested in and "step" to enter ones you are.
>
> --
> Craig Ringer http://www.2ndQuadrant.com/
> PostgreSQL Development, 24x7 Support, Training & Services
>

Please tel me how to attached gdb to pid and debug.

Also what I understood from your reply is that everything is abstracted, so
am doesnot care abt backend implementation. Now, I want to modify B tree
indexing scheme. So, which files I should focus ?

Regards,
Rohit Goyal

Hi Rohit,

On 2013-11-19 13:11:12 +0100, Rohit Goyal wrote:
> Please tel me how to attached gdb to pid and debug.

> Also what I understood from your reply is that everything is abstracted, so
> am doesnot care abt backend implementation. Now, I want to modify B tree
> indexing scheme. So, which files I should focus ?

I am sorry to be harsh, but these type of questions don't really seem to
be on-topic for -hackers. Several people gave you hints where to start
reading, but from there on you need to take the lead yourself.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 11/19/2013 08:11 PM, Rohit Goyal wrote:
>
> Also what I understood from your reply is that everything is abstracted,
> so am doesnot care abt backend implementation. Now, I want to modify B
> tree indexing scheme. So, which files I should focus ?

Depends on whether you can do what you want without modifying the index
access method. You still haven't explained what you are trying to
achieve, what your goal is.

I don't think this conversation is productive. There's plenty of
existing documentation to review to help you get started, and you can
find guides on how to use gdb everywhere across the Internet. The code
is full of comments.

If you had a detailed, specific question maybe someone here could help
you. Without that you're just going to have to start learning the
relevant code.

--
Craig Ringer http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services