DEV Community

Franck Pachot for AWS Heroes

Posted on

3

Indexing for NOT EQUAL (<>,!=) in YugabyteDB, PostgreSQL, Oracle Database, SQL Server, and MongoDB

Imagine you have a table where most rows contain value=0 and a few different values scattered throughout. To retrieve those other values, you would use WHERE value != 0 or WHERE value <> 0. This query is quite selective, making index access desirable, and column statistics provide this information to the query planner.
Do you know of an SQL database that can handle this with a full index on value? It's straightforward: only two ranges of values must be read from the index: one before and one after the specified value. However, not many database optimizers can do that. There are workarounds, but they vary between databases.

Indexing for Not-Equal in YugabyteDB

I started with YugabyteDB. It's one of the most advanced SQL databases for reading multiple ranges from an index, as it benefits from the PostgreSQL query planner and an additional LSM tree skip scan. Let's see how it behaves with not-equal.

I create the following table:

create table demo (
 id int generated always as identity
 , value int
);

create index demo_value on demo(value asc);

create extension if not exists tablefunc;

insert into demo(value)
select * from normal_rand(100000,0,0.2);

analyze demo;

Enter fullscreen mode Exit fullscreen mode

I inserted nearly a hundred thousand rows with value = 0 and one thousand for other values:

yugabyte=> select value,count(*) from demo group by value order by 2;

 value | count
-------+-------
     1 |   620
    -1 |   635
     0 | 98745
(3 rows)
Enter fullscreen mode Exit fullscreen mode

I have created an index on "value," but it is not used for a not-equal predicate:

yugabyte=> explain (analyze, dist, debug, costs off, summary off)
select * from demo where value!=0
;
                           QUERY PLAN
-----------------------------------------------------------------
 Seq Scan on demo (actual time=23.464..23.621 rows=1255 loops=1)
   Storage Filter: (value <> 0)
   Storage Table Read Requests: 1
   Storage Table Read Execution Time: 23.385 ms
   Storage Table Rows Scanned: 100000
   Metric rocksdb_number_db_seek: 3.000
   Metric rocksdb_number_db_next: 100000.000
   Metric rocksdb_number_db_seek_found: 3.000
   Metric rocksdb_number_db_next_found: 99997.000
   Metric rocksdb_iter_bytes_read: 7780923.000
   Metric docdb_keys_found: 100000.000
   Metric ql_read_latency: sum: 64226.000, count: 3.000
(12 rows)
Enter fullscreen mode Exit fullscreen mode

Reading 100,000 rows to get only 1255 is inefficient, even if the filtering was pushed down to the storage.

Fortunately, YugabyteDB inherits optimizations from PostgreSQL and can use a bitmap scan to read from two ranges of the index, but this requires re-writing the SQL statement:

yugabyte=> set yb_enable_bitmapscan to on;
SET

