You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "avantgardnerio (via GitHub)" <gi...@apache.org> on 2023/02/22 03:39:14 UTC
[GitHub] [arrow-datafusion] avantgardnerio opened a new pull request, #5362: Add index interface method
avantgardnerio opened a new pull request, #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362
# Which issue does this PR close?
Closes #5357.
# Rationale for this change
If the planner/optimizer has information about how a table is / can be sorted, then it opens up the ability to push more predicates down to the TableProvider.
For example, TPC-H query 9 might perform far better, since the table could be naturally ordered on the primary key `(PS_PARTKEY, PS_SUPPKEY)`:
```
SELECT
nation,
o_year,
SUM(amount) AS sum_profit
FROM
(
SELECT
n_name AS nation,
YEAR(o_orderdate) AS o_year,
l_extendedprice * (1 - l_discount) - ps_supplycost * l_quantity AS amount
FROM
part,
supplier,
lineitem,
partsupp,
orders,
nation
WHERE
s_suppkey = l_suppkey
AND ps_suppkey = l_suppkey
AND ps_partkey = l_partkey
```
after the subquery is de-correlated, it will be trying to join on the primary key, so it will likely:
```
EquiJoin( ps_suppkey = l_suppkey and ps_partkey = l_partkey)
Sort(PS_PARTKEY, PS_SUPPKEY)
TableScan [filter=s_suppkey]
```
When the filter could actually filter far more rows using both columns, and the sort could be avoided entirely.
# What changes are included in this PR?
An interface change to allow `TableProviders` to inform the planner about single or multi-column, primary or secondary indexes, so that a future (fast-follow) PR can push predicates down to filter & sort in the `TableProvider` automatically.
# Are these changes tested?
No, it's an interface change.. though maybe I could test that?
# Are there any user-facing changes?
No, existing `TableProvider`s should be fine.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441022110
Here's the other PR I referenced BTW https://github.com/apache/arrow-datafusion/pull/5367
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1440976811
> often Hash Joins are used
I checked, this is true for query 9. I was trying to find a broadly applicable example, but I'm having a difficult time.
> all the predicates it can
Unfortunately, it pushes them down after it splits the conjunctions. The indexes may not be helpful for partial predicates. By exposing this information to the planner, it can try pushing down ones that match the available indexes. As a side benefit, it might also help to decide when to use a sort-merge-join (without the sort) because PK & FK sides are already ordered correctly for the join.
> non trivial to implement / test / get right.
I was hoping this could be the first step towards that - giving existing index info to the planner certainly couldn't hurt?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441040939
> using a cost model to choose between the plans -- but DataFusion doesn't have this feature at the moment
That was exactly where I foresaw this going. I was aware we merged _some_ cost-based optimization logic recently. If exposing those stats along with the index is the correct direction, I'd be happy to start looking into that.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1442447598
@thinkharderdev also, PTAL at https://github.com/apache/arrow-datafusion/pull/5367 which addresses the pushdown issue (but not the order/index issue).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441002452
> The current planner will test each individual part of the conjunction and the Table will have to scan() all Gardners - even though it would have done a point lookup on Brent Gardner (assuming I'm the only one).
I guess I was imagining the current planner would make something like the following (pushed all predicates down)
```
TableScan (filters: [f_name = 'Brent', l_name = 'Gardner', age > 21])
```
The `TableProvider` would then get called `scan(... filters: [f_name = 'Brent', l_name = 'Gardner', age > 21]...)`
Then whatever implemented the table scan could look at that list of predicates and figure out it could use its index on `[l_name, f_name]` to quickly answer with the `Brent Gardner` row. So while the interface says "scan" the `TableProvider` implementation could really do an `IndexScan`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441012937
Unfortunately, as I put in the original issue, given the sql `WHERE s_i_id = $1 AND s_w_id = $2` the planner calls the `TableProvider.supports_filter_pushdown()` with each part of the clause:
```
ArrowTableProvider::supports_filter_pushdown() proj=stock.s_i_id = Int32(3604)
ArrowTableProvider::supports_filter_pushdown() proj=stock.s_w_id = Int32(1)
```
I suppose what I can do is just return `Exact` for everything, then the TableProvider would get the full predicate. Unfortunately that means it would also get `age > 21` which might be simple enough to deal with, but it would also have to evaluate all possible expressions `x / sqrt(pi) * UDF(y)` which starts looking more like something we'd want to have happening in a higher layer...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441019524
I guess in the case I get `f_name` before `l_name`, I could just return exact for both because even though I don't have an index that starts with `f_name`, I could hope `l_name` is coming next, and either way since they are simple `BinaryExpression`s I could know that they:
1. might be part of an index I have
2. be able to evaluate them anyway if not
I was just hoping to get a cleaner interface on this that made it easier on `TableProvider`s and simultaneously providing the `planner` with info it would find useful as we add the ability to work with indexes in the future.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] boazberman commented on pull request #5362: Add index interface method
Posted by "boazberman (via GitHub)" <gi...@apache.org>.
boazberman commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1440351641
Hmm my approach to this (when trying to implement index usage) is a bit different different. I wrote an optimization rule to rewrite the query plan to use a different table. This is yet to be working (I have schema related errors), but I think it is at least worth throwing that into the discussion.
In terms of best approach, I think it would be wise to a new physical plan node called `IndexScan` (like _TableScan_), to have a more meaningful query plans with `EXPLAIN`, and to make it closer to how OLTP databases present that data.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441737279
>> using a cost model to choose between the plans -- but DataFusion doesn't have this feature at the moment
> That was exactly where I foresaw this going. I was aware we merged some cost-based optimization logic recently. If exposing those stats along with the index is the correct direction, I'd be happy to start looking into that.
I agree that the usecase of DataFusion to cost out multiple possible TableScans (e.g. using different indexes) as part of the overall plan makes sense, though I am not sure if this PR's interface is ideal for that scenario -- it seems more like we could model the different paths as potentially different TableProviders might be more natural
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb closed pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed pull request #5362: Add index interface method
URL: https://github.com/apache/arrow-datafusion/pull/5362
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1440675211
> physical plan node called IndexScan (like TableScan), to have a more meaningful query plans with EXPLAIN, and to make it closer to how OLTP databases present that data.
Though I agree that would make the plans read better, I think the index needs to live within the `TableProvider` / `TableScan` node because we don't want to return all of the filtered data any farther up the tree than we need to, much like predicate pushdown.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1442445977
> Is the idea here that we bubble information about global sort indexes up to the logical TableProvider so we avoid splitting those two predicates when pushing down to the scan?
Yes, I was hoping this API would provide enough info for the planner to see that there is no index on `f_name` or `[f_name, l_name]` but there was one on `[l_name, f_name]` and call `supports_filter_pushdown()` on the latter and if it gets `Exact` then to use it, rather than always breaking it down into individual BinaryExpressions.
Additionally, later, my hope was that the planner could realize:
1. There is an orders table with a PK `(merch_id, order_id)`
2. There is a line items table with a keys: `(merch_id, order_id, lineitem_id)`, `(merch_id, order_id)`
3. Know that it can sort-merge-join the (pre-sorted) tables as long as it picks the indexes for `(merch_id, order_id)`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1445403630
> #5367 supercedes this PR
That solves the point-lookup filter pushdown issue, but doesn't address primary or secondary indexes or natural sort order of the results of `TableProvider::scan()` (i.e. if sorted by correct key can avoid Sort nodes up the tree in the plan).
I'm totally fine closing this one for now, but the above issues and more will arise again if things go well at S&T this year.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1446365060
> I can find time to help write up some thoughts
That would be great, ty!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1445354180
I believe https://github.com/apache/arrow-datafusion/pull/5367 supercedes this PR. Please reopen if I got that wrong.
Thanks @avantgardnerio
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441729348
> I guess in the case I get f_name before l_name, I could just return exact for both because even though I don't have an index that starts with f_name, I could hope l_name is coming next, and either way since they are simple BinaryExpressions I could know that they:
I think I am confused. I thought if the TableProvider returned `TableProviderFilterPushDown::Inexact` you would get all the filters as part of the scan. I tried to ask this question more clearly in https://github.com/apache/arrow-datafusion/issues/5357#issuecomment-1441721936
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1440963131
> Though I agree that would make the plans read better, I think the index needs to live within the TableProvider / TableScan node because we don't want to return all of the filtered data any farther up the tree than we need to, much like predicate pushdown.
One way might be to extend the `TableScan` display to include something from the `TablerProvider`
So something like this perhaps
```rust
trait TableProvider {
/// return optional extra content to include in an EXPLAIN plan
fn explain_plan_extras(&self) -> Option<String>;
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #5362: Add index interface method
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1446233230
> I'm totally fine closing this one for now, but the above issues and more will arise again if things go well at S&T this year.
I agree -- I can find time to help write up some thoughts on adding indexes (aka alternate access paths) to DataFusion if that would be helpful. I think we probably should have a bigger architectural discussion / plan about how it would work.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1439396153
Thinking about it a little more... we might still need the ability for the `TableProvider` to specify what the sort columns for the returned items are.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] thinkharderdev commented on pull request #5362: Add index interface method
Posted by "thinkharderdev (via GitHub)" <gi...@apache.org>.
thinkharderdev commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1442362033
> The current planner will test each individual part of the conjunction and the Table will have to scan() all `Gardner`s - even though it would have done a point lookup on `Brent Gardner` (assuming I'm the only one).
This is a bit awkward in the current model. We have a (very rudimentary) notion of cost modeling when doing predicate pushdown in the parquet scan when determining what order to evaluate the predicates. As you mention it's not quite ideal since by that point we have already split the conjunctions, but it has one advantage in that by that point you are dealing with a single file so you have more metadata to make a cost calculation (column chunk sizes, etc). Is the idea here that we bubble information about global sort indexes up to the logical `TableProvider` so we avoid splitting those two predicates when pushing down to the scan?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1441989689
> not sure if this PR's interface is ideal for that scenario
I had anticipated that this signature would solicit the above response:
```
fn ordered_indexes(&self) -> Result<Vec<Vec<(Column, SortOptions)>>>
```
But was hoping that by submitting the PR we could begin the discussion of what would be better, i.e.:
```
enum Cost {
LogN,
MLogN,
Etc
}
struct OrderedIndex {
columns: Vec<Column>,
cost_per_row: Cost
}
fn ordered_indexes(&self) -> Result<Vec<OrderedIndex>>
```
> modeling the different paths as different TableProviders
That is a surprising (to me) way of modelling it, and why submitting the PR early seemed like the best approach (so we could converge our understandings early).
The reason it is surprising to me is that all of the various TableProviders would represent the same underlying data, have the same schema & name, etc. I understand this might be easier to fit into the existing planner, but I'm not sure how we would over come these issues, particularly duplicate names?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] avantgardnerio commented on pull request #5362: Add index interface method
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #5362:
URL: https://github.com/apache/arrow-datafusion/pull/5362#issuecomment-1440980257
> it can try pushing down ones that match the available indexes
Let me provide an example: `select * from person where f_name='Brent' and l_name='Gardner' and age > 21`. There may be an ordered index on `[l_name, f_name]` but nothing else.
The current planner will test each individual part of the conjunction and the Table will have to scan() all `Gardner`s - even though it would have done a point lookup on `Brent Gardner` (assuming I'm the only one).
With the changes in my other PR, it tries to push down the whole clause, which the TableProvider will return `Unsupported` since it doesn't have an index on all 3.
This PR would give enough information to the planner to let it know it can push down 2/3 of the parts of the predicate.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org