sql: better query planning for OR expressions

[petermattis]

Consider a query like SELECT * FROM foo WHERE a > 1 OR b > 2. Even if there are appropriate indexes to satisfy both a > 1 and b > 2, the current query planner will perform a full table or index scan because it can't use both conditions at once. Instead, the query planner should check to see if 2 separate index scans can be used and their results merged using a "union" operation.

This is essentially a generalization of #2140.

[petermattis]

We really want UNION before implementing this. I'm going to punt it to 1.0 for now.

[spencerkimball]

@RaduBerinde @knz is this still an active issue? Should it be 1.0 if so? If not, please close.

[knz]

It's still active. We don't optimize OR. Probably won't make it for 1.0 though. Meta: what about we don't reclassify active but postponed issues blindly but instead ensure first there's a doc issue/PR to mark the thing as known limitation? -- Sent from my Android device with K-9 Mail. Please excuse my brevity.

[jseldess]

Document this as known limitation with cockroachdb/docs#1381 (review). @knz, @petermattis, please review my language there and let me know if we need to add a workaround.

[knz]

Deassigning myself as I am not working on this before a suitable IR.
The item is now listed on #12418 though.

[andy-kimball]

2nd oldest open issue in the project finally closed!

[Bessonov]

@andy-kimball cool! But it depends on the interpretation. The issue mention the use case of SELECT * FROM foo WHERE a > 1 OR b > 2, but the fix is about SELECT * FROM foo WHERE a = 1 OR b = 2 only. Well it's better, but not for the majority of real use cases.

Our use case is the JSONB comparison: 'scope'->'name' @> '[{"type":"column"}]' OR 'scope'->'name2' @> '[{"type":"column"}]'.

[andy-kimball]

This change fixes the inequality case as well, as long as the optimizer estimates that there are fewer rows to scan in the two index case than the one index case.

As for the JSON case, can you give a complete example, including schema, some rows of sample data, and full SQL query? We can see if the new code handles that case.

[andy-kimball]

Here's an inequality example:

root@:26257/defaultdb> create table t (x int primary key, y int, z int, index(y), index(z));
CREATE TABLE

root@:26257/defaultdb> insert into t select a, a, a from generate_series(1,100000) temp(a);
INSERT 100000

root@:26257/defaultdb> explain (opt) select * from t where y>90000 OR z>95000;
                      text
+----------------------------------------------+
  union
   ├── index-join t
   │    └── scan t@t_y_idx
   │         └── constraint: /2/1: [/90001 - ]
   └── index-join t
        └── scan t@t_z_idx
             └── constraint: /7/5: [/95001 - ]

In this case, the optimizer estimates that the first index scan will return ~10K rows, and then second index scan will return ~5K rows. It decides that the UNION of these two is better than scanning all 100K rows of the primary index, and so uses the new plan enabled by this work.

[Bessonov]

Great, I've looked at the description and the tests and couldn't see the inequality case.

It's not a complete query (I can provide the complete query, but it has another problems with query planer: full table scan on left join, where look up should be more cheaper), but I think it's a good starting point and makes a huge difference:

select version();
                                          version                                           
+------------------------------------------------------------------------------------------+
  CockroachDB CCL v19.2.5 (x86_64-unknown-linux-gnu, built 2020/03/16 18:27:12, go1.12.12)


CREATE TABLE t (
	id UUID NOT NULL DEFAULT gen_random_uuid(),
	perms JSONB NOT NULL,
	CONSTRAINT "primary" PRIMARY KEY (id ASC),
	INVERTED INDEX ix_perms (perms)
);

insert into t (perms) select jsonb_build_object('scope', jsonb_build_object('xx' || a::string, jsonb_build_array(jsonb_build_object('type', 'column')))) from generate_series(1,100000) temp(a);

> explain (opt) select * from t where perms->'scope'->'xx2000' @> '[{"type":"column"}]' or perms->'scope'->'xx4000' @> '[{"type":"column"}]';
                                                               text                                                               
+--------------------------------------------------------------------------------------------------------------------------------+
  select                                                                                                                          
   ├── scan t                                                                                                                     
   └── filters                                                                                                                    
        └── (perms @> '{"scope": {"xx2000": [{"type": "column"}]}}') OR (perms @> '{"scope": {"xx4000": [{"type": "column"}]}}')

> select * from t where perms->'scope'->'xx2000' @> '[{"type":"column"}]' or perms->'scope'->'xx4000' @> '[{"type":"column"}]';
                   id                  |                    perms                     
+--------------------------------------+---------------------------------------------+
  6815b87d-4af4-4a58-aee0-de00dc4375f4 | {"scope": {"xx4000": [{"type": "column"}]}}  
  9102f2a6-a26a-4139-b085-7b33948b4652 | {"scope": {"xx2000": [{"type": "column"}]}}  
(2 rows)

Time: 668.315636ms

> select * from t where perms->'scope'->'xx9000' @> '[{"type":"column"}]';
                   id                  |                    perms                     
+--------------------------------------+---------------------------------------------+
  93025901-3c48-4d79-94ba-ee32bf4f0a2a | {"scope": {"xx9000": [{"type": "column"}]}}  
(1 row)

Time: 1.05896ms

This one could be fixed in 20.1 (not tested yet):

• UNION on json columns doesn't work #35260
• sql: support ordering by JSON (pq: unable to encode table key: *tree.DJSON) #35706
• DISTINCT doesn't work with jsonb_build_object #46709

> select * from t where perms->'scope'->'xx20000' @> '[{"type":"column"}]' union select * from t where perms->'scope'->'xx41000' @> '[{"type":"col
umn"}]';
pq: unable to encode table key: *tree.DJSON

[andy-kimball]

It appears that 20.1 fixes #35260 and #46709, but not #35706.

Also, the newly merged UNION rule (which will go into 20.2 since it missed cutoff for 20.1) does not handle this JSON case you give, because it only splits OR clauses that operate over different columns from the input table. I opened an issue to track the inverted index case: #47340.