forked frompostgres/postgres
- Notifications
You must be signed in to change notification settings - Fork6
Commit9d9c02c
committed
Teach planner and executor about monotonic window funcs
Window functions such as row_number() always return a value higher thanthe previously returned value for tuples in any given window partition.Traditionally queries such as;SELECT * FROM ( SELECT *, row_number() over (order by c) rn FROM t) t WHERE rn <= 10;were executed fairly inefficiently. Neither the query planner nor theexecutor knew that once rn made it to 11 that nothing further would matchthe outer query's WHERE clause. It would blindly continue until alltuples were exhausted from the subquery.Here we implement means to make the above execute more efficiently.This is done by way of adding a pg_proc.prosupport function to various ofthe built-in window functions and adding supporting code to allow thesupport function to inform the planner if the window function ismonotonically increasing, monotonically decreasing, both or neither. Theplanner is then able to make use of that information and possibly allowthe executor to short-circuit execution by way of adding a "run condition"to the WindowAgg to allow it to determine if some of its execution workcan be skipped.This "run condition" is not like a normal filter. These run conditionsare only built using quals comparing values to monotonic window functions.For monotonic increasing functions, quals making use of the btreeoperators for <, <= and = can be used (assuming the window function columnis on the left). You can see here that once such a condition becomes falsethat a monotonic increasing function could never make it subsequently trueagain. For monotonically decreasing functions the >, >= and = btreeoperators for the given type can be used for run conditions.The best-case situation for this is when there is a single WindowAgg nodewithout a PARTITION BY clause. Here when the run condition becomes falsethe WindowAgg node can simply return NULL. No more tuples will ever matchthe run condition. It's a little more complex when there is a PARTITIONBY clause. In this case, we cannot return NULL as we must still processother partitions. To speed this case up we pull tuples from the outerplan to check if they're from the same partition and simply discard themif they are. When we find a tuple belonging to another partition we startprocessing as normal again until the run condition becomes false or we runout of tuples to process.When there are multiple WindowAgg nodes to evaluate then this complicatesthe situation. For intermediate WindowAggs we must ensure we alwaysreturn all tuples to the calling node. Any filtering done could lead toincorrect results in WindowAgg nodes above. For all intermediate nodes,we can still save some work when the run condition becomes false. We'veno need to evaluate the WindowFuncs anymore. Other WindowAgg nodes cannotreference the value of these and these tuples will not appear in the finalresult anyway. The savings here are small in comparison to what can besaved in the top-level WingowAgg, but still worthwhile.Intermediate WindowAgg nodes never filter out tuples, but here we changeWindowAgg so that the top-level WindowAgg filters out tuples that don'tmatch the intermediate WindowAgg node's run condition. Such filtersappear in the "Filter" clause in EXPLAIN for the top-level WindowAgg node.Here we add prosupport functions to allow the above to work for;row_number(), rank(), dense_rank(), count(*) and count(expr). It appearstechnically possible to do the same for min() and max(), however, it seemsunlikely to be useful enough, so that's not done here.Bump catversionAuthor: David RowleyReviewed-by: Andy Fan, Zhihong YuDiscussion:https://postgr.es/m/CAApHDvqvp3At8++yF8ij06sdcoo1S_b2YoaT9D4Nf+MObzsrLQ@mail.gmail.com1 parent2f4d0d6 commit9d9c02c
File tree
24 files changed
+1547
-151
lines changed- src
- backend
- commands
- executor
- nodes
- optimizer
- path
- plan
- util
- utils/adt
- include
- catalog
- nodes
- optimizer
- test/regress
- expected
- sql
24 files changed
+1547
-151
lines changedLines changed: 8 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1988 | 1988 | | |
1989 | 1989 | | |
1990 | 1990 | | |
| 1991 | + | |
| 1992 | + | |
| 1993 | + | |
| 1994 | + | |
| 1995 | + | |
| 1996 | + | |
| 1997 | + | |
| 1998 | + | |
1991 | 1999 | | |
1992 | 2000 | | |
1993 | 2001 | | |
| |||
0 commit comments
Comments
(0)