4 ms·

am i wrong in thinking that a missing index can change an O(logn) query to an O(n), while an additional index is going to add a constant cost to writes? becaus

am i wrong in thinking that a missing index can change an O(logn) query to an O(n), while an additional index is going to add a constant cost to writes? because if that's correct then it makes sense to err on the side of too many indices. of course, it is better to be perfect. but if you have an error, which side would you prefer to be on? and you don't need "significant" volumes to hurt with a full table scan (ie it will hurt most of you). [what surprised me was the 99% cache. that is very dependent on your application, but i guess is common for web apps?]

craigkerstiens 14y ago
The 99% cache recommendation is absolutely for web applications. Most web applications will want queries to return in less than 10 ms and are only retrieving a small amount of data. With data warehousing and reporting applications this definitely changes.
chanks 14y ago
One thing people don't mention that often with Postgres, but is worth some attention, is the Heap-Only Tuples (HOT) optimization that was added in 8.3. During an UPDATE, Postgres will try to fit the new version of the row on the same page as the old one - if it's able to do this, it means the indices don't have to be updated at all. So if you're expecting a table to have a heavy UPDATE load it may be a good idea to lower its fillfactor from the default of 100 (for example, ALTER TABLE foo SET (fillfactor = 95);). This means that once a page is 95% full no new rows will be inserted into it, and the remaining 5% will be available for updated rows. HOT will also do "mini-vacuums" on individual pages as needed to free up space. Of course, it's up to you to decide whether this tradeoff is worth increasing the effective size of your table by ~5%. But even tables with fillfactors at the default of 100 will get some benefit from HOT. More info: https://github.com/postgres/postgres/blob/master/src/backend/access/heap/README.HOT https://github.com/postgres/postgres/blob/master/src/backend... Edit to add: One caveat is that HOT won't work if you UPDATE a column that is indexed - then, of course, Postgres will have to touch the index.
btilly 14y ago
You are correct. However high performance applications are usually not brought down by occasional slow operations, but rather by a myriad of more expensive than needed ones.
joevandyk 14y ago
It would be nice to have a program that analyzed postgresql statistics and queries and made observations/recommendations. This might be much easier to do with the new pg_stat_statements extension in 9.2.
lmm 14y ago
If n is your number of rows, adding a constant cost to each write is an O(n) total penalty. But the asymptotic performance isn't really the point for many real-world workloads (e.g. an O(1) hashtable lookup is generally much slower than an O(n) linked list traversal). As the grandparent says, read performance problems are generally easier to work around than write performance ones, and reporting aggregation reads (which are the ones that tend to require table scans) are often far less time-sensitive than writes.
cafard 14y ago
The problem you can run into, and this will depend on the state of your optimizer, is that you may have a join, and the presence of the index may give you a nested-loops path when a hash join would be more efficient.
- jeltz 14y ago
  The PostgreSQL optimizer is cost based and uses statistics to choose join method. So that problem is quite rare and is best debugged using EXPLAIN/EXPLAIN ANALYZE.
Someone 14y ago
I do not think an extra index adds a constant cost to writes. If it is an index that allows for range queries (I haven't seen 'equality-only' indices, but that probably is because I haven't looked hard enough), writing an index entry is (or should be) like an insert into a sorted dictionary. That will be O(logn).
- btilly 14y ago
  You are right that indexes are usually (though not always!) implemented as a tree. But in practice the number of levels of that tree is usually fixed, so in practice it is constant. (And the number of writes to disk per write to the index averages under 1 - the top levels generally get overwritten multiple times before they have to hit disk on a checkpoint, and sometimes the leaf gets overwritten again.)
  - Someone 14y ago
    But that would mean you would have to make it wider and wider. That cannot be done at O(1) time, can it? Or are they just starting a second, third, etc. tree whenever one fills up? If so, what is the benefit over adding another level? More localized disk I/O during writing? Do you have a reference?
    - btilly 14y ago
      http://www.stanford.edu/class/cs276a/projects/docs/berkeleydb/ref/am_conf/cachesize.html http://www.stanford.edu/class/cs276a/projects/docs/berkeleyd... describes the performance of BTree data structures in real world databases. (It is discussing a standalone key/value store, but the internals of a database index work the same way.) As noted, 3 levels suffices for a moderate sized table, and it would be rare to need more than 5 levels. The "levels" in question are pages of memory that have to be looked at. The reason that this is less than you expect is that inside of each page you essentially have a tree that has several levels to traverse. However the time to traverse that tree is less than the time to fetch the next page, so the operations of concern are fetches of pages. The most important number noted in that link is that under normal operation once caches are warmed up, it should a maximum of one disk seek to traverse the index. That single disk seek, if it happens, takes longer than all other operations. The long and short of it is, "in theory log(n), in practice a reasonably small constant."

craigkerstiens 14y ago

The 99% cache recommendation is absolutely for web applications. Most web applications will want queries to return in less than 10 ms and are only retrieving a small amount of data. With data warehousing and reporting applications this definitely changes.

chanks 14y ago

One thing people don't mention that often with Postgres, but is worth some attention, is the Heap-Only Tuples (HOT) optimization that was added in 8.3. During an UPDATE, Postgres will try to fit the new version of the row on the same page as the old one - if it's able to do this, it means the indices don't have to be updated at all. So if you're expecting a table to have a heavy UPDATE load it may be a good idea to lower its fillfactor from the default of 100 (for example, ALTER TABLE foo SET (fillfactor = 95);). This means that once a page is 95% full no new rows will be inserted into it, and the remaining 5% will be available for updated rows. HOT will also do "mini-vacuums" on individual pages as needed to free up space. Of course, it's up to you to decide whether this tradeoff is worth increasing the effective size of your table by ~5%. But even tables with fillfactors at the default of 100 will get some benefit from HOT. More info: https://github.com/postgres/postgres/blob/master/src/backend/access/heap/README.HOT https://github.com/postgres/postgres/blob/master/src/backend... Edit to add: One caveat is that HOT won't work if you UPDATE a column that is indexed - then, of course, Postgres will have to touch the index.

btilly 14y ago

You are correct. However high performance applications are usually not brought down by occasional slow operations, but rather by a myriad of more expensive than needed ones.

joevandyk 14y ago

It would be nice to have a program that analyzed postgresql statistics and queries and made observations/recommendations. This might be much easier to do with the new pg_stat_statements extension in 9.2.

lmm 14y ago

If n is your number of rows, adding a constant cost to each write is an O(n) total penalty. But the asymptotic performance isn't really the point for many real-world workloads (e.g. an O(1) hashtable lookup is generally much slower than an O(n) linked list traversal). As the grandparent says, read performance problems are generally easier to work around than write performance ones, and reporting aggregation reads (which are the ones that tend to require table scans) are often far less time-sensitive than writes.

cafard 14y ago

The problem you can run into, and this will depend on the state of your optimizer, is that you may have a join, and the presence of the index may give you a nested-loops path when a hash join would be more efficient.

jeltz 14y ago
The PostgreSQL optimizer is cost based and uses statistics to choose join method. So that problem is quite rare and is best debugged using EXPLAIN/EXPLAIN ANALYZE.

Someone 14y ago

I do not think an extra index adds a constant cost to writes. If it is an index that allows for range queries (I haven't seen 'equality-only' indices, but that probably is because I haven't looked hard enough), writing an index entry is (or should be) like an insert into a sorted dictionary. That will be O(logn).

btilly 14y ago
You are right that indexes are usually (though not always!) implemented as a tree. But in practice the number of levels of that tree is usually fixed, so in practice it is constant. (And the number of writes to disk per write to the index averages under 1 - the top levels generally get overwritten multiple times before they have to hit disk on a checkpoint, and sometimes the leaf gets overwritten again.)
- Someone 14y ago
  But that would mean you would have to make it wider and wider. That cannot be done at O(1) time, can it? Or are they just starting a second, third, etc. tree whenever one fills up? If so, what is the benefit over adding another level? More localized disk I/O during writing? Do you have a reference?
  - btilly 14y ago
    http://www.stanford.edu/class/cs276a/projects/docs/berkeleydb/ref/am_conf/cachesize.html http://www.stanford.edu/class/cs276a/projects/docs/berkeleyd... describes the performance of BTree data structures in real world databases. (It is discussing a standalone key/value store, but the internals of a database index work the same way.) As noted, 3 levels suffices for a moderate sized table, and it would be rare to need more than 5 levels. The "levels" in question are pages of memory that have to be looked at. The reason that this is less than you expect is that inside of each page you essentially have a tree that has several levels to traverse. However the time to traverse that tree is less than the time to fetch the next page, so the operations of concern are fetches of pages. The most important number noted in that link is that under normal operation once caches are warmed up, it should a maximum of one disk seek to traverse the index. That single disk seek, if it happens, takes longer than all other operations. The long and short of it is, "in theory log(n), in practice a reasonably small constant."