Re: I'd like to learn a bit more about how indexes work

If you want to discover how B+Trees or B-Trees work, I suggest a web search.  A database like PostgreSQL is not going
touse an ordinary btree for an index, but they use special trees that have page level structures, such as B-Trees, GiST
trees,etc.    For PostgreSQL the list includes {IIRC} B-tree, Hash, GiST and GIN, though I am not sure it is current.
Ibelieve that there is also a GIS extension to PostgreSQL which probably uses Octrees or Quadtrees, but that is purely
aguess. 
Place this criteria into your favorite search engine, for instance:
"B-Tree" index

You can qualify it with "PostgreSQL" if you like, but I suspect you just want to know how indexes work in general with
differentindex types. 

I suspect that what you really want to eventually understand is:

"How does the optimizer make plans to create efficient queries" which is what is indicated in your questions below.

If that is the case, then I suggest performing search queries with keywords such as:
sql cost based optimizer

-----Original Message-----
From: pgsql-general-owner@postgresql.org [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Mike Christensen
Sent: Tuesday, June 05, 2012 3:25 PM
To: pgsql-general@postgresql.org
Subject: [GENERAL] I'd like to learn a bit more about how indexes work

Hi -

I'm trying to increase my general knowledge about how indexes work in databases.  Though my questions are probably
generaland implemented in a similar way across major relational DBs, I'm also curious as to how they're implemented in
Postgresspecifically (mainly because I like PG, and am always interested in knowing if PG does things in some cool and
interestingway). 

I know the basics of how binary trees work, so I understand a query such as :

select * from Table where Id = 5;

Provided Id has a btree index on it.  I'm curious as to how indexes are used with OR and AND clauses.

Something like:

select * from Table where X = 5 or y = 3;

It seems to me both the index of X would be scanned and those rows would be loaded into memory, and then the index of Y
wouldbe scanned and loaded.  Then, Postgres would have to merge both sets into a set of unique rows.  Is this pretty
muchwhat's going on?  Let's ignore table stats for now. 

Then, something like:

select * from Table where X = 5 AND y = 3;

I would imagine the same thing is going on, only Postgres would find rows that appear in both sets.  I also imagine
Postgresmight create a hash table from the larger set, and then iterate through the smaller set looking for rows that
werein that hash table. 

Lastly, If you had a query such as:

select * from Table where X IN (1,2,3,4,5,6,7);

I would imagine Postgres would parse that query as a bunch of OR clauses.  Does this mean the index for X would be
scanned7 times and merged into a set of unique results?  Though, obviously if Postgres estimated this would return the
majorityof the rows in the table, it would probably just ignore the index completely. 

Thanks!
Mike

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general