Opened 4 years ago

Closed 4 years ago

#31376 closed Cleanup/optimization (fixed)

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

Reported by: Simon Charette Owned by: Simon Charette
Component: Database layer (models, ORM) Version: dev
Severity: Normal Keywords:
Cc: Triage Stage: Accepted
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: no UI/UX: no

Description

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.

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 |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+

Change History (3)

comment:2 by Mariusz Felisiak, 4 years ago

Owner: changed from nobody to Simon Charette
Status: newassigned
Summary: Avoid unnecessary null checks ordering when possible on database that don't support NULLS (FIRST|LAST)Avoid unnecessary null checks ordering when possible on database that don't support NULLS (FIRST|LAST).
Triage Stage: UnreviewedAccepted

comment:3 by Mariusz Felisiak <felisiak.mariusz@…>, 4 years ago

Resolution: fixed
Status: assignedclosed

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.

Note: See TracTickets for help on using tickets.
Back to Top