New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Make optimizer to consider ORDER BY optimization when making decision about join order [CORE1482] #1898
Comments
Modified by: @livius2description: i have problem with Firebird 1.5.4 and Select First i do something like that SELECT FIRST 10 ID, NAME FROM TABLEX and tableX have 1 000 000 records this query run in 10 minutes! definition of table "ID" INTEGER CONSTRAINT "NK_HIST_DB__ID" NOT NULL, => i have problem with Firebird 1.5.4 and Select First i do something like that select PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) and HIST_DB have 1 000 000 records this query run in 10 minutes! |
Commented by: @livius2 I found better plan |
Modified by: @livius2description: i have problem with Firebird 1.5.4 and Select First i do something like that select PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) and HIST_DB have 1 000 000 records this query run in 10 minutes! => i have problem with Firebird 1.5.4 and Select First i do something like that select PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) and HIST_DB have 1 000 000 records this query run in 10 minutes! plan should be like this summary: SELECT FIRST and big table - geting few records take long time => SELECT FIRST and big table - geting few records take long time - wrong plan |
Commented by: @pcisar There is nothing to improve in engine here. The fact that you want to get only one row is irrelevant, because you asked for row from ordered set, so engine has to process the whole result set from your poor query (inner join of big tables without constraints that has to be processed as natural scan of 100k rows joining X rows from 1m rows) and then sort it to find the row you wanted. It should be order of magnitude faster without ORDER BY. The execution plan you wanted could be hardly created. Query execution is a waterfall-like process defined in trees, but to achieve your desired plan, optimizer has to internally merge different adjacent operations from different levels into one and re-optimize the result to see whether resulted plan is better. This would require one hell of complex optimizer that may get better plans in few special cases, but would otherwise just waste cycles. Next time consult firebird-support or firebird-devel list before making pointless tracker entries, please. |
Commented by: @livius2 as you can see this plan PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) but when thises words occure optimizer should use anodher algoritm i try this query in MSSQL with Top clause and this run in percent of milisecond |
Commented by: @dyemanov Pavel, you're wrong here. The master stream (H) can be easily navigated via the index and row-by-row joined with the dependent stream (A). Moreover, the optimizer always chooses such a plan if possible, even if the FIRST clause is not specified. So, I really don't know why this is not happening here. Karol, is index PK_HIST_DB__ID active? Do you have an up-to-date index statistics? Did you try this query on FB2 (after restoring as an ODS11 database)? Anyway, I doubt this can be fixed in the v1.5 series, as there are no plans to release v1.5.5. |
Commented by: @livius2 yes - before i post this heare i will try this on FB2 but not today |
Commented by: @pcisar Dmitry, it seems that you didn't get it right either :-) ORDER BY is applied to final result, i.e. optimization via navigational index is considered after join order is chosen and checked against it. Table cardinalities (with absence of constraints) lead optimizer to choose A->H join order that doesn't allow to use navigational index on H. What Karol is asking for is to add a heuristic to the optimizer on condition when FIRST/ROWS + ORDER BY is used (it's pointless without FIRST/ROWS) to use (if possible, of course) join order that would allow navigational index without using standard join order calculation (it's only way to get to the desired H->A join order in this case). While it could be relatively easy to implement to get better plans for simple joins like this, it could quickly turn into nightmare on more complex ones. I'm not against adding heuristic extensions to basically cost-based optimizer per se, but this one would be quite complex (with pushing information down the stream) to get great plan for very special case. I think that's not worth the effort. For cases like this we have PLAN clause to force the desired plan. |
Commented by: @livius2 Pavel Cisar wrote: "For cases like this we have PLAN clause to force the desired plan. " I known that plan clause can by used- i post this only to do Firebird better - now is very good - but can be better if optimizer spent one more ms to check this i suppose this is acceptable? in real world systems - plan can not by explicitly specified (not always) becaouse users add something to where clause |
Commented by: @pcisar Ok, I have reopened this entry to keep the idea around for consideration. But don't expect it re-evaluated sooner than after 3.0 release. |
Modified by: @pcisarpriority: Major [ 3 ] => Minor [ 4 ] Version: 2.0.3 [ 10200 ] Version: 2.1.0 [ 10041 ] description: i have problem with Firebird 1.5.4 and Select First i do something like that select PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) and HIST_DB have 1 000 000 records this query run in 10 minutes! plan should be like this => When only limited number of rows is requested (using FIRST/ROW) from ordered set, fetching records in index order is preferable to sort. Optimizer should prefer join order that will allow using navigational index. Just an idea: Introducing fixed cardinality of result set forced by FIRST/ROWS into calculations may solve this issue naturally. Original description: i do something like that select PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ))) and HIST_DB have 1 000 000 records this query run in 10 minutes! plan should be like this summary: SELECT FIRST and big table - geting few records take long time - wrong plan => Make optimizer to consider ORDER BY optimization when making decision about join order environment: WINDOWS 2003 SERVER on Server side and WinXP Prof on Client side => |
Modified by: @dyemanovassignee: Dmitry Yemanov [ dimitr ] |
Modified by: @pcisarWorkflow: jira [ 13190 ] => Firebird [ 13975 ] |
Modified by: @dyemanovstatus: Reopened [ 4 ] => In Progress [ 3 ] |
Modified by: @dyemanovstatus: In Progress [ 3 ] => Open [ 1 ] |
Modified by: @dyemanovstatus: Open [ 1 ] => Resolved [ 5 ] resolution: Fixed [ 1 ] Fix Version: 3.0 Beta 1 [ 10332 ] |
Modified by: @pavel-zotovstatus: Resolved [ 5 ] => Resolved [ 5 ] QA Status: Done successfully Test Details: in 2.1 and 2.5: PLAN SORT (JOIN (M NATURAL, D INDEX (THORSES_COLOR_ID))) -- doesn`t see 'rows 1'. |
Submitted by: @livius2
Relate to CORE4428
Is related to QA628
Votes: 2
When only limited number of rows is requested (using FIRST/ROW) from ordered set, fetching records in index order is preferable to sort. Optimizer should prefer join order that will allow using navigational index.
Just an idea: Introducing fixed cardinality of result set forced by FIRST/ROWS into calculations may solve this issue naturally.
Original description:
i have problem with Firebird 1.5.4 and Select First
i do something like that
select
FIRST 1
*
FROM
HIST_DB H
INNER JOIN ADRESY_DB A ON A.ID=H.ID_OBJ
ORDER BY http://H.ID ASC
PLAN SORT (JOIN (A NATURAL,H INDEX (FK_HIST_DB__ID_OBJ)))
and HIST_DB have 1 000 000 records
ADRESY_DB have 100 000 records
this query run in 10 minutes!
plan should be like this
PLAN JOIN (H ORDER PK_HIST_DB__ID,A INDEX (PK_ADRESY_DB__ID))
Commits: 15113ae FirebirdSQL/fbt-repository@2f66134
====== Test Details ======
in 2.1 and 2.5: PLAN SORT (JOIN (M NATURAL, D INDEX (THORSES_COLOR_ID))) -- doesn`t see 'rows 1'.
in 3.0 plan should CHANGE and take in account 'rows N' limit.
The text was updated successfully, but these errors were encountered: