Databases
StackOverflow2013
Postsdbo
POtop-N query doing too much work in spite of STOPKEY optimization
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POtop-N query doing too much work in spite of STOPKEY optimization
    primarykey
    data
    text
    <p>This is going to be long, so here's a quick summary to draw you in: my top-N query with <code>COUNT STOPKEY</code> and <code>ORDER BY STOPKEY</code> in its plan is still slow for no good reason.</p> <p>Now, the details. It starts with a slow function. In real life it involves string manipulations with regexps. For demonstration purposes, here's an intentionally stupid recursive Fibonacci algorithm. I find it to be pretty fast for inputs up to about 25, slow around 30, and ridiculous at 35.</p> <pre><code>-- I repeat: Please no advice on how to do Fibonacci correctly. -- This is slow on purpose! CREATE OR REPLACE FUNCTION tmp_fib ( n INTEGER ) RETURN INTEGER AS BEGIN IF n = 0 OR n = 1 THEN RETURN 1; END IF; RETURN tmp_fib(n-2) + tmp_fib(n-1); END; / </code></pre> <p>Now some input: a list of names and numbers.</p> <pre><code>CREATE TABLE tmp_table ( name VARCHAR2(20) UNIQUE NOT NULL, num NUMBER(2,0) ); INSERT INTO tmp_table (name,num) SELECT 'Alpha', 10 FROM dual UNION ALL SELECT 'Bravo', 11 FROM dual UNION ALL SELECT 'Charlie', 33 FROM dual; </code></pre> <p>Here's an example of a slow query: use the slow Fibonacci function to select rows whose num generates a Fibonacci number with a doubled digit.</p> <pre><code>SELECT p.name, p.num FROM tmp_table p WHERE REGEXP_LIKE(tmp_fib(p.num), '(.)\1') ORDER BY p.name; </code></pre> <p>This is true for 11 and 33, so <code>Bravo</code> and <code>Charlie</code> are in the output. It takes about 5 seconds to run, almost all of which is the slow calculation of <code>tmp_fib(33)</code>. So I want to do a faster version of the slow query by converting it to a top-N query. With N=1, it looks like this:</p> <pre><code>SELECT * FROM ( SELECT p.name, p.num FROM tmp_table p WHERE REGEXP_LIKE(tmp_fib(p.num), '(.)\1') ORDER BY p.name ) WHERE ROWNUM &lt;= 1; </code></pre> <p>And now it returns the top result, <code>Bravo</code>. But it still takes 5 seconds to run! The only explanation is that it's still calculating <code>tmp_fib(33)</code>, even though the result of that calculation is irrelevant to the result. It should have been able to decide that <code>Bravo</code> was going to be output, so there's no need to test the WHERE condition for the rest of the table.</p> <p>I've thought that maybe the optimizer just needs to be told that <code>tmp_fib</code> is expensive. So I tried to tell it that, like this:</p> <pre><code>ASSOCIATE STATISTICS WITH FUNCTIONS tmp_fib DEFAULT COST (999999999,0,0); </code></pre> <p>That alters some of the cost numbers in the plan, but it doesn't make the query run faster.</p> <p>Output of <code>SELECT * FROM v$version</code> in case this is version-dependent:</p> <pre><code>Oracle Database 11g Enterprise Edition Release 11.2.0.2.0 - 64bit Production PL/SQL Release 11.2.0.2.0 - Production CORE 11.2.0.2.0 Production TNS for 64-bit Windows: Version 11.2.0.2.0 - Production NLSRTL Version 11.2.0.2.0 - Production </code></pre> <p>And here's the autotrace of the top-1 query. It appears to be claiming that the query took 1 second, but that's not true. It ran for about 5 seconds.</p> <pre><code>NAME NUM -------------------- ---------- Bravo 11 Execution Plan ---------------------------------------------------------- Plan hash value: 548796432 ------------------------------------------------------------------------------------- | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | ------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | 55 | 4 (25)| 00:00:01 | |* 1 | COUNT STOPKEY | | | | | | | 2 | VIEW | | 1 | 55 | 4 (25)| 00:00:01 | |* 3 | SORT ORDER BY STOPKEY| | 1 | 55 | 4 (25)| 00:00:01 | |* 4 | TABLE ACCESS FULL | TMP_TABLE | 1 | 55 | 3 (0)| 00:00:01 | ------------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 1 - filter(ROWNUM&lt;=1) 3 - filter(ROWNUM&lt;=1) 4 - filter( REGEXP_LIKE (TO_CHAR("TMP_FIB"("P"."NUM")),'(.)\1')) Note ----- - dynamic sampling used for this statement (level=2) Statistics ---------------------------------------------------------- 27 recursive calls 0 db block gets 25 consistent gets 0 physical reads 0 redo size 593 bytes sent via SQL*Net to client 524 bytes received via SQL*Net from client 2 SQL*Net roundtrips to/from client 1 sorts (memory) 0 sorts (disk) 1 rows processed </code></pre> <p><strong>UPdATE</strong>: As I mentioned in the comments, an <code>INDEX</code> hint helps this query a lot. It would be good enough to be accepted as the correct answer, even though it doesn't translate well to my real-world scenario. And in an ironic twist, Oracle seems to have learned from the experience, and now chooses the <code>INDEX</code> plan by default; I have to tell it <code>NO_INDEX</code> to reproduce the original slow behavior.</p> <p>In the real-world scenario I've applied a more complex solution, rewriting the query as a PL/SQL function. Here's how my technique looks, applied to the <code>fib</code> problem:</p> <pre><code>CREATE OR REPLACE PACKAGE tmp_package IS TYPE t_namenum IS TABLE OF tmp_table%ROWTYPE; FUNCTION get_interesting_names (howmany INTEGER) RETURN t_namenum PIPELINED; END; / CREATE OR REPLACE PACKAGE BODY tmp_package IS FUNCTION get_interesting_names (howmany INTEGER) RETURN t_namenum PIPELINED IS CURSOR c IS SELECT name, num FROM tmp_table ORDER BY name; rec c%ROWTYPE; outcount INTEGER; BEGIN OPEN c; outcount := 0; WHILE outcount &lt; howmany LOOP FETCH c INTO rec; EXIT WHEN c%NOTFOUND; IF REGEXP_LIKE(tmp_fib(rec.num), '(.)\1') THEN PIPE ROW(rec); outcount := outcount + 1; END IF; END LOOP; END; END; / SELECT * FROM TABLE(tmp_package.get_interesting_names(1)); </code></pre> <p>Thanks to the responders who read the question and ran the tests and helped me understand the execution plans, and I will dispose of this question however they suggest.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USWumpus Q. Wumbley
    1. USWumpus Q. Wumbley
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. USJon Heller
      1. VTFavorite
    1. CONotice where the `filter` is occurring - _before_ the sort. You can't assume that `11` is the first row that will be checked for validity.
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. USMat
    2. CO@Mat so this is my question then: how do I convince oracle to do the filter after the sort?
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. USWumpus Q. Wumbley
    3. COWithout evaluating the `where` clause for every row in the table, how would it know that `Bravo` isn't going to be filtered out?
      singulars
      1. POtop-N query doing too much work in spite of STOPKEY optimization
      1. USAlex Poole
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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