StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>On a table with 158k pseudo-random rows (usr_id uniformly distributed between 0 and 10k, <code>trans_id</code> uniformly distributed between 0 and 30),</p> <p><em>By query cost, below, I am referring to Postgres' cost based optimizer's cost estimate (with Postgres' default <code>xxx_cost</code> values), which is a weighed function estimate of required I/O and CPU resources; you can obtain this by firing up PgAdminIII and running "Query/Explain (F7)" on the query with "Query/Explain options" set to "Analyze"</em></p> <ul> <li>Quassnoy's query has a cost estimate of 745k (!), and completes in 1.3 seconds (given a compound index on (<code>usr_id</code>, <code>trans_id</code>, <code>time_stamp</code>))</li> <li>Bill's query has a cost estimate of 93k, and completes in 2.9 seconds (given a compound index on (<code>usr_id</code>, <code>trans_id</code>))</li> <li><strong>Query #1 below</strong> has a cost estimate of 16k, and completes in 800ms (given a compound index on (<code>usr_id</code>, <code>trans_id</code>, <code>time_stamp</code>))</li> <li><strong>Query #2 below</strong> has a cost estimate of 14k, and completes in 800ms (given a compound function index on (<code>usr_id</code>, <code>EXTRACT(EPOCH FROM time_stamp)</code>, <code>trans_id</code>)) <ul> <li>this is Postgres-specific</li> </ul></li> <li><strong>Query #3 below</strong> (Postgres 8.4+) has a cost estimate and completion time comparable to (or better than) query #2 (given a compound index on (<code>usr_id</code>, <code>time_stamp</code>, <code>trans_id</code>)); it has the advantage of scanning the <code>lives</code> table only once and, should you temporarily increase (if needed) <a href="http://www.postgresql.org/docs/current/static/runtime-config-resource.html#GUC-WORK-MEM" rel="noreferrer">work_mem</a> to accommodate the sort in memory, it will be by far the fastest of all queries.</li> </ul> <p>All times above include retrieval of the full 10k rows result-set.</p> <p>Your goal is minimal cost estimate <em>and</em> minimal query execution time, with an emphasis on estimated cost. Query execution can dependent significantly on runtime conditions (e.g. whether relevant rows are already fully cached in memory or not), whereas the cost estimate is not. On the other hand, keep in mind that cost estimate is exactly that, an estimate.</p> <p>The best query execution time is obtained when running on a dedicated database without load (e.g. playing with pgAdminIII on a development PC.) Query time will vary in production based on actual machine load/data access spread. When one query appears slightly faster (<20%) than the other but has a <em>much</em> higher cost, it will generally be wiser to choose the one with higher execution time but lower cost.</p> <p>When you expect that there will be no competition for memory on your production machine at the time the query is run (e.g. the RDBMS cache and filesystem cache won't be thrashed by concurrent queries and/or filesystem activity) then the query time you obtained in standalone (e.g. pgAdminIII on a development PC) mode will be representative. If there is contention on the production system, query time will degrade proportionally to the estimated cost ratio, as the query with the lower cost does not rely as much on cache <em>whereas</em> the query with higher cost will revisit the same data over and over (triggering additional I/O in the absence of a stable cache), e.g.:</p> <pre><code> cost | time (dedicated machine) | time (under load) | -------------------+--------------------------+-----------------------+ some query A: 5k | (all data cached) 900ms | (less i/o) 1000ms | some query B: 50k | (all data cached) 900ms | (lots of i/o) 10000ms | </code></pre> <p><strong>Do not forget to run <code>ANALYZE lives</code> once after creating the necessary indices.</strong></p> <hr> <p><strong>Query #1</strong></p> <pre><code>-- incrementally narrow down the result set via inner joins -- the CBO may elect to perform one full index scan combined -- with cascading index lookups, or as hash aggregates terminated -- by one nested index lookup into lives - on my machine -- the latter query plan was selected given my memory settings and -- histogram SELECT l1.* FROM lives AS l1 INNER JOIN ( SELECT usr_id, MAX(time_stamp) AS time_stamp_max FROM lives GROUP BY usr_id ) AS l2 ON l1.usr_id = l2.usr_id AND l1.time_stamp = l2.time_stamp_max INNER JOIN ( SELECT usr_id, time_stamp, MAX(trans_id) AS trans_max FROM lives GROUP BY usr_id, time_stamp ) AS l3 ON l1.usr_id = l3.usr_id AND l1.time_stamp = l3.time_stamp AND l1.trans_id = l3.trans_max </code></pre> <p><strong>Query #2</strong></p> <pre><code>-- cheat to obtain a max of the (time_stamp, trans_id) tuple in one pass -- this results in a single table scan and one nested index lookup into lives, -- by far the least I/O intensive operation even in case of great scarcity -- of memory (least reliant on cache for the best performance) SELECT l1.* FROM lives AS l1 INNER JOIN ( SELECT usr_id, MAX(ARRAY[EXTRACT(EPOCH FROM time_stamp),trans_id]) AS compound_time_stamp FROM lives GROUP BY usr_id ) AS l2 ON l1.usr_id = l2.usr_id AND EXTRACT(EPOCH FROM l1.time_stamp) = l2.compound_time_stamp[1] AND l1.trans_id = l2.compound_time_stamp[2] </code></pre> <p><strong>2013/01/29 update</strong></p> <p>Finally, as of version 8.4, Postgres supports <a href="http://www.postgresql.org/docs/8.4/static/functions-window.html#FUNCTIONS-WINDOW-TABLE" rel="noreferrer">Window Function</a> meaning you can write something as simple and efficient as:</p> <p><strong>Query #3</strong></p> <pre><code>-- use Window Functions -- performs a SINGLE scan of the table SELECT DISTINCT ON (usr_id) last_value(time_stamp) OVER wnd, last_value(lives_remaining) OVER wnd, usr_id, last_value(trans_id) OVER wnd FROM lives WINDOW wnd AS ( PARTITION BY usr_id ORDER BY time_stamp, trans_id ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING ); </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload