23#ifndef SQL_JOIN_OPTIMIZER_INTERESTING_ORDERS_H
24#define SQL_JOIN_OPTIMIZER_INTERESTING_ORDERS_H
252 used_at_end, homogenize_tables);
263 return !
m_orderings[ordering_idx].ordering.empty() &&
307 void Build(
THD *thd, std::string *trace);
340 fd_set.set(new_fd_idx - 1);
356 if (ordering_idx == 0) {
362 return m_dfsm_states[state_idx].follows_interesting_order.test(
393 std::bitset<kMaxSupportedOrderings> ignored_orderings)
const {
395 std::bitset<kMaxSupportedOrderings> a =
396 m_dfsm_states[a_idx].follows_interesting_order & ~ignored_orderings;
397 std::bitset<kMaxSupportedOrderings> b =
398 m_dfsm_states[b_idx].follows_interesting_order & ~ignored_orderings;
399 std::bitset<kMaxSupportedOrderings> future_a =
400 m_dfsm_states[a_idx].can_reach_interesting_order & ~ignored_orderings;
401 std::bitset<kMaxSupportedOrderings> future_b =
402 m_dfsm_states[b_idx].can_reach_interesting_order & ~ignored_orderings;
403 return (a & b) != a || (future_a & future_b) != future_a;
614 bool used_at_end,
table_map homogenize_tables);
652 THD *thd,
Ordering reduced_ordering,
bool used_at_end,
int table_idx,
672 int *generation,
int extra_allowed_fd_idx);
695 int *start_point)
const;
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:850
Definition: interesting_orders.h:214
void SetHeadForAggregates(Bounds_checked_array< ItemHandle > head)
Definition: interesting_orders.h:284
void CreateOrderingsFromGroupings(THD *thd)
We don't currently have any operators that only group and do not sort (e.g.
Definition: interesting_orders.cc:886
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:1051
bool ItemHandleBeforeInGroup(ItemHandle a, ItemHandle b)
Definition: interesting_orders.h:602
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:560
Mem_root_array< OrderingWithInfo > m_orderings
Definition: interesting_orders.h:572
Bounds_checked_array< int > m_optimized_fd_mapping
Definition: interesting_orders.h:592
StateIndex SetOrder(int ordering_idx) const
Definition: interesting_orders.h:327
int num_orderings() const
Definition: interesting_orders.h:256
bool DoesFollowOrder(StateIndex state_idx, int ordering_idx) const
Definition: interesting_orders.h:354
bool m_rollup
Definition: interesting_orders.h:455
int m_longest_ordering
Definition: interesting_orders.h:575
int AddArtificialState(THD *thd, Ordering ordering)
Definition: interesting_orders.cc:1224
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:1169
Mem_root_array< DFSMState > m_dfsm_states
Definition: interesting_orders.h:584
bool m_built
Definition: interesting_orders.h:411
int RemapOrderingIndex(int ordering_idx) const
Definition: interesting_orders.h:320
void FinalizeDFSMState(THD *thd, int state_idx)
Definition: interesting_orders.cc:1669
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:779
void PrintDFSMDottyGraph(std::string *trace) const
Definition: interesting_orders.cc:2027
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:846
void SetRollup(bool rollup)
Definition: interesting_orders.h:291
void PrintFunctionalDependencies(std::string *trace)
Definition: interesting_orders.cc:1939
void CreateHomogenizedOrderings(THD *thd)
For each interesting ordering, see if we can homogenize it onto each table.
Definition: interesting_orders.cc:974
Mem_root_array< NFSMState > m_states
Definition: interesting_orders.h:580
int AddOrderingInternal(THD *thd, Ordering order, OrderingWithInfo::Type type, bool used_at_end, table_map homogenize_tables)
Definition: interesting_orders.cc:154
void AddFDsFromConstItems(THD *thd)
Try to add FDs from items that are constant by themselves, e.g.
Definition: interesting_orders.cc:674
int AddFunctionalDependency(THD *thd, FunctionalDependency fd)
Definition: interesting_orders.cc:207
void PrintNFSMDottyGraph(std::string *trace) const
Definition: interesting_orders.cc:1992
Mem_root_array< DFSMEdge > m_dfsm_edges
Definition: interesting_orders.h:585
bool MoreOrderedThan(StateIndex a_idx, StateIndex b_idx, std::bitset< kMaxSupportedOrderings > ignored_orderings) const
Definition: interesting_orders.h:391
bool AlwaysActiveFD(int fd_idx)
Definition: interesting_orders.cc:1664
void BuildNFSM(THD *thd)
Definition: interesting_orders.cc:1291
Mem_root_array< NFSMEdge > m_edges
Definition: interesting_orders.h:581
void BuildEquivalenceClasses()
Definition: interesting_orders.cc:454
int StateIndex
Definition: interesting_orders.h:325
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:1066
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:1255
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:1532
Item * item(ItemHandle item) const
Definition: interesting_orders.h:222
void FindElementsThatCanBeAddedByFDs()
Definition: interesting_orders.cc:735
void PrintInterestingOrders(std::string *trace)
Definition: interesting_orders.cc:1956
StateIndex ApplyFDs(StateIndex state_idx, FunctionalDependencySet fds) const
Definition: interesting_orders.cc:299
Bounds_checked_array< int > m_optimized_ordering_mapping
Definition: interesting_orders.h:589
void AddGroupingFromOrdering(THD *thd, int state_idx, Ordering ordering, OrderElement *tmpbuf)
Definition: interesting_orders.cc:1426
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:1686
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:1445
void PruneFDs(THD *thd)
Definition: interesting_orders.cc:385
void PruneUninterestingOrders(THD *thd)
Try to get rid of uninteresting orders, possibly by discarding irrelevant suffixes and merging them w...
Definition: interesting_orders.cc:331
void AddFDsFromAggregateItems(THD *thd)
Definition: interesting_orders.cc:697
std::string PrintOrdering(Ordering ordering) const
Definition: interesting_orders.cc:1892
bool ItemBeforeInGroup(const OrderElement &a, const OrderElement &b)
Definition: interesting_orders.h:608
Bounds_checked_array< ItemHandle > CollectHeadForStaticWindowFunction(THD *thd, ItemHandle argument_item, Window *window)
Definition: interesting_orders.cc:519
Mem_root_array< ItemInfo > m_items
Definition: interesting_orders.h:446
ItemHandle GetHandle(Item *item)
Definition: interesting_orders.cc:1131
void FindInitialStatesForOrdering()
Definition: interesting_orders.cc:1880
LogicalOrderings(THD *thd)
Definition: interesting_orders.cc:132
Mem_root_array< FunctionalDependency > m_fds
Definition: interesting_orders.h:577
void ConvertNFSMToDFSM(THD *thd)
From the NFSM, convert an equivalent DFSM.
Definition: interesting_orders.cc:1731
Bounds_checked_array< ItemHandle > m_aggregate_head
Definition: interesting_orders.h:450
FunctionalDependencySet GetFDSet(int fd_idx) const
Definition: interesting_orders.h:336
void RecanonicalizeGroupings()
Definition: interesting_orders.cc:504
std::string PrintFunctionalDependency(const FunctionalDependency &fd, bool html) const
Definition: interesting_orders.cc:1906
void AddEdge(THD *thd, int state_idx, int required_fd_idx, Ordering ordering)
Definition: interesting_orders.cc:1240
int num_fds() const
Definition: interesting_orders.h:273
void Build(THD *thd, std::string *trace)
Definition: interesting_orders.cc:237
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:33
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:104
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
bool always_active
Definition: interesting_orders.h:211
Bounds_checked_array< ItemHandle > head
Definition: interesting_orders.h:188
enum FunctionalDependency::@100 type
@ FD
Definition: interesting_orders.h:179
@ DECAY
Definition: interesting_orders.h:172
@ EQUIVALENCE
Definition: interesting_orders.h:185
Definition: interesting_orders.h:516
int state_idx
Definition: interesting_orders.h:518
int required_fd_idx
Definition: interesting_orders.h:517
const DFSMState * state(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:524
const FunctionalDependency * required_fd(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:520
Definition: interesting_orders.h:473
FunctionalDependencySet can_use_fd
Definition: interesting_orders.h:495
Mem_root_array< int > nfsm_states
Definition: interesting_orders.h:475
std::bitset< kMaxSupportedOrderings > follows_interesting_order
Definition: interesting_orders.h:483
Mem_root_array< int > outgoing_edges
Definition: interesting_orders.h:474
std::bitset< kMaxSupportedOrderings > can_reach_interesting_order
Definition: interesting_orders.h:490
Bounds_checked_array< int > next_state
Definition: interesting_orders.h:480
Definition: interesting_orders.h:413
bool used_desc
Definition: interesting_orders.h:441
bool used_in_grouping
Definition: interesting_orders.h:442
ItemHandle canonical_item
Definition: interesting_orders.h:427
bool can_be_added_by_fd
Definition: interesting_orders.h:433
bool used_asc
Definition: interesting_orders.h:440
Item * item
Definition: interesting_orders.h:415
Definition: interesting_orders.h:498
const NFSMState * state(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:512
int required_fd_idx
Definition: interesting_orders.h:503
const FunctionalDependency * required_fd(const LogicalOrderings *orderings) const
Definition: interesting_orders.h:508
int state_idx
Definition: interesting_orders.h:506
Definition: interesting_orders.h:457
Mem_root_array< int > outgoing_edges
Definition: interesting_orders.h:459
std::bitset< kMaxSupportedOrderings > can_reach_interesting_order
Definition: interesting_orders.h:464
int satisfied_ordering_idx
Definition: interesting_orders.h:461
@ ARTIFICIAL
Definition: interesting_orders.h:458
@ DELETED
Definition: interesting_orders.h:458
@ INTERESTING
Definition: interesting_orders.h:458
int seen
Definition: interesting_orders.h:471
enum LogicalOrderings::NFSMState::@101 type
Ordering satisfied_ordering
Definition: interesting_orders.h:460
Definition: interesting_orders.h:529
StateIndex state_idx
Definition: interesting_orders.h:569
Ordering ordering
Definition: interesting_orders.h:530
bool used_at_end
Definition: interesting_orders.h:563
Type
Definition: interesting_orders.h:535
@ UNINTERESTING
Definition: interesting_orders.h:560
@ INTERESTING
Definition: interesting_orders.h:538
@ HOMOGENIZED
Definition: interesting_orders.h:553
enum LogicalOrderings::OrderingWithInfo::Type type
table_map homogenize_tables
Definition: interesting_orders.h:566
Definition: interesting_orders_defs.h:43
ItemHandle item
Definition: interesting_orders_defs.h:44