yugabyte=> explain (analyze, dist, debug, costs off, summary off)
select * from demo where value<0 or value>0
;
                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 YB Bitmap Table Scan on demo (actual time=5.536..7.065 rows=1255 loops=1)
   Storage Table Read Requests: 2
   Storage Table Read Execution Time: 3.844 ms
   Storage Table Rows Scanned: 1255
   Metric rocksdb_number_db_seek: 1254.000
   Metric rocksdb_number_db_next: 2100.000
   Metric rocksdb_number_db_seek_found: 1254.000
   Metric rocksdb_number_db_next_found: 2100.000
   Metric rocksdb_iter_bytes_read: 250992.000
   Metric docdb_keys_found: 1255.000
   Metric ql_read_latency: sum: 3279.000, count: 6.000
   Average ybctid Size: 40 B
   ->  BitmapOr (actual time=2.371..2.372 rows=1255 loops=1)
         ->  Bitmap Index Scan on demo_value (actual time=1.383..1.384 rows=635 loops=1)
               Index Cond: (value < 0)
               Storage Index Read Requests: 1
               Storage Index Read Execution Time: 1.173 ms
               Storage Index Rows Scanned: 635
               Metric rocksdb_number_db_seek: 1.000
               Metric rocksdb_number_db_next: 635.000
               Metric rocksdb_number_db_seek_found: 1.000
               Metric rocksdb_number_db_next_found: 635.000
               Metric rocksdb_iter_bytes_read: 36792.000
               Metric docdb_keys_found: 635.000
               Metric ql_read_latency: sum: 362.000, count: 1.000
         ->  Bitmap Index Scan on demo_value (actual time=0.983..0.983 rows=620 loops=1)
               Index Cond: (value > 0)
               Storage Index Read Requests: 1
               Storage Index Read Execution Time: 0.819 ms
               Storage Index Rows Scanned: 620
               Metric rocksdb_number_db_seek: 1.000
               Metric rocksdb_number_db_next: 620.000
               Metric rocksdb_number_db_seek_found: 1.000
               Metric rocksdb_number_db_next_found: 619.000
               Metric rocksdb_iter_bytes_read: 35865.000
               Metric docdb_keys_found: 620.000
               Metric ql_read_latency: sum: 340.000, count: 1.000
(37 rows)
Enter fullscreen mode Exit fullscreen mode

The bitmap can separate the two ranges. (value < 0) has read 635 rows, and (value > 0) has read 620 rows. Each index scan is optimal with 1 seek at the beginning of its range and reading next rows until the end of the range. The result is a bitmap of row identifiers (ybctid) combined with an OR operation, and 1255 rows are read from the table.

YugabyteDB can use skip scan only with a discrete list of values. You can re-write the statement to use DISTINCT pushdown and Batched Nested Loop. Here is an example if you want to try it:

yugabyte=> explain 
select * from demo where value in (
 select distinct value from demo where value<>0
) ;
                                               QUERY PLAN
--------------------------------------------------------------------------------------------------------
 YB Batched Nested Loop Join  (cost=0.00..394.38 rows=100000 width=8)
   Join Filter: (demo.value = demo_1.value)
   ->  Unique  (cost=0.00..0.35 rows=3 width=4)
         ->  Distinct Index Only Scan using demo_value on demo demo_1  (cost=0.00..0.35 rows=3 width=4)
               Distinct Keys: demo_1.value
               Storage Filter: (value <> 0)
   ->  Index Scan using demo_value on demo  (cost=0.00..121.33 rows=1000 width=8)
         Index Cond: (value = ANY (ARRAY[demo_1.value, $1, $2, ..., $1023]))
(8 rows)
Enter fullscreen mode Exit fullscreen mode

Finally, in this simple case, we only want to use an index when the value != 0 is highly selective. There's no need to index value = 0 that returns most rows. I replace my index with a partial index:

yugabyte=> drop index demo_value;
DROP INDEX

yugabyte=> create index demo_value on demo(value asc)
           where value != 0
;

yugabyte=> explain (analyze, dist, debug, costs off, summary off)
select * from demo where value != 0
;
                                    QUERY PLAN
----------------------------------------------------------------------------------
 Index Scan using demo_value on demo (actual time=4.942..7.017 rows=1255 loops=1)
   Storage Table Read Requests: 2
   Storage Table Read Execution Time: 4.282 ms
   Storage Table Rows Scanned: 1255
   Storage Index Read Requests: 2
   Storage Index Read Execution Time: 1.190 ms
   Storage Index Rows Scanned: 1255
   Metric rocksdb_number_db_seek: 1241.000
   Metric rocksdb_number_db_next: 4987.000
   Metric rocksdb_number_db_seek_found: 1241.000
   Metric rocksdb_number_db_next_found: 4986.000
   Metric rocksdb_iter_bytes_read: 448556.000
   Metric docdb_keys_found: 2511.000
   Metric ql_read_latency: sum: 3876.000, count: 7.000
