Avoid unnecessary null checks ordering when possible on database that don't support NULLS (FIRST|LAST).

[Simon Charette]

On backends that don't support NULLS (FIRST|LAST) we emulate support by prepending a field IS (NOT)? NULL to the ORDER BY clause.

This unfortunately prevent usage of indices on both core backends that don't support this clause (SQLite and MySQL).

SQLite (notice the number of operations and no IdxRowid accesses

SQLite version 3.24.0 2018-06-04 14:10:15
Enter ".help" for usage hints.
sqlite> CREATE TABLE foo (
   ...>   id integer NOT NULL PRIMARY KEY AUTOINCREMENT,
   ...>   val int
   ...> );
sqlite> CREATE INDEX foo_val_idx ON foo (val);
sqlite> EXPLAIN SELECT * FROM foo ORDER BY val IS NOT NULL, val;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     21    0                    00  Start at 21
1     SorterOpen     1     5     0     k(2,B,B)       00
2     OpenRead       0     2     0     2              00  root=2 iDb=0; foo
3     Rewind         0     13    0                    00
4       Rowid          0     3     0                    00  r[3]=rowid
5       Integer        1     1     0                    00  r[1]=1
6       Column         0     1     5                    00  r[5]=foo.val
7       NotNull        5     9     0                    00  if r[5]!=NULL goto 9
8       Integer        0     1     0                    00  r[1]=0
9       Copy           5     2     0                    00  r[2]=r[5]
10      MakeRecord     1     3     6                    00  r[6]=mkrec(r[1..3])
11      SorterInsert   1     6     1     3              00  key=r[6]
12    Next           0     4     0                    01
13    OpenPseudo     2     7     5                    00  5 columns in r[7]
14    SorterSort     1     20    0                    00
15      SorterData     1     7     2                    00  r[7]=data
16      Column         2     1     4                    00  r[4]=val
17      Column         2     2     3                    00  r[3]=id
18      ResultRow      3     2     0                    00  output=r[3..4]
19    SorterNext     1     15    0                    00
20    Halt           0     0     0                    00
21    Transaction    0     0     2     0              01  usesStmtJournal=0
22    Goto           0     1     0                    00

MySQL (5.6, 5.7, 8) notice Using filesort

MySQL [django]> CREATE TABLE foo (
    ->   id int NOT NULL AUTO_INCREMENT PRIMARY KEY,
    ->   val int
    -> );
Query OK, 0 rows affected (0.005 sec)

MySQL [django]>
MySQL [django]> CREATE INDEX foo_val_idx ON foo (val);
Query OK, 0 rows affected (0.007 sec)
Records: 0  Duplicates: 0  Warnings: 0

MySQL [django]> EXPLAIN SELECT * FROM foo ORDER BY val IS NOT NULL, val;
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | foo   | NULL       | index | NULL          | foo_val_idx | 5       | NULL |    1 |   100.00 | Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------------+

Given both engine documents that they default to returning NULL values first when ordering by ascending order and vice-versa there's an optimization opportunity for OrderBy.asc(nulls_first=True) and .desc(nulls_last=True) to completely omit these IS NULL clause which prevents indices to be used while returning the same result set.

• ​https://sqlite.org/lang_select.html (The ORDER BY clause)
• ​https://dev.mysql.com/doc/refman/5.8/en/working-with-null.html

SQLite notice the reduced number of operations and IdxRowid acceses

sqlite> EXPLAIN SELECT * FROM foo ORDER BY val;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     9     0                    00  Start at 9
1     Noop           1     4     0                    00
2     OpenRead       2     4     0     k(2,,)         00  root=4 iDb=0; foo_val_idx
3     Rewind         2     8     1     0              00
4       IdxRowid       2     1     0                    00  r[1]=rowid
5       Column         2     0     2                    00  r[2]=foo.val
6       ResultRow      1     2     0                    00  output=r[1..2]
7     Next           2     4     0                    01
8     Halt           0     0     0                    00
9     Transaction    0     0     2     0              01  usesStmtJournal=0
10    Goto           0     1     0                    00

MySQL (5.6, 5.7, 8) notice Using index only.

MySQL [django]> EXPLAIN SELECT * FROM foo ORDER BY val;;
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | foo   | NULL       | index | NULL          | foo_val_idx | 5       | NULL |    1 |   100.00 | Using index |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+

[Simon Charette]

​https://github.com/django/django/pull/12583

[Mariusz Felisiak <felisiak.mariusz@…>]

In 9f07f271:

Fixed #31376 -- Optimized nulls ordering when possible on SQLite and MySQL.

Both backends order NULLs first on ascending ordering and last on
descending ordering which makes ORDER BY IS (NOT)? NULL wasteful when
asc(nulls_first) and desc(nulls_last) are used since it prevents indice
usage.