What affects the speed of a count(*) besides the number of records I have a query like

SELECT COUNT(*) FROM Foo Where Bar = 1 AND Baz = 2


the table has 12934600 records of which 1000001 match that predicate

Looking at the query statistics I see


  (1 row(s) affected) Table 'Foo'. Scan count 1, logical reads 1863,
  physical reads 0, read-ahead reads 0, lob logical reads 0, lob
  physical reads 0, lob read-ahead reads 0.
  
  (1 row(s) affected)
  
  SQL Server Execution Times:    CPU time = 250 ms,  elapsed time = 503
  ms.


Looking at the query plan 80% of the time is spent in a index seek on the Bar and Baz columns and 20% on aggregating the result. 

is there a way to speed this up and if so how? I would also like to understand which hardware components have a big influence here CPU or Disk IO or bus speed.
Bear in mind that the query plan shows an estimate of cost which is not the same as time.  The estimated cost values are a unitless aggregation of CPU, memory, and IO, not how long each operation takes to execute.  Also bear in mind that the cost values are estimates even in an "actual" execution plan.

The biggest bottleneck for this and most other SQL Server operations is disk IO.  Your example STATISTICS looks to be from a second run since there are no physical reads, though, so you see a higher CPU which is used for the aggregation/sorting.

You may be able to speed this particular query up with a filtered index, if your WHERE predicate is consistent (i.e. always Bar = 1 AND Baz = 2).

Otherwise I'm not aware of a way to speed it up beyond something more drastic like an indexed view.