(14 rows)

Enter fullscreen mode Exit fullscreen mode

As the partial index skips the value = 0, there's only one range to scan, and a regular Index Scan can retrieve only the interesting rows.

Indexing for Not-Equal in PostgreSQL

I started with YugabyteDB because the EXPLAIN with the DIST option shows the number of rows scanned and returned, which helps to understand the efficiency. Here is the same example on PostgreSQL:

postgres=> select value,count(*) from demo group by value order by 2;

 value | count
-------+-------
     1 |   608
    -1 |   623
     0 | 98769
(3 rows)

Enter fullscreen mode Exit fullscreen mode

The query with not-equal uses a full table scan, and the number of rows scanned can be calculated by adding rows= and Rows Removed by Filter::

postgres=> explain (analyze, buffers, costs off, summary off)
select * from demo where value != 0
;
                          QUERY PLAN
---------------------------------------------------------------
 Seq Scan on demo (actual time=0.012..3.972 rows=1231 loops=1)
   Filter: (value <> 0)
   Rows Removed by Filter: 98769
   Buffers: shared hit=443
(4 rows)

Enter fullscreen mode Exit fullscreen mode

Like with YugabyteDB, rewriting the query to have explicit ranges in the WHERE clause can use the index with a bitmap scan:

postgres=> explain (analyze, buffers, costs off, summary off)
select * from demo where value<0 or value>0
;
                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 Bitmap Heap Scan on demo (actual time=0.107..0.627 rows=1231 loops=1)
   Recheck Cond: ((value < 0) OR (value > 0))
   Heap Blocks: exact=419
   Buffers: shared hit=424
   ->  BitmapOr (actual time=0.066..0.067 rows=0 loops=1)
         Buffers: shared hit=5
         ->  Bitmap Index Scan on demo_value (actual time=0.041..0.041 rows=623 loops=1)
               Index Cond: (value < 0)
               Buffers: shared hit=2
         ->  Bitmap Index Scan on demo_value (actual time=0.025..0.025 rows=608 loops=1)
               Index Cond: (value > 0)
               Buffers: shared hit=3
(12 rows)

Enter fullscreen mode Exit fullscreen mode

A partial index is the best option for this simple example:

yugabyte=> drop index demo_value;
DROP INDEX

yugabyte=> create index demo_value on demo(value asc)
           where value != 0
;

yugabyte=> explain (analyze, buffers, costs off, summary off)
select * from demo where value != 0
;

                                    QUERY PLAN
----------------------------------------------------------------------------------
 Index Scan using demo_value on demo (actual time=0.020..0.662 rows=1231 loops=1)
   Buffers: shared hit=677
(2 rows)

Enter fullscreen mode Exit fullscreen mode

Let's try another popular SQL database known for its powerful optimizer transformations, Oracle Database 23ai.

Indexing for Not-Equal in Oracle Database

Here is the same example adapted to the Oracle Database:

create table demo (
    id number generated always as identity,
    value int
);

-- insert data using a normal random distribution function
begin
 for i in 1..100000 loop
  -- simulate normal distribution (box-muller transform)
  insert into demo (value) values (
     0 + 0.2 * sqrt(-2 * ln(dbms_random.value())) 
             * cos(2 * 3.14 * dbms_random.value())
  );
 end loop;
 commit;
end;
/

exec dbms_stats.gather_table_stats(user,'demo');
Enter fullscreen mode Exit fullscreen mode

I check that I generated a similar data distribution:

ORA> select value, count(*)
      from demo
      group by value
      order by count(*) asc;

   VALUE    COUNT(*)
________ ___________
      -1         612
       1         638
       0      98,750

Enter fullscreen mode Exit fullscreen mode

The query with a non-equal predicate doesn't use the index:

ORA> set autotrace trace explain

Autotrace TraceOnly
 Exhibits the performance statistics with silent query output

