23#ifndef SQL_JOIN_OPTIMIZER_INTERESTING_ORDERS_H
24#define SQL_JOIN_OPTIMIZER_INTERESTING_ORDERS_H
252 used_at_end, homogenize_tables);
306 void Build(
THD *thd, std::string *trace);
339 fd_set.set(new_fd_idx - 1);
355 if (ordering_idx == 0) {
361 return m_dfsm_states[state_idx].follows_interesting_order.test(
392 std::bitset<kMaxSupportedOrderings> ignored_orderings)
const {
394 std::bitset<kMaxSupportedOrderings> a =
395 m_dfsm_states[a_idx].follows_interesting_order & ~ignored_orderings;
396 std::bitset<kMaxSupportedOrderings> b =
397 m_dfsm_states[b_idx].follows_interesting_order & ~ignored_orderings;
398 std::bitset<kMaxSupportedOrderings> future_a =
399 m_dfsm_states[a_idx].can_reach_interesting_order & ~ignored_orderings;
400 std::bitset<kMaxSupportedOrderings> future_b =
401 m_dfsm_states[b_idx].can_reach_interesting_order & ~ignored_orderings;
402 return (a & b) != a || (future_a & future_b) != future_a;
609 bool used_at_end,
table_map homogenize_tables);
650 THD *thd,
Ordering reduced_ordering,
bool used_at_end,
int table_idx,
670 int *generation,
int extra_allowed_fd_idx);
693 int *start_point)
const;
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:802
Definition: interesting_orders.h:214
void SetHeadForAggregates(Bounds_checked_array< ItemHandle > head)
Definition: interesting_orders.h:283
void CreateOrderingsFromGroupings(THD *thd)
We don't currently have any operators that only group and do not sort (e.g.
Definition: interesting_orders.cc:837
Ordering ReduceOrdering(Ordering ordering, bool all_fds, OrderElement *tmpbuf) const
Remove redundant elements using the functional dependencies that we have, to give a more canonical fo...
Definition: interesting_orders.cc:1002
bool ItemHandleBeforeInGroup(ItemHandle a, ItemHandle b)
Definition: interesting_orders.h:597
void AddFDsFromComputedItems(THD *thd)
Try to add new FDs from items that are not base items; e.g., if we have an item (a + 1),...
Definition: interesting_orders.cc:511
Mem_root_array< OrderingWithInfo > m_orderings
Definition: interesting_orders.h:567
Bounds_checked_array< int > m_optimized_fd_mapping
Definition: interesting_orders.h:587
StateIndex SetOrder(int ordering_idx) const
Definition: interesting_orders.h:326
int num_orderings() const
Definition: interesting_orders.h:256
bool DoesFollowOrder(StateIndex state_idx, int ordering_idx) const
Definition: interesting_orders.h:353
bool m_rollup
Definition: interesting_orders.h:450
int m_longest_ordering
Definition: interesting_orders.h:570
int AddArtificialState(THD *thd, Ordering ordering)
Definition: interesting_orders.cc:1175
bool CouldBecomeInterestingOrdering(Ordering ordering) const
For a given ordering, check whether it ever has the hope of becoming an interesting ordering.
Definition: interesting_orders.cc:1120
Mem_root_array< DFSMState > m_dfsm_states
Definition: interesting_orders.h:579
bool m_built
Definition: interesting_orders.h:406
int RemapOrderingIndex(int ordering_idx) const
Definition: interesting_orders.h:319
void FinalizeDFSMState(THD *thd, int state_idx)
Definition: interesting_orders.cc:1592
bool ImpliedByEarlierElements(ItemHandle item, Ordering prefix, bool all_fds) const
Checks whether the given item is redundant given previous elements in the ordering; ie....
Definition: interesting_orders.cc:730
void PrintDFSMDottyGraph(std::string *trace) const
Definition: interesting_orders.cc:1941
bool ordering_is_relevant_for_sortahead(int ordering_idx) const
Definition: interesting_orders.h:262
void PreReduceOrderings(THD *thd)
Do safe reduction on all orderings (some of them may get merged by PruneUninterestingOrders() later),...
Definition: interesting_orders.cc:797
void SetRollup(bool rollup)
Definition: interesting_orders.h:290
void PrintFunctionalDependencies(std::string *trace)
Definition: interesting_orders.cc:1853
void CreateHomogenizedOrderings(THD *thd)
For each interesting ordering, see if we can homogenize it onto each table.
Definition: interesting_orders.cc:925
Mem_root_array< NFSMState > m_states
Definition: interesting_orders.h:575
int AddOrderingInternal(THD *thd, Ordering order, OrderingWithInfo::Type type, bool used_at_end, table_map homogenize_tables)
Definition: interesting_orders.cc:122
void AddFDsFromConstItems(THD *thd)
Try to add FDs from items that are constant by themselves, e.g.
Definition: interesting_orders.cc:625
int AddFunctionalDependency(THD *thd, FunctionalDependency fd)
Definition: interesting_orders.cc:175
void PrintNFSMDottyGraph(std::string *trace) const
Definition: interesting_orders.cc:1906
Mem_root_array< DFSMEdge > m_dfsm_edges
Definition: interesting_orders.h:580
bool MoreOrderedThan(StateIndex a_idx, StateIndex b_idx, std::bitset< kMaxSupportedOrderings > ignored_orderings) const
Definition: interesting_orders.h:390
bool AlwaysActiveFD(int fd_idx)
Definition: interesting_orders.cc:1587
void BuildNFSM(THD *thd)
Definition: interesting_orders.cc:1242
Mem_root_array< NFSMEdge > m_edges
Definition: interesting_orders.h:576
void BuildEquivalenceClasses()
Definition: interesting_orders.cc:405
int StateIndex
Definition: interesting_orders.h:324
void AddHomogenizedOrderingIfPossible(THD *thd, Ordering reduced_ordering, bool used_at_end, int table_idx, Bounds_checked_array< std::pair< ItemHandle, ItemHandle > > reverse_canonical, OrderElement *tmpbuf)
Helper function for CreateHomogenizedOrderings().
Definition: interesting_orders.cc:1017
Ordering ordering(int ordering_idx) const
Definition: interesting_orders.h:258
bool FunctionalDependencyApplies(const FunctionalDependency &fd, const Ordering ordering, int *start_point) const
Definition: interesting_orders.cc:1206
void PruneNFSM(THD *thd)
Try to prune away irrelevant nodes from the NFSM; it is worth spending some time on this,...
Definition: interesting_orders.cc:1457
Item * item(ItemHandle item) const
Definition: interesting_orders.h:222
void FindElementsThatCanBeAddedByFDs()
Definition: interesting_orders.cc:686
void PrintInterestingOrders(std::string *trace)
Definition: interesting_orders.cc:1870
StateIndex ApplyFDs(StateIndex state_idx, FunctionalDependencySet fds) const
Definition: interesting_orders.cc:250
Bounds_checked_array< int > m_optimized_ordering_mapping
Definition: interesting_orders.h:584
void AddGroupingFromOrdering(THD *thd, int state_idx, Ordering ordering, OrderElement *tmpbuf)
Definition: interesting_orders.cc:1378
int AddOrdering(THD *thd, Ordering order, bool interesting, bool used_at_end, table_map homogenize_tables)
Definition: interesting_orders.h:247
void ExpandThroughAlwaysActiveFDs(Mem_root_array< int > *nfsm_states, int *generation, int extra_allowed_fd_idx)
Definition: interesting_orders.cc:1609
void TryAddingOrderWithElementInserted(THD *thd, int state_idx, int fd_idx, Ordering old_ordering, size_t start_point, ItemHandle item_to_add, enum_order direction, OrderElement *tmpbuf)
Definition: interesting_orders.cc:1397
void PruneFDs(THD *thd)
Definition: interesting_orders.cc:336
void PruneUninterestingOrders(THD *thd)
Try to get rid of uninteresting orders, possibly by discarding irrelevant suffixes and merging them w...
Definition: interesting_orders.cc:282
void AddFDsFromAggregateItems(THD *thd)
Definition: interesting_orders.cc:648
std::string PrintOrdering(Ordering ordering) const
Definition: interesting_orders.cc:1806
bool ItemBeforeInGroup(const OrderElement &a, const OrderElement &b)
Definition: interesting_orders.h:603
Bounds_checked_array< ItemHandle > CollectHeadForStaticWindowFunction(THD *thd, ItemHandle argument_item, Window *window)
Definition: interesting_orders.cc:470
Mem_root_array< ItemInfo > m_items
Definition: interesting_orders.h:441
ItemHandle GetHandle(Item *item)
Definition: interesting_orders.cc:1082
void FindInitialStatesForOrdering()
Definition: interesting_orders.cc:1794
LogicalOrderings(THD *thd)
Definition: interesting_orders.cc:100
Mem_root_array< FunctionalDependency > m_fds
Definition: interesting_orders.h:572
void ConvertNFSMToDFSM(THD *thd)
From the NFSM, convert an equivalent DFSM.
Definition: interesting_orders.cc:1654
Bounds_checked_array< ItemHandle > m_aggregate_head
Definition: interesting_orders.h:445
FunctionalDependencySet GetFDSet(int fd_idx) const
Definition: interesting_orders.h:335
void RecanonicalizeGroupings()
Definition: interesting_orders.cc:455
std::string PrintFunctionalDependency(const FunctionalDependency &fd, bool html) const
Definition: interesting_orders.cc:1820
void AddEdge(THD *thd, int state_idx, int required_fd_idx, Ordering ordering)
Definition: interesting_orders.cc:1191
int num_fds() const
Definition: interesting_orders.h:272
void Build(THD *thd, std::string *trace)
Definition: interesting_orders.cc:205
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:421
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:945
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:104
bool IsGrouping(Ordering ordering)
Definition: interesting_orders.cc:96
std::bitset< kMaxSupportedFDs > FunctionalDependencySet
Definition: interesting_orders_defs.h:62
static constexpr int kMaxSupportedFDs
Definition: interesting_orders_defs.h:61
static constexpr int kMaxSupportedOrderings
Definition: interesting_orders_defs.h:64
int ItemHandle
Definition: interesting_orders_defs.h:38
enum_order
Definition: key_spec.h:64
uint64_t table_map
Definition: my_table_map.h:29
required string type
Definition: replication_group_member_actions.proto:33
Definition: interesting_orders.h:157
ItemHandle tail
Definition: interesting_orders.h:189
enum FunctionalDependency::@93 type
@ FD
Definition: interesting_orders.h:179
@ DECAY
Definition: interesting_orders.h:172
@ EQUIVALENCE
Definition: interesting_orders.h:185
bool always_active
Definition: interesting_orders.h:211
Bounds_checked_array< ItemHandle > head
Definition: interesting_orders.h:188
Definition: interesting_orders.h:511
int state_idx
Definition: interesting_orders.h:513
int required_fd_idx
Definition: interesting_orders.h:512
const DFSMState * state(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:519
const FunctionalDependency * required_fd(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:515
Definition: interesting_orders.h:468
FunctionalDependencySet can_use_fd
Definition: interesting_orders.h:490
Mem_root_array< int > nfsm_states
Definition: interesting_orders.h:470
std::bitset< kMaxSupportedOrderings > follows_interesting_order
Definition: interesting_orders.h:478
Mem_root_array< int > outgoing_edges
Definition: interesting_orders.h:469
std::bitset< kMaxSupportedOrderings > can_reach_interesting_order
Definition: interesting_orders.h:485
Bounds_checked_array< int > next_state
Definition: interesting_orders.h:475
Definition: interesting_orders.h:408
bool used_desc
Definition: interesting_orders.h:436
bool used_in_grouping
Definition: interesting_orders.h:437
ItemHandle canonical_item
Definition: interesting_orders.h:422
bool can_be_added_by_fd
Definition: interesting_orders.h:428
bool used_asc
Definition: interesting_orders.h:435
Item * item
Definition: interesting_orders.h:410
Definition: interesting_orders.h:493
const NFSMState * state(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:507
int required_fd_idx
Definition: interesting_orders.h:498
const FunctionalDependency * required_fd(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:503
int state_idx
Definition: interesting_orders.h:501
Definition: interesting_orders.h:452
Mem_root_array< int > outgoing_edges
Definition: interesting_orders.h:454
enum LogicalOrderings::NFSMState::@94 type
std::bitset< kMaxSupportedOrderings > can_reach_interesting_order
Definition: interesting_orders.h:459
@ ARTIFICIAL
Definition: interesting_orders.h:453
@ DELETED
Definition: interesting_orders.h:453
@ INTERESTING
Definition: interesting_orders.h:453
int satisfied_ordering_idx
Definition: interesting_orders.h:456
int seen
Definition: interesting_orders.h:466
Ordering satisfied_ordering
Definition: interesting_orders.h:455
Definition: interesting_orders.h:524
StateIndex state_idx
Definition: interesting_orders.h:564
Ordering ordering
Definition: interesting_orders.h:525
bool used_at_end
Definition: interesting_orders.h:558
Type
Definition: interesting_orders.h:530
@ UNINTERESTING
Definition: interesting_orders.h:555
@ INTERESTING
Definition: interesting_orders.h:533
@ HOMOGENIZED
Definition: interesting_orders.h:548
enum LogicalOrderings::OrderingWithInfo::Type type
table_map homogenize_tables
Definition: interesting_orders.h:561
Definition: interesting_orders_defs.h:43
ItemHandle item
Definition: interesting_orders_defs.h:44