geoindex: false negatives producing incorrect results for geography intersection

cockroach-teamcity commented 2 years ago

roachtest.tlp failed with artifacts on release-22.1.0 @ b80486467afdcf9b7c3d1a2739e890722eae6cd8:

The test failed on branch=release-22.1.0, cloud=gce:
test artifacts and logs in: /artifacts/tlp/run_1
    tlp.go:172,tlp.go:76,test_runner.go:875: expected unpartitioned and partitioned results to be equal
        (1) attached stack trace
          -- stack trace:
          | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runTLPQuery.func2
          |     github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:245
          | github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests.runWithTimeout.func1
          |     github.com/cockroachdb/cockroach/pkg/cmd/roachtest/tests/tlp.go:270
          | runtime.goexit
          |     GOROOT/src/runtime/asm_amd64.s:1581
        Wraps: (2) expected unpartitioned and partitioned results to be equal
          |   []string{
          |     "0000-01-01 00:00:00 +1559 +1559,NULL,NULL,4098006260,\x1d\x1dQ!5\x05,\x02,-0"...,
          |     "0000-01-01 00:00:00 +1559 +1559,NULL,NULL,4098006260,\x1d\x1dQ!5\x05,\x02,0."...,
          | -   "0000-01-01 00:00:00 +1559 +1559,NULL,NULL,4098006260,\x1d\x1dQ!5\x05,\x02,0.47358095266246736,NULL,NULL,0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC234D9FA4FC032A6F3C0BE1051C001010000004F"...,
          |     "0000-01-01 00:00:00 +1559 +1559,NULL,NULL,4098006260,\x1d\x1dQ!5\x05,\x02,3."...,
          |     "0000-01-01 00:00:00 +1559 +1559,NULL,NULL,4098006260,\x1d\x1dQ!5\x05,\x02,NU"...,
          |     ... // 23 identical elements
          |     "0000-01-01 00:28:44.539502 -0150 -0150,NULL,3213525050,275649357"...,
          |     "0000-01-01 00:28:44.539502 -0150 -0150,NULL,3213525050,275649357"...,
          | -   "0000-01-01 00:28:44.539502 -0150 -0150,NULL,3213525050,2756493570,5,\x02,0.47358095266246736,NULL,NULL,0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC234D9FA4FC032A6F3C0BE1051C00101"...,
          |     "0000-01-01 00:28:44.539502 -0150 -0150,NULL,3213525050,275649357"...,
          |     "0000-01-01 00:28:44.539502 -0150 -0150,NULL,3213525050,275649357"...,
          |     ... // 23 identical elements
          |     "0000-01-01 06:23:54.380386 -0547 -0547,{feb9c8b1-6219-439d-a075-"...,
          |     "0000-01-01 06:23:54.380386 -0547 -0547,{feb9c8b1-6219-439d-a075-"...,
          | -   "0000-01-01 06:23:54.380386 -0547 -0547,{feb9c8b1-6219-439d-a075-18e104df5bdf},721930405,721930405,5,,0.47358095266246736,NULL,NULL,0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC"...,
          |     "0000-01-01 06:23:54.380386 -0547 -0547,{feb9c8b1-6219-439d-a075-"...,
          |     "0000-01-01 06:23:54.380386 -0547 -0547,{feb9c8b1-6219-439d-a075-"...,
          |     ... // 23 identical elements
          |     "0000-01-01 08:32:01.481563 +1100 +1100,{786b971b-952a-4c1b-b4b2-"...,
          |     "0000-01-01 08:32:01.481563 +1100 +1100,{786b971b-952a-4c1b-b4b2-"...,
          | -   "0000-01-01 08:32:01.481563 +1100 +1100,{786b971b-952a-4c1b-b4b2-2dd1a55f5064,16ef4af9-79ba-4713-a2d2-0a193be72c49,8512d8b6-4e42-4731-8af8-6667815a5c88,7907b1de-2ee4-44dc-a346-4ef025b6b42e},3410462862,1875874811,5,,0.47358095266246736,NULL,NULL,0104000020E6"...,
          |     "0000-01-01 08:32:01.481563 +1100 +1100,{786b971b-952a-4c1b-b4b2-"...,
          |     "0000-01-01 08:32:01.481563 +1100 +1100,{786b971b-952a-4c1b-b4b2-"...,
          |     ... // 23 identical elements
          |     "NULL,{122ae9b7-f1e0-4908-812b-6999c6f445c8,4949916f-861b-41fc-86"...,
          |     "NULL,{122ae9b7-f1e0-4908-812b-6999c6f445c8,4949916f-861b-41fc-86"...,
          | -   "NULL,{122ae9b7-f1e0-4908-812b-6999c6f445c8,4949916f-861b-41fc-866d-4f1e32da9358},NULL,3685560203,\x1d\x1dQ!5\x05,,0.47358095266246736,NULL,NULL,0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001"...,
          |     "NULL,{122ae9b7-f1e0-4908-812b-6999c6f445c8,4949916f-861b-41fc-86"...,
          |     "NULL,{122ae9b7-f1e0-4908-812b-6999c6f445c8,4949916f-861b-41fc-86"...,
          |     ... // 23 identical elements
          |   }
          | sql: SELECT * FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON true
          | (SELECT * FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL) UNION ALL (SELECT * FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON NOT (st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL)) UNION ALL (SELECT * FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON (st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL) IS NULL)
          | with args: []
        Error types: (1) *withstack.withStack (2) *errutil.leafError

Help

See: [roachtest README](https://github.com/cockroachdb/cockroach/blob/master/pkg/cmd/roachtest/README.md) See: [How To Investigate \(internal\)](https://cockroachlabs.atlassian.net/l/c/SSSBr8c7)

Same failure on other branches

- #80047 roachtest: tlp failed [C-test-failure O-roachtest O-robot T-sql-queries branch-release-22.1]

/cc @cockroachdb/sql-queries

This test on roachdash | Improve this report!

Jira issue: CRDB-15742

cucaroach commented 2 years ago

This fails in 21.2.5 the same way as 22.1, removing release blocker labels.

cucaroach commented 2 years ago

Here's a reduced repro, guessing its a geo thing:

CREATE TABLE table2 (col2_0 TIMETZ, col2_3 REGPROC);

CREATE TABLE table5 (
  col5_0 FLOAT8, col5_3 GEOGRAPHY, col5_4 DATE, col5_6 DECIMAL, col5_7 STRING,
  INDEX (col5_7 DESC),
  INVERTED INDEX (col5_3 ASC)
);

INSERT INTO table2 (col2_0, col2_3) VALUES ('00:00:00+15:59:00', 0);

INSERT
  INTO table5 (col5_0, col5_3, col5_4, col5_6)
VALUES (
        0,
        '0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC234D9FA4FC032A6F3C0BE1051C001010000004FCAE361214452C0B8C3171AA0E552400101000000035E7A43C0E352C030FDD4FB3E2B4840010100000021432579E97C65C0CC0DDAAFD6B23940010100000018DD72AEB8FE5E4037CB45DA4A7C47C001010000000CBA9522724E65406CF65B95512053C0',
        '1995-04-22',
        0
       );

SELECT count(*) FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON true;

(SELECT count(*) FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON
st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL)
UNION ALL
(SELECT count(*) FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON NOT (st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL))
UNION ALL
(SELECT count(*) FROM defaultdb.public.table2 AS tab_54801 JOIN defaultdb.public.table5 AS tab_54802 ON (st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, tab_54802.col5_3::GEOGRAPHY, 0.24216150138503956::FLOAT8, (NOT false)::BOOL)::BOOL) IS NULL);

This outputs:

Time: 131ms

  count
---------
      1
(1 row)

Time: 2ms

  count
---------
      0
      0
      0
(3 rows)

