Thread: Getting sorted data from foreign server

On Tue, Oct 6, 2015 at 6:46 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> standard_qp_callback() sets root->query_pathkeys to pathkeys on which the
> result of query_planner are expected be sorted upon (see the function for
> more details). The patch checks if any prefix of these pathkeys can be
> entirely evaluated using the foreign relation and at the foreign server
> under consideration. If yes, it gets estimates of costs involved and adds
> paths with those pathkeys. There can be multiple pathkeyless paths added for
> a given base relation. For every such path one path with pathkeys is added.
> If there is an index matching on the foreign server, getting the data sorted
> from foreign server improves execution time as seen from the results. The
> patch adds this functionality entirely in postgres_fdw.

In the interest of full disclosure, I asked Ashutosh to work on this
patch and have discussed the design with him several times.  I believe
that this is a good direction for PostgreSQL to be going.  It's
trivially easy right now to write a query against an FDW that performs
needlessly easy, because a join, or a sort, or an aggregate is
performed on the local server rather than the remote one.   I, and
EnterpriseDB, want that to get fixed.  However, we also want it to get
fixed in the best possible way, and not to do anything unless there is
consensus on it.  So, if anyone has opinions on this topic, please
jump in.

That having been said, here are some review comments on this patch:

- You consider pushing down ORDER BY if any prefix of the query
pathkeys satisfy is_foreign_expr(), but that doesn't seem right to me.
If the user says SELECT * FROM remotetab ORDER BY a, unsafe(a),
ordering the result set by a doesn't help us much.  We've talked a few
times about an incremental sort capability that would take a stream of
tuples already ordered by one or more columns and sort each group by
additional columns, but I don't think we have that currently.  Without
that capability, I don't think there's much benefit in sorting by a
prefix of the pathkeys.  I suspect that if we can't get them all, it's
not worth doing.

- Right now, you have this code below the point where we bail out if
use_remote_estimate is not set.  If we keep it like that, the comment
needs updating.  But I suggest that we consider an ordered path even
if we are not using remote estimates.  Estimate the sorted path to
cost somewhat more than the unsorted path, so that we only choose that
path if the sort actually benefits us.  I don't know exactly how to
come up with a principled estimate given that we don't actually know
whether the remote side will need an extra sort or not, but maybe a
dumb estimate is still better than not trying a sorted path.

- In the long run, we should probably either add some configuration so
that the local side can make better estimates even without
use_remote_estimate, or maybe have a way for the FDW to keep a cache
of data in the system catalogs that is updated by ANALYZE.  Then,
analyzing a foreign table could store information locally about
indexes and so forth, instead of starting each query planning cycle
with no knowledge about the remote side.  That's not a matter for this
patch, I don't think, but it seems like something we should do.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 08/10/15 17:09, Robert Haas wrote:
> - You consider pushing down ORDER BY if any prefix of the query
> pathkeys satisfy is_foreign_expr(), but that doesn't seem right to me.
> If the user says SELECT * FROM remotetab ORDER BY a, unsafe(a),
> ordering the result set by a doesn't help us much.  We've talked a few
> times about an incremental sort capability that would take a stream of
> tuples already ordered by one or more columns and sort each group by
> additional columns, but I don't think we have that currently.  Without
> that capability, I don't think there's much benefit in sorting by a
> prefix of the pathkeys.  I suspect that if we can't get them all, it's
> not worth doing.

That depends how often the additional columns affect the sorted
order, if the sort method takes advantage of sorted input.
-- 
Jeremy

On Thu, Oct 8, 2015 at 3:04 PM, Jeremy Harris <jgh@wizmail.org> wrote:
> That depends how often the additional columns affect the sorted
> order, if the sort method takes advantage of sorted input.

What I'm saying is - ours doesn't.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Oct 13, 2015 at 3:29 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
>> - You consider pushing down ORDER BY if any prefix of the query
>> pathkeys satisfy is_foreign_expr(), but that doesn't seem right to me.
>> If the user says SELECT * FROM remotetab ORDER BY a, unsafe(a),
>> ordering the result set by a doesn't help us much.  We've talked a few
>> times about an incremental sort capability that would take a stream of
>> tuples already ordered by one or more columns and sort each group by
>> additional columns, but I don't think we have that currently.  Without
>> that capability, I don't think there's much benefit in sorting by a
>> prefix of the pathkeys.  I suspect that if we can't get them all, it's
>> not worth doing.
>
> I somehow thought, we are using output, which is ordered by prefix of
> pathkeys in Sort nodes. But as you rightly pointed out that's not the case.
> Only complete pathkeys are useful.

A truncated list of pathkeys is useful for merge joins, but not for
toplevel ordering.

>> - Right now, you have this code below the point where we bail out if
>> use_remote_estimate is not set.  If we keep it like that, the comment
>> needs updating.  But I suggest that we consider an ordered path even
>> if we are not using remote estimates.  Estimate the sorted path to
>> cost somewhat more than the unsorted path, so that we only choose that
>> path if the sort actually benefits us.  I don't know exactly how to
>> come up with a principled estimate given that we don't actually know
>> whether the remote side will need an extra sort or not, but maybe a
>> dumb estimate is still better than not trying a sorted path.
>
> I like that idea, although there are two questions
> 1. How can we estimate cost of getting the data sorted? If there is an
> appropriate index on foreign server we can get the data sorted at no extra
> cost. If there isn't the cost of sorting is proportionate to NlogN where N
> is the size of data. It seems unreasonable to arrive at the cost of sorting
> by multiplying with some constant multiplier. Also, the constant multiplier
> to the NlogN estimate depends heavily upon the properties of foreign server
> e.g. size of memory available for sorting, disk and CPU speed etc. The last
> two might have got factored into fdw_tuple_cost and fdw_startup_cost, so
> that's probably taken care of. If the estimate we come up turns out to be
> too pessimistic, we will not get sorted data even if that's the right thing
> to do. If too optimistic, we will incur heavy cost at the time of execution.
> Setting the cost estimate to some constant factor of NlogN would be too
> pessimistic if there is an appropriate index on foreign server. Otherway
> round if there isn't an appropriate index on foreign server.
>
> Even if we leave these arguments aside for a while, the question remains as
> to what should be the constant factor 10% or 20% or 50% or 100% or something
> else on top of the estimate for simple foreign table scan estimates (or
> NlogN of that)? I am unable to justify any of these factors myself. What do
> you say?

I think we want to estimate the cost in such a way that we'll tend to
pick the ordered path if it's useful, but skip it if it's not.  So,
say we pick 10%.  That's definitely enough that we won't pick a remote
sort when it's useless, but it's small enough that if a remote sort is
useful, we will probably choose to do it.  I think that's what we
want.  I believe we should err on the side of a small estimate because
it's generally better to do as much work as possible on the remote
side.  In some cases the sort may turn out to be free at execution
time because the remote server was going to generate the results in
that order anyway, and it may know that because of its own pathkeys,
and thus be able to skip the explicit ordering step.

>> - In the long run, we should probably either add some configuration so
>> that the local side can make better estimates even without
>> use_remote_estimate, or maybe have a way for the FDW to keep a cache
>> of data in the system catalogs that is updated by ANALYZE.  Then,
>> analyzing a foreign table could store information locally about
>> indexes and so forth, instead of starting each query planning cycle
>> with no knowledge about the remote side.  That's not a matter for this
>> patch, I don't think, but it seems like something we should do.
>
> To an extent knowing which indexes are available on the tables on foreign
> server will help. Now, I do understand that not every foreign server will
> have indexes like PostgreSQL, but as long as whatever they have can be
> translated into a language that PostgreSQL can understand it should be fine.
> From that point of view, will it help if we have declarative indexes on
> foreign tables similar to the declarative constraints? Obviously, we will be
> burdening user with extra work of maintaining the declarative indexes in
> sync like we do for constraints. But we might ease the burden when we get to
> fetch that information automatically from the foreign server.