ORA> select * from demo where value != 0;

1,250 rows selected.


PLAN_TABLE_OUTPUT
_______________________________________________________________________________________
SQL_ID  61srvku0vr1a0, child number 0
-------------------------------------
select * from demo where value != 0

Plan hash value: 4000794843

------------------------------------------------------------------------------------
| Id  | Operation         | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |      1 |        |   1250 |00:00:00.01 |     271 |
|*  1 |  TABLE ACCESS FULL| DEMO |      1 |   1250 |   1250 |00:00:00.01 |     271 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("VALUE"<>0)

Statistics
-----------------------------------------------------------
...
          148127  table scan disk non-IMC rows gotten
          148127  table scan rows gotten
...

Enter fullscreen mode Exit fullscreen mode

The statistics show the inefficiency of scanning too many rows compared to the result.

The query with two ranges in the WHERE clause uses an OR-Expansion transformation to read the two ranges like a UNION ALL:

ORA> select * from demo where value < 0 or value > 0
;                                                                                                                       

1,250 rows selected.


PLAN_TABLE_OUTPUT
_______________________________________________________________________________________________________________________________
SQL_ID  fjbhxb5c90xz4, child number 0
-------------------------------------
select * from demo where value < 0 or value > 0

Plan hash value: 559697324

----------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                             | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
----------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                      |                 |      1 |        |   1250 |00:00:00.01 |     468 |      4 |
|   1 |  VIEW                                 | VW_ORE_86AC2526 |      1 |   1250 |   1250 |00:00:00.01 |     468 |      4 |
|   2 |   UNION-ALL                           |                 |      1 |   1250 |   1250 |00:00:00.01 |     468 |      4 |
|   3 |    TABLE ACCESS BY INDEX ROWID BATCHED| DEMO            |      1 |    613 |    612 |00:00:00.01 |     233 |      2 |
|*  4 |     INDEX RANGE SCAN                  | DEMO_VALUE_IDX  |      1 |    613 |    612 |00:00:00.01 |      41 |      2 |
|   5 |    TABLE ACCESS BY INDEX ROWID BATCHED| DEMO            |      1 |    637 |    638 |00:00:00.01 |     235 |      2 |
|*  6 |     INDEX RANGE SCAN                  | DEMO_VALUE_IDX  |      1 |    637 |    638 |00:00:00.01 |      45 |      2 |
----------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("VALUE"<0)
   6 - access("VALUE">0)


Statistics
-----------------------------------------------------------
...
               2  index range scans
            1250  table fetch by rowid
Enter fullscreen mode Exit fullscreen mode

Oracle stores table rows in heap tables and rows accessed by the index are fetched by ROWID in two range scans.

Oracle Database supports no WHERE clause in index creation, but partitioning can isolate the range of value = 0:

ORA> ALTER TABLE demo MODIFY
    PARTITION BY LIST (value) (
        PARTITION value_zero VALUES (0),
        PARTITION other_values VALUES (DEFAULT)
    );

ALTER TABLE demo MODIFY
    PARTITION BY RANGE (value) (
        PARTITION value_zero VALUES (0),
        PARTITION other_values VALUES (DEFAULT)
    );

Table DEMO altered.

ORA> select /*+ INDEX(demo) */ * from demo where value != 0;

1,250 rows selected.


PLAN_TABLE_OUTPUT
___________________________________________________________________________________________________________________________________
SQL_ID  83yy7ngzb865a, child number 0
-------------------------------------
select /*+ INDEX(demo) */ * from demo where value != 0

Plan hash value: 2696029685