with * instead of count:


      col2_0     | col2_3 | col5_0 |                                                                                                                                                                                   col5_3                                                                                                                                                                                   |   col5_4   | col5_6 | col5_7
-----------------+--------+--------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+------------+--------+---------
  00:00:00+15:59 |      0 |      0 | 0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC234D9FA4FC032A6F3C0BE1051C001010000004FCAE361214452C0B8C3171AA0E552400101000000035E7A43C0E352C030FDD4FB3E2B4840010100000021432579E97C65C0CC0DDAAFD6B23940010100000018DD72AEB8FE5E4037CB45DA4A7C47C001010000000CBA9522724E65406CF65B95512053C0 | 1995-04-22 |      0 | NULL
(1 row)

Time: 5ms

  col2_0 | col2_3 | col5_0 | col5_3 | col5_4 | col5_6 | col5_7
---------+--------+--------+--------+--------+--------+---------
(0 rows)

Time: 5ms

rytaft commented 2 years ago

Here's an even more reduced reproduction:

CREATE TABLE tab (
  geo_col GEOGRAPHY,
  INVERTED INDEX (geo_col ASC)
);

INSERT
  INTO tab (geo_col)
VALUES ('0104000020E610000008000000010100000054A4D87CD5AD4B40E8B73A825C8637C0010100000081A76E24086666C0AC4CF2E3AF584C4001010000001A7FC234D9FA4FC032A6F3C0BE1051C001010000004FCAE361214452C0B8C3171AA0E552400101000000035E7A43C0E352C030FDD4FB3E2B4840010100000021432579E97C65C0CC0DDAAFD6B23940010100000018DD72AEB8FE5E4037CB45DA4A7C47C001010000000CBA9522724E65406CF65B95512053C0');

SELECT count(*) FROM tab@tab_geo_col_idx WHERE st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, geo_col, 0.24216150138503956, true);

SELECT count(*) FROM tab@tab_pkey WHERE st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, geo_col, 0.24216150138503956, true);

Notice the difference in the plans between these two queries:

demo@127.0.0.1:26257/defaultdb> explain SELECT count(*) FROM tab@tab_geo_col_idx WHERE st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, geo_col, 0.24216150138503956, true);
                                                                                                                                                                                          info
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • group (scalar)
  │ estimated row count: 1
  │
  └── • filter
      │ estimated row count: 0
      │ filter: st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241', geo_col, 0.24216150138503956, true)
      │
      └── • index join
          │ estimated row count: 0
          │ table: tab@tab_pkey
          │
          └── • inverted filter
              │ inverted column: geo_col_inverted_key
              │ num spans: 54
              │
              └── • scan
                    estimated row count: 0 (<0.01% of the table; stats collected 13 seconds ago)
                    table: tab@tab_geo_col_idx
                    spans: 54 spans
(22 rows)

Time: 2ms total (execution 1ms / network 0ms)

demo@127.0.0.1:26257/defaultdb> explain SELECT count(*) FROM tab@tab_pkey WHERE st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, geo_col, 0.24216150138503956, true);
                                                                                                                                                                                          info
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • group (scalar)
  │ estimated row count: 1
  │
  └── • filter
      │ estimated row count: 0
      │ filter: st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241', geo_col, 0.24216150138503956, true)
      │
      └── • scan
            estimated row count: 1 (100% of the table; stats collected 18 seconds ago)
            table: tab@tab_pkey
            spans: FULL SCAN
(14 rows)

Time: 1ms total (execution 1ms / network 0ms)

Looks like the plan with the inverted index is producing incorrect results.

rytaft commented 2 years ago

