Index not used with join and multiple identical SORT statements

Author: matchoCreated Nov 26, 2021Updated Sep 15, 2026

My Environment

ArangoDB Version: 3.8.3
Storage Engine: RocksDB
Deployment Mode: Leader/Follower ("Master/Slave")
Deployment Strategy: systemd
Infrastructure: own
Operating System: Ubuntu 20.04
Total RAM in your machine: 256 GB
Disks in use: HDD
Used Package: Ubuntu .deb

Component, Query & Data

Affected feature: AQL query optimizer

AQL query (if applicable):

FOR u IN users
    SORT u.date_updated DESC
    FOR um IN users_meta 
        FILTER um.user_id == u._key
        SORT u.date_updated DESC
        LIMIT 0, 101
        RETURN { u: u._key, m: um._key }

AQL explain and/or profile (if applicable):

Query String (180 chars, cacheable: true):
 FOR u IN users
 	SORT u.date_updated DESC
 	FOR um IN users_meta 
 		FILTER um.user_id == u._key
 	    SORT u.date_updated DESC
     	LIMIT 0, 101
     	RETURN { u: u._key, m: um._key }


Execution plan:
 Id   NodeType                     Est.   Comment
  1   SingletonNode                   1   * ROOT
  2   EnumerateCollectionNode   2864508     - FOR u IN users   /* full collection scan, projections: `_key`, `date_updated`  */
  3   CalculationNode           2864508       - LET #2 = u.`date_updated`   /* attribute expression */   /* collections used: u : users */
 13   IndexNode                 2864508       - FOR um IN users_meta   /* hash index scan, projections: `_key` */    
  9   SortNode                  2864508         - SORT #2 DESC   /* sorting strategy: constrained heap */
 10   LimitNode                     101         - LIMIT 0, 101
 11   CalculationNode               101         - LET #8 = { "u" : u.`_key`, "m" : um.`_key` }   /* simple expression */   /* collections used: u : users, um : users_meta */
 12   ReturnNode                    101         - RETURN #8

Indexes used:
 By   Name        Type   Collection   Unique   Sparse   Selectivity   Fields          Ranges
 13   idx_49318   hash   users_meta   true     false       100.00 %   [ `user_id` ]   (um.`user_id` == u.`_key`)

Optimization rules applied:
 Id   RuleName
  1   move-calculations-up
  2   remove-redundant-calculations
  3   remove-unnecessary-calculations
  4   remove-redundant-sorts
  5   use-indexes
  6   remove-filter-covered-by-index
  7   remove-unnecessary-calculations-2
  8   sort-limit
  9   reduce-extraction-to-projection

Optimization rules with highest execution times:
 RuleName                                    Duration [s]
 use-indexes                                      0.00006
 reduce-extraction-to-projection                  0.00003
 remove-redundant-calculations                    0.00003
 move-calculations-up                             0.00003
 remove-unnecessary-calculations                  0.00002

43 rule(s) executed, 1 plan(s) created

Dataset: Around 2M docs in each collection (users and users_meta), with a 1-to-1 relation.

An index exists on users.date_updated with 99.68% selectivity.

Steps to reproduce

Run query above. Index on users.date_updated is not used, query takes around 100s to return
Remove second SORT statement
Run query again. Index on users.date_updated is used, query takes around 30ms to return (see excerpt of explain below)

Indexes used:
 By   Name              Type       Collection   Unique   Sparse   Selectivity   Fields               Ranges
 12   idx_10220164868   skiplist   users        false    false        99.68 %   [ `date_updated` ]   *
 11   idx_49318         hash       users_meta   true     false       100.00 %   [ `user_id` ]        (um.`user_id` == u.`_key`)

Problem: The query above was generated by some piece of code, which explains why it has a duplicate sort.

Although it is obviously a bad practice to have a duplicate SORT statement inside and outside a join, one might expect that the appropriate index is used anyway.

Unless I missed something, it seems that in such a case, result cannot be different whether sorting is applied again after the join or not.

We'll fix the generating code anyway :)

Expected result: Index on the SORT field is used, even when SORT statement is duplicated.

Thank you, Greetings

Source: arangodb/arangodb

View original on GitHub View discussion on GitHub