opt: avoid estimated row counts of 0

[jordanlewis]

Given the simple table:

[email protected]:65097/defaultdb> create table a (a int);
CREATE TABLE

Check out the following two queries. I expect the output to look like the first one, always, and never the second one.

Good plan (only a single sort):

[email protected]:65097/defaultdb> explain select * from a order by a limit 1 offset 100;
       tree      | field  | description
+----------------+--------+-------------+
  limit          |        |
   │             | count  | 1
   │             | offset | 100
   └── sort      |        |
        │        | order  | +a
        └── scan |        |
                 | table  | a@primary
                 | spans  | ALL
(8 rows)

Bad plan (two sorts):

[email protected]:65097/defaultdb> explain select * from a order by a limit 1 offset 9999;
            tree           | field  | description
+--------------------------+--------+-------------+
  limit                    |        |
   │                       | count  | 1
   └── sort                |        |
        │                  | order  | +a
        └── limit          |        |
             │             | offset | 9999
             └── sort      |        |
                  │        | order  | +a
                  └── scan |        |
                           | table  | a@primary
                           | spans  | ALL
(11 rows)

As far as I can tell, the table should already be sorted after the offset - so there should be no reason to put another sort in between the offset and the limit.

[andy-kimball]

@RaduBerinde, can you take a look?

[RaduBerinde]

The estimated row count after "offset 9999" is 0, which makes the sort "free", and the plan with the sort is considered first. There are two fixes (we probably want both):

• add a constant cpu cost per operator (which would reflect the overhead of setting up the execution for the operator)
• make the row count small but not 0; though I don't know exactly where this value would come from.

  limit                                        
   ├── columns: a:1(int)                       
   ├── internal-ordering: +1                   
   ├── cardinality: [0 - 1]                    
   ├── stats: [rows=0]                         
   ├── cost: 1249.31569                        
   ├── key: ()                                 
   ├── fd: ()-->(1)                            
   ├── sort                                    
   │    ├── columns: a:1(int)                  
   │    ├── stats: [rows=0]                    
   │    ├── cost: 1249.31569                   
   │    ├── ordering: +1                       
   │    └── offset                             
   │         ├── columns: a:1(int)             
   │         ├── internal-ordering: +1         
   │         ├── stats: [rows=0]               
   │         ├── cost: 1249.31569              
   │         ├── sort                          
   │         │    ├── columns: a:1(int)        
   │         │    ├── stats: [rows=1000]       
   │         │    ├── cost: 1249.31569         
   │         │    ├── ordering: +1             
   │         │    ├── prune: (1)               
   │         │    └── scan a                   
   │         │         ├── columns: a:1(int)   
   │         │         ├── stats: [rows=1000]  
   │         │         ├── cost: 1030          
   │         │         └── prune: (1)          
   │         └── const: 9999 [type=int]        
   └── const: 1 [type=int]                     

[RaduBerinde]

The specific case reported here is fixed, however I'm going to repurpose the issue to track the larger problem of 0 row counts.

We should avoid estimated row counts of 0 short of situations where we know it's exactly 0. A row count of 0 prevents the optimizer from making reasonable choices since operators have the same cost.

Note that in this example, without stats, we are subtracting a definite count from an "arbitrary unit" which is also problematic.

[andy-kimball]

I think we could fix this without causing ripples by always adding 1 to the estimated row count. That way, it's always > 0, but still smoothly preserves relative costs between plans.

[RaduBerinde]

Every operator would add 1? So for example, a project would have 1 more row than its input? Or maybe just in those cases where we are making an estimation?

Related to this, I think that whenever we are using real table stats that say 0 rows, we should override them to 1 row (or a few rows).

[andy-kimball]

I was mostly thinking about table stats. I'm suggesting we could always add 1 to them so we never get an estimate of 0 rows. I'm assuming that most (all?) other estimates will be non-zero as long as they have non-zero inputs. The only operators that should return 0 rows would be those where we know there are zero rows, like a Select with a False filter.

[RaduBerinde]

Oh, yeah, that makes sense.

[RaduBerinde]

@rytaft - putting this on your plate. It is possible that #37611 makes the problem of 0 row stats worse. We should do the simple fix of adding 1 to table stats that are zero.