According to explain analyze, we're not reading any rows in the scan:

    info
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  planning time: 681µs
  execution time: 7ms
  distribution: local
  vectorized: true
  cumulative time spent in KV: 6ms
  maximum memory usage: 60 KiB
  network usage: 0 B (0 messages)

  • group (scalar)
  │ nodes: n1
  │ actual row count: 1
  │
  └── • filter
      │ nodes: n1
      │ actual row count: 0
      │ filter: st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241', geo_col, 0.24216150138503956, true)
      │
      └── • index join
          │ nodes: n1
          │ actual row count: 0
          │ KV time: 2µs
          │ KV contention time: 0µs
          │ KV rows read: 0
          │ KV bytes read: 0 B
          │ estimated max memory allocated: 0 B
          │ estimated max sql temp disk usage: 0 B
          │ table: tab@tab_pkey
          │
          └── • inverted filter
              │ nodes: n1
              │ actual row count: 0
              │ estimated max memory allocated: 0 B
              │ estimated max sql temp disk usage: 0 B
              │ inverted column: geo_col_inverted_key
              │ num spans: 54
              │
              └── • scan
                    nodes: n1
                    actual row count: 0
                    KV time: 6ms
                    KV contention time: 0µs
                    KV rows read: 0
                    KV bytes read: 0 B
                    estimated max memory allocated: 30 KiB
                    missing stats
                    table: tab@tab_geo_col_idx
                    spans: 54 spans
(47 rows)

rytaft commented 2 years ago

These are the keys in the index:

  B\xfd!\x9e-\x02\x0f\xa8+\xbd\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfdL\xdcI#\xe9u\xd4\xa1\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfdN9\xce\xd0\xebGta\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfdW~c\x82\x8fJ\xdc\x8b\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfd|\x8f\xec\x8c\xb1wou\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfd\xabm\xb8\xa0\xf0\x8a\x12;\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfd\xafz\xba\xe1\xaf\xe9\xc5;\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1
  B\xfd\xbbx,\xe1\x95\x1f\xaf\x05\x00?\xee\xea\xf3\xd5w8\xb2\xbf\xf5]=\x8f2P\x9b\xbf\xf1\xdcf\x14\xa2\x9d\xdc?\xf5\x1b\xad\xefw\xe4\xe1

These are the spans scanned:

/"B\xfd\f\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\f\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\r\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\r\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\r\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\r\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x10\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x10\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\x11\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x11\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\x11\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\x11\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x12\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd\x13\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x13\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x13\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\x13\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\x13\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x13\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd\x14\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x14\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x14\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\x14\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\x16\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x16\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\x18\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x18\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd\x18\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd\x19\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x19\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\x1c\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\x1c\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\"\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd#\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd#\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd#\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd#\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd#\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd$\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd$\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd$\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd%\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd%\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd%\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd%\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd%\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd,\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd,\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd/\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd/\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd/\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd0\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd0\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd0\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd0\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd0\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd0\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd1\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd1\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd1\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd4\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd4\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd7\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd7\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd7\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd7\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd7\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd8\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd8\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd@\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd@\x00\x00\x00\x00\x00\x00\x01"-/"B\xfdH\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfdH\x00\x00\x00\x00\x00\x00\x01"-/"B\xfdH\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfdH\x80\x00\x00\x00\x00\x00\x01"-/"B\xfdI\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfdI\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdI\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdL\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdL\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdO\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdO\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdO\x00\x00\x00\x00\x00\x00\x01"-/"B\xfdO\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfdO\x80\x00\x00\x00\x00\x00\x01"-/"B\xfdP\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfdP\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdP\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdP\x00\x00\x00\x00\x00\x00\x01"-/"B\xfdP\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfdQ\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdQ\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdT\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdT\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfdZ\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd[\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd[\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd[\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd[\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd[\x80\x00\x00\x00\x00\x00\x00" 
/"B\xfd\\\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd\\\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd\\\x80\x00\x00\x00\x00\x00\x01"-/"B\xfd]\x00\x00\x00\x00\x00\x00\x00" 
/"B\xfd]\x00\x00\x00\x00\x00\x00\x00"-/"B\xfd]\x00\x00\x00\x00\x00\x00\x01" 
/"B\xfd]\x00\x00\x00\x00\x00\x00\x01"-/"B\xfd]\x80\x00\x00\x00\x00\x00\x00"

rytaft commented 2 years ago

In the optimizer, these spans are represented differently:

      info
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  scalar-group-by
   ├── select
   │    ├── index-join tab
   │    │    └── inverted-filter
   │    │         ├── inverted expression: /5
   │    │         │    ├── tight: false, unique: false
   │    │         │    └── union spans
   │    │         │         ├── ["B\xfd\f\x00\x00\x00\x00\x00\x00\x00", "B\xfd\f\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\r\x00\x00\x00\x00\x00\x00\x00", "B\xfd\r\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\r\x00\x00\x00\x00\x00\x00\x01", "B\xfd\r\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x10\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x10\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\x11\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x11\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\x11\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x11\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x12\x80\x00\x00\x00\x00\x00\x01", "B\xfd\x13\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x13\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x13\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\x13\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x13\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x13\x80\x00\x00\x00\x00\x00\x01", "B\xfd\x14\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x14\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x14\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\x14\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x16\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x16\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x18\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x18\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x18\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\x19\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x19\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\x1c\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x1c\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\"\x80\x00\x00\x00\x00\x00\x01", "B\xfd#\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd#\x00\x00\x00\x00\x00\x00\x00", "B\xfd#\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd#\x00\x00\x00\x00\x00\x00\x01", "B\xfd#\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd$\x00\x00\x00\x00\x00\x00\x00", "B\xfd$\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd$\x80\x00\x00\x00\x00\x00\x01", "B\xfd%\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd%\x00\x00\x00\x00\x00\x00\x00", "B\xfd%\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd%\x00\x00\x00\x00\x00\x00\x01", "B\xfd%\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd,\x00\x00\x00\x00\x00\x00\x00", "B\xfd,\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd/\x00\x00\x00\x00\x00\x00\x00", "B\xfd/\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd/\x80\x00\x00\x00\x00\x00\x01", "B\xfd0\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd0\x00\x00\x00\x00\x00\x00\x00", "B\xfd0\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd0\x00\x00\x00\x00\x00\x00\x01", "B\xfd0\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd0\x80\x00\x00\x00\x00\x00\x01", "B\xfd1\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd1\x00\x00\x00\x00\x00\x00\x00", "B\xfd1\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd4\x00\x00\x00\x00\x00\x00\x00", "B\xfd4\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd7\x00\x00\x00\x00\x00\x00\x00", "B\xfd7\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd7\x00\x00\x00\x00\x00\x00\x01", "B\xfd7\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd7\x80\x00\x00\x00\x00\x00\x01", "B\xfd8\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd8\x00\x00\x00\x00\x00\x00\x01", "B\xfd@\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd@\x00\x00\x00\x00\x00\x00\x01", "B\xfdH\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdH\x00\x00\x00\x00\x00\x00\x01", "B\xfdH\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdH\x80\x00\x00\x00\x00\x00\x01", "B\xfdI\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdI\x00\x00\x00\x00\x00\x00\x00", "B\xfdI\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdL\x00\x00\x00\x00\x00\x00\x00", "B\xfdL\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdO\x00\x00\x00\x00\x00\x00\x00", "B\xfdO\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdO\x00\x00\x00\x00\x00\x00\x01", "B\xfdO\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdO\x80\x00\x00\x00\x00\x00\x01", "B\xfdP\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdP\x00\x00\x00\x00\x00\x00\x00", "B\xfdP\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdP\x00\x00\x00\x00\x00\x00\x01", "B\xfdP\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfdQ\x00\x00\x00\x00\x00\x00\x00", "B\xfdQ\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdT\x00\x00\x00\x00\x00\x00\x00", "B\xfdT\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfdZ\x80\x00\x00\x00\x00\x00\x01", "B\xfd[\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd[\x00\x00\x00\x00\x00\x00\x00", "B\xfd[\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd[\x00\x00\x00\x00\x00\x00\x01", "B\xfd[\x80\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd\\\x00\x00\x00\x00\x00\x00\x00", "B\xfd\\\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         ├── ["B\xfd\\\x80\x00\x00\x00\x00\x00\x01", "B\xfd]\x00\x00\x00\x00\x00\x00\x00")
   │    │         │         ├── ["B\xfd]\x00\x00\x00\x00\x00\x00\x00", "B\xfd]\x00\x00\x00\x00\x00\x00\x00"]
   │    │         │         └── ["B\xfd]\x00\x00\x00\x00\x00\x00\x01", "B\xfd]\x80\x00\x00\x00\x00\x00\x00")
   │    │         ├── pre-filterer expression
   │    │         │    └── st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241', geo_col, 0.24216150138503956)
   │    │         └── scan tab@tab_geo_col_idx
   │    │              ├── inverted constraint: /5/2
   │    │              │    └── spans
   │    │              │         ├── ["B\xfd\f\x00\x00\x00\x00\x00\x00\x00", "B\xfd\f\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\r\x00\x00\x00\x00\x00\x00\x00", "B\xfd\r\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\r\x00\x00\x00\x00\x00\x00\x01", "B\xfd\r\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x10\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x10\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\x11\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x11\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\x11\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x11\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x12\x80\x00\x00\x00\x00\x00\x01", "B\xfd\x13\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x13\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x13\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\x13\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x13\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x13\x80\x00\x00\x00\x00\x00\x01", "B\xfd\x14\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x14\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x14\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\x14\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x16\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x16\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x18\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x18\x00\x00\x00\x00\x00\x00\x01", "B\xfd\x18\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\x19\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x19\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\x1c\x00\x00\x00\x00\x00\x00\x00", "B\xfd\x1c\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\"\x80\x00\x00\x00\x00\x00\x01", "B\xfd#\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd#\x00\x00\x00\x00\x00\x00\x00", "B\xfd#\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd#\x00\x00\x00\x00\x00\x00\x01", "B\xfd#\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd$\x00\x00\x00\x00\x00\x00\x00", "B\xfd$\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd$\x80\x00\x00\x00\x00\x00\x01", "B\xfd%\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd%\x00\x00\x00\x00\x00\x00\x00", "B\xfd%\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd%\x00\x00\x00\x00\x00\x00\x01", "B\xfd%\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd,\x00\x00\x00\x00\x00\x00\x00", "B\xfd,\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd/\x00\x00\x00\x00\x00\x00\x00", "B\xfd/\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd/\x80\x00\x00\x00\x00\x00\x01", "B\xfd0\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd0\x00\x00\x00\x00\x00\x00\x00", "B\xfd0\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd0\x00\x00\x00\x00\x00\x00\x01", "B\xfd0\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd0\x80\x00\x00\x00\x00\x00\x01", "B\xfd1\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd1\x00\x00\x00\x00\x00\x00\x00", "B\xfd1\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd4\x00\x00\x00\x00\x00\x00\x00", "B\xfd4\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd7\x00\x00\x00\x00\x00\x00\x00", "B\xfd7\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd7\x00\x00\x00\x00\x00\x00\x01", "B\xfd7\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd7\x80\x00\x00\x00\x00\x00\x01", "B\xfd8\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd8\x00\x00\x00\x00\x00\x00\x01", "B\xfd@\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd@\x00\x00\x00\x00\x00\x00\x01", "B\xfdH\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdH\x00\x00\x00\x00\x00\x00\x01", "B\xfdH\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdH\x80\x00\x00\x00\x00\x00\x01", "B\xfdI\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdI\x00\x00\x00\x00\x00\x00\x00", "B\xfdI\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdL\x00\x00\x00\x00\x00\x00\x00", "B\xfdL\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdO\x00\x00\x00\x00\x00\x00\x00", "B\xfdO\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdO\x00\x00\x00\x00\x00\x00\x01", "B\xfdO\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdO\x80\x00\x00\x00\x00\x00\x01", "B\xfdP\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdP\x00\x00\x00\x00\x00\x00\x00", "B\xfdP\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdP\x00\x00\x00\x00\x00\x00\x01", "B\xfdP\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfdQ\x00\x00\x00\x00\x00\x00\x00", "B\xfdQ\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdT\x00\x00\x00\x00\x00\x00\x00", "B\xfdT\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfdZ\x80\x00\x00\x00\x00\x00\x01", "B\xfd[\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd[\x00\x00\x00\x00\x00\x00\x00", "B\xfd[\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd[\x00\x00\x00\x00\x00\x00\x01", "B\xfd[\x80\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd\\\x00\x00\x00\x00\x00\x00\x00", "B\xfd\\\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         ├── ["B\xfd\\\x80\x00\x00\x00\x00\x00\x01", "B\xfd]\x00\x00\x00\x00\x00\x00\x00")
   │    │              │         ├── ["B\xfd]\x00\x00\x00\x00\x00\x00\x00", "B\xfd]\x00\x00\x00\x00\x00\x00\x00"]
   │    │              │         └── ["B\xfd]\x00\x00\x00\x00\x00\x00\x01", "B\xfd]\x80\x00\x00\x00\x00\x00\x00")
   │    │              └── flags: force-index=tab_geo_col_idx
   │    └── filters
   │         └── st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241', geo_col, 0.24216150138503956)
   └── aggregations
        └── count-rows
