[Django] #31376: Avoid unnecessary null checks ordering when possible on database that don't support NULLS (FIRST|LAST)
Django
support NULLS (FIRST|LAST)
-------------------------------------+-------------------------------------
Reporter: Simon | Owner: nobody
Charette |
Type: | Status: new
Cleanup/optimization |
Component: Database | Version: master
layer (models, ORM) |
Severity: Normal | Keywords:
Triage Stage: | Has patch: 0
Unreviewed |
Needs documentation: 0 | Needs tests: 0
Patch needs improvement: 0 | Easy pickings: 0
UI/UX: 0 |
-------------------------------------+-------------------------------------
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
{{{#!sql
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`
{{{#!python
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
{{{#!sql
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.
{{{#!sql
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 |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/31376>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.
Django
support NULLS (FIRST|LAST)
-------------------------------------+-------------------------------------
Type: | Status: new
Cleanup/optimization |
Component: Database layer | Version: master
(models, ORM) |
Severity: Normal | Resolution:
Keywords: | Triage Stage:
| Unreviewed
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* has_patch: 0 => 1
Comment:
https://github.com/django/django/pull/12583
--
Ticket URL: <https://code.djangoproject.com/ticket/31376#comment:1>
Django
-------------------------------------+-------------------------------------
Reporter: Simon Charette | Owner: Simon
Type: | Charette
Cleanup/optimization | Status: assigned
Component: Database layer | Version: master
(models, ORM) |
Severity: Normal | Resolution:
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* owner: nobody => Simon Charette
* status: new => assigned
* stage: Unreviewed => Accepted
--
Ticket URL: <https://code.djangoproject.com/ticket/31376#comment:2>
Django
-------------------------------------+-------------------------------------
Reporter: Simon Charette | Owner: Simon
Type: | Charette
Component: Database layer | Version: master
(models, ORM) |
Keywords: | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
* status: assigned => closed
* resolution: => fixed
Comment:
In [changeset:"9f07f27124540e27b4c3140235da375b974c4175" 9f07f271]:
{{{
#!CommitTicketReference repository=""
revision="9f07f27124540e27b4c3140235da375b974c4175"
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.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/31376#comment:3>