[#MCOL-4895] Reduce a number of ColumnCommanJL steps processing single-column WHERE filter predicate

select * from cs1 where (i = 3 or i = 42) and (i=43 or i =45);

MariaDB [test]> select calgettrace(1)\G

*************************** 1. row ***************************

calgettrace(1): TBPS: TupleBPS        ses:6 txn:0 ver:  SCN: 3400

  Txns:  st:0 tb/col:7575/7576 alias:cs1 not del (0x7f506d07cb00[19]) nf:2 in:

  UUID: 0d6794a7-3b58-40b8-a8de-c82c380ad393

  Query UUID: 0586abff-e57e-4abe-af25-96e39ad199bd

  BatchPrimitiveProcessorJL:

   -- scan driven

   2 filter steps:

      ColumnCommandJL: 2 filters  colwidth=8 oid=7576 name=i (scan)

      ColumnCommandJL: 2 filters  colwidth=8 oid=7576 name=i

   1 projection steps:

      PassThruCommandJL: colwidth=8 oid=7576 colName=i

ses:6 st: 0 finished at 2021-10-13 12:07:26.986298; PhyI/O-1; CacheI/O-2; MsgsSent-1; MsgsRvcd-1; BlocksTouched-2; BlockedFifoIn/Out-0/0; output size-0

	PartitionBlocksEliminated-0; MsgBytesIn-0KB; MsgBytesOut-1KB; TotalMsgs-1

	1st read 2021-10-13 12:07:26.956948; EOI 2021-10-13 12:07:26.986252; runtime-0.029304s

	UUID 0d6794a7-3b58-40b8-a8de-c82c380ad393

	Query UUID 0586abff-e57e-4abe-af25-96e39ad199bd

	Job completion status 0

TNS: ses:6 st: 1 finished at Wed Oct 13 12:07:26 2021; total rows returned-0

	1st read 2021-10-13 12:07:26.986679; EOI 2021-10-13 12:07:26.986699; runtime-0.000020s;

	UUID 83af49ab-3bd7-429b-93f3-7c4c3830d491

	Job completion status 0

1 row in set (0.000 sec)

The tree of this predicate contains AND on top and two leaves with ORs inside. It takes two scans AKA ColumnCommands to process this expression. If one changes the query so that it contains only one logical operator: OR, XOR, AND there will be a single ColumnCommand.

select * from cs1 where (i = 3 or i = 42) or (i=43 or i =45);

MariaDB [test]> select calgettrace(1)\G

*************************** 1. row ***************************

calgettrace(1): TBPS: TupleBPS        ses:6 txn:0 ver:  SCN: 3400

  Txns:  st:0 tb/col:7575/7576 alias:cs1 not del (0x7f506d07c780[19]) nf:4 in:

  UUID: 04615867-ae44-4a11-89a1-b9b1d96255a5

  Query UUID: d0d470fe-a768-4101-8377-f60338723b2b

  BatchPrimitiveProcessorJL:

   -- scan driven

   1 filter steps:

      ColumnCommandJL: 4 filters  colwidth=8 oid=7576 name=i (scan)

   1 projection steps:

      PassThruCommandJL: colwidth=8 oid=7576 colName=i

ses:6 st: 0 finished at 2021-10-13 12:08:20.745725; PhyI/O-0; CacheI/O-1; MsgsSent-1; MsgsRvcd-1; BlocksTouched-1; BlockedFifoIn/Out-0/0; output size-2

	PartitionBlocksEliminated-0; MsgBytesIn-0KB; MsgBytesOut-0KB; TotalMsgs-1

	1st read 2021-10-13 12:08:20.743571; EOI 2021-10-13 12:08:20.745675; runtime-0.002104s

	UUID 04615867-ae44-4a11-89a1-b9b1d96255a5

	Query UUID d0d470fe-a768-4101-8377-f60338723b2b

	Job completion status 0

TNS: ses:6 st: 1 finished at Wed Oct 13 12:08:20 2021; total rows returned-2

	1st read 2021-10-13 12:08:20.745960; EOI 2021-10-13 12:08:20.745999; runtime-0.000039s;

	UUID 2da6e58f-2ade-460d-b2b8-a47a65de6c58

	Job completion status 0

The suggested solution is to get an equivalent CNF of the single-column expression that contains only comparisons and logical operators using Tseytin transformation so that we produce the minimal possible CNF out of an arbitrary complex original expression with the limitations meantioned.
There must be a microbenchmark preceding the project to prove this feature worth to be implemented.

[MCOL-4895] Reduce a number of ColumnCommanJL steps processing single-column WHERE filter predicate Created: 2021-10-13 Updated: 2023-12-15
Status:	Open
Project:	MariaDB ColumnStore
Component/s:	ExeMgr, PrimProc
Affects Version/s:	6.1.1
Fix Version/s:	Icebox

[MCOL-4895] Reduce a number of ColumnCommanJL steps processing single-column WHERE filter predicate Created: 2021-10-13 Updated: 2023-12-15