Home Ask Login Register

Developers Planet

Your answer is one click away!

MetaChrome February 2016

Does postgresql have O(1) lookups against the clustered index?

The questions are the following:

  1. Does postgresql (or other database implementations) have O(1) lookups against the clustered index? ie, a direct lookup of the row position on the file system from the row's id (where the id column is the clustered index)

  2. If there is no way to do a such lookups, is the lookup for a row by id log2n?

  3. Considering this, does postgresql or any sql engine have a way to have indexes yield positions to rows in other tables to avoid this?
  4. Does postgresql or any sql engine have a way to lookup rows directly (and the lifecycle associated with how rows are moved)? I am presuming rows don't move relative to database engine storage format unless the clustered index is changed...

These questions stem from the following junction table necessary for implementing many-to-many relationships:



retrieving set of child_ids

select * from junction_table where parent_id=parent_value

a fundamentally correct implementation should yield a set of locations for the child rows worse, at least a way to calculate child rows positions from the set of child_ids

VS a one-to-many query that yields the direction location of the child row:



select * from child_table where p_id=parent_value


Rick James February 2016

Many Issues -- Let me mention each, the put the pieces together.

BTrees, by their nature are O(logn). But, you can think of it pretty much as O(1). A BTree might typically have 100 child links in each node. That says that a million rows would be only 3 levels deep; a trillion rows would be about 6 levels deep.

Furthermore, LRU caching (such as MySQL does at the block level) tends to keep at least the non-leaf nodes in cache. (Having what you need in cache is the real optimization for large databases.)

B+Tree -- Take a BTree and add bidirectional links between the leaf nodes. This makes "range scans" very efficient.

B+Tree indexes are the "best overall".

Clustering In this context, let's say that 'clustering' implies that the unique row identifier is stored with the data. (For MySQL, that's the PRIMARY KEY; some others us a 'rownum'.)

PRIMARY KEY may be clustered and/or unique -- this varies with database implementations.

Secondary key is usually a BTree, but getting from it to the data is implemented in different ways. It might point directly to the data; it might have a "rownum", which can be used to find the record; or it might have a copy of the Primary key, thereby allowing the lookup of the row via the PK.

MyISAM's InnoDB -- A PRIMARY KEY is clustered with the data, organized as a B+Tree, and unique. This implies that a point query by the PK will do one dive in a BTree to find the entire row.

A Secondary key in InnoDB has a separate BTree, and a copy of the PK is found in the leaf node. So, a secondary key lookup is two dives (one in secondary BTree, one in PK+data BTree). That is, unless the index is 'covering' and all the columns needed (for a SELECT) are found in the Secondary key + primary key.

Post Status

Asked in February 2016
Viewed 2,016 times
Voted 7
Answered 1 times


Leave an answer

Quote of the day: live life