On Sun, 30 Dec 2018 at 13:00, James Coleman <jtc...@gmail.com> wrote: > Note that the index scan (or bitmap scan) nodes return all 1500 rows > matching `bar_fk IN (1,2,3)`. After all rows are returned, that total > set is ordered, and finally the LIMIT is applied. While only 50 rows > were requested, 30x that were fetched from the heap. > > I believe it is possible to use the index > `index_foos_on_bar_fk_and_created_at` to fulfill both the `bar_fk IN > (1,2,3)` qualifier and (at least partially; more on that later) the > ordering `ORDER BY created_at` while fetching fewer than all rows > matching the qualifier. > > Areas of extension: (given index `(a, b, c)`) include `a = 1 and b in > (...) order by c` and `a in (...) and b = 1 order by c` (and further > similar derivations with increasing numbers of equality quals).
I don't quite understand this the above paragraph, but I assume this would be possible to do with some new index am routine which allowed multiple different values for the initial key. Probably execution for something like this could be handled by having 1 IndexScanDesc per initial key. A scan would have to scan all of those for the first tuple and return the lowest order key. Subsequent scans would fetch the next tuple for the IndexScanDesc used previously then again, return the lowest order tuple. There's some binary heap code and examples in nodeMergeAppend.c about how that could be done fairly efficiently. The hard part about that would be knowing when to draw the line. If there was 1000's of initial keys then some other method might be better. Probably the planner would have to estimate which method was best. There are also issues if there are multiple prefix keys as you'd need to scan a cartesian product of the keys, which would likely get out of hand quickly with 2 or more initial keys. There were discussions and a patch for a planner-level implementation of which could likely assist with this in [1]. I'm not sure if this particular case was handled in the patch. I believe it was more intended for queries such as: SELECT ... FROM t WHERE a = 1 OR b = 2 and could transform this into something more along the lines of: SELECT .. FROM t WHERE a = 1 UNION SELECT ... FROM t WHERE b = 1, and using the table's ctid to uniquify the rows. You could get away with something similar but use UNION ALL instead. You don't need UNION since your "OR" is on the same column, meaning there can be no overlapping rows. Something like: (SELECT * FROM foos WHERE bar_fk = 1 LIMIT 50) UNION ALL (SELECT * FROM foos WHERE bar_fk = 2 LIMIT 50) UNION ALL (SELECT * FROM foos WHERE bar_fk = 3 LIMIT 50) ORDER BY created_at LIMIT 50; > Note: Another (loosely) related problem is that sorting can't > currently take advantage of cases where an index provides a partial > (prefix of requested pathkeys) ordering. There has been a patch [2] around for about 4 years now that does this. I'm unsure of the current status, other than not yet committed. [1] https://www.postgresql.org/message-id/flat/7f70bd5a-5d16-e05c-f0b4-2fdfc8873489%40BlueTreble.com [2] https://www.postgresql.org/message-id/flat/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etze...@mail.gmail.com -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services
