I have a query that executes against a table that can grow to millions of rows. The query comes out of a QA tool that we use that is outside the standard functionality of the DB (as far as what is indexed and how and why). The query is:

SELECT id FROM thisTable t
WHERE col = 'val'
AND ((not exists (SELECT 1 FROM thisTable WHERE refid = t.id) and refbool = 0) or refbool = 1)
ORDER BY newid()

Basically, let's say the table has id, refid, refbool, and col columns. So you could have data as follows:

  id  |  refid  |  refbool  |  col
   1  |   NULL  |    0      |  val
   2  |   NULL  |    0      |  val
   3  |   NULL  |    0      |  val
   4  |    2    |    1      |  val
   5  |   NULL  |    0      |  val
   6  |    1    |    1      |  val

The query should never pick the rows for id in (1, 2) because they are referred to by other rows. It should only grab rows where refbool = 1, OR refbool = 0 AND that row's id is not any other row's refid. This statement is horribly non-performant, but I'm not sure what a better query would look like for this. Assume that no indexes, views, stored procedures, or other underlying machinations can be added - it must be a query.

The overall query is significantly larger, JOINS to two additional tables and gathers quite a bit of data. However, I've narrowed it does to this particular bit as commenting out this line takes the query execution time from 16s to <1s.

I'm also reordering the rows by newid() as I need to randomly select a sample item. Removing the ORDER BY also make the query significantly faster even leaving the third row in. It appears that the two operations combined causes the slowness. I've tried designing a CTE, but have failed to increase performance doing so.

I've looked at the execution plan. There are indices that would be added that would improve this query. However, performance of internal QA tools do not take precedence over performance in client production environments, and making changes to the structure in a QA environment for the utility in relation to indices, etc. invalidates it's usefulness as a QA environment as it will likely perform differently than a production environment.

I could certainly write a query that would perform worse than my current query by changing the logic of the query itself. I'm sure we all could. I'm asking to apply that sort of reasoning to improve the performance of the query instead.

  • Is refid always null when refbool equals 0? In other words, does your sample data faithfully reproduce actual data? – mustaccio Aug 6 at 20:45
  • That’s actually a good question. I believe it is the case, though that makes me wonder why the Boolean column exists at all. I’d have to dig into the sprocs to be absolutely certain. – Jesse Williams Aug 6 at 20:50

An execution plan was not included, but the typical issue with queries like this (sorting aside) is the optimizer choosing a nested loops anti semi join without a good supporting index. It can also be a rogue top (1), or a poorly-performing transformation to a semi-join with nested start-up filters and an anti-semi join.

Regardless, there are two usual workarounds:

  1. Rewrite the OR manually as a UNION (or, if guaranteed disjoint, as a UNION ALL).
  2. Rewrite the NOT EXISTS as a left join filtering the preserved side for NULL.

The following incorporates both:

DECLARE @thisTable table
    id integer PRIMARY KEY,
    refid integer NULL,
    refbool bit NOT NULL,
    col varchar(10) NOT NULL

INSERT @thisTable
    (id, refid, refbool, col)
    (1, NULL, 0, 'val'),
    (2, NULL, 0, 'val'),
    (3, NULL, 0, 'val'),
    (4,  2  , 1, 'val'),
    (5, NULL, 0, 'val'),
    (6,  1  , 1, 'val');
    -- T.refbool = 1
    SELECT T.id 
    FROM @thisTable AS T
        T.col = 'val'
        AND T.refbool = 1

    -- Or (disjoint)

    -- T.refbool = 0 and not exists
    SELECT T.id 
    FROM @thisTable AS T
    LEFT JOIN @thisTable AS T2
        ON T2.refid = T.id
        T.col = 'val'
        AND T.refbool = 0
        AND T2.id IS NULL
) AS U

db<>fiddle online demo

For more alternatives on random ordering see the existing Q & A:

Don't just try the top answer.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.