--------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                  | Name           | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
--------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                           |                |      1 |        |   1250 |00:00:00.10 |     362 |    193 |
|   1 |  PARTITION LIST ALL                        |                |      1 |   1200 |   1250 |00:00:00.10 |     362 |    193 |
|   2 |   TABLE ACCESS BY LOCAL INDEX ROWID BATCHED| DEMO           |      2 |   1200 |   1250 |00:00:00.10 |     362 |    193 |
|*  3 |    INDEX FULL SCAN                         | DEMO_VALUE_IDX |      2 |   1200 |   1250 |00:00:00.10 |     276 |    193 |
--------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - filter("VALUE"<>0)

Enter fullscreen mode Exit fullscreen mode

Unfortunately, partition pruning didn't work here, and all partitions were scanned (PARTITION LIST ALL) even if we know that no rows came from PARTITION "value_zero".

To skip this partition, I need to rewrite the query and get OR expansion to kick in:

ORA> select /*+ INDEX(demo) */ * from demo 
              where value < 0 or value > 0 
;

1,250 rows selected.


PLAN_TABLE_OUTPUT
_____________________________________________________________________________________________________________________________
SQL_ID  fxzmx534wrw15, child number 0
-------------------------------------
select /*+ INDEX(demo) */ * from demo where value < 0 or value > 0

Plan hash value: 461924341

--------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                    | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                             |                 |      1 |        |   1250 |00:00:00.01 |     172 |
|   1 |  VIEW                                        | VW_ORE_86AC2526 |      1 |   1200 |   1250 |00:00:00.01 |     172 |
|   2 |   UNION-ALL                                  |                 |      1 |   1200 |   1250 |00:00:00.01 |     172 |
|   3 |    PARTITION LIST SINGLE                     |                 |      1 |    536 |    612 |00:00:00.01 |      82 |
|   4 |     TABLE ACCESS BY LOCAL INDEX ROWID BATCHED| DEMO            |      1 |    536 |    612 |00:00:00.01 |      82 |
|*  5 |      INDEX RANGE SCAN                        | DEMO_VALUE_IDX  |      1 |    536 |    612 |00:00:00.01 |      41 |
|   6 |    PARTITION LIST SINGLE                     |                 |      1 |    664 |    638 |00:00:00.01 |      90 |
|   7 |     TABLE ACCESS BY LOCAL INDEX ROWID BATCHED| DEMO            |      1 |    664 |    638 |00:00:00.01 |      90 |
|*  8 |      INDEX RANGE SCAN                        | DEMO_VALUE_IDX  |      1 |    664 |    638 |00:00:00.01 |      45 |
--------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   5 - access("VALUE"<0)
   8 - access("VALUE">0)

Enter fullscreen mode Exit fullscreen mode

Oracle can use bitmap indexes if your workload allows it (not for OLTP!). On the original table, I dropped the regular index and created a bitmap index:

ORA> create bitmap index demo_value_bix on demo (value);

Index DEMO_VALUE_BIX created.

ORA> select /*+ INDEX(demo) */ * from demo where value != 0;

1,250 rows selected.


PLAN_TABLE_OUTPUT
___________________________________________________________________________________________________________________
SQL_ID  83yy7ngzb865a, child number 0
-------------------------------------
select /*+ INDEX(demo) */ * from demo where value != 0

Plan hash value: 2356352366

----------------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name           | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                |      1 |        |   1250 |00:00:00.01 |      93 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| DEMO           |      1 |   2037 |   1250 |00:00:00.01 |      93 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |                |      1 |        |   1250 |00:00:00.01 |       5 |
|*  3 |    BITMAP INDEX FULL SCAN           | DEMO_VALUE_BIX |      1 |        |      2 |00:00:00.01 |       5 |
----------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - filter("VALUE"<>0)

Enter fullscreen mode Exit fullscreen mode

This is similar to the PostgreSQL Bitmap Scan, except that the bitmaps are already created, and multiple ranges can be read without combining multiple bitmaps. This index was used without rewriting the not-equal query. Note that bitmap indexes are compact, which makes them efficient for queries but not for concurrent DML. Typically, you use them for an analytic database without OLTP workloads.


