为何筛选美国州的Wikidata SPARQL查询超时，相似查询却正常？

问题背景 #

我要查询每位美国总统出生地所属的州，编写了如下Wikidata SPARQL查询：

SELECT * WHERE {
  # P31 = 实例类型
  # Q5 = 人类（排除虚构角色）
  ?president wdt:P31 wd:Q5.

  # P39 = 担任职位
  # Q11696 = 美国总统
  ?president wdt:P39 wd:Q11696.

  # P19 = 出生地
  ?president wdt:P19 ?birthPlace.

  # P131 = 隶属于行政区域
  ?birthPlace wdt:P131* ?state.

  # P31 = 实例类型
  # Q35657 = 美国州级行政区
  #?state wdt:P31 wd:Q35657.
}

该查询返回所有总统的出生地及其所属的所有行政区域，耗时743毫秒，共得到140条结果（例如西奥多·罗斯福对应曼哈顿、纽约州）。但取消最后一行注释（仅保留美国州级行政区结果）后，查询触发60秒超时。

调试观察 #

• P131的行政层级链最长不超过4级，通常为「社区/区→城市→州→美国」，美国无上级行政区域
• 平均每位总统对应3.1条结果（140条结果 / 45位总统）

查询计划对比分析 #

通过BlazeGraph查询计划可以看到两个查询的执行逻辑差异：

全行政区域查询（无超时） #

# 全行政区域查询执行计划
块式物化操作[14](投影操作[13])[ 变量=[president, birthPlace, state] ]
  投影操作[13](哈希连接操作[12])[ 选择=[president, birthPlace, state] ]
    哈希连接操作[12](路径操作[11])[ 命名集合引用=NamedSolutionSetRef{localName=set-7,连接变量=[birthPlace]} ]
      路径操作[11](哈希索引操作[10])[ 子查询=连接[9]()[谓语=SPO[8](主语=null, P131, 宾语=null)[估算基数=14287222]], 左项=birthPlace, 右项=state, 输入变量=[birthPlace], 丢弃变量=[主语, 宾语] ]
      @子查询:
        连接[9]()[ 谓语=SPO[8](主语=null, P131, 宾语=null)[估算基数=14287222] ]
        哈希索引操作[10](连接[6])[ 命名集合引用=NamedSolutionSetRef{localName=set-7,连接变量=[birthPlace]} ]
          连接[6](连接[4])[ 谓语=SPO[5](president=null, P31, Q5)[估算基数=12613937] ]
            连接[4](连接[2])[ 谓语=SPO[3](president=null, P19, birthPlace=null)[估算基数=3720416]]
              连接[2]()[ 谓语=SPO[1](president=null, P39, Q11696)[估算基数=63] ]

执行顺序：先筛选美国总统（P39=Q11696，估算基数63）→ 关联出生地→ 遍历P131路径找所有行政区域。从小基数集合出发，后续处理的数据量可控。

仅州级行政区查询（超时） #

# 仅州级行政区查询执行计划
块式物化操作[16](投影操作[15])[ 变量=[president, birthPlace, state] ]
  投影操作[15](连接[14])[ 共享状态=true, 选择=[president, birthPlace, state] ]
    连接[14](连接[12])[ 谓语=SPO[13](president=null, P31, Q5)[估算基数=12613938] ]
      连接[12](连接[10])[ 谓语=SPO[11](president=null, P39, Q11696)[估算基数=63] ]
        连接[10](哈希连接操作[8])[ 谓语=SPO[9](president=null, P19, birthPlace=null)[估算基数=3720417] ]
          哈希连接操作[8](路径操作[7])[ 命名集合引用=NamedSolutionSetRef{localName=set-3,连接变量=[state]} ]
            路径操作[7](哈希索引操作[6])[ 子查询=连接[5]()[谓语=SPO[4](主语=null, P131, 宾语=null)[估算基数=14287225]], 左项=birthPlace, 右项=state, 输入变量=[state], 丢弃变量=[主语, 宾语] ]
            @子查询:
              连接[5]()[ 谓语=SPO[4](主语=null, P131, 宾语=null)[估算基数=14287225] ]
              哈希索引操作[6](连接[2])[ 哈希连接变量=[state], 命名集合引用=NamedSolutionSetRef{localName=set-3,连接变量=[state]} ]
                连接[2]()[ 谓语=SPO[1](state=null, P31, Q35657)[估算基数=50] ]

执行顺序：先筛选美国州级行政区（P31=Q35657，估算基数50）→ 反向遍历P131路径找所有隶属于这些州的地点→ 关联到出生地→ 再筛选总统。这里反向遍历P131会产生海量中间结果（估算基数1400万+），再关联370万+的出生地数据，最后才筛选总统，数据量爆炸导致超时。

疑问解答 #

1. 结论正确：两个查询的执行顺序完全相反，全区域查询从小基数的总统集合出发，而州级查询从州集合反向扩展，导致中间数据量差异巨大。
2. 先筛选总统更优：先处理基数为63的总统集合，后续只需要处理这63个实体对应的出生地（最多几十条），再找对应的州；而先查出生地的话，要处理372万+的实体，再筛选关联总统，数据量差5个数量级，效率差距明显。
3. 引导查询规划器调整执行顺序的方法：
   • 用子查询强制优先筛选总统集合：将总统和出生地的筛选逻辑放到子查询中，让规划器先处理小基数部分，再扩展州的查询
   • 限制P131路径深度：由于层级最多4级，出生地到州最多3步，用wdt:P131{1,3}替代wdt:P131+，帮助规划器更准确估算基数，避免不必要的遍历
   • 避免反向遍历：尽量从出生地向上找州，而不是从州向下找所有地点

优化后的查询 #

方案1：子查询优先筛选总统 #

SELECT * WHERE {
  # 先获取总统及其出生地的小集合
  {
    SELECT ?president ?birthPlace WHERE {
      ?president wdt:P31 wd:Q5;
                 wdt:P39 wd:Q11696;
                 wdt:P19 ?birthPlace.
    }
  }
  # 从出生地向上遍历1-3层行政区域，找到州级行政区
  ?birthPlace wdt:P131{1,3} ?state.
  ?state wdt:P31 wd:Q35657.
}

方案2：直接限制路径深度（更简洁） #

SELECT ?president ?birthPlace ?state WHERE {
  ?president wdt:P31 wd:Q5;
             wdt:P39 wd:Q11696;
             wdt:P19 ?birthPlace.
  # 限制路径深度为1到3步，避免规划器选择反向遍历
  ?birthPlace wdt:P131{1,3} ?state.
  ?state wdt:P31 wd:Q35657.
}

这两个方案都会强制规划器先处理总统小集合，再从有限的出生地出发找州，大幅减少中间数据量，避免超时。

内容的提问来源于stack exchange，提问作者charmoniumQ