(125 rows)

I wonder if this has something to do with the conversion of the equality spans to open-ended spans. e.g.,

["B\xfdL\x00\x00\x00\x00\x00\x00\x00", "B\xfdL\x00\x00\x00\x00\x00\x00\x00"]

becomes

/"B\xfdL\x00\x00\x00\x00\x00\x00\x00"-/"B\xfdL\x00\x00\x00\x00\x00\x00\x01"

rytaft commented 2 years ago

I'm going to take a break from this for now. I think debugging this further is going to require a deeper dive into how the spans are generated. The relevant code is here: https://github.com/cockroachdb/cockroach/blob/928f605c3e84efb30cab213b47b2f4a66b816701/pkg/sql/opt/invertedidx/geo.go#L123-L127

cc @sumeerbhola in case you have time to take a peek at this and/or have any insight into what might be happening

sumeerbhola commented 2 years ago

These shapes are intersecting based on

root@:26257/defaultdb> SELECT count(*) FROM tab@tab_geo_col_idx WHERE st_intersects('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD9
  count
---------
      0
(1 row)

root@:26257/defaultdb> SELECT count(*) FROM tab@tab_pkey WHERE st_intersects('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911D
  count
---------
      1

But I have to bump up the ST_DWithin distance to 717,000 meters before the index returns true

root@:26257/defaultdb> SELECT count(*) FROM tab@tab_geo_col_idx WHERE st_dwithin('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::GEOGRAPHY, geo_col, 717000, true);
  count
---------
      1
(1 row)

The following steps may help to narrow this down:

Use @otan's visualizer on these 2 shapes, and on the output of st_s2covering, just to see if anything obvious pops out.
The query is unioning a set of key spans corresponding to cellids. We can print them out, since they are simple integer ranges and easier to understand:
- Whether we are using ST_DWithin or ST_Intersects, the code will call into intersectsUsingCovering which will produce UnionKeySpans here https://github.com/cockroachdb/cockroach/blob/master/pkg/geo/geoindex/geoindex.go#L530-L540.
- We need the cellids under which the original shape was indexed. We can instrument CoveringGeography https://github.com/cockroachdb/cockroach/blob/master/pkg/geo/geoindex/s2_geography_index.go#L219-L222 called by st_s2covering to get that.

sumeerbhola commented 2 years ago

I tried the second step (I won't get a chance to look at this more for the next couple of days). The cells are non-intersecting. The viz will probably tell us something.

There are 8 cells in the covering (the latter 3 are longer in terms of an extra digit):

2422423136447769533
5538382060348363937
5636763805326734433
6304585940766219403
8975652671389658997
12352732354316997179
12644624382277829947
13508596429678948101

ST_Intersects produces the following cellid ranges (the numbers have the same number of digits as the first 5 above, but no overlap):

[
1441151880758558721,
1585267068834414591
]
[
1585267068834414593,
1621295865853378559
]
[
4035225266123964417,
4611686018427387903
]
[
4611686018427387905,
5188146770730811391
]

There are also 5 ancestors which also don't match.

(I should have used fixed-width hex in these logs, since this requires some unnecessary squinting)

otan commented 2 years ago

Use @otan's visualizer on these 2 shapes, and on the output of st_s2covering, just to see if anything obvious pops out.

sorry i forgot to reply to this -- use https://geojson.io/ instead of my tool (convert using st_asgeojson(...)).

otan commented 2 years ago

using

SELECT json_build_object(
    'type', 'FeatureCollection',
    'features', json_agg(ST_AsGeoJSON(t.*)::json)
    )
FROM ( VALUES (1, 'original shape', '01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::geography),
              (2, 'two', st_s2covering('01060000E0E61000000100000001030000C001000000040000002410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241280A013B1F235340F8BF387C28115640D42C81DD911DF7C15068D6DBDEE7CCC10CA4E8AB08844D40125A0D02ADB35440F86FC12B1966DD4104A5183738C5FF412410B7E16B9D4440F80C9162CE5C2140459E64E4C1D0F2C1A82FC5D8CCBDF241'::geography))
     ) as t(id, name, geom);

into https://geojson.io/, and clicking on one shape and changing the colouring, you can see the S2 covering doesn't quite match the shape...

{
  "type": "FeatureCollection",
  "features": [
    {
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [
                41.229854788,
                8.681262093,
                -5050736198.28864
              ],
              [
                76.548781158,
                88.268096023,
                -6205021656.073444
              ],
              [
                59.031514634,
                82.807434571,
                1972921519.022459
              ],
              [
                41.229854788,
                8.681262093,
                -5050736198.28864
              ]
            ]
          ]
        ]
      },
      "properties": {
        "stroke": "#555555",
        "stroke-width": 2,
        "stroke-opacity": 1,
        "fill": "#f45252",
        "fill-opacity": 0.5,
        "id": 1,
        "name": "original shape"
      },
      "type": "Feature"
    },
    {
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [
                22.619864948,
                21.037511025
              ],
              [
                45,
                16.416440374
              ],
              [
                45,
                35.264389683
              ],
              [
                22.619864948,
                42.709389957
              ],
              [
                22.619864948,
                21.037511025
              ]
            ]
          ],
          [
            [
              [
                34.508522988,
                8.783194988
              ],
              [
                45,
                7.55237228
              ],
              [
                45,
                16.416440374
              ],
              [
                34.508522988,
                18.949950004
              ],
              [
                34.508522988,
                8.783194988
              ]
            ]
          ],
          [
            [
              [
                45,
                0
              ],
              [
                90,
                0
              ],
              [
                90,
                45
              ],
              [
                45,
                35.264389683
              ],
              [
                45,
                0
              ]
            ]
          ],
          [
            [
              [
                45,
                35.264389683
              ],
              [
                90,
                45
              ],
              [
                -180,
                90
              ],
              [
                0,
                45
              ],
              [
                45,
                35.264389683
              ]
            ]
          ]
        ]
      },
      "properties": {
        "id": 2,
        "name": "two"
      },
      "type": "Feature"
    }
  ]
}

i do wonder whether the original shape "is valid" -- it's valid for st_isvalid for geometry but not geography

rytaft commented 2 years ago

Thanks, @otan. I'm going to assign you, @sumeerbhola, since it looks like this is either a bug in s2 or our geoindex code, but either way, you probably have the most context.

mgartner commented 1 year ago

I've verified this is still an issue.

mgartner commented 1 year ago

@sumeerbhola any chance you'll have some cycles to look into this in the next couple weeks?

cockroachdb / cockroach

geoindex: false negatives producing incorrect results for geography intersection #80374