Transformations like Bitmap Scan or OR-expansion enhance the efficiency of row scanning. Nevertheless, the developer must adjust the query instead of utilizing a not-equal predicate.

Are you aware of any SQL databases that seamlessly perform this transformation?

Microsoft SQL Server transforms value != 0 into value < 0 or value > 0:

SET SHOWPLAN_TEXT ON
SELECT * FROM demo WITH (INDEX(demo_value)) 
WHERE value != 0 ORDER BY value;

|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
   |--Index Seek(OBJECT:([demo_value]), SEEK:([value] < (0) OR [value] > (0)) ORDERED FORWARD)
   |--RID Lookup(OBJECT:([demo]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
Enter fullscreen mode Exit fullscreen mode

Ideally, SQL databases should permit the creation of an SQL statement without regard to data access methods, allowing the optimizer to manage the necessary transformations.

Interestingly, a NoSQL database can achieve this. I'll execute the same in MongoDB.

Indexing for Not-Equal in MongoDB

MongoDB uses syntax closer to the programming languages found in modern applications. I've asked ChatGPT to translate my SQL commands to run on MongoDB Shell.

Instead of the normal_rand() function from tablefunc extension, I defined the following function and use it to generate data in a demo collection:

function normalRand(mean, stddev, count) {
    const rand = () => Math.sqrt(-2 * Math.log(Math.random())) 
                       * Math.cos(2 * Math.PI * Math.random());
    return Array.from({ length: count }, () => Math.round(mean + stddev * rand()));
}

db.demo.insertMany(
 normalRand(0, 0.2, 100000).map(value => ({ value }))
);

db.demo.createIndex({ value: 1 });

Enter fullscreen mode Exit fullscreen mode

I checked the data distribution with an aggregation pipeline:

mlab> db.demo.aggregate([
     { $group: { _id: "$value", count: { $sum: 1 } } },
     { $sort: { count: 1 } }
 ]);

[
  { _id: -1, count: 613 },
  { _id: 1, count: 646 },
  { _id: 0, count: 98741 }
]

Enter fullscreen mode Exit fullscreen mode

This is a similar dataset with a hundred thousand rows with { value: 0 } and a thousand with a different value.

As I did with PostgreSQL and YugabyteDB, I can run the query with the two ranges of values, lower than zero and greater than zero ({ $lt: 0 } and { $gt: 0 }), and look at the execution plan:

mlab> db.demo.find(
 { $or: [ { value: { $lt: 0 } }, { value: { $gt: 0 } } ] }
).explain().queryPlanner.winningPlan
;

{
  stage: 'SUBPLAN',
  inputStage: {
    stage: 'FETCH',
    inputStage: {
      stage: 'IXSCAN',
      keyPattern: { value: 1 },
      indexName: 'value_1',
      isMultiKey: false,
      multiKeyPaths: { value: [] },
      isUnique: false,
      isSparse: false,
      isPartial: false,
      indexVersion: 2,
      direction: 'forward',
      indexBounds: { value: [ '[-inf.0, 0)', '(0, inf.0]' ] }
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

No complicated bitmap combinations are necessary since MongoDB can access multiple ranges from a WiredTiger index. The explain command displays these ranges in indexBounds: [-inf.0, 0) and (0, inf.0].

Moreover, MongoDB allows you to avoid rewriting your query for explicit ranges and provides the same functionality when utilizing a not-equal predicate ({ $ne: 0 }):

mlab> db.demo.find(
 { value: { $ne: 0 } }
).explain().queryPlanner.winningPlan
;

{
  stage: 'FETCH',
  inputStage: {
    stage: 'IXSCAN',
    keyPattern: { value: 1 },
    indexName: 'value_1',
    isMultiKey: false,
    multiKeyPaths: { value: [] },
    isUnique: false,
    isSparse: false,
    isPartial: false,
    indexVersion: 2,
    direction: 'forward',
    indexBounds: { value: [ '[MinKey, 0)', '(0, MaxKey]' ] }
  }
}
Enter fullscreen mode Exit fullscreen mode

MongoDB examined two ranges, [MinKey, 0) and (0, MaxKey], in the index to retrieve rows that do not equal 0 without re-writing the query and without bitmap calculation overhead.

Additionally, MongoDB provides detailed instrumentation, allowing us to analyze execution statistics:

mlab> db.demo.find(
 { value: { $ne: 0 } }
).explain("executionStats").executionStats
;

{
  executionSuccess: true,
  nReturned: 1259,
  executionTimeMillis: 4,
  totalKeysExamined: 1260,
  totalDocsExamined: 1259,
  executionStages: {
    stage: 'FETCH',
    nReturned: 1259,
    executionTimeMillisEstimate: 0,
    works: 1261,
    advanced: 1259,
    needTime: 1,
    needYield: 0,
    saveState: 1,
    restoreState: 1,
    isEOF: 1,
    docsExamined: 1259,
    alreadyHasObj: 0,
    inputStage: {
      stage: 'IXSCAN',
      nReturned: 1259,
      executionTimeMillisEstimate: 0,
      works: 1261,
      advanced: 1259,
      needTime: 1,
      needYield: 0,
      saveState: 1,
      restoreState: 1,
      isEOF: 1,
      keyPattern: { value: 1 },
      indexName: 'value_1',
      isMultiKey: false,
      multiKeyPaths: { value: [] },
      isUnique: false,
      isSparse: false,
      isPartial: false,
      indexVersion: 2,
      direction: 'forward',
      indexBounds: { value: [ '[MinKey, 0)', '(0, MaxKey]' ] },
      keysExamined: 1260,
      seeks: 2,
      dupsTested: 0,
      dupsDropped: 0
    }
  }
}

Enter fullscreen mode Exit fullscreen mode

These figures illustrate how MongoDB optimized the scan for a non-equal predicate, resulting in just two seeks (seeks: 2) on two ranges when scanning the index (stage: 'IXSCAN'). It examined only the necessary keys (keysExamined: 1260) to get the result (nReturned: 1259).

Note that this makes sense only when the not-equal predicate is highly selective, such as when a popular value is skipped, and partial indexing can avoid indexing popular values. However, $ne is not one of the supported partial index expressions in MongoDB 8.0

mlab> db.demo.createIndex({ value: 1 } , { partialFilterExpression: { value: { $ne: 0 } } } );
Uncaught:
MongoServerError[CannotCreateIndex]: Error in specification { partialFilterExpression: { value: { $ne: 0 } }, name: "value_1", key: { value: 1 }, v: 2 } :: caused by :: Expression not supported in partial index: $not
    value $eq 0
Enter fullscreen mode Exit fullscreen mode

You can create one with $or: [ { value: { $lt: 0 } }, { value: { $gt: 0 } } ], but it will be used only when the same filter is used in the query, and you should prefer indexes that benefit to many queries.

So, the workaround used in other databases is not available, but it is also not required because a regular index is sufficient.


Different databases have varying implementations, and you might be surprised by their capabilities. The WiredTiger indexes allow multi-range scans, and the MongoDB query optimizer can use it with a not-equal predicate. PostgreSQL and YugabyteDB can combine index range scans with Bitmap Scan, and Oracle Database can utilize OR expansion when rewriting the query to have one predicate per range. With PostgreSQL and YugabyteDB, a partial index is probably the best solution to scan a single range, given the low selectivity of the skipped range.

The most important is to know your database. To accurately evaluate the performance of your queries, you must review the execution plan and ensure that they scan only the necessary data. By analyzing the execution plan, you can determine whether to adjust your query or add additional indexes. Avoid making assumptions without displaying the execution plan, as database optimizers can perform numerous optimizations you might overlook.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay