1377{
1382 int listidx;
1384 int nfunc_dependencies;
1385 int total_ndeps;
1387 int ndependencies;
1391
1392 /* unique expressions */
1393 Node **unique_exprs;
1394 int unique_exprs_cnt;
1395
1396 /* check if there's any stats that might be useful for us. */
1398 return 1.0;
1399
1402
1403 /*
1404 * We allocate space as if every clause was a unique expression, although
1405 * that's probably overkill. Some will be simple column references that
1406 * we'll translate to attnums, and there might be duplicates. But it's
1407 * easier and cheaper to just do one allocation than repalloc later.
1408 */
1410 unique_exprs_cnt = 0;
1411
1412 /*
1413 * Pre-process the clauses list to extract the attnums seen in each item.
1414 * We need to determine if there's any clauses which will be useful for
1415 * dependency selectivity estimations. Along the way we'll record all of
1416 * the attnums for each clause in a list which we'll reference later so we
1417 * don't need to repeat the same work again. We'll also keep track of all
1418 * attnums seen.
1419 *
1420 * We also skip clauses that we already estimated using different types of
1421 * statistics (we treat them as incompatible).
1422 *
1423 * To handle expressions, we assign them negative attnums, as if it was a
1424 * system attribute (this is fine, as we only allow extended stats on user
1425 * attributes). And then we offset everything by the number of
1426 * expressions, so that we can store the values in a bitmapset.
1427 */
1428 listidx = 0;
1429 foreach(l, clauses)
1430 {
1434
1435 /* ignore clause by default */
1437
1439 {
1440 /*
1441 * If it's a simple column reference, just extract the attnum. If
1442 * it's an expression, assign a negative attnum as if it was a
1443 * system attribute.
1444 */
1446 {
1447 list_attnums[listidx] =
attnum;
1448 }
1451 &expr))
1452 {
1453 /* special attnum assigned to this expression */
1455
1457
1458 /* If the expression is duplicate, use the same attnum. */
1459 for (
i = 0;
i < unique_exprs_cnt;
i++)
1460 {
1461 if (
equal(unique_exprs[
i], expr))
1462 {
1463 /* negative attribute number to expression */
1465 break;
1466 }
1467 }
1468
1469 /* not found in the list, so add it */
1471 {
1472 unique_exprs[unique_exprs_cnt++] = expr;
1473
1474 /* after incrementing the value, to get -1, -2, ... */
1475 attnum = (-unique_exprs_cnt);
1476 }
1477
1478 /* remember which attnum was assigned to this clause */
1479 list_attnums[listidx] =
attnum;
1480 }
1481 }
1482
1483 listidx++;
1484 }
1485
1487
1488 /*
1489 * How much we need to offset the attnums? If there are no expressions,
1490 * then no offset is needed. Otherwise we need to offset enough for the
1491 * lowest value (-unique_exprs_cnt) to become 1.
1492 */
1493 if (unique_exprs_cnt > 0)
1494 attnum_offset = (unique_exprs_cnt + 1);
1495 else
1496 attnum_offset = 0;
1497
1498 /*
1499 * Now that we know how many expressions there are, we can offset the
1500 * values just enough to build the bitmapset.
1501 */
1503 {
1505
1506 /* ignore incompatible or already estimated clauses */
1508 continue;
1509
1510 /* make sure the attnum is in the expected range */
1511 Assert(list_attnums[
i] >= (-unique_exprs_cnt));
1513
1514 /* make sure the attnum is positive (valid AttrNumber) */
1515 attnum = list_attnums[
i] + attnum_offset;
1516
1517 /*
1518 * Either it's a regular attribute, or it's an expression, in which
1519 * case we must not have seen it before (expressions are unique).
1520 *
1521 * XXX Check whether it's a regular attribute has to be done using the
1522 * original attnum, while the second check has to use the value with
1523 * an offset.
1524 */
1527
1528 /*
1529 * Remember the offset attnum, both for attributes and expressions.
1530 * We'll pass list_attnums to clauselist_apply_dependencies, which
1531 * uses it to identify clauses in a bitmap. We could also pass the
1532 * offset, but this is more convenient.
1533 */
1535
1537 }
1538
1539 /*
1540 * If there's not at least two distinct attnums and expressions, then
1541 * reject the whole list of clauses. We must return 1.0 so the calling
1542 * function's selectivity is unaffected.
1543 */
1545 {
1547 pfree(list_attnums);
1548 return 1.0;
1549 }
1550
1551 /*
1552 * Load all functional dependencies matching at least two parameters. We
1553 * can simply consider all dependencies at once, without having to search
1554 * for the best statistics object.
1555 *
1556 * To not waste cycles and memory, we deserialize dependencies only for
1557 * statistics that match at least two attributes. The array is allocated
1558 * with the assumption that all objects match - we could grow the array to
1559 * make it just the right size, but it's likely wasteful anyway thanks to
1560 * moving the freed chunks to freelists etc.
1561 */
1564 nfunc_dependencies = 0;
1565 total_ndeps = 0;
1566
1568 {
1570 int nmatched;
1571 int nexprs;
1572 int k;
1574
1575 /* skip statistics that are not of the correct type */
1576 if (
stat->kind != STATS_EXT_DEPENDENCIES)
1577 continue;
1578
1579 /* skip statistics with mismatching stxdinherit value */
1580 if (
stat->inherit != rte->
inh)
1581 continue;
1582
1583 /*
1584 * Count matching attributes - we have to undo the attnum offsets. The
1585 * input attribute numbers are not offset (expressions are not
1586 * included in stat->keys, so it's not necessary). But we need to
1587 * offset it before checking against clauses_attnums.
1588 */
1589 nmatched = 0;
1590 k = -1;
1592 {
1594
1595 /* skip expressions */
1597 continue;
1598
1599 /* apply the same offset as above */
1601
1603 nmatched++;
1604 }
1605
1606 /* count matching expressions */
1607 nexprs = 0;
1608 for (
i = 0;
i < unique_exprs_cnt;
i++)
1609 {
1611
1612 foreach(lc,
stat->exprs)
1613 {
1615
1616 /* try to match it */
1617 if (
equal(stat_expr, unique_exprs[
i]))
1618 nexprs++;
1619 }
1620 }
1621
1622 /*
1623 * Skip objects matching fewer than two attributes/expressions from
1624 * clauses.
1625 */
1626 if (nmatched + nexprs < 2)
1627 continue;
1628
1630
1631 /*
1632 * The expressions may be represented by different attnums in the
1633 * stats, we need to remap them to be consistent with the clauses.
1634 * That will make the later steps (e.g. picking the strongest item and
1635 * so on) much simpler and cheaper, because it won't need to care
1636 * about the offset at all.
1637 *
1638 * When we're at it, we can ignore dependencies that are not fully
1639 * matched by clauses (i.e. referencing attributes or expressions that
1640 * are not in the clauses).
1641 *
1642 * We have to do this for all statistics, as long as there are any
1643 * expressions - we need to shift the attnums in all dependencies.
1644 *
1645 * XXX Maybe we should do this always, because it also eliminates some
1646 * of the dependencies early. It might be cheaper than having to walk
1647 * the longer list in find_strongest_dependency later, especially as
1648 * we need to do that repeatedly?
1649 *
1650 * XXX We have to do this even when there are no expressions in
1651 * clauses, otherwise find_strongest_dependency may fail for stats
1652 * with expressions (due to lookup of negative value in bitmap). So we
1653 * need to at least filter out those dependencies. Maybe we could do
1654 * it in a cheaper way (if there are no expr clauses, we can just
1655 * discard all negative attnums without any lookups).
1656 */
1657 if (unique_exprs_cnt > 0 ||
stat->exprs !=
NIL)
1658 {
1659 int ndeps = 0;
1660
1662 {
1666
1668 {
1673
1674 /* undo the per-statistics offset */
1676
1677 /*
1678 * For regular attributes we can simply check if it
1679 * matches any clause. If there's no matching clause, we
1680 * can just ignore it. We need to offset the attnum
1681 * though.
1682 */
1684 {
1686
1688 {
1690 break;
1691 }
1692
1693 continue;
1694 }
1695
1696 /*
1697 * the attnum should be a valid system attnum (-1, -2,
1698 * ...)
1699 */
1701
1702 /*
1703 * For expressions, we need to do two translations. First
1704 * we have to translate the negative attnum to index in
1705 * the list of expressions (in the statistics object).
1706 * Then we need to see if there's a matching clause. The
1707 * index of the unique expression determines the attnum
1708 * (and we offset it).
1709 */
1711
1712 /* Is the expression index is valid? */
1714
1716
1717 /* try to find the expression in the unique list */
1718 for (int m = 0; m < unique_exprs_cnt; m++)
1719 {
1720 /*
1721 * found a matching unique expression, use the attnum
1722 * (derived from index of the unique expression)
1723 */
1724 if (
equal(unique_exprs[m], expr))
1725 {
1726 unique_attnum = -(m + 1) + attnum_offset;
1727 break;
1728 }
1729 }
1730
1731 /*
1732 * Found no matching expression, so we can simply skip
1733 * this dependency, because there's no chance it will be
1734 * fully covered.
1735 */
1737 {
1739 break;
1740 }
1741
1742 /* otherwise remap it to the new attnum */
1744 }
1745
1746 /* if found a matching dependency, keep it */
1748 {
1749 /* maybe we've skipped something earlier, so move it */
1752
1753 ndeps++;
1754 }
1755 }
1756
1757 deps->
ndeps = ndeps;
1758 }
1759
1760 /*
1761 * It's possible we've removed all dependencies, in which case we
1762 * don't bother adding it to the list.
1763 */
1764 if (deps->
ndeps > 0)
1765 {
1766 func_dependencies[nfunc_dependencies] = deps;
1767 total_ndeps += deps->
ndeps;
1768 nfunc_dependencies++;
1769 }
1770 }
1771
1772 /* if no matching stats could be found then we've nothing to do */
1773 if (nfunc_dependencies == 0)
1774 {
1775 pfree(func_dependencies);
1777 pfree(list_attnums);
1778 pfree(unique_exprs);
1779 return 1.0;
1780 }
1781
1782 /*
1783 * Work out which dependencies we can apply, starting with the
1784 * widest/strongest ones, and proceeding to smaller/weaker ones.
1785 */
1787 total_ndeps);
1788 ndependencies = 0;
1789
1790 while (true)
1791 {
1794
1795 /* the widest/strongest dependency, fully matched by clauses */
1797 nfunc_dependencies,
1798 clauses_attnums);
1799 if (!dependency)
1800 break;
1801
1802 dependencies[ndependencies++] = dependency;
1803
1804 /* Ignore dependencies using this implied attribute in later loops */
1807 }
1808
1809 /*
1810 * If we found applicable dependencies, use them to estimate all
1811 * compatible clauses on attributes that they refer to.
1812 */
1813 if (ndependencies != 0)
1815 sjinfo, dependencies, ndependencies,
1816 list_attnums, estimatedclauses);
1817
1818 /* free deserialized functional dependencies (and then the array) */
1819 for (
i = 0;
i < nfunc_dependencies;
i++)
1820 pfree(func_dependencies[
i]);
1821
1822 pfree(dependencies);
1823 pfree(func_dependencies);
1825 pfree(list_attnums);
1826 pfree(unique_exprs);
1827
1829}
Datum idx(PG_FUNCTION_ARGS)
#define AttributeNumberIsValid(attributeNumber)
#define AttrNumberIsForUserDefinedAttr(attributeNumber)
#define InvalidAttrNumber
int bms_next_member(const Bitmapset *a, int prevbit)
Bitmapset * bms_del_member(Bitmapset *a, int x)
bool bms_is_member(int x, const Bitmapset *a)
Bitmapset * bms_add_member(Bitmapset *a, int x)
BMS_Membership bms_membership(const Bitmapset *a)
MVDependencies * statext_dependencies_load(Oid mvoid, bool inh)
static bool dependency_is_compatible_expression(Node *clause, Index relid, List *statlist, Node **expr)
static bool dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
static Selectivity clauselist_apply_dependencies(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo, MVDependency **dependencies, int ndependencies, AttrNumber *list_attnums, Bitmapset **estimatedclauses)
static MVDependency * find_strongest_dependency(MVDependencies **dependencies, int ndependencies, Bitmapset *attnums)
bool equal(const void *a, const void *b)
bool has_stats_of_kind(List *stats, char requiredkind)
Assert(PointerIsAligned(start, uint64))
#define MaxHeapAttributeNumber
void pfree(void *pointer)
#define planner_rt_fetch(rti, root)
static const struct exclude_list_item skip[]
static void * list_nth(const List *list, int n)
MVDependency * deps[FLEXIBLE_ARRAY_MEMBER]
AttrNumber attributes[FLEXIBLE_ARRAY_MEMBER]