I think fetching the information from the remote server automatically
is better than forcing the user to declare it.  Quite aside from the
administrative burden, there's no guarantee that the remote data
source's indexing capabilities are representable in our system catalog
structure.  For postgres_fdw they likely will be, unless the remote
server is a newer version with newer magical abilities, but other
systems might behave in ways that don't map onto our notions of what
an index looks like.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Oct 14, 2015 at 7:30 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> The patch uses a factor of 1.1 (10% increase) to multiple the startup and
> total costs in fpinfo for unsorted data.
>
> This change has caused the plans for few queries in the test postgres_fdw to
> change. There is ORDER BY and LIMIT clause in the queries in postgres_fdw
> testcase to keep test outputs sane and consistent. These ORDER BY clauses
> are not being pushed down the foreign servers. I tried using values upto 2
> for this but still the foreign paths with pathkeys won over those without
> pathkeys.

That's great.  Seeing unnecessary sorts disappear from the regression
tests as a result of this patch is, IMHO, pretty cool.  But these
compiler warnings might also be related:

postgres_fdw.c:605:7: error: variable 'rows' is used uninitialized whenever 'if'     condition is false
[-Werror,-Wsometimes-uninitialized]              if (fpinfo->use_remote_estimate)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
postgres_fdw.c:628:13: note: uninitialized use occurs here ...rows,    ^~~~
postgres_fdw.c:605:3: note: remove the 'if' if its condition is always true               if
(fpinfo->use_remote_estimate)              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
postgres_fdw.c:596:15: note: initialize the variable 'rows' to silence this     warning               double
rows;                                  ^                                    = 0.0
 
postgres_fdw.c:605:7: error: variable 'startup_cost' is used uninitialized     whenever 'if' condition is false
[-Werror,-Wsometimes-uninitialized]              if (fpinfo->use_remote_estimate)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
postgres_fdw.c:629:13: note: uninitialized use occurs here ...startup_cost,    ^~~~~~~~~~~~
postgres_fdw.c:605:3: note: remove the 'if' if its condition is always true               if
(fpinfo->use_remote_estimate)              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
postgres_fdw.c:598:21: note: initialize the variable 'startup_cost' to silence     this warning               Cost
     startup_cost;                                           ^                                            = 0.0
 
postgres_fdw.c:605:7: error: variable 'total_cost' is used uninitialized     whenever 'if' condition is false
[-Werror,-Wsometimes-uninitialized]              if (fpinfo->use_remote_estimate)
^~~~~~~~~~~~~~~~~~~~~~~~~~~
postgres_fdw.c:630:13: note: uninitialized use occurs here ...total_cost,    ^~~~~~~~~~
postgres_fdw.c:605:3: note: remove the 'if' if its condition is always true               if
(fpinfo->use_remote_estimate)              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
postgres_fdw.c:599:19: note: initialize the variable 'total_cost' to silence     this warning               Cost
   total_cost;                                         ^                                          = 0.0
 

At least some of those look like actual mistakes.

I would suggest that instead of the regression test you added, you
instead change one of the existing tests to order by a non-pushable
expression that produces the same final output ordering.  The revised
EXPLAIN output shows that the existing tests are already testing that
the sort is getting pushed down; we don't need another test for the
same thing.  Instead, let's adjust one of the tests so that we can
also show that we don't push down ORDER BY clauses when it would be
wrong to do so.  For example, suppose the user specifies a collation
in the ORDER BY clause.

appendOrderByClause could use a header comment, and its definition
line is more than 80 characters, so it should be wrapped.

DEFAULT_FDW_SORT_MULTIPLIER should have a one-line comment, like /* If
no remote estimates, assume a sort costs 10% extra */.  The comment
inside postgresGetForeignPaths shouldn't refer specifically to the 10%
value, in case we change it.  So maybe: "Assume sorting costs
something, so that we won't ask for sorted results when they aren't
useful, but not too much, so that remote sorts will look attractive
when the ordering is useful to us."  Note that "attractive" is missing
a "t" in the patch.

Do you need to ignore ec_has_volatile equivalence classes in
find_em_expr_for_rel?  I bet yes.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Oct 15, 2015 at 6:28 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> Attached is the patch which takes care of above comments.

I spent some time on this patch today.  But it's still not right.

I've attached a new version which fixes a serious problem with your
last version - having postgresGetForeignPaths do the costing of the
sorted path itself instead of delegating that to
estimate_path_cost_size is wrong.  In your version, 10% increment gets
applied to the network transmission costs as well as the cost of
generating the tupes - but only when use_remote_estimate == false.  I
fixed this and did some cosmetic cleanup.

But you'll notice if you try this some of postgres_fdw's regression
tests fail.  This is rather mysterious:

***************
*** 697,715 ****
   Sort
     Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
     Sort Key: t1.c1
!    ->  Nested Loop Semi Join
           Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
!          Join Filter: (t1.c3 = t2.c3)
           ->  Foreign Scan on public.ft1 t1
                 Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
                 Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
!          ->  Materialize
                 Output: t2.c3
!                ->  Foreign Scan on public.ft2 t2
                       Output: t2.c3
!                      Filter: (date(t2.c4) = '01-17-1970'::date)
!                      Remote SQL: SELECT c3, c4 FROM "S 1"."T 1"
WHERE (("C 1" > 10))
! (15 rows)

  EXECUTE st2(10, 20);
   c1 | c2 |  c3   |              c4              |            c5
      | c6 |     c7     | c8
--- 697,718 ----
   Sort
     Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
     Sort Key: t1.c1
!    ->  Hash Join
           Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
!          Hash Cond: (t1.c3 = t2.c3)
           ->  Foreign Scan on public.ft1 t1
                 Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
                 Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
!          ->  Hash
                 Output: t2.c3
!                ->  HashAggregate
                       Output: t2.c3
!                      Group Key: t2.c3
!                      ->  Foreign Scan on public.ft2 t2
!                            Output: t2.c3
!                            Filter: (date(t2.c4) = '01-17-1970'::date)
!                            Remote SQL: SELECT c3, c4 FROM "S 1"."T
1" WHERE (("C 1" > 10))
! (18 rows)

What I think is happening here is that the planner notices that
instead of doing a parameterized nestloop, it could pull down the data
already sorted from the remote side, cheaply unique-ify it by using
the ordering provided by the remote side, and then do a standard hash
join.  That might well be a sensible approach, but the ORDER BY that
would make it correct doesn't show up in the Remote SQL.  I don't know
why that's happening, but it's not good.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Oct 21, 2015 at 5:23 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> Increasing the sorting cost factor (when use_remote_estimates = false) from
> 1.1 to 1.2 makes the difference disappear.
>
> Since the startup costs for postgres_fdw are large portion of total cost,
> extra 10% of rest of the cost is comparable to 1% fuzzy limit. IMO, we
> shouldn't bother too much about it as the path costs are not much different.

My feeling is that cranking the sorting cost factor up to 20-25% would
be a good idea, just so we have less unnecessary plan churn.  I dunno
if sorting always costs that much, but if a 10% cost overhead is
really 1% because it only applies to a fraction of the cost, I don't
think that's good.  The whole point was to pick something large enough
that we wouldn't take the sorted path unless we will benefit from the
sort, and clearly that's not what happened here.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Oct 30, 2015 at 6:19 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> If there is a collate clause in the ORDER BY, the server crashes with
> assertion
> +    Assert(loc_cxt.state == FDW_COLLATE_NONE ||
> +            loc_cxt.state == FDW_COLLATE_SAFE);
>
>
> The assertion is fine as long as is_foreign_expr() tests only boolean
> expressions (appearing in quals). This patch uses the function to test an
> expression appearing in ORDER BY clause, which need not be boolean. Attached
> patch removed the assertion and instead makes the function return false,
> when the walker deems collation of the expression unsafe. The walker can not
> return false when it encounter unsafe expression since the subtree it's
> examining might be part of an expression which does not use the collation
> ultimately.

I've committed this version.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company