|
9 | 9 | * |
10 | 10 | * |
11 | 11 | * IDENTIFICATION |
12 | | - * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.176 2005/04/22 21:58:31 tgl Exp $ |
| 12 | + * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.177 2005/04/23 01:57:34 tgl Exp $ |
13 | 13 | * |
14 | 14 | *------------------------------------------------------------------------- |
15 | 15 | */ |
@@ -63,6 +63,8 @@ static List *generate_bitmap_or_paths(Query *root, RelOptInfo *rel, |
63 | 63 | boolisjoininner, |
64 | 64 | Relidsouter_relids); |
65 | 65 | staticPath*choose_bitmap_and(Query*root,RelOptInfo*rel,List*paths); |
| 66 | +staticintbitmap_path_comparator(constvoid*a,constvoid*b); |
| 67 | +staticCostbitmap_and_cost_est(Query*root,RelOptInfo*rel,List*paths); |
66 | 68 | staticboolmatch_clause_to_indexcol(IndexOptInfo*index, |
67 | 69 | intindexcol,Oidopclass, |
68 | 70 | RestrictInfo*rinfo, |
@@ -476,15 +478,140 @@ generate_bitmap_or_paths(Query *root, RelOptInfo *rel, |
476 | 478 | staticPath* |
477 | 479 | choose_bitmap_and(Query*root,RelOptInfo*rel,List*paths) |
478 | 480 | { |
479 | | -Assert(paths!=NIL);/* else caller error */ |
480 | | -if (list_length(paths)==1) |
481 | | -return (Path*)linitial(paths);/* easy case */ |
| 481 | +intnpaths=list_length(paths); |
| 482 | +Path**patharray; |
| 483 | +Costcostsofar; |
| 484 | +List*qualsofar; |
| 485 | +ListCell*lastcell; |
| 486 | +inti; |
| 487 | +ListCell*l; |
| 488 | + |
| 489 | +Assert(npaths>0);/* else caller error */ |
| 490 | +if (npaths==1) |
| 491 | +return (Path*)linitial(paths);/* easy case */ |
| 492 | + |
482 | 493 | /* |
483 | | - * XXX temporary stopgap: always use all available paths |
| 494 | + * In theory we should consider every nonempty subset of the given paths. |
| 495 | + * In practice that seems like overkill, given the crude nature of the |
| 496 | + * estimates, not to mention the possible effects of higher-level AND and |
| 497 | + * OR clauses. As a compromise, we sort the paths by selectivity. |
| 498 | + * We always take the first, and sequentially add on paths that result |
| 499 | + * in a lower estimated cost. |
| 500 | + * |
| 501 | + * We also make some effort to detect directly redundant input paths, |
| 502 | + * as can happen if there are multiple possibly usable indexes. For |
| 503 | + * this we look only at plain IndexPath inputs, not at sub-OR clauses. |
| 504 | + * And we consider an index redundant if all its index conditions were |
| 505 | + * already used by earlier indexes. (We could use pred_test() to have |
| 506 | + * a more intelligent, but much more expensive, check --- but in most |
| 507 | + * cases simple equality should suffice, since after all the index |
| 508 | + * conditions are all coming from the same query clauses.) |
484 | 509 | */ |
| 510 | + |
| 511 | +/* Convert list to array so we can apply qsort */ |
| 512 | +patharray= (Path**)palloc(npaths*sizeof(Path*)); |
| 513 | +i=0; |
| 514 | +foreach(l,paths) |
| 515 | +{ |
| 516 | +patharray[i++]= (Path*)lfirst(l); |
| 517 | +} |
| 518 | +qsort(patharray,npaths,sizeof(Path*),bitmap_path_comparator); |
| 519 | + |
| 520 | +paths=list_make1(patharray[0]); |
| 521 | +costsofar=bitmap_and_cost_est(root,rel,paths); |
| 522 | +if (IsA(patharray[0],IndexPath)) |
| 523 | +{ |
| 524 | +Assert(list_length(((IndexPath*)patharray[0])->indexclauses)==1); |
| 525 | +qualsofar= (List*)linitial(((IndexPath*)patharray[0])->indexclauses); |
| 526 | +qualsofar=list_copy(qualsofar); |
| 527 | +} |
| 528 | +else |
| 529 | +qualsofar=NIL; |
| 530 | +lastcell=list_head(paths);/* for quick deletions */ |
| 531 | + |
| 532 | +for (i=1;i<npaths;i++) |
| 533 | +{ |
| 534 | +Path*newpath=patharray[i]; |
| 535 | +List*newqual=NIL; |
| 536 | +Costnewcost; |
| 537 | + |
| 538 | +if (IsA(newpath,IndexPath)) |
| 539 | +{ |
| 540 | +Assert(list_length(((IndexPath*)newpath)->indexclauses)==1); |
| 541 | +newqual= (List*)linitial(((IndexPath*)newpath)->indexclauses); |
| 542 | +if (list_difference(newqual,qualsofar)==NIL) |
| 543 | +continue;/* redundant */ |
| 544 | +} |
| 545 | + |
| 546 | +paths=lappend(paths,newpath); |
| 547 | +newcost=bitmap_and_cost_est(root,rel,paths); |
| 548 | +if (newcost<costsofar) |
| 549 | +{ |
| 550 | +costsofar=newcost; |
| 551 | +if (newqual) |
| 552 | +qualsofar=list_concat(qualsofar,list_copy(newqual)); |
| 553 | +lastcell=lnext(lastcell); |
| 554 | +} |
| 555 | +else |
| 556 | +{ |
| 557 | +paths=list_delete_cell(paths,lnext(lastcell),lastcell); |
| 558 | +} |
| 559 | +Assert(lnext(lastcell)==NULL); |
| 560 | +} |
| 561 | + |
| 562 | +if (list_length(paths)==1) |
| 563 | +return (Path*)linitial(paths);/* no need for AND */ |
485 | 564 | return (Path*)create_bitmap_and_path(root,rel,paths); |
486 | 565 | } |
487 | 566 |
|
| 567 | +/* qsort comparator to sort in increasing selectivity order */ |
| 568 | +staticint |
| 569 | +bitmap_path_comparator(constvoid*a,constvoid*b) |
| 570 | +{ |
| 571 | +Path*pa=*(Path*const*)a; |
| 572 | +Path*pb=*(Path*const*)b; |
| 573 | +Costacost; |
| 574 | +Costbcost; |
| 575 | +Selectivityaselec; |
| 576 | +Selectivitybselec; |
| 577 | + |
| 578 | +cost_bitmap_tree_node(pa,&acost,&aselec); |
| 579 | +cost_bitmap_tree_node(pb,&bcost,&bselec); |
| 580 | + |
| 581 | +if (aselec<bselec) |
| 582 | +return-1; |
| 583 | +if (aselec>bselec) |
| 584 | +return1; |
| 585 | +/* if identical selectivity, sort by cost */ |
| 586 | +if (acost<bcost) |
| 587 | +return-1; |
| 588 | +if (acost>bcost) |
| 589 | +return1; |
| 590 | +return0; |
| 591 | +} |
| 592 | + |
| 593 | +/* |
| 594 | + * Estimate the cost of actually executing a BitmapAnd with the given |
| 595 | + * inputs. |
| 596 | + */ |
| 597 | +staticCost |
| 598 | +bitmap_and_cost_est(Query*root,RelOptInfo*rel,List*paths) |
| 599 | +{ |
| 600 | +BitmapAndPathapath; |
| 601 | +Pathbpath; |
| 602 | + |
| 603 | +/* Set up a dummy BitmapAndPath */ |
| 604 | +apath.path.type=T_BitmapAndPath; |
| 605 | +apath.path.parent=rel; |
| 606 | +apath.bitmapquals=paths; |
| 607 | +cost_bitmap_and_node(&apath,root); |
| 608 | + |
| 609 | +/* Now we can do cost_bitmap_heap_scan */ |
| 610 | +cost_bitmap_heap_scan(&bpath,root,rel, (Path*)&apath, false); |
| 611 | + |
| 612 | +returnbpath.total_cost; |
| 613 | +} |
| 614 | + |
488 | 615 |
|
489 | 616 | /**************************************************************************** |
490 | 617 | *---- ROUTINES TO CHECK RESTRICTIONS ---- |
|