PFC wrote:
On Wed, 21 May 2008 16:10:53 +0200, H. Hall wrote:
Does anyone know if there is a source that provides "Big O" notation
for postgres's aggregate functions and operations? For example is
count(*) = O(1) or O(n)?
Do the developers for postgres use Big O when selecting algorithms?
If so, is the info easily available?
You can't do any better than O( n rows examined by the aggregate )
except for max() and min() on an indexed expression, which in this
case aren't really aggrgates anymore since they are internally
rewritten as an index lookup to get the value you want... but stuff
like sum() or avg() or count() will always have to see all the rows
selected (and some more) unless you use clever hacks like materialized
views etc, in which case the thing in the O() will change, or at least
the O() constant will change...
Thank you PFC and also Jonah, and Richard for your replies.
It occurs to me that Big O might be a useful way to understand/explain
what is happening with situations like Albert's earlier today:
I've got a query similar to this:
>
> select * from t1, t2 where t1.id > 158507 and t1.id = t2.id;
>
> That took > 84 minutes (the query was a bit longer but this is the part
> that made the difference) after a little change the query took ~1 second:
>
> select * from t1, t2 where t1.id > 158507 and t2.id > 158507 and t1.id =
> t2.id;
BTW, anyone reading this and not familiar with Big O notation might want
to check out these links. All are intro type articles:
* An informal introduction to O(N) notation:
http://www.perlmonks.org/?node_id=227909
* Analysis of Algorithms and Selection of Algorithms:
http://www.cs.utk.edu/~parker/Courses/CS302-Fall06/Notes/complexity.html
* Complexity and Big-O Notation
http://pages.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html
--
H. Hall
ReedyRiver Group LLC
http://www.reedyriver.com
